0195136047.pdf

286 DIGITAL BUILDING BLOCKS AND COMPUTER SYSTEMS

for example, has an assignment ofA ̄·B ̄·C·D( ̄ = 0 · 0 · 1 · 0 ), whereas them 3 cell has the

assignment ofA ̄·B ̄·C·D(= 0 · 0 · 1 · 1 ), which differs only in the value of the variableD.

A function can be represented in a K map by simply entering 1s in the cells that correspond

to the minterms of the function. This is best illustrated by an example.

EXAMPLE 6.1.9

Show the K-map representations of the following Boolean functions:

(a)F(A,B,C)=

∑

mi( 0 , 2 , 3 , 5 , 7 )

(b)F(A,B,C,D)=

∑

mi( 1 , 3 , 5 , 6 , 9 , 10 , 13 , 14 )

Solution

Figure E6.1.9 shows the K-map representations of the functions.

(a)

1

0

00 01 11

F(A, B, C) = Σ mi(0, 2, 3, 5, 7)

AB

C^10

111

1 1

(b)

01

11

10

00

00 01 11

F(A, B, C, D) = Σ mi(1, 3, 5, 6, 9, 10, 13, 14)

AB

CD^10

1 111

111

1

Figure E6.1.9

Simplification of ann-variable Boolean function by using a K map is achieved by grouping

adjacent cells that contain 1s. The number of adjacent cells that may be grouped is always equal

to 2m, for 0≤m≤n, i.e., 1, 2, 4, 8, 16, 32,... cells. Such a group or set of 2mcells is called a

subcubeand is expressed by the product term containing only the variables that are common to

the adjacent cells. The larger the subcube is, the fewer variables are needed to express the product

term. This statement can be justified by using Boolean identities. For example, in a four-variable

K map, the following possible subcubes can be formed.

• 1-cell subcube (having one minterm) expressed by a product term containing four, orn−m,
  variables; note thatn=4 andm=0 for this case.


• 2-cell subcube (having two minterms) expressed by a product term containing three, or
  n−m, variables; note thatn=4 andm=1 for this case.


• 4-cell subcube (having four minterms) expressed by a product term containing two, or
  n−m, variables; note thatn=4 andm=2 for this case.


• 8-cell subcube (having eight minterms) expressed by a product term containing one orn−m
  variables; note thatn=4 andm=3 for this case.


• 16-cell subcube (having sixteen minterms) expressed by the logic 1; that is, the function is
  always equal to 1.
  Let us now present an example to illustrate the concepts related to subcubes.