You are here

K-Map Redundant and Don’t Care

Introduction

In Simplification using K-Map we used minterms or Maxterms to group 1’s or 0’s respectively to form pair, quad or octets. There may be situations where all the 1’s which are part of one group are overlapped by other groups or certain input conditions may not be contributing in getting the minterms or maxterms of the output functions. In the following discussions, we will see how to account for such conditions.

Redundant Groups

A redundant group is one whose all the 1’s have been used or ovelapped by other groups. We can always  eliminate such group. Let us take an example and understand how redundant group can be dropped thus not part of solution.

Example: Simplify the SOP equation given by F(ABC) = ∑(2,3,5,7).

Figure-1

There are three possible pairs in the K-Map for the function F(ABC) = ∑(2,3,5,7). Pairs are named Gp-1, Gp-2, Gp-3 in figure(a). Note that both the 1’s of Gp-1 (in blue) are used by other pairs (Gp-2 and Gp-3), upper 1 used by Gp-2 pair and lower ‘1’ used by Gp-3. So we can neglect Gp-1.

The  K-Map of figure-(b) shows only two pairs actually required to be formed. Upper pair reduces to A’B and lower pair gives AC.

The solution thus is:

F(ABC) =   A’B + AC

Example-2: Simplify the Boolean function given by F(ABCD) =   (1,5,6,7,11,12,13,15)

Figure-2

Again clearly seen that there are five possible groups, four pairs (in blue) and one quad (in Red). As all the 1’s of the Quad are consumed by the four pairs, hence we can drop the quad . This lead to the new K-Map as seen in figure-(b) that consist of only four pairs. Each pair reduces to A’C’D, A’BC, ACD, ABC’ respectively AND hence the solution to the given function is :

F(ABCD) = A’C’D   +   A’BC   + ACD   + ABC’

The logic circuit which implement above solution requires 04 inverters, 04 AND gate, and 01 OR gate.

           

Figure-3

Don’t Care Conditions

A don’t care is one whose presence or absence in the equation does not matter, however if, properly used then it may lead to even better solution. A don’t care term can be treated as to be a ‘0’ or ‘1’ as per our convenience if it leads a better solution. It is marked as ‘X’ in the K-Map. Following example clarifies the use of don’t care conditions:

Example: Simplify the Boolean function F(ABC) =∑m(3,5,6,7) + ∑d(0,2)

The question contains SOP term and sum od don’t care terms. The don’t care terms are marked as X in the K-Map. It is up to us to assign a ‘0’ or a ‘1’ value to this X (don’t care). The designer has assign a value ‘1’ if it helps in better solution else he may assign it as ‘0’.

Figure-4

In the K-Map in this figure the don’t care at position ‘0’ is assigned a ‘0’ and the X at position ‘2’ in the map is assumed as ‘1’ since this contributes in forming a quad.

The solution thus is F= B + AC

Practice Problems

  1. Simplify the following 3-variable SOP equations
  2. F(ABC) =∑m(1,3,7) + ∑d(0,2,5,6)
  3. F(ABC) =∑m(0, 2,3,4,7) + ∑d(1, 6)
  4. F(ABC) =∑m(3,6,7) + ∑d(0,2,5)

Leave a Reply

Top
error: Content is protected !!