Logic Design - Unit 1 - v1.6 - 20210915

UNIT 1
NUMBER SYSTEMS AND

CONVERSIONS
PROF. JIUN-IN GUO
INSTITUTE OF ELECTRONICS, NYCU

[email protected]
Fall 2021
Number Systems and Conversions
2
¨ Contents
¤ Digital systems
¤ Number systems and conversion
¤ Binary arithmetic
¤ Representation of negative numbers
n Addition of two’s complement numbers
n Addition of one’s complement numbers
¤ Binary codes
¤ Binary storage and register
¤ Binary register

Digital Systems
3
p Digital system examples: Digital telephones, digital TV,

DVD, digital cameras (DC), digital videos (DV), and
digital computers.
p Digital systems: Manipulate discrete data
p Binary: Numbers are presented by two discrete values
(0 and 1), Binary digit = Bit
p Group of bits: Binary code
p Digital systems: A system manipulates discrete elements
of information that is represented internally binary form.
p HDL (Hardware description language): A programming
language and suitable for describing digital circuits in
textual form.

Number Systems (1/2)
4
¨ Positional notation: Each digit is multiplied by an appropriate
power of base depending on its position in the number
¤ The point separates the positive and negative powers of base
¤ e.g., decimal (base 10) numbers
n 953.7810 = 9x102+5x101+3x100+7x10-1+8x10-2
(210.-1-2): powers of base
¤ A positive number N with base (radix) R (positive integer, R>1):

N = (a4a3 a2a1a0.a-1a-2a-3)R
= a4xR4+a3xR3+a2xR2+a1xR1+a0xR0+a-1xR-1+a-2xR-2+a-3xR-3
n Base is also called radix
n Base is indicated as subscript
¤ Q: Why do people use the decimal number system?

Number Systems (2/2)
5
¨ Examples:
¤ Decimal (base 10) numbers
n 953.7810=9x102+5x101+3x100+7x10-1+8x10-2
¤ Binary (base 2) numbers
n 1011.112=1x23+0x22+1x21+1x20+1x2-1+1x2-2=11.7510
¤ Octal (base 8) numbers
n 147.38=1x82+4x81+7x80+3x8-1=103.37510
¤ Hexadecimal (base 16) numbers
n A2F16=10x162+2x161+15x160=260710

Common Number Systems
6
Name Decimal Binary Octal Hexadecimal

Radix 10 2 8 16
0,1,2,3,4, 0,1,2,3, 0,1,2,3,4,5,6,7,
Digits 0,1
5,6,7,8,9 4,5,6,7 8,9,A,B,C,D,E,F
0 0 0 0
1 1 1 1
2 10 2 2
3 11 3 3
4 100 4 4
5 101 5 5
6 110 6 6
First 17 7 111 7 7
positive 8 1000 10 8
integers 9 1001 11 9
10 1010 12 A
11 1011 13 B
12 1100 14 C
13 1101 15 D
14 1110 16 E
15 1111 17 F
16 10000 20 10

Conversion of a Decimal Integer
7
¨ Convert a decimal integer to base R using division:
¤ N = (anan-1...a2a1a0)R = anRn + an-1Rn-1 + ... + a2R2 + a1R1 + a0
¤ N/R = anRn-1 + an-1Rn-2 + ... + a2R1 + a1 = Q1 ........... remainder a0
¤ Q1/R = anRn-2 + an-1Rn-3 + ... + a3R1 + a2 = Q2 ......... remainder a1
¤ Q2/R = anRn-3 + an-1Rn-4 + ... + a3 = Q3 ..................... remainder a2

¤ …
¤ Continued until we finally obtain …………………….remainder an
¤ e.g., convert 5310 to binary
2 53
2 26 …… remainder = 1 = a0 (LSB)
2 13 …… remainder = 0 = a1
2 6 …… remainder = 1 = a2 5310 = 1101012
2 3 …… remainder = 0 = a3
2 1 …… remainder = 1 = a4
0 …… remainder = 1 = a5 (MSB)

Conversion of a Decimal Fraction (1/2)
8
¨ Convert a decimal fraction to base R using multiplication:
¤ F = (.a-1a-2a-3...a-m)R = a-1R-1 + a-2R-2 + a-3R-3 + ... + a-mR-m
¤ FR = a-1 + a-2R-1 + a-3R-2 + ... + a-mR-m+1 = a-1 + F1
¤ F1R = a-2 + a-3R-1 + ... + a-mR-m+2 = a-2 + F2

integer fraction
¤ F2R = a-3 + ... + a-mR-m+3 = a-3 + F3
¤ …
¤ Continued until we finally obtain a sufficient number of digits
¤ e.g., convert .62510 to binary

.625
x 2
(1).250 (a-1=1, MSB)
x 2
(0).500 (a-2=0) .62510 = .1012
x 2
(1).000 (a-3=1, LSB)

Conversion of a Decimal Fraction (2/2)
9
¨ Sometimes, the result is a repeating fraction
¤ e.g., convert 0.710 to binary
.7
x 2
(1).4
x 2
(0).8
x 2
(1).6
x 2
(1).2
x 2 Start repeating!
(0).4 .4 was previously obtained
x 2 0.710 = .1 0110 0110 0110 …2
(0).8

Conversion between Two Bases (1/2)
10
¨ Convert between two bases R1 and R2 other than decimal
¤ Base R1 Þ base 10 Þ base R2
¤ e.g., convert 231.34 to base 7
231.34 = 2x42+3x41+1x40+3x4-1 = 45.7510

integer fraction
.75
x 7
7 45 (5).25 Repeat!
7 6 …… rem. 3 x 7 Þ .517
0 …… rem. 6 (1).75
Þ 637 x 7
(5).25
x 7
(1).75
integer fraction
231.34 = 45.7510 = 63.517
Conversion between Two Bases (2/2)
11
¨ Convert between binary and octal/hexadecimal by inspection
1. Start at the binary point
2. Divide bits into groups of three/four, adding 0’s if necessary
3. Replace each group by an octal/hexadecimal digit
4. And vice versa
¤ Binary Û octal
1001101.0101112 = 001 001 101 . 010 1112 =115.278
1 1 5 2 7
adding 0’s
¤ Binary Û hexadecimal
1001101.0101112 = 0100 1101 . 0101 11002 =4D.5C16
4 D 5 C

12 Binary Arithmetic

Binary Arithmetic -- Addition
13
¨ Addition table:
¤ 0+0=0
¤ 0+1=1
¤ 1+0=1
¤ 1 + 1 = 0 (and carry 1 to the next column)

¤ e.g., add 1310 and 1110 in binary
1111 carries
1310 = 1101
1110 = 1011
11000 = 2410

Binary Arithmetic -- Subtraction
14
¨ Subtraction table:
¤ 0–0=0
¤ 1–0=1
¤ 1–1=0
¤ 0 – 1 = 1 (and borrow 1 from the next column)

n Borrow 1 from the next column
º have -1 at the next column
= obtain R at the current column
¤ e.g., subtract 1910 from 2910 in binary
1 borrow
2910 = 11101
1910 = 10011
1010 = 1010

Binary Arithmetic -- Multiplication
15
¨ Multiplication table:
¤ 0x0=0
¤ 0x1=0
¤ 1x0=0
¤ 1x1=1
¤ e.g., multiply 1310 by 1110 in binary
1101 = 1310 multiplicand

x 1011 = 1110 multiplier
1101
1101 copy of multiplicand if “1”
0000
1101
10001111 = 14310

Binary Arithmetic -- Division
16
¨ Is similar to (easier than) decimal division
¤ e.g., divide 14510 by 1110 in binary
1101 = quotient
divisor 1110 = 1011 10010001 = 14510 dividend
1011
1110
1011
1101
1011
10 = remainder

17 Representation of Negative Numbers
Addition of two’s complement numbers

Addition of one’s complement numbers

Negative Numbers
18
¨ Sign and Magnitude: 1-bit sign + (n-1)-bit magnitude
S Magnitude word length: n
sign bit: 0 for positive, 1 for negative

¤ e.g., 0011sm = +310, 1011sm = -310
¤ Is common for people but awkward for computers
¨ 1’s complement: N_ = (2n –1) – N

¤ Complement +N bit-by-bit
¤ e.g., +3 = 0011, 3_ = 1100
¨ 2’s complement: N* = 2n – N = N_ + 1
¤ Complement +N bit-by-bit and then add 1
¤ Or complement all bits to the left of the rightmost 1
¤ e.g., +3 = 0011, 3* = 1101

Signed Binary Integers
19
Word length: n = 4
Positive Negative integers
integers Sign and 2’s complement 1’s complement
+N (all systems) -N magnitude N* N_
+0 0000 -0 1000 ---- 1111
+1 0001 -1 1001 1111 1110
+2 0010 -2 1010 1110 1101
+3 0011 -3 1011 1101 1100
+4 0100 -4 1100 1100 1011
+5 0101 -5 1101 1011 1010
+6 0110 -6 1110 1010 1001
+7 0111 -7 1111 1001 1000
-8 ---- 1000 ----
¨ For word length n, there are 2n different permutations

¤ SM and N_: [+7, …, +0, -0, …, -7] (redundant -0)
¤ N*: [+7, …, +0, …, -8] (-2n-1 ~ +2n-1-1)
¨ View the first bit as the sign bit: positive/negative Û 0/1

Warning: Unsigned or Signed Numbers
20
¨ For word length n, there are 2n different permutations
¤ Unsigned:
n [0, 2n-1]
¤ Signed
n SM (sign and magnitude) and N_ (1’s complement ) :

[-2n-1+1, +2n-1-1] (redundant -0)
n N* (2’s complement) : [-2n-1, +2n-1-1]
¨ e.g., what is 1110?

Addition of Two’s Complement Numbers
21
1. Add just as if all numbers were positive
2. Discard the carry from the sign bit
¤ Why to discard the carry? (i.e., subtract 2n)
1. Add(-A, +B), B > A

n A* + B = (2n – A) + B = 2n + (B – A)
n Þ –2n Þ (B – A)
2. Add(-A, -B), A+B £ 2n-1
n A* + B* = (2n – A) + (2n – B) = 2n + 2n – (A + B) = 2n + (A + B)*
n Þ –2n Þ (A + B)*
¨ e.g.,
Add(+A, +B) Add(+A, -B) Add(-A, +B) Add(-A, -B)
A+B < 2n-1 B>A B>A A+B £ 2n-1
+3 0011 +5 0101 -5 1011 -3 1101
+4 0100 -6 1010 +6 0110 -4 1100
+7 0111 -1 1111 +1 (1)0001 -7 (1)1001
Exception: Overflow in Two’s Complement
22
¨ An overflow means out of range of representation
¤ When the word length is n bits, the correct representation of a
number (including sign) requires more than n bits
¨ How to detect overflow?
¤ Check sign!
n (+) + (+) Þ (-) or (-) + (-) Þ (+)

¨ e.g.,
Add(+A, +B) Add(-A, -B)
A+B ³ 2n-1 A+B > 2n-1
+5 0101 -5 1011
+6 0110 -6 1010
1011 (1)0101
Wrong answer! Wrong answer!
Overflow: +11 Overflow: -11
requires 5 bits requires 5 bits
including sign including sign

Addition of One’s Complement Numbers
23
¨ End-around carry: Add the carry out back to the rightmost bit
¤ Why to take end-around carry? (i.e., subtract 2n & add 1)
1. Add(-A, +B), B > A
n A_ + B = (2n – 1 – A) + B = 2n + (B – A) – 1
n Þ –2n & +1 Þ (B – A)
2. Add(-A, -B), A+B £ 2n-1
n A_ + B_ = (2n – 1 – A) + (2n – 1 – B) = 2n + 2n – 1 – (A + B) – 1
= 2n + (A + B)_ – 1
n Þ –2n & +1 Þ (A + B)_
¨ e.g.,
Add(+A, +B) Add(+A, -B) Add(-A, +B) Add(-A, -B)
A+B < 2n-1 B>A B>A A+B £ 2n-1
+3 0011 +5 0101 -5 1010 -3 1100
+4 0100 -6 1001 +6 0110 -4 1011
+7 0111 -1 1110 +1 (1)0000 -7 (1)0111
1 1
Number Systems and Conversions 0001 1000
Exception: Overflow in One’s Complement
24
¨ How to detect overflow?
¤ Check sign!
n (+) + (+) Þ (-) or (-) + (-) Þ (+)
¨ e.g.,
Add(+A, +B) Add(-A, -B)
A+B ³ 2n-1 A+B ³ 2n-1
+5 0101 -5 1010
+6 0110 -6 1001
1011 (1)0011
Wrong answer! 1
Overflow: +11 0100
requires 5 bits Wrong answer!
including sign Overflow: -11
requires 5 bits
including sign

25 Binary Codes

Binary Codes
26
¨ n-bit binary code can distinct 2n discrete values !!

¨ 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
BCD
27
n Feature of BCD
k-digit decimal requires 4k-bits in BCD !!
n Example of BCD
(185)10=(0001 1000 0101)BCD=(10111001)2

BCD Arithmetic
28
n BCD Addition
k-digit decimal requires 4k-bits in BCD !!
n 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
BCD Arithmetic
29
n 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
BCD Arithmetic
30
n 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

Other Decimal Codes
31
Decimal BCD 2421 Excess-3 8 4-2-1

digit 8421 Self-complementing Code
0 0000 0000 0011 0 00 0

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

1011 0110 0001 0 01 0
Unused Bits 1100 0111 0010 0 01 1
1101 1000 1101 1 10 0
1110 1001 1110 1 10 1
1111 1010 1111 1 11 0
Self Complementing Codes
32
n 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)

Gray Code
33
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
Feature of Gray Code
34
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

Decimal Digits to Binary Codes
35
¨ Input/output interface generally uses decimal numbers
¨ How to represent decimal numbers using binary codes?
¤ Choose 10 elements from 16 binary numbers of 4 bits Many
¤ e.g., 937.25 Þ BCD: 1001 0011 0111 . 0010 0101 options!
Decimal 8-4-2-1 6-3-1-1 Excess-3 2-out-of-5 Gray
digit code code code code code
0 0000 0000 0011 00011 0000
1 0001 0001 0100 00101 0001
2 0010 0011 0101 00110 0011
3 0011 0100 0110 01001 0010
4 0100 0101 0111 01010 0110
5 0101 0111 1000 01100 0111
6 0110 1000 1001 10001 0101
7 0111 1001 1010 10010 0100
8 1000 1011 1011 10100 1100
9 1001 1100 1100 11000 1101
Only 1 bit changes as
Weighted Weighted Only 2 bits are one
Property = BCD+3 counting up/down
a.k.a. BCD Þ For error checking
Number Systems and Conversions Þ For analog quantities
2 out of 5 Code
36

Warning: Conversion or Coding?
37
¨ Do NOT mix up conversion of a decimal number to a binary
number with coding a decimal number with a binary code
¤ e.g.,
1310 Û 11012 (This is conversion)
13 Û 0001 0011 (This is coding)

Text to Binary Codes
38
¨ ASCII
¤ American Standard Code for Information Interchange
¤ English alphanumeric symbols
¤ 7 bits
¨ Big-5 code
¤ Traditional Chinese characters
¤ Double-byte coding (16 bits)
94 printable
characters are
numbered 3210 to
12610 in ASCII code

ASCII Codes
39
¨ ASCII (American Standard Code for Information Interchange)

Extended ASCII Codes
40

Error Detecting Codes
41
n Error-Detecting Code:
Communication and computation will cause error
Even Parity Odd Parity

ASCII A=1000001 01000001 11000001
ASCII T=1010100 11010100 01010100

Binary Storage and Registers
42
n 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

43
n 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.

44
n Transfer of Information with Register

Processor Unit
Input Unit Processor Register
8-bit 8-bit 8-bit 8-bit 8-bit

Register Register Register Register Register
keybord
J
O Keyboard
Strike
H Controller
J O H N
N 01001010 01001111 01001000 01001110
Memory Register
Memory Unit

45
Memory Unit
Sum
0000000000
Operand 1 0011100001
Operand 2
0001000010
n Transfer of
Information with 0001000010 R1
Register
Digital logic
circuits for 0100100011 R3
binary addition
0011100001 R2
Processor Unit
Binary Logic
46
n Binary Logic
1. 1/0
2. True/False
3. Yes/No

Definition of Binary Logic
47
Binary Logic: 1. Arithmetic operation

2. Logical operation
Basic Logical Operation: AND / OR/ NOT

Binary Logic
48
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

Binary Logic
49
n 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

Example of Binary Logic Value
50
Volts
4
Range for Logic 1
3
Transition occurs
between these limits
1
Range for Logic 0
0
Binary Logic
51
n 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

Binary Logic
52
n Input-Output Signal for Logic Gates

Binary Logic
53
n 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

Q&A
54 (To be continued)
Thank you very much

for your attention !
Homework of Unit 1
55
¨ Problem set: 1.4, 1.5, 1.7, 1.17, 1.19, 1.28, 1.39, 1.44
¨ Deadline: 1 week

Logic Design - Unit 1 - v1.6 - 20210915

Uploaded by

Copyright:

Available Formats

Logic Design - Unit 1 - v1.6 - 20210915

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Logic Design - Unit 1 - v1.6 - 20210915

Uploaded by

Copyright:

Available Formats

UNIT 1

NUMBER SYSTEMS AND

INSTITUTE OF ELECTRONICS, NYCU

Number Systems and Conversions

p Digital system examples: Digital telephones, digital TV,

Number Systems and Conversions

(210.-1-2): powers of base

¤ A positive number N with base (radix) R (positive integer, R>1):

¤ Q: Why do people use the decimal number system?

Number Systems and Conversions

Number Systems and Conversions

Name Decimal Binary Octal Hexadecimal

Number Systems and Conversions

¤ Q1/R = anRn-2 + an-1Rn-3 + ... + a3R1 + a2 = Q2 ......... remainder a1

¤ Q2/R = anRn-3 + an-1Rn-4 + ... + a3 = Q3 ..................... remainder a2

¤ Continued until we finally obtain …………………….remainder an

¤ e.g., convert 5310 to binary

Number Systems and Conversions

¤ F1R = a-2 + a-3R-1 + ... + a-mR-m+2 = a-2 + F2

¤ Continued until we finally obtain a sufficient number of digits

¤ e.g., convert .62510 to binary

Number Systems and Conversions

Number Systems and Conversions

231.34 = 2x42+3x41+1x40+3x4-1 = 45.7510

Number Systems and Conversions

Number Systems and Conversions

¤ 1 + 1 = 0 (and carry 1 to the next column)

Number Systems and Conversions

¤ 0 – 1 = 1 (and borrow 1 from the next column)

Number Systems and Conversions

1101 = 1310 multiplicand

Number Systems and Conversions

Number Systems and Conversions

Addition of two’s complement numbers

Number Systems and Conversions

S Magnitude word length: n

sign bit: 0 for positive, 1 for negative

¨ 1’s complement: N_ = (2n –1) – N

¤ e.g., +3 = 0011, 3* = 1101

Number Systems and Conversions

¨ For word length n, there are 2n different permutations

Number Systems and Conversions

n SM (sign and magnitude) and N_ (1’s complement ) :

Number Systems and Conversions

1. Add(-A, +B), B > A

n (+) + (+) Þ (-) or (-) + (-) Þ (+)

Number Systems and Conversions

Number Systems and Conversions

Number Systems and Conversions

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

Decimal Symbol BCD Digit

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

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

Number Systems and Conversions

n Example of BCD Addition

4 0100 4 0100 8 1000

n Why add 0110 into result if result >9 ?

n Example of BCD Addition: 184+576 in BCD

Number Systems and Conversions