ELCT201: DIGITAL LOGIC DESIGN

Prof. Dr. Eng. Tallal El-Shabrawy,

tallal.el-shabrawy@guc.edu.eg

Dr. Eng. Wassim Alexan,

Lecture 2
wassim.joseph@guc.edu.eg

Following the slides of Dr. Ahmed H. Madian

COURSE OUTLINE
1. Introduction
2. Gate-Level Minimization
3. Combinational Logic
4. Synchronous Sequential Logic
5. Registers and Counters
6. Memories and Programmable Logic
BASIC LOGIC GATES
• We have defined three basic logic gates and operators

• We could build any digital circuit from those basic logic

gates

• In digital logic, we are not using normal mathematics,

we are using Boolean algebra

3
 DERIVED GATES
NAND NOR XOR XNOR
AND-Invert OR-Invert Odd Even

X Y Z X Y Z X Y Z X Y Z
0 0 1 0 0 1 0 0 0 0 0 1
0 1 1 0 1 0 0 1 1 0 1 0
1 0 1 1 0 0 1 0 1 1 0 0
1 1 0 1 1 0 1 1 0 1 1 1

4
PRACTICAL EXAMPLES OF AND & OR GATES
A seat belt alarm system An intrusion detection system

Floyd 11th edition

5
PRACTICAL ICS FOR LOGIC GATES

74 Series Logic Gate Functions

6
PRACTICAL ICS FOR LOGIC GATES

74 Series Logic Gate Functions

7
MEASUREMENT DEVICES
How to practically monitor the output of a gate?

Oscilloscope

8
MEASUREMENT DEVICES

Logic State Analyzer

Probe
Floyd 11th edition

9
 MEASUREMENT DEVICES

A hand-held Logic State

Analyzer

10
EXPRESSIONS AND LOGIC CIRCUITS

• Now that we are familiar with Boolean algebra and

logic gates, how would that help us build logic circuits?
• If you want to build a logic circuit, you must have a
Boolean expression to represent it with logic gates!

11
EXPRESSIONS AND LOGIC CIRCUITS
• Any Boolean expression can be converted into a circuit by combining
basic gates in a relatively straightforward way
• The diagram below shows the inputs and outputs of each gate
• The precedencies are explicit in a circuit. Clearly, we have to make
sure that the hardware does the operations in the right order!

12
SIMPLIFICATION OF THE LOGIC
FUNCTION
F(A,B)=A’B’ + A’B + AB’
= A’ * (B’ + B) + A * B’ (Distributivity)
= A’ * (B + B’) + A * B’ (Commutativity)
= A’ * 1 + A * B’ (x + x’ = 1)
= A’ + (A * B’) (x +x’y)=(x+x’)(x+y)(Distributivity)

= (A’ + B’) (De Morgan’s)

= (A B)’ 1 GATE (NAND) ONLY

By using simplification rules, we can optimize the design, so that it is

implemented with a single gate, instead of 7
13
ALGEBRAIC FORMS OF REPRESENTING
BOOLEAN FUNCTIONS
• Sum of Products (SOP)
• Product of Sums (POS)

14
SUM OF PRODUCTS (SOP)
Switching functions formed by:
SUMMING (ORing) PRODUCT (ANDed) terms.
Example:
sum terms

F  A , B , C , D   A BC  B D  AC D
literals
(product terms)
15
SUM OF PRODUCTS (SOP)

Product terms are known as minterms

F = 001 011 101 110 111
F = A'B'C + A'BC + AB'C + ABC' + ABC

A B C F
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1 The apostrophe ’ here means invert

16
 SUM OF PRODUCTS (SOP)
Product term (or minterm)
 ANDed product – input combination for which output is true
 Each variable appears exactly once, in true or inverted form (but not both)

From the pervious example:

F(A, B, C) = m(1,3,5,6,7)
A B C F minterms = m1 + m3 + m5 + m6 + m7
0 0 0 0 A'B'C‘ m0 = A'B'C + A'BC + AB'C + ABC' + ABC
0 0 1 1 A'B'C m1 This form is called the canonical form
0 1 0 0 A'BC' m2
0 1 1 1 A'BC m3 F(A, B, C) = A'B'C + A'BC + AB'C + ABC + ABC'
1 0 0 0 AB'C' m4 = (A'B' + A'B + AB' + AB)C + ABC'
1 0 1 1 AB'C m5 = ((A' + A)(B' + B))C + ABC'
1 1 0 1 ABC' m6 = C + ABC'
1 1 1 1 ABC m7 = ABC' + C
= AB + C
Short-hand notation for This form is called the minimal form
minterms of 3 variables 17
 HOW TO BUILD A CIRCUIT FROM THE SOP FUNCTION?
F = A'B'C + A'BC + AB'C + ABC' + ABC

Answer:

SOP  AND/OR
Two-level Implementation

18
 PRODUCT OF SUMS (POS)
Switching functions formed by taking the:
PRODUCT (ANDing) of SUM (ORed) terms.
Example: Literals
(Sum terms)


F  A , B , C , D   A  B C  B  D  A  C  D 
Products
19
PRODUCT OF SUMS (POS)
Sum terms are known as Maxterms
F= 000 010 100
F = (A + B + C) (A + B' + C) (A' + B + C)

A B C F
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1

20
PRODUCT-OF-SUMS (CONT’D)
Sum term (or maxterm)
 ORed sum of literals – input combination for which output is false
 Each variable appears exactly once in a sum term, in true or inverted form (but
not both)

F(A, B, C) = M(0,2,4)
A B C F Maxterms = M0 • M2 • M4
0 0 0 0 A+B+C M0 = (A + B + C) (A + B' + C) (A' + B + C)
0 0 1 1 A+B+C’ M1
0 1 0 0 A+B’+C M2 This form is called the canonical form
0 1 1 1 A+B'+C’ M3
1 0 0 0 A'+B+C M4
1 0 1 1 A'+B+C’ M5 F(A, B, C) = (A + B + C) (A + B' + C) (A' + B + C)
1 1 0 1 A'+B’+C M6 = (A + C) (B + C)
1 1 1 1 A'+B'+C’ M7 This form is called the minimal form

short-hand notation for

Maxterms of 3 variables
21
HOW TO BUILD A CIRCUIT FROM THE POS FUNCTION?
F(A, B, C) = (A + B + C) (A + B' + C) (A' + B + C)

Answer:

POS OR/AND
Two-level Implementation

22
SOP AND POS REPRESENT THE SAME FUNCTION
A B C F
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1

F=m(1,3,5,6,7) F=M(0,2,4)

23
 POS VERSUS SOP

• Any expression can be written either way!

• We can convert from one form to the other using theorems

• Sometimes, SOP looks simpler

AB + CD = ( A + C )( B + C )( A + D )( B + D )
• Other times, POS looks simpler
(A + B)(C + D) = BD + AD + BC + AC
• However, SOP is most commonly used

24
 MINIMIZATION OF LOGIC FUNCTIONS
We have chips with millions of gates
 Why care about minimizing a function?
 What do a few gates matter?
Basic logic functions are replicated thousands of times
 Saving one gate for a memory cell pays off
What is the criterion for minimization?
 Should we minimize the…
 Number of product terms?
 Number of logic operations?
 Number of variables (literals)?
 Number/length of wires?
 …?
For implementation: minimize the number of gates!
25
HOW TO MINIMIZE THE GATE COUNT?
Example: F=A’BC’+AB’C’+AB’C+ABC’= Σm(2,4,5,6)
How many gates do we need for implementation?
 If AND gates have 3 inputs and OR gates have 4 inputs?
 If all gates are binary (2 inputs)?

Are there any tricks we can use?

 Combine minterms:
 A’BC’+ABC’=BC’
 AB’C’+AB’C=AB’
F = BC’+AB’

 How many gates does F need now?

This mainly depends on your experience but we need a systematic
approach to minimize Boolean expressions

Answer: Karnaugh maps (K-maps) 26

KARNAUGH MAPS
• Karnaugh maps (K-maps) are graphical representations of Boolean
functions
• One map cell corresponds to a row in the truth table
• Also, one map cell corresponds to a minterm or a maxterm in the
Boolean expression
• Multiple-cell areas of the map correspond to standard terms

x y minterm
0 0 m0
0 1 m1
1 0 m2
1 1 m3

27
2-VARIABLE K-MAP
y x
x 0 1 y 0 1
0 1 0 2
0 m0 m1 OR 0 m0 m2
2 3 1 3
1 m2 m3 1 m1 m3

• The ordering of variables is important for 𝑓(𝑥, 𝑦), 𝑥 is the

row, 𝑦 is the column
• For the K map on the left, cell 0 represents 𝑥 ′ 𝑦′; cell 1
represents 𝑥 ′ 𝑦, etc…
• If a minterm is present in the function, then a 1 is placed
in the corresponding cell
28
BOOLEAN FUNCTIONS IN A K-MAP
The1s and 0s represent a function in a K-map
 A 1 represents the On-set (F=1), while a 0 represents the Off-set (F=0)
 Similar to the truth table
 0s are typically not shown

x y f x y f
0 0 0 0 0 0
0 1 0 0 1 1
1 0 0 1 0 1
1 1 1 1 1 1

29
2-VARIABLE K-MAP
Any two adjacent cells in the map differ by ONLY one variable,
which appears complemented in one cell and uncomplemented in
the other
Example

𝑚0 (= 𝑥 ′ 𝑦 ′ ) is adjacent to 𝑚1 (= 𝑥 ′ 𝑦),
this means that
𝑥 ′ 𝑦 ′ + 𝑥 ′ 𝑦 = 𝑥 ′ 𝑦 ′ + 𝑦 = 𝑥′
Also 𝑚0 (= 𝑥 ′ 𝑦 ′ ) is adjacent to 𝑚2 (= 𝑥𝑦 ′ )
𝑥 ′ 𝑦 ′ + 𝑥𝑦′ = 𝑦 ′ 𝑥 ′ + 𝑥 = 𝑦′
but 𝑚0 (= 𝑥 ′ 𝑦 ′ ) is NOT adjacent 𝑚3 (= 𝑥𝑦)! 30
 2-VARIABLE K-MAP: AN EXAMPLE
𝐹 𝑥1 , 𝑥2 = 𝑥1 ′𝑥2 ′+ 𝑥1 ′ 𝑥2 + 𝑥1 𝑥2′
= 𝑚0 + 𝑚1 + 𝑚2
= 𝑥1′ + 𝑥2 ′
The 1s are placed in the K-map for specified
minterms: 𝑚0 , 𝑚1 and 𝑚2
Grouping (ORing) of 1s allows for
simplification
What (simpler) function is represented by
each dashed rectangle?
𝑥1′ = 𝑚0 + 𝑚1
𝑥2′ = 𝑚0 + 𝑚2

Note that m0 is covered twice!

31
3-VARIABLE MAP
• Note the order of the
minterms

• Gray code is used, so that

the difference between any
adjacent cells is still ONLY
one literal

32
 3-VARIABLE MAP: EXAMPLE I
Simplify the Boolean expression: F 𝑥, 𝑦, 𝑧 = Σ(2,3,4,5)

F 𝑥, 𝑦, 𝑧 = 𝑥𝑦 ′ + 𝑥 ′ 𝑦

33
 3-VARIABLE MAP: EXAMPLE II
Simplify the Boolean expression: F 𝑥, 𝑦, 𝑧 = Σ(3,4,6,7)

F 𝑥, 𝑦, 𝑧 = 𝑦𝑧 + 𝑥𝑧′

34
 3-VARIABLE MAP: EXAMPLE III
Simplify the Boolean expression: F 𝑥, 𝑦, 𝑧 = Σ(0,2,4,5,6)

F 𝑥, 𝑦, 𝑧 = 𝑧 ′ + 𝑥𝑦′

35
 3-VARIABLE MAP: EXAMPLE IV
Let the Boolean function 𝐹(𝐴, 𝐵, 𝐶) = 𝐴′ 𝐶 + 𝐴′ 𝐵 + 𝐴𝐵′ 𝐶 + 𝐵𝐶
(a) Express this function as a sum of minterms
(b) Find the minimal SOP expression

𝐹 𝐴, 𝐵, 𝐶 = 𝛴(1,2,3,5,7) 𝐹 𝐴, 𝐵, 𝐶 = 𝐶 + 𝐴′ 𝐵
36
NOTES ON A 3-VARIABLE MAP
• The number of adjacent cells that may be combined must always
represent a number that is a power of two, such as 1, 2, 4 and 8
• As more adjacent cells are combined, we obtain a product term
with fewer literals
• One cell represents one minterm, giving a term with 3 literals
• Two adjacent cells represent a term with 2 literals
• Four adjacent cells represent a term with 1 literal
• Eight adjacent cells encompass the entire map and produce a
function that is always equal to logic 1

37