0195136047.pdf

288 DIGITAL BUILDING BLOCKS AND COMPUTER SYSTEMS

Let us now illustrate the application of this procedure in the following example.

EXAMPLE 6.1.11

Obtain a minimum Boolean expression for

F(A,B,C,D)=

∑

mi( 1 , 3 , 4 , 5 , 6 , 7 , 10 , 12 )

Solution

1. The K map ofFis shown in Figure E6.1.11(a).

(a) (b)

01

11

10

00

A ⋅ D

A ⋅ B ⋅ C ⋅ D

A ⋅ B

01

11

10

00

00 01 11

AB

CD^1000 01 11 10

AB

CD

1

11

1

1

1

1

1

1

B ⋅ C ⋅ D

1

1

1

1

(^11)
1
Figure E6.1.11

2. The prime implicants, as depicted in Figure E6.1.11(b), are(A ̄·D),(A ̄·B),(B·C ̄·D) ̄ ,
   and(A·B ̄·C·D) ̄.


3. All prime implicants happen to be essential, since each of the subcubes contains at least
   one 1 cell that is not covered by any other subcube.


4. F(A,B,C,D)=A ̄·D+A ̄·B+B·C ̄·D ̄+A·B ̄·C·D ̄.


5. The 1 cells that are covered by the subcubes expressed by the essential prime implicants
   are checked, as shown in Figure E6.1.11(b).


6. Since all the 1 cells have been checked, it follows that
   F(A,B,C,D)=A ̄·D+A ̄·B+B·C ̄·D ̄+A·B ̄·C·D ̄

The minimum POS expression for a Boolean function can be obtained easily by using K

maps in a procedure very similar to that used for the minimum SOP expression. By using the 0s

of the map and obtaining prime implicants again by using the 0 cells, this can be done. Since the

0 cells represent the compliment of the function, complementing the minimum SOP expression

for the 0s of the function yields the minimum POS form of the function. Even though the two

forms (POS and SOP) are completely equivalent, logically, one of the two forms may lead to a

realization involving a smaller number of gates.

In designing a digital system, one often encounters a situation where the output cannot be

specified due to either physical or logical constraints. Figure 6.1.15 illustrates one such situation,

where the input linesBandCto the black box of logic circuitry are physically connected together.

For such a circuit, the input combinationA=0,B=1, andC=0 is not possible, and therefore

the output corresponding to this combination cannot be specified. Such an output is hence known