Digital Systems

Standard Forms
Standard Sum-of-Products (SOP) form: equations
are written as "AND" terms summed with "OR"
operators.
Standard Product-of-Sums (POS) form: equations
are written as "OR" terms, all "ANDed" together.
Examples:
SOP: A B C+AB C + B
POS: (A + B)  (A+B +C)  (C)
These "Mixed" forms are not SOP or POS
Wrong: (A B + C) (A + C) or A BC +A C (A + B)
Standard Sum-of-Products (SOP)
 A Sum of Minterms form for n variables can be written
down directly from a truth table.
 Implementation of this form is a two-level network of
gates such that:
 The first level consists of n-input AND gates, and
 The second level is a single OR gate (with fewer
n
than 2 inputs).
 This form:
 is usually not a minimum literal expression, and
 leads to a more expensive implementation (in terms
of two levels of AND and OR gates) than needed.
 Standard Sum-of-Products (SOP)
 T h e r e f o r e , w e tr y to c o m b in e te r m s to g e t a lo w e r
lite r a l c o s t e x p r e s s io n , le a d in g to a le s s e x p e n s iv e
im p le m e n ta tio n .
 E x a m p l e : F ( A , B , C )   (1 ,4 ,5 ,6 ,7 ) Note term A B C
 S im p lif y in g duplicated
F = A B C + A B  C + A  B C + A  B  C +  A  B C
= A B (C +  C ) + A  B C + A  B  C The Canonical Sum-
+ A  B C +  A  B C of-Minterms form
= A B + A  B (C +  C ) + (A +  A ) B C has (5 * 3) = 15
= A B + A  B +  B C literals and 5 terms.
= A (B +  B ) +  B C The reduced SOP
= A +  B C form has 3 literals
and 2 terms.
AND/OR Two-level Implementation
of SOP Expression
The two implementations for F are
shown below: (Which is simpler?)

A
F
B
C
Standard Product-of-Sums (POS)
 A Product of Maxterms form for n variables can be
written down directly from a truth table.
 Implementation of this form is a two-level network of
gates such that:
 The first level consists of n-input OR gates, and
 The second level is a single AND gate (with fewer
than 2n inputs).
 This form:
 is usually not a minimum literal expression, and
 leads to a more expensive implementation (in terms
of two levels of AND and OR gates) than needed.
Standard Product-of-Sums (POS)
We can use Boolean algebra to minimize the literal cost of
an expression for POS forms.
Example: F  ( 0, 2 , 3)

Becomes: F= (A+B+C)(A+B'+C)(A+B'+C')
(Note duplicate F= (A+C+B)(A+C+B')(A+B'+C)(A+B'+C')
term) = ((A+C)+BB')((A+B')+CC')
= ((A+C)+0)((A+B')+0)
= (A+C)(A+B')
Standard Product-of-Sums (POS)
Therefore, we try to combine terms to get a lower
literal cost expression, leading to a less expensive
implementation.
Example: F  Note term A  B  C
 ( 0 , 2 , 3 ) duplicated
Simplifying
F= (A + B + C)(A +B + C)(A +B +C)
F= (A + C + B)(A + C +B)(A+B + C)(A +B +C)
= ((A + C) + BB)((A +B) + CC)
= ((A + C) + 0)((A +B) + 0) The Canonical Product-
= (A + C)(A +B) of-Maxterms form had (3
* 3) = 9 literals and 3
terms. The reduced POS
form had 4 literals and 2
terms.
OR/AND Two-level Implementation
The two implementations for F are shown
below: (Which is simpler?)
SOP and POS Observations
The previous examples show several things:
Canonical Forms (Sum-of-minterms, Product-of-
Maxterms), or other standard forms (SOP, POS)
can differ in literal cost.
Boolean algebra can be used to manipulate
equations into simpler forms.
Simpler equations lead to simpler two-level
implementations
Questions:
How can we attain a minimum literal
expression?
Is there only one minimum cost circuit?
Equivalent Cost Circuits
Given: F( A, B, C)  ( 0, 2, 3,4,5,7 )
F = A'B'C'+A'BC'+A'BC+AB'C' +AB'C+ ABC
= A'C'B'+A'C'B+AB'C+AB'C' +A'BC+ ABC
= A'C'(B+B')+AB'(C+C')+(A+A')BC
= A'C' + AB' + BC
By pairing terms differently at the start:
F = AB'C+ ABC+A'BC'+A'BC +AB'C'+A'B'C'
We arrive at:
F = AC + A'B + B'C'
BOTH HAVE THE SAME LITERALS COUNTS
AND NUMBER OF TERMS !!
Boolean Function Simplification
•Reducing the literal cost of a Boolean Expression
leads to simpler networks.
•Simpler networks are less expensive to implement.
•Boolean Algebra can help us minimize literal cost.
•When do we stop trying to reduce the cost?
•Do we know when we have a minimum?
•We will introduce a systematic way to arrive a a
minimum cost, two-level POS or SOP network.
Karnaugh Maps (K-map)
Diagram is a collection of squares
Each square represents a minterm
Collection of squares is a graphical representation of
the Boolean function
Adjacent squares differ in one variable
Pattern recognition is used to derive alternative
algebraic expressions for the same function
The Karnaugh Map can be viewed as
an extension of the truth table
The Karnaugh Map can be viewed as a topologically
warped Venn diagram as used to visualize sets
Uses of Karnaugh Maps
• Provide a means for finding optimum:
 Simple SOP and POS standard forms, and
 Small two-level AND/OR and OR/AND
circuits
• Visualize concepts related to
manipulating Boolean expressions
• Demonstrate concepts used by computer-
aided design programs to simplify large
circuits
Two Variable Maps
A Two variable Karnaugh Map:
 Note that minterm m0 and y=0 y=1
minterm m1 are "adjacent"
and differ in the value of the x=0 m0 = m1 =
variable y. x y x y
 Similarly, minterm m0 and x=1 m2 m3 =x
minterm m2 differ in the x =xy y
variable.
 Note that m1 and m3 differ in
the x variable as well.
 Minterms m2 and m3 differ in
the value of the variable y
K-Map and Function Tables
The K-Map is just a different form of the function
table. For two variables, both are shown below.
We choose a,b,c and d from the set {0,1} to
implement a particular function, F(x,y).
Function Table
K-Map
Input Function
Values Value y=0 y=1
(x,y) F(x,y)
00 a
x=0 a b
01 b x=1 c d
10 c
11 d
K-Map Function Representations
Examples F(x,y) = x G(x,y) = x+y
F=x y=0 y=1 G=x+y y=0 y=1

x=0 0 0 x=0 0 1

x=1 1 1 x=1 1 1

• For function F(x,y), the two adjacent cells containing 1’s

can be combined using the Minimization Theorem:
F ( x , y )  x y  x y x
• For G(x,y), two pairs of adjacent cells containing 1’s can
be combined using the Minimization Theorem:
G( x, y )  x y  x y    xy  x y  x  y
Duplicate x y
 Three Variable Maps
A three variable Karnaugh Map is shown
below: yz=00 yz=01 yz=11 yz=10
x=0 m0 m1 m3 m2
x=1 m4 m5 m7 m6
Where each minterm corresponds to the product
terms below: yz=00 yz=01 yz=11 yz=10
x=0 xyz xy z x y z x y z

x=1 xyz xy z xyz x yz

Note that if the binary value for an index differs in one bit
position, the minterms are adjacent on the Karnaugh Map
Example Functions
By convention, we represent the minterms by a "1" in
the map and leave the other terms blank. A function
table would also show the "0" terms.
yz=00 yz=01 yz=11 yz=10
Example: x=0 1 1
 m(2,3,4,5)
x=1 1 1

yz=00 yz=01 yz=11 yz=10

Example: x=0 1
 m(3,4,6,7) x=1 1 1 1
 Combining Squares
• By combining squares, we reduce the representation for a
term, reducing the number of literals in the Boolean
equation.
• On a three-variable K-Map:
One square represents a minterm with three variables
Two adjacent squares represent a product term with two
variables
Four “adjacent” terms represent a product term with one
variable
Eight “adjacent” terms is the function of all ones (no
variables) = 1.
 Combining Squares Example
Example: Let F =  m(2,3,6,7)

F yz=00 yz=01 yz=11 yz=10

x=0 1 1
x=1 1 1
Applying the Minimization Theorem three times:

F( x , y , z ) x y z  x y z  x y z  x y z
 yz  yz
y
Thus the four terms that form a 2 × 2 square correspond to
the term "y".
Alternate K-Map Diagram
There are many ways to draw a three variable
K-Map. Three common ways are shown below:
y yz
x 00 01 11 10
m0 m1 m3 m2
0 m0 m1 m3 m2
x m4 m5 m7 m6
1 m m m m
4 5 7 6
z
y
yz
x 00 01 11 10
0 m0 m1 m3 m2

x 1 m m m m
4 5 7 6