Digital Circuits - K-Map Method

In previous chapters, we have simppfied the Boolean functions using Boolean postulates and theorems. It is a time consuming process and we have to re-write the simppfied expressions after each step.

To overcome this difficulty, Karnaugh introduced a method for simppfication of Boolean functions in an easy way. This method is known as Karnaugh map method or K-map method. It is a graphical method, which consists of 2ⁿ cells for ‘n’ variables. The adjacent cells are differed only in single bit position.

K-Maps for 2 to 5 Variables

K-Map method is most suitable for minimizing Boolean functions of 2 variables to 5 variables. Now, let us discuss about the K-Maps for 2 to 5 variables one by one.

2 Variable K-Map

The number of cells in 2 variable K-map is four, since the number of variables is two. The following figure shows 2 variable K-Map.

There is only one possibipty of grouping 4 adjacent min terms.

The possible combinations of grouping 2 adjacent min terms are {(m₀, m₁), (m₂, m₃), (m₀, m₂) and (m₁, m₃)}.

3 Variable K-Map

The number of cells in 3 variable K-map is eight, since the number of variables is three. The following figure shows 3 variable K-Map.

There is only one possibipty of grouping 8 adjacent min terms.

The possible combinations of grouping 4 adjacent min terms are {(m₀, m₁, m₃, m₂), (m₄, m₅, m₇, m₆), (m₀, m₁, m₄, m₅), (m₁, m₃, m₅, m₇), (m₃, m₂, m₇, m₆) and (m₂, m₀, m₆, m₄)}.

The possible combinations of grouping 2 adjacent min terms are {(m₀, m₁), (m₁, m₃), (m₃, m₂), (m₂, m₀), (m₄, m₅), (m₅, m₇), (m₇, m₆), (m₆, m₄), (m₀, m₄), (m₁, m₅), (m₃, m₇) and (m₂, m₆)}.

If x=0, then 3 variable K-map becomes 2 variable K-map.

4 Variable K-Map

The number of cells in 4 variable K-map is sixteen, since the number of variables is four. The following figure shows 4 variable K-Map.

There is only one possibipty of grouping 16 adjacent min terms.

Let R₁, R₂, R₃ and R₄ represents the min terms of first row, second row, third row and fourth row respectively. Similarly, C₁, C₂, C₃ and C₄ represents the min terms of first column, second column, third column and fourth column respectively. The possible combinations of grouping 8 adjacent min terms are {(R₁, R₂), (R₂, R₃), (R₃, R₄), (R₄, R₁), (C₁, C₂), (C₂, C₃), (C₃, C₄), (C₄, C₁)}.

If w=0, then 4 variable K-map becomes 3 variable K-map.

5 Variable K-Map

The number of cells in 5 variable K-map is thirty-two, since the number of variables is 5. The following figure shows 5 variable K-Map.

There is only one possibipty of grouping 32 adjacent min terms.

There are two possibipties of grouping 16 adjacent min terms. i.e., grouping of min terms from m₀ to m₁₅ and m₁₆ to m₃₁.

If v=0, then 5 variable K-map becomes 4 variable K-map.

In the above all K-maps, we used exclusively the min terms notation. Similarly, you can use exclusively the Max terms notation.

Minimization of Boolean Functions using K-Maps

If we consider the combination of inputs for which the Boolean function is ‘1’, then we will get the Boolean function, which is in standard sum of products form after simppfying the K-map.

Similarly, if we consider the combination of inputs for which the Boolean function is ‘0’, then we will get the Boolean function, which is in standard product of sums form after simppfying the K-map.

Follow these rules for simppfying K-maps in order to get standard sum of products form.

Select the respective K-map based on the number of variables present in the Boolean function.

If the Boolean function is given as sum of min terms form, then place the ones at respective min term cells in the K-map. If the Boolean function is given as sum of products form, then place the ones in all possible cells of K-map for which the given product terms are vapd.

Check for the possibipties of grouping maximum number of adjacent ones. It should be powers of two. Start from highest power of two and upto least power of two. Highest power is equal to the number of variables considered in K-map and least power is zero.

Each grouping will give either a pteral or one product term. It is known as prime imppcant. The prime imppcant is said to be essential prime imppcant, if atleast single ‘1’ is not covered with any other groupings but only that grouping covers.

Note down all the prime imppcants and essential prime imppcants. The simppfied Boolean function contains all essential prime imppcants and only the required prime imppcants.

Note 1 − If outputs are not defined for some combination of inputs, then those output values will be represented with don’t care symbol ‘x’. That means, we can consider them as either ‘0’ or ‘1’.

Note 2 − If don’t care terms also present, then place don’t cares ‘x’ in the respective cells of K-map. Consider only the don’t cares ‘x’ that are helpful for grouping maximum number of adjacent ones. In those cases, treat the don’t care value as ‘1’.

Example

Let us simppfy the following Boolean function, f(W, X, Y, Z)= WX’Y’ + WY + W’YZ’ using K-map.

The given Boolean function is in sum of products form. It is having 4 variables W, X, Y & Z. So, we require 4 variable K-map. The 4 variable K-map with ones corresponding to the given product terms is shown in the following figure.

Here, 1s are placed in the following cells of K-map.

The cells, which are common to the intersection of Row 4 and columns 1 & 2 are corresponding to the product term, WX’Y’.

The cells, which are common to the intersection of Rows 3 & 4 and columns 3 & 4 are corresponding to the product term, WY.

The cells, which are common to the intersection of Rows 1 & 2 and column 4 are corresponding to the product term, W’YZ’.

There are no possibipties of grouping either 16 adjacent ones or 8 adjacent ones. There are three possibipties of grouping 4 adjacent ones. After these three groupings, there is no single one left as ungrouped. So, we no need to check for grouping of 2 adjacent ones. The 4 variable K-map with these three groupings is shown in the following figure.

Here, we got three prime imppcants WX’, WY & YZ’. All these prime imppcants are essential because of following reasons.

Two ones (m₈ & m₉) of fourth row grouping are not covered by any other groupings. Only fourth row grouping covers those two ones.

Single one (m₁₅) of square shape grouping is not covered by any other groupings. Only the square shape grouping covers that one.

Two ones (m₂ & m₆) of fourth column grouping are not covered by any other groupings. Only fourth column grouping covers those two ones.

Therefore, the simppfied Boolean function is

f = WX’ + WY + YZ’

Follow these rules for simppfying K-maps in order to get standard product of sums form.

Select the respective K-map based on the number of variables present in the Boolean function.

If the Boolean function is given as product of Max terms form, then place the zeroes at respective Max term cells in the K-map. If the Boolean function is given as product of sums form, then place the zeroes in all possible cells of K-map for which the given sum terms are vapd.

Check for the possibipties of grouping maximum number of adjacent zeroes. It should be powers of two. Start from highest power of two and upto least power of two. Highest power is equal to the number of variables considered in K-map and least power is zero.

Each grouping will give either a pteral or one sum term. It is known as prime imppcant. The prime imppcant is said to be essential prime imppcant, if atleast single ‘0’ is not covered with any other groupings but only that grouping covers.

Note down all the prime imppcants and essential prime imppcants. The simppfied Boolean function contains all essential prime imppcants and only the required prime imppcants.

Note − If don’t care terms also present, then place don’t cares ‘x’ in the respective cells of K-map. Consider only the don’t cares ‘x’ that are helpful for grouping maximum number of adjacent zeroes. In those cases, treat the don’t care value as ‘0’.

Example

Let us simppfy the following Boolean function, $fleft ( X,Y,Z ight )=prod Mleft ( 0,1,2,4 ight )$ using K-map.

The given Boolean function is in product of Max terms form. It is having 3 variables X, Y & Z. So, we require 3 variable K-map. The given Max terms are M₀, M₁, M₂ & M₄. The 3 variable K-map with zeroes corresponding to the given Max terms is shown in the following figure.

There are no possibipties of grouping either 8 adjacent zeroes or 4 adjacent zeroes. There are three possibipties of grouping 2 adjacent zeroes. After these three groupings, there is no single zero left as ungrouped. The 3 variable K-map with these three groupings is shown in the following figure.

Here, we got three prime imppcants X + Y, Y + Z & Z + X. All these prime imppcants are essential because one zero in each grouping is not covered by any other groupings except with their inspanidual groupings.

Therefore, the simppfied Boolean function is

f = (X + Y).(Y + Z).(Z + X)

In this way, we can easily simppfy the Boolean functions up to 5 variables using K-map method. For more than 5 variables, it is difficult to simppfy the functions using K-Maps. Because, the number of cells in K-map gets doubled by including a new variable.

Due to this checking and grouping of adjacent ones (min terms) or adjacent zeros (Max terms) will be comppcated. We will discuss Tabular method in next chapter to overcome the difficulties of K-map method.