0195136047.pdf

6.1 DIGITAL BUILDING BLOCKS 287

EXAMPLE 6.1.10

Consider a Boolean functionF(A, B, C, D) defined by the K map of Figure E6.1.10(a). Form the
possible subcubes and express them by their corresponding product terms.

(a) (b)

01

11

10

00

A ⋅ D

A ⋅ B ⋅ C

A ⋅ B ⋅ C ⋅ D

01 C^ ⋅^ D

11

10

00

00 01 11

AB

CD^1000 01 11 10

AB

CD

111

1

1

1

1

1

1 1 1 1

1 1

1

1

Figure E6.1.10(a)K map.(b)K map with subcubes.

Solution

Figure E6.1.10(b) shows the K map ofF(A,B,C,D)=

∑
mi( 1 , 3 , 5 , 7 , 8 , 9 , 13 , 14 )with
subcubes.
Observe that the four-cell subcube consisting of mintermsm 1 ,m 3 ,m 5 , andm 7 can be expressed
by the product term(A ̄·D), sinceA ̄andDare the only variables common to the four minterms
involved. The other subcubes shown in Figure E6.1.10(b) can be checked for their product-term
expressions. Note that any cell may be included in as many subcubes as desired.

Once a Boolean function is represented in a K map and its different subcubes are formed,
that Boolean function can be expressed as the logic SOP terms corresponding to theminimum
set of subcubes that cover all its 1 cells. Obviously then, in forming a subcube, one should not
select a subcube that is totally contained in another subcube. The product term representing the
subcube containing the maximum possible number of adjacent 1 cells in the map is called aprime
implicant. A prime implicant is known as anessential prime implicantif the subcube represented
by the prime implicant contains at least one 1 cell that is not covered by any other subcube. If,
on the other hand,allthe 1 cells of a subcube of a prime implicant are covered by some other
subcubes, then such a prime implicant is known as anoptional prime implicant. The minimized
Boolean expression is obtained by the logic sum (OR) of all the essential prime implicants and
some other optional prime implicants that cover any remaining 1 cells that are not covered by the
essential prime implicants.
The procedure for K-map simplification of ann-variable Boolean function may be summa-
rized in the following steps.

1. Represent the function in ann-variable K map.


2. Mark all prime implicants that correspond to subcubes of the maximum adjacent 1 cells.


3. Determine the essential prime implicants.


4. Develop the minimum expression with the logic sum of the essential prime implicants.


5. In the K map, check the 1 cells that are covered by the subcubes expressed by the essential
   prime implicants.


6. No other terms are needed if all the 1 cells of the map are checked. Otherwise add to
   your expression the minimum number of optional prime implicants that correspond to the
   subcubes which include the unchecked 1 cells.