Transcript Chap1-3 - GEOCITIES.ws

CS151
Introduction to Digital Design
Chapter 1
Lecture 3
1
Octal to Binary and Back

Octal to Binary:


Restate the octal as three binary digits
starting at the radix point and going both
ways.
Binary to Octal :


Group the binary digits into three bit groups
starting at the radix point and going both
ways, padding with zeros as needed in the
fractional part.
Convert each group of three bits to an octal
digit.
CS 151
2
Hexadecimal to Binary and Back

Hexadecimal to Binary:


Restate the hexadecimal as four binary digits
starting at the radix point and going both
ways.
Binary to Hexadecimal:


Group the binary digits into four bit groups
starting at the radix point and going both
ways, padding with zeros as needed in the
fractional part.
Convert each group of three bits to a
hexadecimal digit.
CS 151
3
Octal to Hexadecimal via Binary




Convert octal to binary.
Use groups of four bits and convert as above to
hexadecimal digits.
Example: Octal to Binary to Hexadecimal
6 3 5 . 1 7 7 8
Why do these conversions work?
Answer in notes page for this slide…
CS 151
4
Conversion Between Bases
 Method 2
 To convert from one base to another:
1) Convert the Integer Part
2) Convert the Fraction Part
3) Join the two results with a radix point
CS 151
5
Conversion Details

To Convert the Integer Part:
Repeatedly divide the number by the new radix and save
the remainders. The digits for the new radix are the
remainders in reverse order of their computation. If the
new radix is > 10, then convert all remainders > 10 to
digits A, B, …

To Convert the Fractional Part:
Repeatedly multiply the fraction by the new radix and
save the integer digits that result. The digits for the new
radix are the integer digits in order of their computation.
If the new radix is > 10, then convert all integers > 10 to
digits A, B, …
CS 151
6
Example: Convert 46.687510 To Base 2
1.
Convert 46 to Base 2
2.
Convert 0.6875 to Base 2:
3.
Join the results together with the
radix point:
Answer in notes page for this slide…
CS 151
7
Additional Issue - Fractional Part



Note that in this conversion, the fractional part
became 0 as a result of the repeated
multiplications.
In general, it may take many bits to get this to
happen or it may never happen.
Example: Convert 0.6510 to N2



0.65 = 0.10 1001 1001 1001 …
The fractional part begins repeating every 4 steps
yielding repeating 1001 forever!
Solution: Specify number of bits to right of radix
point and round or truncate to this number.
CS 151
8
Checking the Conversion
To convert back, sum the digits times their
respective powers of r.
 From the prior conversion of 46.687510
1011102 = 1*32 + 0*16 +1*8 +1*4 + 1*2 +0*1
= 32 + 8 + 4 + 2
= 46
0.10112 = 1/2 + 1/8 + 1/16
= 0.5000 + 0.1250 + 0.0625
= 0.6875

CS 151
9
Number Ranges
Consider a 3-digit counter.
What is the minimum number it can show? 000
What is the maximum number it can show? 999
What is it’s number range?
Each position has 10
possibilities: 0,1,2,3,4,5,6,7,8,9.
Range: 0  999
0  (10 3 -1)
4
2
6
10 * 10 * 10 = 10
3
# Positions
Radix
CS 151
10
Number Ranges
What if the counter was a 3-bit binary counter?
What is the minimum number it can show? (000)2
What is the maximum number it can show? (111) = 7
2
10
What is it’s number range?
Range: 0  7
0  (2 3 -1)
Each position has 2 possibilities:
0,1.
0
1
0
# positions (bits)
2 * 2 * 2 = 23
Radix
CS 151
11
Number Ranges
Given n digits in radix r, there are rn distinct
elements that can be represented.
These elements range from 0 to rn -1
BONUS: What is the minimum number of
bits, n, needed to represent a binary code of
M elements ???
CS 151
12
Number Ranges

Range of numbers is based on the number of
bits available in the hardware structure that
store and process information. (E.g. registers).

Usually, size of these structures is a power of 2.
(8 bits, 16 bits, 32 bits, 64 bits and 128 bits).
CS 151
13
Binary Arithmetic






Single Bit Addition with Carry
Multiple Bit Addition
Single Bit Subtraction with Borrow
Multiple Bit Subtraction
Multiplication
BCD Addition
When working with base-r, use ONLY r allowable digits
(0..r-1) and perform all computations with base r digits.
CS 151
14
Single Bit Binary Addition with
Carry
Given two binary digits (X,Y), a carry in (Z) we get the
following sum (S) and carry (C):
Carry in (Z) of 0:
Carry in (Z) of 1:
Z
X
+Y
0
0
+0
0
0
+1
0
1
+0
0
1
+1
CS
00
01
01
10
Z
X
+Y
CS
1
0
+0
01
1
0
+1
10
1
1
+0
10
1
1
+1
11
CS 151
15
Multiple Bit Binary Addition

Extending this to two multiple bit
examples:
Carries
Augend
0
0
01100 10110
+10001 +10111
Addend
Sum
 Note: The 0 is the default Carry-In to the
least significant bit.
Kindly view notes page for answer.
CS 151
16
Single Bit Binary Subtraction with Borrow



Given two binary digits (X,Y), a borrow in (Z) we
get the following difference (S) and borrow (B):
Borrow in (Z) of 0: Z
0
0
0
0
X
-Y
0
-0
0
-1
1
-0
1
-1
BS
Borrow in (Z) of 1:
Z
00
1
11
1
01
1
00
1
X
-Y
0
-0
0
-1
1
-0
1
-1
BS
11
10
00
11
CS 151
17
Multiple Bit Binary Subtraction

Extending this to two multiple bit examples:
Borrows
Minuend
Subtrahend
0
0
10110 10110
- 10010 - 10011
Difference
 Notes: The 0 is a Borrow-In to the least significant
bit. If the Subtrahend > the Minuend, interchange
and append a – to the result.
Kindly view notes page for answer.
CS 151
18
Multiple Bit Binary Subtraction

Binary Subtraction
 Swap
Borrows:
Minuend:
10011
Subtrahend: - 11110
19
- 30
Difference:
CS 151
0 0110
11110
- 10011
- 19
-01011
-11
30
19
Binary Multiplication
The binary multiplication table is simple:
00=0 | 10=0 | 01=0 | 11=1
Extending multiplication to multiple digits:
Multiplicand
Multiplier
Partial Products
+
Product
CS 151
1011
x 101
1011
0000 1011 - 110111
20
Octal Multiplication
Multiplicand:
Multiplier: x
Product:
762
45
4672
3710 43772
Octal
Decimal
Octal
5x2 =
10= 8+2
12
5x6 +1=
31= 24+7
37
5x7 +3=
38= 32+6
46
4x2=
8 = 8+0
10
4x6 +1=
25= 24+1
31
4x7 +3=
31= 24+7
37
Form a table to calculate sums
and products of 2 digits in base-r
(in this case, base-8)
CS 151
21
Hexadecimal Addition
Hex
Decimal
1
1
Carry
Carry
+
5
59F
E46
13E5
+
+
14
1
9
4
19 =16+ 3 14 = E
CS 151
15
+
6
21 =16+ 5
22