Full semester notes for digital electronics

Microsoft PowerPoint - Lecture5-Karnaugh Map.ppt
Cot 2007E1.2 Digital Electronics I 5.1
Lecture 5: Logic Simplication &
Karnaugh Map
Professor Peter Cheung
Department of EEE, Imperial College London
(Floyd 4.5-4.11)
(Tocci 4.1-4.5)
Cot 2007E1.2 Digital Electronics I
Points Addressed in this Lecture
• Standard form of Boolean Expressions
– Sum-of-Products (SOP), Product-of-Sums (POS)
– Canonical form
• Boolean simplification with Boolean Alge
a
• Boolean simplification using Karnaugh Maps
• “Don’t cares”
Cot 2007E1.2 Digital Electronics I
Forms of Boolean Expressions
• Sum-of-products form (SOP)
– first the product (AND) terms are formed then these
are summed (OR)
– eg: ABC + DEF + GHI
• Product-of-sum form (POS)
– first the sum (OR) terms are formed then the products
are taken (AND)
– eg: (A+B+C) (D+E+F) (G+H+I)
• It is possible to convert between these two forms
using Boolean alge
a (DeMorgan’s)
Cot 2007E1.2 Digital Electronics I
Canonical Form
• Canonical form is not efficient but sometimes
useful in analysis and design
• In an expression in canonical form, every
variable appears in every term
– note that the dot (meaning AND) is often omitted
f(A,B,C,D) = ABCD +ABCD +ABCD
Cot 2007E1.2 Digital Electronics I
– An SOP expression can be forced into canonical form
y ANDing the incomplete terms with terms of the
form where X is the name of the missing
variable
– eg:
– The product term in a canonical SOP expression is
called a 'minterm'
(X X )+
f A B C AB BC
AB C C A A BC
ABC ABC ABC ABC
ABC ABC ABC
( , , )
( ) ( )
= +
= + + +
= + + +
= + +
Cot 2007E1.2 Digital Electronics I
A Notation using Canonical Form
• Previous example:
• Construct the truth table for this function
– use a 0 when the variable is complemented, 1 otherwise
– f can be written as the sum of row numbers having TRUE minterms
f A B C ABC ABC ABC( , , ) = + +
Row N um ber A B C f
0 0 0 0 0
1 0 0 1 0
2 0 1 0 0
3 0 1 1 1
4 1 0 0 0
5 1 0 1 0
6 1 1 0 1
7 1 1 1 1
f =∑ ( , , )3 6 7
Cot 2007E1.2 Digital Electronics I 5.7
Simplifying Logic Circuits
• First obtain one expression for the circuit, then try to simplify.
• Example:
• Two methods for simplifying
– Alge
aic method (use Boolean alge
a theorems)
– Karnaugh mapping method (systematic, step-by-step approach)
Cot 2007E1.2 Digital Electronics I
Method 1: Minimization by Boolean Alge
a
• Make use of relationships and theorems to simplify
Boolean Expressions
– perform alge
aic manipulation resulting in a
complexity reduction
– this method relies on your alge
aic skill
– 3 things to try
Cot 2007E1.2 Digital Electronics I
• a) Grouping
– Given
– write it as
– then apply
– Minimized...