§Although truth tables
representation of a function is unique, it can be expressed algebraically in
different forms
§The procedure of simplifying Boolean expressions (in 2-4) is difficult
since it lacks specific rules to predict the successive steps in the
simplification process.
§ Alternative: Karnaugh Map
(K-map) Method.
§Straight forward procedure for minimizing Boolean Function §Fact: Any function can be expressed as sum of minterms
§K-map method can be seen as a pictorial form of the truth table.
y
y 0
|
|||||||
x
|
1
|
||||||
m0
|
m1
|
x' y'
|
x' y
|
||||
0
|
|||||||
m2
|
m3
|
xy'
|
xy
|
||||
x
|
1
|
||||||
Two-variable
map 1
y
|
||||||
y
|
||||||
x
|
0
|
1
|
||||
x' y'
|
x' y
|
|||||
0
|
||||||
xy'
|
xy
|
|||||
x
|
1
|
|||||
y
|
y
|
||||||||||||
y
|
y
|
||||||||||||
x
|
0
|
1
|
x
|
0
|
1
|
||||||||
1
|
|||||||||||||
0
|
0
|
||||||||||||
x
|
|||||||||||||
1
|
1
|
x
|
1
|
1
|
1
|
||||||||
F1
|
= xy
|
F2 = m1 + m2 + m3 =
|
|
= x' y + xy'+xy
|
|||
2
y
|
y
|
||||||||||||||||
y
|
y
|
||||||||||||||||
x
|
0
|
1
|
x
|
0
|
1
|
||||||||||||
x' y'
|
x' y
|
||||||||||||||||
0
|
0
|
1
|
|||||||||||||||
x
|
xy'
|
xy
|
|||||||||||||||
1
|
x
|
1
|
|||||||||||||||
1
|
1
|
||||||||||||||||
F2 = x + y
The three
squares can be determined from the intersection of variable x in the second row and variable y in the second column.
3
§ Any two
adjacent squares differ by only one variable.
§ M5 is row 1 column 01. è 101= xy’z=m5
§ Since adjacent squares differ by one variable (1 primed, 1 unprimed) §From the postulates of Boolean algebra, the sum of two minterms in
adjacent squares can be simplified to a simple AND
§For example m5+m7=xy’z+xyz=xz(y’+y)=xz
4
Example 1
F
= S ( m2 , m3 , m4 , m5 ) = x ' yz '+ x ' yz + xy ' z '+ xy ' z
=
x ' y (
z + z ') + xy '( z + z ') = x ' y + xy '
5
Example 2
Simplify:
F (x, y, z) = S(3,4,6,7)
m0
|
m1
|
m3
|
m2
|
m4
|
m5
|
m7
|
m6
|
yz
xz' xz'
6
7
8
Example 4
Given: F ( A, B, C) = A'C + A' B + AB'C + BC
(a) Express F in sum of minterms.
(b) Find the
minimal sum of products using K-Map
A'C(B + B' ) = A' BC + A' B'C
A' B(C + C' ) = A' BC + A' BC '
AB'C
BC( A + A' ) = ABC + A' BC
(a)
F ( A,
B, C) = A' B'C + A' BC '+ A' BC + AB'C + ABC
=
S(1,2,3,5,7)
9
10
•
No zeros allowed in a group.
•
No diagonals.
•
Only power of 2 number of cells in each group.
•
Groups should be as large as possible.
•
Every one must be in at least one group.
•
Overlapping allowed.
•
Wrap around allowed.
•
Fewest number of groups possible.
11
• Need to
ensure that all Minterms of function are covered
•The
number of terms is minimized
• But avoid
any redundant terms whose minterms are already covered
•
Prime Implicant is product Term
obtained by combining maximum possible number of adjacent squares
•
If a minterm in a square is
covered by only prime implicant then ESSENTIAL
PRIME
IMPLICANT
Essential
prime implicant BD and B’D’
|
Non
Essential prime implicant
|
12
|
|
CD, B’C, AD and AB’
|
There are
four possible ways that the function can
be expressed
with four product terms of two literals each:
F = BD + BD +
CD + AD
=
BD + BD +
CD + AB
=
BD + BD +
BC + AD
=
BD + BD +
BC + AB
13
• One
square represents one minterm à a term
of 3 literals
• Two
adjacent squares à a term
of 2 literals
• Four
adjacent squares à a term
of 1 literal
• Eight
adjacent squares à the
function equals to 1
14
15
16
Example 6 Simplify F(A,B,C,D)
= A' B'C'+B'CD'+A' BCD'+AB'C'
A' B'C' Represented
by 0001 or 0000
F = B' D'+B'C'+A'CD'
17
• One
square represents one minterm à a term
of 4 literals
• Two
adjacent squares à a term
of 3 literals
• Four
adjacent squares à a term
of 2 literal
• Eight
adjacent squares à a term
of 1 literal
• sixteen
adjacent squares à the
function equals to 1
0 comments:
Post a Comment