Unit Ii

The Map Method
⚫ In many digital circuits and practical problems we need to

find Boolean expression with minimum variables.
⚫ Although Boolean algebraic laws and theorems can be used
to achieve the objective, the process becomes tedious and
error-prone as the number of variables involved increases.
⚫ This necessitates the use of a suitable, relatively-simple
simplification technique like that of Karnaugh map or
Veitch diagram (K-map), introduced by Maurice
Karnaugh in 1953 at Bell Labs.
⚫ The minimization will result in reduction of the number
of gates (resulting from less number of terms) and the
number of inputs per gate (resulting from less number
of variables per term) • The minimization will
reduce cost, efficiency and power consumption.
The Map Method
⚫ The K-map method is used for expressions containing 2,
3, 4, 5 and 6 variables. For a higher number of variables,
there is another method used for simplification called the
Quine-McClusky method.
⚫ The map is made up of squares. Each square
represents one minterm. Since any Boolean function
can be expressed as a sum of minterms, it follows that a
Boolean function is recognized graphically in the map from
the area enclosed by those squares whose minterms are
included in the function.
⚫ In K-map, the number of cells is similar to the total
number of variable input combinations. For example, if the
number of variables is three, the number of cells is 23=8,
and if the number of variables is four, the number of cells
is 24=16.
The Map Method
⚫ Further, each cell within a K-map has a definite place-
value which is obtained by using an encoding technique
known as Gray code (Cyclic code or Reflected
code).
⚫ First four codes of Gray code are 00, 01, 11, 10. Using
these first four codes, we can generate remaining gray
codes.
⚫ The specialty of this code is the fact that the adjacent
code values differ only by a single bit. That is, if the
given code-word is 01, then the previous and the next
code-words can be 11 or 00, in any order, but cannot
be 10 in any case.
The Map Method
The Map Method
⚫ The following steps used to solve the expressions using K-
map:
◦ First, we find the K-map as per the number of variables.
◦ Find the maxterm and minterm in the given expression.
◦ Fill cells of K-map for SOP with 1 respective to the minterms.
◦ Fill cells of the K-map for POS with 0 respective to the
maxterm.
◦ Next, we create rectangular groups that contain total terms in the
power of two like 2, 4, 8, … and try to cover as many elements as
we can in one group.
◦ With the help of these groups, we find the product terms and
sum them up for the SOP form.
(or)
◦ With the help of these groups, we find the sum terms and
product them up for the POS form.
Two and Three Variable Maps
⚫Simplify the Boolean function:

F(A,B) = A’B+AB’+AB = ∑m(1,2,3) = ∑
(m1,m2,m3)

F(A,B) = A’B+AB’+AB

F(A,B) = ∑m(0,1,3)
Three Variable K-Map

Three Variable K-Map

⚫Simplify the Boolean functions

◦ F = x’yz+x’yz’+xy’z’+xy’z
◦ F = x’yz+xy’z’+xyz+xyz’
◦ F = A’C+A’B+AB’C+BC
◦ F(x,y,z) = ∑(0,2,4,5,6)

◦ F = x’yz+x’yz’+xy’z’+xy’z = x’y+xy’
◦ F = x’yz+xy’z’+xyz+xyz’ = yz+xz’
◦ F = A’C+A’B+AB’C+BC = C+A’B
◦ F(x,y,z) = ∑(0,2,4,5,6) = z’+xy’
Four Variable Map
Four Variable K-Map

Four Variable Map
Four Variable K-Map

Four Variable Map
Four Variable K-Map

Four Variable Map
Four Variable K-Map

Four Variable Map
Four Variable K-Map

Four Variable Map

◦ F(w,x,y,z) = ∑(0,1,2,4,5,6,8,9,12,13,14)
◦ F = A’B’C’+B’CD’+A’BCD’+AB’C’
Four Variable Map

◦ F(w,x,y,z) = ∑(0,1,2,4,5,6,8,9,12,13,14)
F = y’+w’z’+xz’
◦ F = A’B’C’+B’CD’+A’BCD’+AB’C’
F = B’D’+B’C+A’CD’
Five Variable Map
Five and Six Variable Map
⚫The five variable map must be thought to

consist of two four-variable maps and the
six-variable map to consist of four four-
variable maps.
⚫The center double line must be
considered as the center of a book, with
each half of the map being a page. When
the book is closed, two adjacent squares
will fall one on the other.
⚫In other words, the center double line is

like a mirror with each square being
adjacent, not only to its four neighboring
squares, but also to its mirror image.
⚫For example, minterm 31 in the five
variable map is adjacent to minterms 30,
15, 29, 23, and 27. The same minterm in
the six variable map is adjacent to all
these minterms plus minterm 63.
⚫From inspection, and taking into account

the new definition of adjacent squares, it
is possible to show that any 2k adjacent
squres, for k=0,1,2,…,n, in an n-variable
map, will represent an area that gives a
term of n-k literals.
Product of Sums simplification
⚫To find the simplified maxterm solution using K-
map is the same as to find for the simplified
minterm solution. There are some minor changes
in the maxterm solution, which are as follows:
◦ Select K-map according to the number of variables.
◦ We will populate the K-map by entering the value of
0 to each sum-term into the K-map cell.
◦ Make rectangular groups containing “0” terms in
power of two like 2,4,8 .. and try to cover as many
elements as you can in one group.
◦ From the groups made in above step find the sum
terms and product them up for POS form.
F(A,B,C)=π(0,3,6,7)
Simplified expression in Product of Sums (POS) –

F = (A’ + B’ + C) . (B’ + C’) . (A + B + C)
F(A,B,C,D)=π(3,5,7,8,10,11,12,13)
Simplified expression in Product of Sums (POS) –

F = (C+D’+B’).(C’+D’+A).(A’+C+D).(A’+B+C’)
⚫Simplify Y=(A'+B')+(A'+B)+(A+B) using
K-Map.
Simplified expression:A'B
⚫Simplify Y=(A + B + C') + (A + B' + C') + (A'
+ B' + C) + (A' + B' + C')
Simplified expression:
Y=(A + C') .(A' + B')
⚫Simplify F(A,B,C,D)=π(3,5,7,8,10,11,12,13)
Simplified expression:
Y=(A + C') .(A' + B')
NAND and NOR Implementation
⚫Digital circuits are more frequently constructed
with NAND and NOR gates than with AND and
OR gates.
⚫NAND and NOR gates are easier to fabricate
with electronic components and are the basic
gates in all IC digital logic families.
⚫Because of the prominence of NAND and NOR
gates in the design of digital circuits, rules and
procedures have been developed for the
conversion from Boolean functions given in
terms of AND, OR, and NOT into equivalent
NAND or NOR logic diagrams.
Three graphic symbols for inverter
x x’
x x’
x x’
⚫Implement the following function with NAND
and NOR gates.
F(x,y,z) = ∑(0,6) = ∏(1,2,3,4,5,7)
⚫Solution:
Sum of products by combining 1’s using k-Map.
F = x’y’z’ + xyz’
F’ = (x+y+z) . (x’+y’+z)
Product of sums by combining 0’s using k-Map.
F = (x+y’) . (x’+y) . z’
F’ = x’y + xy’ + z
Two-Level Implementation
⚫The implementation of a function in a standard
form (SOP & POS) is said to be a Two-level
implementation.
⚫The Sum-Of-Products (SOP) expression is
implemented with a group of AND gates, one
for each AND term. The output of the AND
gates are connected to the inputs of a single
OR gate.
⚫The Product-Of-Sums (POS) expression is
implemented with a group of OR gates, one
for each OR term. The output of the OR gates
are connected to the inputs of a single AND
gate.
Other Two-Level Implementations
⚫Some NAND or NOR gates (but not all)
allow the possibility of a wire connection
between the outputs of two gates to provide
a specific logic function. This type of logic is
called “wired logic”.
⚫Open-collector TTL NAND gates, when tied
together, perform the wired-AND logic.
⚫The wired-AND gate is not a physical gate
but only a symbol to designate the function
obtained from the indicated wired
connection.
Wired – And in open – collector TTL NAND gates

(AND – OR – INVERT)
•The logic function implemented by the circuit is

F = (AB)’ . (CD)’ = (AB + CD)’ and is called an
AND-OR-INVERT function.
⚫ Similarly,the NOR output of ECL gates can be
tied together to perform a wired-OR function.
The logic function implemented by the circuit is
F = (A+B)’ + (C+D)’ = [(A+B)(C+D)]’ and is
called an OR-AND-INVERT function.
Don’t Care Conditions
⚫ One of the very significant and useful concept in
simplifying the output expression using K-Map is the
concept of “Don’t Cares”.
⚫ The “Don’t Care” conditions allow us to replace the
empty cell of a K-Map to form a grouping of the
variables which is larger than that of forming groups
without don’t cares.
⚫ While forming groups of cells, we can consider a
“Don’t Care” cell as 1 or 0 or we can also
ignore that cell. Therefore, “Don’t Care” condition
can help us to form a larger group of cells.
⚫ A Don’t Care cell can be represented by a cross(X) in
K-Maps representing a invalid combination.
⚫Minimise the following function in POS minimal form
using K-Maps:
F(A, B, C, D) = M(6, 7, 8, 9) + d(12, 13, 14, 15)
⚫F = (A'+ C).(B' + C')

⚫Minimise the following function in SOP minimal form
using K-Maps:
F(A, B, C, D) = m(1, 2, 6, 7, 8, 13, 14, 15) + d(0, 3, 5,
12)
⚫F = AC'D' + A'D + A'C + AB

Solve?
⚫Minimize f = m(1,5,6,12,13,14) + d(4) in
SOP minimal form.
⚫Minimize F(A,B,C,D) = m(0,1,2,3,4,5) +
d(10,11,12,13,14,15) in POS minimal form.
⚫Minimize the following function in SOP
minimal form using K-Maps: F(A, B, C, D)
= m(1, 2, 6, 7, 8, 13, 14, 15) + d(3, 5, 12).
Solution?
⚫Minimize f = m(1,5,6,12,13,14) + d(4) in
SOP minimal form.
f = BC' + BD' + A'C'D
⚫Minimize F(A,B,C,D) = m(0,1,2,3,4,5) +
d(10,11,12,13,14,15) in POS minimal form.
F = A'(B' + C')
⚫Minimize the following function in SOP
minimal form using K-Maps: F(A, B, C, D)
= m(1, 2, 6, 7, 8, 13, 14, 15) + d(3, 5, 12).
f = AC'D' + A'D + A'C + AB
The Tabulation Method
⚫ The advantages of the K-map method are
◦ It is a fast method for simplifying expression up to four
variables.
◦ It gives a visual method of logic simplification.
◦ Suitable for both SOP and POS forms of reduction.
◦ It is more suitable for class room teachings on logic
simplification.
⚫ The disadvantages of the K-map method are
◦ K-maps are not suitable when the number of variables
involved exceed four.
◦ As the number of variables increases, the excessive number
of squares prevents a reasonable selection of adjacent
squares.
◦ Care must be taken to fill in every cell with the relevant
entry, such as a 0, 1 (or) don’t care terms.
◦ It is not suitable for computer reduction.
⚫The Tabulation method overcomes this
difficulty. The Tabulation method was first
formulated by Quine and later improved by
McCluskey.
⚫It is also known as the Quine-McCluskey
method.
⚫It is a specific step-by-step procedure that
guaranteed to produce a simplified standard
form expression for a function.
⚫It can be applied to problems with many
variables and has the advantage of being
suitable for machine computation.
⚫It is quite tedious for human use and is prone
to mistakes because of its routine,
monotonous process.
⚫The tabular method of simplification consists
of two parts.
⚫The first is to find by an exhaustive search all
the terms that are candidates for inclusion in
the simplified function. These terms are
called “Prime-implicants”.
⚫The second operation is to choose among
the prime-implicants those that give an
expression with the least number of literals.
Selection of Prime-implicants
⚫The selection of prime-implicants that form the
minimized function is made from a prime-
implicant table.
⚫In this table, each prime-implicant is
represented in a row and each minterm in a
column.
⚫Crosses are placed in each row to show the
composition of minterms that make the prime-
implicants.
⚫A minimum set of prime-implicants is then
chosen that covers all the minterms in the
function.
⚫ The completed prime-implicant table is inspected for
columns containing only a single cross.
⚫ In the above example, there are two minterms whose
columns have a single cross: 5, 8.
⚫ Prime-implicants that cover minterms with a single
cross in their column are called “Essential
Prime-implicants”.
⚫ To enable the final simplified expression to contain all
the minterms, we have no alternative but to include
Essential Prime-implicants.
⚫ A check mark is placed in the table next to the Essential
Prime-implicants to indicate that they have been
selected.
⚫ Next we check each column whose minterm is covered by the

selected essential prime-implicants.
⚫ For example, the selected prime-implicant b’d’ covers minterms 0, 2,
8, 10. A check is inserted in the bottom of the columns.
⚫ Similarly, prime-implicant a’d covers minterms 1, 3, 5,
• 7. A check is inserted in the bottom of the columns.
⚫ Inspection of the prime-implicant table shows that the selection of
the essential prime-implicants covers all the minterms of the
function except 14, 15. These two minterms must be included by the
selection of one or more prime-implicants.
⚫ In this example, it is clear that prime-implicant abc
covers both minterms and is therefore the one to be
selected.
⚫ We have thus found the minimum set of
prime-implicants whose sum gives the required
minimized function.
F = b’d’ + a’d + abc
⚫The selection of prime-implicants that form the
minimized function is made from a prime-
implicant table.
⚫In this table, each prime-implicant is
represented in a row and each minterm in a
column.
⚫Crosses are placed in each row to show the
composition of minterms that make the prime-
implicants.
⚫A minimum set of prime-implicants is then
chosen that covers all the minterms in the
function.
⚫ The completed prime-implicant table is inspected for
columns containing only a single cross.
⚫ In the above example, there are two minterms whose
columns have a single cross: 5, 8.
⚫ Prime-implicants that cover minterms with a single
cross in their column are called “Essential
Prime-implicants”.
⚫ To enable the final simplified expression to contain all
the minterms, we have no alternative but to include
Essential Prime-implicants.
⚫ A check mark is placed in the table next to the Essential
Prime-implicants to indicate that they have been
selected.
⚫ Next we check each column whose minterm is covered by the

selected essential prime-implicants.
⚫ For example, the selected prime-implicant b’d’ covers minterms 0, 2,
8, 10. A check is inserted in the bottom of the columns.
⚫ Similarly, prime-implicant a’d covers minterms 1, 3, 5,
• 7. A check is inserted in the bottom of the columns.
⚫ Inspection of the prime-implicant table shows that the selection of
the essential prime-implicants covers all the minterms of the
function except 14, 15. These two minterms must be included by the
selection of one or more prime-implicants.
⚫ In this example, it is clear that prime-implicant abc
covers both minterms and is therefore the one to be
selected.
⚫ We have thus found the minimum set of
prime-implicants whose sum gives the required
minimized function.
F = b’d’ + a’d + abc

Unit Ii

Uploaded by

Copyright:

Available Formats

Unit Ii

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Unit Ii

Uploaded by

Copyright:

Available Formats

The Map Method

⚫ In many digital circuits and practical problems we need to

⚫Simplify the Boolean function:

⚫Simplify the Boolean function:

⚫Simplify the Boolean function:

Three Variable K-Map

Three Variable K-Map

⚫Simplify the Boolean functions

⚫Simplify the Boolean functions

Four Variable K-Map

Four Variable K-Map

Four Variable K-Map

Four Variable K-Map

Four Variable K-Map

⚫Simplify the Boolean functions

⚫Simplify the Boolean functions

⚫The five variable map must be thought to

⚫In other words, the center double line is

⚫From inspection, and taking into account

Simplified expression in Product of Sums (POS) –

Simplified expression in Product of Sums (POS) –

Wired – And in open – collector TTL NAND gates

•The logic function implemented by the circuit is

⚫F = (A'+ C).(B' + C')

⚫F = AC'D' + A'D + A'C + AB

⚫ Next we check each column whose minterm is covered by the

⚫ Next we check each column whose minterm is covered by the

You might also like