Page 74 - DCAP108_DIGITAL_CIRCUITS_AND_LOGIC_DESIGNS

Unit 4: Minimization of Boolean Algebra

To summarize: Notes
Looping an octet of 1s eliminates the three variables that appear in both complemented and
uncomplemented form.
Complete Simplification Process

We have seen how looping of pairs, quads, and octets on a K-map can be used to obtain a
simplified expression. We can summarize the rule for loops of any size: When a variable appears
in both complemented and uncomplemented form within a loop, that variable is eliminated from
the expression. Variables that are the same for all squares of the loop must appear in the final
expression.
It should be clear that a larger loop of 1s eliminates more variables. To be exact, a loop of two
eliminates one variable, a loop of four eliminates two, and a loop of eight eliminates three. This
principle will now be used to obtain a simplified logic expression from a K-map that contains
any combination of 1s and 0s.

The procedure will first be outlined and then applied to several examples. The steps below are
followed in using the K-map method for simplifying a Boolean expression:

1. Construct the K-map and place 1s in those squares corresponding to the 1s in the truth
table. Place 0s in the other squares.
2. Examine the map for adjacent 1s and loop those 1s which are not adjacent to any other 1s.
These are called isolated 1s.
3. Next, look for those 1s which are adjacent to only one other 1. Loop any pair containing
such a 1.
4. Loop any octet even if it contains some 1s that have already been looped.

5. Loop any quad that contains one or more 1s which have not already been looped, making
sure to use the minimum number of loops.

6. Loop any pair necessary to include any 1s that have not yet been looped, making sure to use
the minimum number of loops.

7. Form the OR sum of all the terms generated by each loop.

Be careful as the analog output signal must be held between sampling periods,
and the outputs must therefore be equipped with sample-and-hold amplifiers.

Figure 4.20 (a) shows the K-map for a four-variable problem. We will assume that the
map was obtained from the problem truth table (Step 1). The squares are numbered for
convenience in identifying each loop.
Step 2. Square 4 is the only square containing a 1 that is not adjacent to any other 1. It is
looped and is referred to as loop 4.
Step 3. Square 15 is adjacent only to square 11. This pair is looped and referred to as loop
11, 15.
Step 4. There are no octets.

LOVELY PROFESSIONAL UNIVERSITY 69