Page 174 - Engineering Digital Design

4.4 KARNAUGH MAP FUNCTION MINIMIZATION 145

Section 4.3, simple examples serve to demonstrate how K-maps can be used to extract both
canonical and minimum SOP and POS forms depending on whether 1's or O's are read.
Now it is necessary to present certain important information that was not explicitly stated
earlier, but was implied.
It should be clear from Section 4.3 that each line or edge of a K-map forms the boundary
between two complementary domains. As a result, minterms or maxterms that are separated
by a line or edge are logically adjacent and can be combined to form a reduced function.
The following rule generalizes this point:

Reduction Rule
Each variable domain boundary crossed in an adjacent group (looping) requires the
absence of that variable in the reduced term.

Thus, a pair of logically adjacent minterms or maxterms crosses one domain boundary and
eliminates the domain variable in the reduced term; a grouping of four logically adjacencies
crosses two domain boundaries and eliminates the two domain variables in the reduced
function. In this way 2" logic adjacencies (n = 1, 2, 3, ...) can be extracted (looped out)
to produce a reduced (N — n)-variable term of an TV-variable function.
To help ensure a minimized result from K-map extraction, thereby avoiding possible
costly redundancies, the following loop-out protocol is recommended but not required:

Loop-out Protocol
Loop out the largest 2" group of logically adjacent minterms or maxterms in the order
of increasing n = 0, 1, 2, 3,

When following this protocol, single isolated minterms or maxterms (monads), if present,
should be looped out first. This should be followed by looping out groups of any two logically
adjacent minterms or maxterms (dyads or duads) that cannot be looped out in any other
way. The process continues with groups of four logic adjacencies (quads), then groups of
eight (octads), etc. — always in groups of 2" logic adjacencies.
As an example of the pitfalls that can result from failure to follow the loop-out protocol,
consider the function represented in the K-map of Fig. 4.14. Instinctively, one may be
tempted to loop out the quad (dashed loop) because it is so conspicuous. However, to do
so creates a redundancy, since all minterms of that grouping are covered by the four dyads
shown by the shaded loops.
Since K-maps are minterm-code based, minimum POS cover can be extracted directly,
avoiding the "NOT" step indicated in Figs. 4.8,4.10,4.11, and 4.13, by using the following
procedure:

Simplified POS Extraction Procedure
Take the union (ORing) of the complemented domains in which the 2" groups of
logically adjacent maxterms exist.

Groups of minterms or maxterms other than 2" groups (e.g., groups of three, five, six,
and seven) are forbidden since such groups are not continuously adjacent. Examples of such