Karnuagh map method becomes difficult to manage when numbers of variables exceed 4. Even with a 4-varaiable K-map, grouping of 1s or 0s depends on the ability of the user to detect optimum groups. Some times some redundant groups are included which adds a product term or a sum term which is not required and thus the expression is not the simplified version.
Consider the two 4-variable K-map with the groups of 1s shown.
In the 4-variable K-map on the left, 6 groups of 4 cells each are formed. The 6 groups form the six termsAB, AC’,AD , BC ,CD and B’D . Out of these six terms three terms are redundant and therefore they are introducing three extra product terms which are not required. The essential terms that are required are AC’, BC and B’D.
Similar Posts:
In the first K-map the group of 1s formed by cells 9, 11, 13 and 15, the group formed by cells 12, 13, 14 and 15 and the group formed by cells 3, 7, 11 and 15 are redundant.
In the 4-variable K-map on the right, 5 groups are formed. The 5 groups form the five terms ABC’, ACD , A’BC, A’C’Dand BD . Out of these five groups the largest group of 4 cells is redundant and therefore it is introducing an extra product term which is not required. The essential terms that are required are ABC’, ACD , A’BCand A’C’D.
In both the Karnaugh maps, finding the redundant terms is not very obvious. The Quine-McCluskey approach of simplifying Boolean expression is based on an exhaustive search where each minterm is compared with every other minterm in order to remove single variables. The exhaustive search is continued until only a few terms remain which do not share any common variable that can be eliminated. From these remaining terms the minimal product terms are selected that represent the simplified form of Boolean expression.
Quine-McCluskey is a program based method that is able to carry out the exhaustive search for removing shared variables. The Quine-McCluskey method is a two step method which comprises of finding Prime Implicants and selecting a minimal set of Prime Implicants.
- Find Prime Implicants: Find by an exhaustive search all the terms that are candidates for inclusion in the simplified function. These terms are known as Prime Implicants.
- Selecting Minimal Set of Prime Implicants: Choose from amongst the Prime Implicants those that give expression with the least number of literals.
[…] Quine-McCluskey Simplification Method […]