課程名稱: 數位系統設計導論 2008/3/12

P-1/80

Part I

Chapter1: Binary System

教 師 : 郭 峻 因 教授
INSTRUCTOR : Prof. Jiun-In Guo

E-mail: jiguo@cs.ccu.edu.tw
 2008/3/12
課程名稱:數位系統設計導論 P-2/80

Special thanks to Prof. CHING-LING SU for

providing this course materials !!!!
Chapter 1 2008/3/12
P-3/80

Chapter 1
Binary Systems
Outline 2008/3/12
P-4/80

1.1 Digital Systems

1.2 Binary Numbers
1.3 Number Base Conversions
1.4 Octal and Hexadecimal Numbers
1.5 Complements
1.6 Signed Binary Numbers
1.7 Binary Codes
1.8 Binary Storage and Registers
1.9 Binary Logic
1.1 Digital Systems 2008/3/12
P-5/80

1.1 Digital Systems

1.2 Binary Numbers
1.3 Number Base Conversions
1.4 Octal and Hexadecimal Numbers
1.5 Complements
1.6 Signed Binary Numbers
1.7 Binary Codes
1.8 Binary Storage and Registers
1.9 Binary Logic
1.1 Digital Systems 2008/3/12
P-6/80

„ Digital Systems
1. Digital system examples: Digital telephones, digital
TV, DVD, digital cameras (DC), digital videos (DV),
and digital computers.
2. Digital systems: Manipulate discrete data
3. Binary: Numbers are presented by two discrete
values (0 and 1), Binary digit = Bit
4. Group of bits: Binary code
5. Digital systems: A system manipulates discrete
elements of information that is represented
internally binary form.
6. HDL (Hardware description language): A
programming language and suitable for describing
digital circuits in textual form.
1.2 Binary Numbers 2008/3/12
P-7/80

1.1 Digital Systems

1.2 Binary Numbers
1.3 Number Base Conversions
1.4 Octal and Hexadecimal Numbers
1.5 Complements
1.6 Signed Binary Numbers
1.7 Binary Codes
1.8 Binary Storage and Registers
1.9 Binary Logic
1.2 Binary Numbers 2008/3/12
P-8/80

„ Decimal Number

1. Decimal number 7392:

7392=7×103+ 3 ×102+ 9 ×101+ 2 ×100
2. Decimal number representation:
a5a4a3a2a1a0.a-1a-2a-3
= 105a5+104a4+103a3+102a2+101a1+100a0+10-1a-1+10-2a-2+10-3a-3
1.2 Binary Numbers 2008/3/12
P-9/80

„ Decimal Number with Binary Number

11010.11=26.75
⇒ 1×24+ 1×23+ 0×22+ 1×21+ 0×20+ 1×2-1+ 1×2-2=26.75
1.2 Binary Numbers 2008/3/12
P-10/80

„ Base-r Number with Binary Number

an⋅ rn + an-1⋅ rn-1 +… + a2⋅ r2 + a1⋅ r + a0 + a-1⋅ r-1 + a-2⋅ r-2 + …+ a-m⋅ r-m
⇒ (4021.2)5 = 4×53+ 0×52+ 2×51+ 1×50+ 2×5-1 = (511.4)10
⇒ (127.4)8 = 1×82+ 2×81+ 7×80+ 4×8-1 = (87.5)10
⇒ (B65F)16 = 11×163+ 6×162+ 5×161+ 15×160 = (46687)10
⇒ (110101)2 = 32+16+4+1 = (53)10
1.2 Binary Numbers 2008/3/12
P-11/80

„ Base-r Number System

1. Base-2, Binary
2. Base-8, Octal
3. Base-10, Decimal
4. Base-16, Hexadecimal, (10=A, 11=B, 12=C, D=13, E=14,
F=15)
1.2 Binary Numbers 2008/3/12
P-12/80

„ Base-2 Power of n

1. n=10, 210=1024, K (kilo)

2. n=20, 220=1048576, M (mega)
3. n=30, 230=130023424, G (giga)
4. n=40, 240=133143986176, T (tera)
1.2 Binary Numbers 2008/3/12
P-13/80

„ Example: Base-2, Power of n

1. 4K=4×210=212
2. 16M=16×220=224
3. 4G=4×230=232
1.2 Binary Numbers 2008/3/12
P-14/80

„ Arithmetic Operation - Addition

Augend: 101101
Addend: 100111
Sum: 1010100
1.2 Binary Numbers 2008/3/12
P-15/80

„ Arithmetic Operation - Subtraction

Minuend: 101101
Subtrahend: 100111
Difference: 000110
1.2 Binary Numbers 2008/3/12
P-16/80

„ Arithmetic Operation - Multiplication

Multiplicand: 1011
Multiplier: 101
1011
0000
1011
Product: 110111
1.3 Number Base Conversions 2008/3/12
P-17/80

1.1 Digital Systems

1.2 Binary Numbers
1.3 Number Base Conversions
1.4 Octal and Hexadecimal Numbers
1.5 Complements
1.6 Signed Binary Numbers
1.7 Binary Codes
1.8 Binary Storage and Registers
1.9 Binary Logic
1.3 Number Base Conversions 2008/3/12
P-18/80

„ Decimal to Binary Conversion: Iterative Division

1.3 Number Base Conversions 2008/3/12
P-19/80

„ Example of Decimal to Binary Conversion:

(41)10 to (101001)2
Integer Reminder Coefficient
Quotient
41/2= 20 + ½ a0=1
20/2= 10 + 0 a1=0
10/2= 5+ 0 a2=0
5/2= 2+ ½ a3=1
2/2= 1+ 0 a4=0
1/2= 0+ ½ a5=1
Answer: (41)10=(a5a4a3a2a1a0)2=(101001)2
1.3 Number Base Conversions 2008/3/12
P-20/80

„ Conveniently Process: (41)10 to (101001)2

2 41
2 20 1
2 10 0
2 5 0
2 2 1
2 1 0
0 1 Answer: 1 0 1 0 0 1
1.3 Number Base Conversions 2008/3/12
P-21/80

„ Conveniently Process:
Decimal (Base-10) to Octal (Base-8)

8 153
8 19 1
8 2 3
0 2 Answer: ( 2 3 1 )8
1.3 Number Base Conversions 2008/3/12
P-22/80

„ Fraction Part Conversion : Iterative Multiplication

1.3 Number Base Conversions 2008/3/12
P-23/80

„ Example of Decimal to Binary Conversion:

(0.6875)10 to (0.1011)2
Integer Fraction Coefficient
0.6875×2= 1+ 0.3750 a-1=1
0.3750×2= 0+ 0.7500 a-2=0
0.7500×2= 1+ 0.5000 a-3=1
0.5000×2= 1+ 0.0000 a-4=1

Answer: (0.6875)10=(0.a-1a-2a-3a-4)2=(0.1011)2
1.3 Number Base Conversions 2008/3/12
P-24/80

„ Conveniently Process: (0.513)10 to Octal

0.513× 8= 4.104
0.104 × 8= 0.832
0.832 × 8= 6.656
0.656 × 8= 5.248
0.248 × 8= 1.984
0.984 × 8= 7.872

Answer: (0.513)10=(0.406517…)8
1.3 Number Base Conversions 2008/3/12
P-25/80

„ Complete Number Conversion:

1. (41.6875)10 = (101001.1011)2
2. (153.513)10 = (231.406517)8
1.4 Octal and Hexadecimal Numbers 2008/3/12
P-26/80

1.1 Digital Systems

1.2 Binary Numbers
1.3 Number Base Conversions
1.4 Octal and Hexadecimal Numbers
1.5 Complements
1.6 Signed Binary Numbers
1.7 Binary Codes
1.8 Binary Storage and Registers
1.9 Binary Logic
1.4 Octal and Hexadecimal Numbers 2008/3/12
P-27/80

„ Octal and Hexadecimal vs. Binary:

Octal Digit = 23 =3 bits

Hexadecimal Digit = 24 =4 bits
1.4 Octal and Hexadecimal Numbers 2008/3/12
P-28/80

„ Number Conversion between Binary to Octal

(10 110 001 101 011 . 111 100 000 110)2 = (26153.7406)8
2 6 1 5 3. 7 4 0 6

„ Number Conversion between Binary to Hexadecimal

(10 1100 0110 1011 . 1111 0010)2 = (2C6B.F2)16

2 C 6 B. F 2
1.4 Octal and Hexadecimal Numbers 2008/3/12
P-29/80

„ Number Conversion between Octal to Binary

(673.124)8 = (110 111 011 . 001 010 100)2

6 7 3. 1 2 4

„ Number Conversion between Hexadecimal to Binary

(306.D)16 = (0011 0000 0110 . 1101)2

3 0 6. D
1.5 Complements 2008/3/12
P-30/80

1.1 Digital Systems

1.2 Binary Numbers
1.3 Number Base Conversions
1.4 Octal and Hexadecimal Numbers
1.5 Complements
1.6 Signed Binary Numbers
1.7 Binary Codes
1.8 Binary Storage and Registers
1.9 Binary Logic
1.5 Complements 2008/3/12
P-31/80

„ Complements

Arithmetic Operation : Subtraction

Logic Operation : 0 ⇔1

Complement
r's Complement
For base-r
r-1's Complement
1.5 Complements 2008/3/12
P-32/80

„ Diminished Radix (r-1)’s Complements

Given a number N in base-r having n digits,

the (r-1)’s complement of N : (rn-1) - N

„ If
r =10 Ö r-1=9 :
9’s complements of N = (10n-1) - N
1.5 Complements 2008/3/12
P-33/80

„ Decimal Example: n = 6 (6 digit) Ö 106-1=999999

The 9’s complement of

546700 is 999999 - 546700 = 453299
012398 is 999999 - 012398 = 987601
1.5 Complements 2008/3/12
P-34/80

„ For Binary Number (r-1)’s Complement: r=2 Ö r-1=1

The 1’s complement of N is (2n-1)-N, if n = 4

Ö 24=(10000)2 then (2n-1)-N = (1111)2-N
1.5 Complements 2008/3/12
P-35/80

„ Binary (r-1)’s Example: n = 7 (7 digit)

Ö 27-1=(1111111)2
The 1’s (r-1)’s complement of
Toggle Each Digit : 0Ù1

1111111 - 1011000 = 0100111

1111111 - 0101101 = 1010010
1.5 Complements 2008/3/12
P-36/80

„ Diminished Radix r’s Complements

Given a number N in base-r having n digits,

the r’s complement of N :

rn-N, for N ≠ 0
0, for N = 0
1.5 Complements 2008/3/12
P-37/80

„ Comparison of r’s and (r-1)’s complement

r’s complement: (r-1)’s complement:

rn- N (rn-1) – N
= [(rn-1) – N]+1
= (r-1)’s complement +1
1.5 Complements 2008/3/12
P-38/80

„ Example of r’s complement

10’s (r’s) complement of decimal

2389 Ö 7610 (9’s complement) +1= 7611
012398 Ö 987601 +1= 987602
246700 Ö 753299 +1=753300
1.5 Complements 2008/3/12
P-39/80

„ Example of r’s complement

2’s (r’s) complement of binary

1101100 Ö 0010011 +1= 0010100
0110111 Ö 1001000 +1= 1001001
1.5 Complements 2008/3/12
P-40/80

„ Subtraction with Complements

1. Add the minuend, M, to the r’s complement of

subtrahend, N. This performs M+(rn-N)=M-N+rn
2. If M ≥ N, the sum will produce an end carry, rn,
which can be discarded; what is left is the result M-
N.
3. If M < N, the sum dose not produce an end carry
and is equal to rn-(N-M), which is the r’s
complement of (N-M). To obtain the answer in a
familiar form, take the r’s complement of the sum
and place a negative sign in front.
1.5 Complements 2008/3/12
P-41/80

„ Example of Subtraction with Complements:

Using 10’s (r’s) complement, subtract 72532-3250

M= 72532
10's complement of N= + 9 6 7 5 0
Sum = 169282
Discard and carry 105= -1 0 0 0 0 0
Answer = 69282
1.5 Complements 2008/3/12
P-42/80

„ Example of Subtraction with Complements:

Using 10’s (r’s) complement, subtract 3250-72532
M= 03250
10's complement of N= + 2 7 4 6 8
Sum = 30718

No carry !!

Answer : - (10's complement of 30718)

= -69282
1.5 Complements 2008/3/12
P-43/80

„ Example of Subtraction with Complements:

Using 2’s (r’s) complement, perform X-Y and Y-X
X=1010100, Y=1000011
(a) X-Y :
X= 1010100
2's complement of Y= + 0111101
Sum = 10010001
Discard end carry 27 = - 10000000
Answer X-Y = 0010001
(a) Y-X :
Y= 1000011
2's complement of X= + 0101100
Sum = 1101111
No carry 27, Answer= -(2'sc of 1101111)
Answer = - 0010001
1.5 Complements 2008/3/12
P-44/80

„ Example of Subtraction with Complements:

Using 1’s (1’s) complement, perform X-Y and Y-X
X=1010100, Y=1000011
(a) X-Y : X= 1010100
1's complement of Y= + 0111100
Sum = 10010000
1'sc+1=2'sc
End-around carry 27 = + 1
Answer X-Y = 0010001
(a) Y-X :
Y= 1000011
1's complement of X= + 0101011
Sum = 1101110
No carry 27, Answer= -(1'sc of 1101110)
Answer = - 0010001
1.6 Signed Binary Numbers 2008/3/12
P-45/80

1.1 Digital Systems

1.2 Binary Numbers
1.3 Number Base Conversions
1.4 Octal and Hexadecimal Numbers
1.5 Complements
1.6 Signed Binary Numbers
1.7 Binary Codes
1.8 Binary Storage and Registers
1.9 Binary Logic
1.6 Signed Binary Numbers 2008/3/12
P-46/80

„ Signed Binary Numbers

an, an-1, an-2, …, a0

Sign Bit Magnitude Bits

(0=+, 1=-)
„ Example
9 (unsigned binary)
01001
9 (signed binary)

25 (unsigned binary)
11001
-9 (signed binary)
1.6 Signed Binary Numbers 2008/3/12
P-47/80

„ Presentation formats of value -9

Signed-magnitude 10001001

-9 Signed-1'sc 11110110

Signed-2'sc 11110111
1.6 Signed Binary Numbers 2008/3/12
P-48/80

„ Presentation formats for 4-bit binary value

Decimal 2’sc 1’sc Signed-Magnitude
+7 0111 0111 0111
+6 0110 0110 0110
+5 0101 0101 0101
…
+1 0001 0001 0001
+0 0000 0000 0000
-0 ------ 1111 1000
-1 1111 1110 1001
-2 1110 1101 1010
…
-6 1010 1001 1110
-7 1001 1000 1111
-8 1000 ------ ------
1.6 Signed Binary Numbers 2008/3/12
P-49/80

„ Features of Number Systems

Signed-Magnitude System: For Ordinary Arithmetic

1'sc: For Logical Operation

2'sc: For Computer Arithmetic Operation

(without end-around carry)
1.6 Signed Binary Numbers 2008/3/12
P-50/80

„ Arithmetic Addition of Signed-Magnitude System

1. The same signed number:

Adder the two magnitudes and give the sum common
sign.
2. Different signed number:
Subtract the smaller magnitude form the larger and
give the result the sign of the larger magnitude.
(+25)+(-37)=-(37-25)=-12

Additional 2 Steps: Compare Magnitude and Signed bit !!

1.6 Signed Binary Numbers 2008/3/12
P-51/80

„ Four 2’sc Cases of Arithmetic Operations

Discard Signed-bit
Extension
+6 00000110 -6 11111010
+13 00001101 +13 00001101

+19 00010011 +7 00000111

n bits
+6 00000110 -6 11111010
-13 11110011 -13 11110011

-7 11111001 -19 11101101

n+1 bits
1.6 Signed Binary Numbers 2008/3/12
P-52/80

„ Four 2’sc Cases of Arithmetic Subtraction

(±A)-(+B)=(±A)+(-B)
(±A)-(-B)=(±A)+(+B)

2'sc of -B
1.7 Binary Codes 2008/3/12
P-53/80

1.1 Digital Systems

1.2 Binary Numbers
1.3 Number Base Conversions
1.4 Octal and Hexadecimal Numbers
1.5 Complements
1.6 Signed Binary Numbers
1.7 Binary Codes
1.8 Binary Storage and Registers
1.9 Binary Logic
1.7 Binary Codes 2008/3/12
P-54/80

„ Binary Codes

n-bit binary code can distinct 2n discrete values !!

1.7 Binary Codes 2008/3/12
P-55/80

„ BCD (Binary Coded Decimal)

Decimal Symbol BCD Digit

0 0000
1 0001
2 0010
3 0011
4 0100
5 0101
6 0110
7 0111
8 1000
9 1001
1.7 Binary Codes 2008/3/12
P-56/80

„ Feature of BCD

k-digit decimal requires 4k-bits in BCD !!

„ Example of BCD

(185)10=(0001 1000 0101)BCD=(10111001)2

1.7 Binary Codes 2008/3/12
P-57/80

„ BCD Addition
k-digit decimal requires 4k-bits in BCD !!

„ Example of BCD Addition

4 0100 4 0100 8 1000

+5 +0101 +8 +1000 +9 +1001
9 1001 12 1100>9 17 10001>9
⇒ Carry out ⇒ Carry out
1100 10001
+0110 +0110
1 0010 1 0111
1.7 Binary Codes 2008/3/12
P-58/80

„ Why add 0110 into result if result >9 ?

Decimal Binary BCD
0 0000 0000
1 0001 0001
2 0010 0010
3 0011 0011
4 0100 0100
5 0101 0101
6 0110 0110
7 0111 0111
8 1000 1000
9 1001 1001
10 1010 +6 1 0000
11 1011 +6 1 0001
12 1100 +6 1 0010
13 1101 +6 1 0011
14 1110 +6 1 0100
15 1111 +6 1 0101
1.7 Binary Codes 2008/3/12
P-59/80

„ Example of BCD Addition: 184+576 in BCD

BCD carry 1 1
0001 1000 0100 184
+0101 0111 0110 +576
Binary Sum 0111 10000 1010
Add 6 0110 0110
BCD Sum 0111 0110 0000 760
1.7 Binary Codes 2008/3/12
P-60/80

„ Decimal Arithmetic

(+375) + (-240) = +135

Negative
0 375
+ 9 760
0 135
1.7 Binary Codes 2008/3/12
P-61/80

„ Other Decimal Codes

Decimal BCD 2421 Excess-3 8 4-2-1
digit 8421 Self-complementing Code

0 0000 0000 0011 0 0 0 0

1 0001 0001 0100 0 1 1 1
2 0010 0010 0101 0 1 1 0
3 0011 0011 0110 0 1 0 1
4 0100 0100 0111 0 1 0 0
5 0101 1011 1000 1 0 1 1
6 0110 1100 1001 1 0 1 0
7 0111 1101 1010 1 0 0 1
8 1000 1110 1011 1 0 0 0
9 1001 1111 1100 1 1 1 1

1010 0101 0000 000 1

1011 0110 0001 001 0
Unused Bits 1100 0111 0010 001 1
1101 1000 1101 110 0
1110 1001 1110 110 1
1111 1010 1111 111 0
1.7 Binary Codes 2008/3/12
P-62/80

„ Example of Self-complementing Code:

9’s complement of (395)10 in Exceed-3 code

(395)10
= 0110 1100 1000 (in Exceed-3)
= 1001 0011 0111 (9'sc 604)
1.7 Binary Codes 2008/3/12
P-63/80

„ Gray Code
Decimal Binary Gray
Code

0 0000 0000
1 0001 0001
2 0010 0011
3 0011 0010
4 0100 0110 Binary: 0 bn b3 b2 b1 b0
...
5 0101 0111
6 0110 0101
7 0111 0100
8 1000 1100 Gray Code: gn g3 g2 g1 g0
...
9 1001 1101
10 1010 1111
11 1011 1110
12 1100 1010
13 1101 1011
14 1110 1001
15 1111 1000
1.7 Binary Codes 2008/3/12
P-64/80

„ Feature of Gray Code

Only one bit in the code group changes from one number
to the next !
Only one bit
change !!
For Example 7 ⇒ 8

Gray Code: 0100 ⇒ 1100

Binary Code: 0111 ⇒ 1000

4 bit change
1.7 Binary Codes 2008/3/12
P-65/80

„ ASCII Code (American Standard Code for Information Interchange)

1.7 Binary Codes 2008/3/12
P-66/80

„ Extended ASCII Code

1.7 Binary Codes 2008/3/12
P-67/80

„ Error-Detecting Code:
Communication and computation will cause error

Even Parity Odd Parity

ASCII A=1000001 01000001 11000001
ASCII T=1010100 11010100 01010100
1.8 Binary Storage and Registers 2008/3/12
P-68/80

1.1 Digital Systems

1.2 Binary Numbers
1.3 Number Base Conversions
1.4 Octal and Hexadecimal Numbers
1.5 Complements
1.6 Signed Binary Numbers
1.7 Binary Codes
1.8 Binary Storage and Registers
1.9 Binary Logic
1.8 Binary Storage and Registers 2008/3/12
P-69/80

„ Register

1. A register is a group of binary cells.

2. A register with n cells can store n-bit information.
3. A register with 16 cells can be in one of 216 possible
states, i.e. number 0~ 216-1 .
4. A 16-bit example: 1100 0011 1100 1001
1.8 Binary Storage and Registers 2008/3/12
P-70/80

„ Register Transfer

1. A register transfer operation is a basic operation in

digital systems.
2. It transfer binary information from one set of
registers to another set of registers.
1.8 Binary Storage and Registers 2008/3/12
P-71/80

„ Transfer of Information with Register

1.8 Binary Storage and Registers 2008/3/12
P-72/80

Memory Unit

Sum
0000000000

Operand 1 0011100001

Operand 2
0001000010

„ Transfer of
Information with 0001000010 R1
Register
Digital logic
circuits for 0100100011 R3
binary addition

0011100001 R2

Processor Unit
1.9 Binary Logic 2008/3/12
P-73/80

1.1 Digital Systems

1.2 Binary Numbers
1.3 Number Base Conversions
1.4 Octal and Hexadecimal Numbers
1.5 Complements
1.6 Signed Binary Numbers
1.7 Binary Codes
1.8 Binary Storage and Registers
1.9 Binary Logic
1.9 Binary Logic 2008/3/12
P-74/80

„ Binary Logic
1. 0/1
2. True/False
3. Yes/No
1.9 Binary Logic 2008/3/12
P-75/80

„ Definition of Binary Logic

Binary Logic: 1. Arithmetic operation

2. Logical operation

Basic Logical Operation: AND / OR/ NOT

1.9 Binary Logic 2008/3/12
P-76/80

„ Binary Logic

x y=z
AND or x AND y is equal to z
xy=z

Why?
OR x y=z x OR y is equal to z

x'=z
NOT or NOT x is equal to z
x=z
1.9 Binary Logic 2008/3/12
P-77/80

„ Truth Table for AND/OR/NOT

AND OR NOT

x y x y x y x+y x x’
0 0 0 0 0 0 0 1
0 1 0 0 1 1 1 0
1 0 0 1 0 1
1 1 1 1 1 1
1.9 Binary Logic 2008/3/12
P-78/80

„ Example of a Digital System

Volts

4
Range for Logic 1
3

Transition occurs
between these limits

1
Range for Logic 0
0
1.9 Binary Logic 2008/3/12
P-79/80

„ Symbol for Digital Logic Circuit

x Two Input
z=x y
y AND Gate

x Two Input
z=x+y
y OR Gate

NOT Gate or
x x' Inverter
1.9 Binary Logic 2008/3/12
P-80/80

„ Input-Output Signal for Logic Gates

1.9 Binary Logic 2008/3/12
P-81/80

„ Gates with Multiple Inputs

A
3 Input
B F=A B C
C AND Gate

A 3 Input
B G=A+B+C OR Gate
C
 2008/3/12

Exercise P-82/80

• Problem set
– 1.1, 1.4, 1.10, 1.13, 1.14, 1.17, 1.20, 1.25,
1.27, 1.28, 1.34, 1.35
• Deadline
– 2008/03/05