Vulms.vu.edu.pk



Simplification of a Boolean Expression using K-Map Table

To explain the simplification of any Boolean expression using K-Map, let us take the example no. 5 which is given at page 95. The 4-variable expression which we need to simply is:

A'B'C'D + A'B'CD + A'BCD + A'BCD' + ABC'D' + ABCD' + ABC'D + ABC'D' + AB'C'D' + AB'C'D + AB'CD

As you can see that there are 11 minterms (product terms) in this expression which are a lot. Some of these terms are redundant and can be eliminated. However, to eliminate those redundant terms, we will use K-Map table method. The K-Map table corresponding to a 4-variable expression consists of 24=16 cells. The table is given below:

|AB/CD |00 |01 |11 |10 |

|00 | | | | |

|01 | | | | |

|11 | | | | |

|10 | | | | |

Now, we will fill each blank cell of the K-Map by looking at each of the 11 minterms of the expression. For each minterm, we will write 1 in its corresponding cell in the K-Map table. Starting from the left most side of the expression, our first minterm is A'B'C'D which corresponds to value 0001. Hence in the cell corresponding to AB=00 and CD=01, we will put 1. As given below:

|AB/CD |00 |01 |11 |10 |

|00 | |1 | | |

|01 | | | | |

|11 | | | | |

|10 | | | | |

Our next term is A'B'CD which corresponds to value 0011 (A=0, B=0, C=1, D=1). Hence in the above given table, we write 1 in the cell corresponding to AB=00 and CD=11. The next table is given below:

|AB/CD |00 |01 |11 |10 |

|00 | |1 |1 | |

|01 | | | | |

|11 | | | | |

|10 | | | | |

Going in the same way, we will fill one cell for each of the minterm of the original expression such that 11 cells of the K-map table are filled as given below:

|AB/CD |00 |01 |11 |10 |

|00 | |1 |1 | |

|01 | | |1 |1 |

|11 |1 |1 |1 |1 |

|10 |1 |1 |1 | |

The remaining cells are filled with 0.

|AB/CD |00 |01 |11 |10 |

|00 |0 |1 |1 |0 |

|01 |0 |0 |1 |1 |

|11 |1 |1 |1 |1 |

|10 |1 |1 |1 |0 |

One the complete K-Map is filled, we will now group the adjacent cells containing 1. The number of cells in each group will be power of 2. It means that each group will contain 1, 2, 4, 8 and so on cells. While making a group, we need to make sure that we start by making a group as large as possible.

From the above given table, we will have following 3 groups of cells.

• The first group of 1s comprising of cells 8, 9, 12 and 13. This group corresponds to cell values 1000, 1001, 1100 and 1101.

|AB/CD |00 |01 |11 |10 |

|00 |0 |1 |1 |0 |

|01 |0 |0 |1 |1 |

|11 |1 |1 |1 |1 |

|10 |1 |1 |1 |0 |

• The second group of 1s comprising of cells 1, 3, 9 and 11. This group corresponds to cell values 0001, 0011, 1001 and 1101. In this group, the cells which are start and end of second and third column become part of a same group.

|AB/CD |00 |01 |11 |10 |

|00 |0 |1 |1 |0 |

|01 |0 |0 |1 |1 |

|11 |1 |1 |1 |1 |

|10 |1 |1 |1 |0 |

The third group of 1s comprising of cells 6, 7, 14 and 15.

|AB/CD |00 |01 |11 |10 |

|00 |0 |1 |1 |0 |

|01 |0 |0 |1 |1 |

|11 |1 |1 |1 |1 |

|10 |1 |1 |1 |0 |

One important thing to note here when making groups is that all the cells of 1s in each group are adjacent to each other.

How to determine minimum terms from the groups

From the first group of 1s consisting of cells 8, 9, 12 and 13, we get the values 1000, 1001, 1100 and 1101. Starting from the left of each of these values, the first bit represents A, the second bit represents B, third bit represents C and laast bit represents D. Now we will compare these four values 1000, 1001, 1100 and 1101 and eliminate all those bits which change from 1 to 0 or 0 to 1 in at least two values. We observe that bits representing A and C do not change since A remains 1 and C remains 0 while B and D are changing so we will eliminate B and D and only left with A and C. Now, as the bit representing A is 1 and bit C representing C is 0. So our minimum minterm will become AC’.

Hence from the first group, we get the term AC’.

The second group of 1s comprising of cells 1, 3, 9 and 11. This group corresponds to cell values 0001, 0011, 1001 and 1011. So we compare these four 4-bit values to check which bits are changing. As we can see that bits representing A and C are changing whereas bits representing B and D remains the same. Hence, we eliminate variable A and C in our resultant term and only keep variable B and D. The value of B in each of the above given 4-bit values is 0 and the value of D is 1.

So, from the second group, we get the term B’D.

The third group of 1s consists of cells 6, 7, 14 and 15. The cells corresponds to values 0110, 0111, 1110 and 1111. Upon comparing these values, we see that bits representing variables A and D are changing whereas the bits representing B and C remain the same such that B = 1 and C = 1.

Hence, our minterm from the third group will be BC.

Our final simplified Boolean expression will be AC’ + B’D + BC. As you can see that original Boolean expression consisted of 11 terms whereas the new simplified expression consists of only 3 terms. However, the only thing to note here is that both the original as well as the new expression are equivalent and generate the same logic.

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download