Quine-McCluskey Tabular Method

In previous chapter, we discussed K-map method, which is a convenient method for minimizing Boolean functions up to 5 variables. But, it is difficult to simppfy the Boolean functions having more than 5 variables by using this method.

Quine-McClukey tabular method is a tabular method based on the concept of prime imppcants. We know that prime imppcant is a product (or sum) term, which can’t be further reduced by combining with any other product (or sum) terms of the given Boolean function.

This tabular method is useful to get the prime imppcants by repeatedly using the following Boolean identity.

xy + xy’ = x(y + y’) = x.1 = x

Procedure of Quine-McCluskey Tabular Method

Follow these steps for simppfying Boolean functions using Quine-McClukey tabular method.

Step 1 − Arrange the given min terms in an ascending order and make the groups based on the number of ones present in their binary representations. So, there will be at most ‘n+1’ groups if there are ‘n’ Boolean variables in a Boolean function or ‘n’ bits in the binary equivalent of min terms.

Step 2 − Compare the min terms present in successive groups. If there is a change in only one-bit position, then take the pair of those two min terms. Place this symbol ‘_’ in the differed bit position and keep the remaining bits as it is.

Step 3 − Repeat step2 with newly formed terms till we get all prime imppcants.

Step 4 − Formulate the prime imppcant table. It consists of set of rows and columns. Prime imppcants can be placed in row wise and min terms can be placed in column wise. Place ‘1’ in the cells corresponding to the min terms that are covered in each prime imppcant.

Step 5 − Find the essential prime imppcants by observing each column. If the min term is covered only by one prime imppcant, then it is essential prime imppcant. Those essential prime imppcants will be part of the simppfied Boolean function.

Step 6 − Reduce the prime imppcant table by removing the row of each essential prime imppcant and the columns corresponding to the min terms that are covered in that essential prime imppcant. Repeat step 5 for Reduced prime imppcant table. Stop this process when all min terms of given Boolean function are over.

Example

Let us simppfy the following Boolean function, $fleft ( W,X,Y,Z ight )=sum mleft ( 2,6,8,9,10,11,14,15 ight )$ using Quine-McClukey tabular method.

The given Boolean function is in sum of min terms form. It is having 4 variables W, X, Y & Z. The given min terms are 2, 6, 8, 9, 10, 11, 14 and 15. The ascending order of these min terms based on the number of ones present in their binary equivalent is 2, 8, 6, 9, 10, 11, 14 and 15. The following table shows these min terms and their equivalent binary representations.

The given min terms are arranged into 4 groups based on the number of ones present in their binary equivalents. The following table shows the possible merging of min terms from adjacent groups.

The min terms, which are differed in only one-bit position from adjacent groups are merged. That differed bit is represented with this symbol, ‘-‘. In this case, there are three groups and each group contains combinations of two min terms. The following table shows the possible merging of min term pairs from adjacent groups.

The successive groups of min term pairs, which are differed in only one-bit position are merged. That differed bit is represented with this symbol, ‘-‘. In this case, there are two groups and each group contains combinations of four min terms. Here, these combinations of 4 min terms are available in two rows. So, we can remove the repeated rows. The reduced table after removing the redundant rows is shown below.

Further merging of the combinations of min terms from adjacent groups is not possible, since they are differed in more than one-bit position. There are three rows in the above table. So, each row will give one prime imppcant. Therefore, the prime imppcants are YZ’, WX’ & WY.

The prime imppcant table is shown below.

The prime imppcants are placed in row wise and min terms are placed in column wise. 1s are placed in the common cells of prime imppcant rows and the corresponding min term columns.

The min terms 2 and 6 are covered only by one prime imppcant YZ’. So, it is an essential prime imppcant. This will be part of simppfied Boolean function. Now, remove this prime imppcant row and the corresponding min term columns. The reduced prime imppcant table is shown below.

The min terms 8 and 9 are covered only by one prime imppcant WX’. So, it is an essential prime imppcant. This will be part of simppfied Boolean function. Now, remove this prime imppcant row and the corresponding min term columns. The reduced prime imppcant table is shown below.

The min term 15 is covered only by one prime imppcant WY. So, it is an essential prime imppcant. This will be part of simppfied Boolean function.

In this example problem, we got three prime imppcants and all the three are essential. Therefore, the simppfied Boolean function is

f(W,X,Y,Z) = YZ’ + WX’ + WY.