Digital Logic Design Start from Zero to Hero 1

Digital Logic Design

1. Binary Systems 1
DIGITAL LOGIC DESIGN
by
Dr. Fenghui Yao
Tennessee State University
Department of Computer Science
Nashville, TN

2. Binary Systems 2
Digital SystemsDigital Systems
They manipulate discrete information They manipulate discrete information
(A finite number of elements)(A finite number of elements)

Example discrete setsExample discrete sets

10 decimal digits, the 26 letters of alphabet 10 decimal digits, the 26 letters of alphabet
Information is represented in binary Information is represented in binary
formform
ExamplesExamples

Digital telephones, digital television, and digital Digital telephones, digital television, and digital
camerascameras

The most commonly used one is DIGITAL The most commonly used one is DIGITAL
COMPUTERSCOMPUTERS

3. Binary Systems 3
CENTRAL PROCESSING UNIT
Digital Computers Digital Computers
Control Unit
Arithmetic
Logic
Unit (ALU)
Registers
R1
R2
Rn
Main
Memory
Disk Keyboard Printer
I/O Devices
Bus

4. Binary Systems 4
Binary SignalsBinary Signals
It means two-statesIt means two-states

1 and 01 and 0

true and falsetrue and false

on and offon and off
A single “on/off”, “true/false”, “1/0” is A single “on/off”, “true/false”, “1/0” is
called a called a bitbit
Example: Toggle switchExample: Toggle switch

5. Binary Systems 5
ByteByte
Computer memory is organized into Computer memory is organized into
groups of eight bitsgroups of eight bits
Each eight bit group is called a Each eight bit group is called a bytebyte

6. Binary Systems 6
Why Computers Use BinaryWhy Computers Use Binary
They can be represented with a They can be represented with a
transistor that is relatively easy to transistor that is relatively easy to
fabricate (in silicon)fabricate (in silicon)

Millions of them can be put in a tiny chipMillions of them can be put in a tiny chip
Unambiguous signal (Either 1 or 0)Unambiguous signal (Either 1 or 0)

This provides noise immunityThis provides noise immunity

7. Binary Systems 7
Analog SignalAnalog Signal

8. Binary Systems 8
Binary SignalBinary Signal
A voltage below the A voltage below the thresholdthreshold

offoff
A voltage above the A voltage above the thresholdthreshold

onon

9. Binary Systems 9
Binary SignalBinary Signal

10. Binary Systems 10
Noise on TransmissionNoise on Transmission
When the signal is transferred it will When the signal is transferred it will
pick up noise from the environmentpick up noise from the environment

11. Binary Systems 11
RecoveryRecovery
Even when the noise is present the Even when the noise is present the
binary values are transmitted without binary values are transmitted without
errorerror

12. Binary Systems 12
Binary NumbersBinary Numbers

A number in a base-r systemA number in a base-r system
x = xx = x
n-1n-1xx
n-2n-2 ... x ... x
11xx
0 0 ..
xx
-1-1 x x
-2-2 ... X ... X
-(m-1)-(m-1) x x
-m-m
m
m
n
n
n
n
rxrxrxrxrxrxxValue










 ......)(
2
2
1
1
0
0
2
2
1
1
10
21012
6
)5.94(6662646362)26.234( 

10
101
8 )5.39(848584)4.45( 


13. Binary Systems 13
Radix Number SystemRadix Number System
Base – 2 (binary numbers)Base – 2 (binary numbers)

0 10 1
Base – 8 (octal numbers)Base – 8 (octal numbers)

0 1 2 3 4 5 6 70 1 2 3 4 5 6 7
Base – 16 (hexadecimal numbers)Base – 16 (hexadecimal numbers)

0 1 2 3 4 5 6 7 8 9 A B C D E F0 1 2 3 4 5 6 7 8 9 A B C D E F

14. Binary Systems 14
Radix OperationsRadix Operations

The same as for decimal numbersThe same as for decimal numbers
11001011
[phone]
101101000
11001011
- 10011101
00101110
101
* 110
000
1010
+10100
11110

15. Binary Systems 15
Conversion From one radix Conversion From one radix
to anotherto another
From decimal to binaryFrom decimal to binary

16. Binary Systems 16
Conversion From one radix Conversion From one radix
to anotherto another
From decimal to base-From decimal to base-rr

Separate the number into an integer part and a Separate the number into an integer part and a
fraction partfraction part

For the integer partFor the integer part

Divide the number and all successive quotients Divide the number and all successive quotients
by by rr

Accumulate the remaindersAccumulate the remainders
165
23
3
0
4
2
3
710 )324()165( 
0.6875 x 2 = 1 + 0.3750
0.3750 x 2 = 0 + 0.7500
0.7500 x 2 = 1 + 0.5000
0.5000 x 2 = 1 + 0.0000
210
)1011.0()6875.0( 

17. Binary Systems 17
Different BasesDifferent Bases

18. Binary Systems 18
Conversion From one radix Conversion From one radix
to anotherto another
From binary to octalFrom binary to octal
Divide into groups of 3 bitsDivide into groups of 3 bits

ExampleExample
11001101001000.1011011 = 31510.55411001101001000.1011011 = 31510.554
From octal to binaryFrom octal to binary

Replace each octal digit with three bitsReplace each octal digit with three bits

ExampleExample

75643.5704 = 111101110100011.10111100010075643.5704 = 111101110100011.101111000100

19. Binary Systems 19
Conversion From one radix Conversion From one radix
to anotherto another
From binary to hexadecimalFrom binary to hexadecimal
Divide into groups of 4 bitsDivide into groups of 4 bits

ExampleExample
11001101001000.1011011 = 3348.B611001101001000.1011011 = 3348.B6
From hexadecimal to binaryFrom hexadecimal to binary

Replace each digit with four bits bitsReplace each digit with four bits bits

ExampleExample

7BA3.BC4 = 111101110100011.1011110001007BA3.BC4 = 111101110100011.101111000100

20. Binary Systems 20
ComplementsComplements

They are used to simplify the subtraction They are used to simplify the subtraction
operationoperation

Two types (for each Two types (for each base-rbase-r system) system)
Diminishing radix complement (r-1 complement)Diminishing radix complement (r-1 complement)
Radix complement (r complement)Radix complement (r complement)
Nr
n
)1(
For n-digit number N
Nr
n

r-1 complement
r complement

21. Binary Systems 21
9’s and 10’s Complements9’s and 10’s Complements
9’s complement of 6746539’s complement of 674653

999999-674653 = 325346999999-674653 = 325346
9’s complement of 0234219’s complement of 023421

999999-023421 = 976578999999-023421 = 976578
10’s complement of 67465310’s complement of 674653

325346+1 = 325347325346+1 = 325347
10’s complement of 02342110’s complement of 023421

976578+1=976579976578+1=976579

22. Binary Systems 22
1’s and 2’s Complements1’s and 2’s Complements
1’s complement of 101110011’s complement of 10111001
11111111 – 10111001 = 0100011011111111 – 10111001 = 01000110

Simply replace 1’s and 0’sSimply replace 1’s and 0’s
1’s complement of 101000101’s complement of 10100010

0101110101011101
2’s complement of 101110012’s complement of 10111001

01000110 + 1 = 0100011101000110 + 1 = 01000111

Add 1 to 1’s complementAdd 1 to 1’s complement

2’s complement of 101000102’s complement of 10100010
01011101 + 1 = 0101111001011101 + 1 = 01011110

23. Binary Systems 23
Subtraction with Subtraction with
Complements of UnsignedComplements of Unsigned
M – NM – N
Add M to r’s complement of N Add M to r’s complement of N
SumSum = M+(r = M+(r
nn
– N) = M – N+ r – N) = M – N+ r
nn


If M > N, If M > N, SumSum will have an end carry r will have an end carry r
nn
, discard it , discard it

If M<N, If M<N, SumSum will not have an end carry and will not have an end carry and

Sum Sum = r= r
nn
– (N – M) (r’s complement of N – M) – (N – M) (r’s complement of N – M)
So M – N = – (r’s complement of Sum)So M – N = – (r’s complement of Sum)

24. Binary Systems 24
Subtraction with Subtraction with
Complements of UnsignedComplements of Unsigned
65438 - 562365438 - 5623
65438
10’s complement of 05623 +94377
159815
Discard end carry 10
5
-100000
Answer 59815

25. Binary Systems 25
Subtraction with Subtraction with
Complements of UnsignedComplements of Unsigned
5623 - 654385623 - 65438
05623
10’s complement of 65438 +34562
40185
There is no end carry =>
-(10’s complement of 40185)
-59815

26. Binary Systems 26
Subtraction with Subtraction with
Complements of UnsignedComplements of Unsigned
10110010 - 1001111110110010 - 10011111
10110010
2’s complement of 10011111 +01100001
100010011
Discard end carry 2^8 -100000000
Answer 000010011

27. Binary Systems 27
Subtraction with Subtraction with
Complements of UnsignedComplements of Unsigned
10011111 -1011001010011111 -10110010
10011111
2’s complement of 10110010 +01001110
11101101
There is no end carry =>
-(2’s complement of 11101101)
Answer = -00010011

28. Binary Systems 28
Signed Binary NumbersSigned Binary Numbers
Unsigned representation can be used Unsigned representation can be used
for positive integersfor positive integers
How about negative integers?How about negative integers?

Everything must be represented in binary Everything must be represented in binary
numbersnumbers

Computers cannot use – or + signsComputers cannot use – or + signs

29. Binary Systems 29
Negative Binary NumbersNegative Binary Numbers
Three different systems have been Three different systems have been
usedused
Signed magnitudeSigned magnitude

One’s complementOne’s complement

Two’s complementTwo’s complement
NOTE: For negative numbers the sign bit is always
1, and for positive numbers it is 0 in these three
systems

30. Binary Systems 30
Signed MagnitudeSigned Magnitude
The leftmost bit is the sign bit (0 is + and 1 The leftmost bit is the sign bit (0 is + and 1
is - ) and the remaining bits hold the is - ) and the remaining bits hold the
absolute magnitude of the numberabsolute magnitude of the number

ExamplesExamples
-47 = -47 = 11 0 0 1 0 1 1 1 11 0 1 1 1 1
 47 = 47 = 00 0 0 1 0 1 1 1 11 0 1 1 1 1
For 8 bits, we can represent the signed integers
–128 to +127
How about for N bits?

31. Binary Systems 31
One’s complementOne’s complement
Replace each 1 by 0 and each 0 by 1Replace each 1 by 0 and each 0 by 1
Example (-6)Example (-6)

First represent 6 in binary format (First represent 6 in binary format (0000011000000110))

Then replace Then replace (11111001)(11111001)

32. Binary Systems 32
Two’s complementTwo’s complement
Find one’s complementFind one’s complement
Add 1Add 1
Example (-6)Example (-6)

First represent 6 in binary format (First represent 6 in binary format (0000011000000110))

One’s complement (One’s complement (1111100111111001))

Two’s complement (Two’s complement (1111101011111010))

33. Binary Systems 33
Arithmetic AdditionArithmetic Addition
Usually represented by 2’s complementUsually represented by 2’s complement
+ 5 00000101
+11 00001011
+16 00010000
- 5 11111011
+11 00001011
+6 100000110
Discard
+ 5 00000101
-11 11110101
-6 11111010
- 5 11111011
-11 11110101
-16 111110000
Discard

34. Binary Systems 34
RegistersRegisters
They can hold a groups of binary dataThey can hold a groups of binary data
Data can be transferred from one Data can be transferred from one
register to anotherregister to another

35. Binary Systems 35
Processor-Memory RegistersProcessor-Memory Registers

36. Binary Systems 36
OperationsOperations

37. Binary Systems 37
Logic Gates - 1Logic Gates - 1

38. Binary Systems 38
Logic Gates - 2Logic Gates - 2

39. Binary Systems 39
RangesRanges
The gate input The gate output

40. Binary Systems 40
Study ProblemsStudy Problems
Course Book Chapter – 1 ProblemsCourse Book Chapter – 1 Problems
1 – 21 – 2

1 – 71 – 7

1 – 81 – 8

1 – 201 – 20

1 – 341 – 34

1 – 351 – 35

1 – 361 – 36

41. Binary Systems 41
Sneak Preview Sneak Preview
Next timeNext time

ASSIGNMENTASSIGNMENT
Will be givenWill be given

QUIZ…….QUIZ…….
Expect a question from each one of the followingExpect a question from each one of the following
Convert decimal to any baseConvert decimal to any base
Convert between binary, octal, and hexadecimalConvert between binary, octal, and hexadecimal
Binary add, subtract, and multiplyBinary add, subtract, and multiply

Negative numbersNegative numbers

42. Binary Systems 42
QuestionsQuestions