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 simplify 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 implicants. We know that prime implicant 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 implicants 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 simplifying 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 implicants.
Step 4 − Formulate the prime implicant table. It consists of set of rows and columns. Prime implicants 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 implicant.
Step 5 − Find the essential prime implicants by observing each column. If the min term is covered only by one prime implicant, then it is essential prime implicant. Those essential prime implicants will be part of the simplified Boolean function.
Step 6 − Reduce the prime implicant table by removing the row of each essential prime implicant and the columns corresponding to the min terms that are covered in that essential prime implicant. Repeat step 5 for Reduced prime implicant table. Stop this process when all min terms of given Boolean function are over.
Example
Let us simplify the following Boolean function, f(W,X,Y,Z)=∑m(2,6,8,9,10,11,14,15)f(W,X,Y,Z)=∑m(2,6,8,9,10,11,14,15) 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.
Group Name | Min terms | W | X | Y | Z |
GA1 | 2 | 0 | 0 | 1 | 0 |
8 | 1 | 0 | 0 | 0 | |
GA2 | 6 | 0 | 1 | 1 | 0 |
9 | 1 | 0 | 0 | 1 | |
10 | 1 | 0 | 1 | 0 | |
GA3 | 11 | 1 | 0 | 1 | 1 |
14 | 1 | 1 | 1 | 0 | |
GA4 | 15 | 1 | 1 | 1 | 1 |
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.
Group Name | Min terms | W | X | Y | Z |
GB1 | 2,6 | 0 | - | 1 | 0 |
2,10 | - | 0 | 1 | 0 | |
8,9 | 1 | 0 | 0 | - | |
8,10 | 1 | 0 | - | 0 | |
GB2 | 6,14 | - | 1 | 1 | 0 |
9,11 | 1 | 0 | - | 1 | |
10,11 | 1 | 0 | 1 | - | |
10,14 | 1 | - | 1 | 0 | |
GB3 | 11,15 | 1 | - | 1 | 1 |
14,15 | 1 | 1 | 1 | - |
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.
Group Name | Min terms | W | X | Y | Z |
GB1 | 2,6,10,14 | - | - | 1 | 0 |
2,10,6,14 | - | - | 1 | 0 | |
8,9,10,11 | 1 | 0 | - | - | |
8,10,9,11 | 1 | 0 | - | - | |
GB2 | 10,11,14,15 | 1 | - | 1 | - |
10,14,11,15 | 1 | - | 1 | - |
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.
Group Name | Min terms | W | X | Y | Z |
GC1 | 2,6,10,14 | - | - | 1 | 0 |
| 8,9,10,11 | 1 | 0 | - | - |
GC2 | 10,11,14,15 | 1 | - | 1 | - |
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 implicant. Therefore, the prime implicants are YZ’, WX’ & WY.
The prime implicant table is shown below.
Min terms / Prime Implicants | 2 | 6 | 8 | 9 | 10 | 11 | 14 | 15 |
YZ’ | 1 | 1 |
|
| 1 |
| 1 |
|
WX’ |
|
| 1 | 1 | 1 | 1 |
|
|
WY |
|
|
|
| 1 | 1 | 1 | 1 |
The prime implicants are placed in row wise and min terms are placed in column wise. 1s are placed in the common cells of prime implicant rows and the corresponding min term columns.
The min terms 2 and 6 are covered only by one prime implicant YZ’. So, it is an essential prime implicant. This will be part of simplified Boolean function. Now, remove this prime implicant row and the corresponding min term columns. The reduced prime implicant table is shown below.
Min terms / Prime Implicants | 8 | 9 | 11 | 15 |
WX’ | 1 | 1 | 1 |
|
WY |
|
| 1 | 1 |
The min terms 8 and 9 are covered only by one prime implicant WX’. So, it is an essential prime implicant. This will be part of simplified Boolean function. Now, remove this prime implicant row and the corresponding min term columns. The reduced prime implicant table is shown below.
Min terms / Prime Implicants | 15 |
WY | 1 |
The min term 15 is covered only by one prime implicant WY. So, it is an essential prime implicant. This will be part of simplified Boolean function.
In this example problem, we got three prime implicants and all the three are essential. Therefore, the simplified Boolean function is
f(W,X,Y,Z) = YZ’ + WX’ + WY.
Digital Circuits - Logic Gates
Digital electronic circuits operate with voltages of two logic levelsnamely Logic Low and Logic High. The range of voltages corresponding to Logic Low is represented with ‘0’. Similarly, the range of voltages corresponding to Logic High is represented with ‘1’.
The basic digital electronic circuit that has one or more inputs and single output is known as Logic gate. Hence, the Logic gates are the building blocks of any digital system. We can classify these Logic gates into the following three categories.
Now, let us discuss about the Logic gates come under each category one by one.
Basic Gates
In earlier chapters, we learnt that the Boolean functions can be represented either in sum of products form or in product of sums form based on the requirement. So, we can implement these Boolean functions by using basic gates. The basic gates are AND, OR & NOT gates.
AND gate
An AND gate is a digital circuit that has two or more inputs and produces an output, which is the logical AND of all those inputs. It is optional to represent the Logical AND with the symbol ‘.’.
The following table shows the truth table of 2-input AND gate.
A | B | Y=A.B |
0 | 0 | 0 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 1 |
Here A, B are the inputs and Y is the output of two input AND gate. If both inputs are ‘1’, then only the output, Y is ‘1’. For remaining combinations of inputs, the output, Y is ‘0’.
The following figure shows the symbol of an AND gate, which is having two inputs A, B and one output, Y.
This AND gate produces an output (Y), which is the logical AND of two inputs A, B. Similarly, if there are ‘n’ inputs, then the AND gate produces an output, which is the logical AND of all those inputs. That means, the output of AND gate will be ‘1’, when all the inputs are ‘1’.
OR gate
An OR gate is a digital circuit that has two or more inputs and produces an output, which is the logical OR of all those inputs. This logical OR is represented with the symbol ‘+’.
The following table shows the truth table of 2-input OR gate.
A | B | Y=A+B |
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 1 |
Here A, B are the inputs and Y is the output of two input OR gate. If both inputs are ‘0’, then only the output, Y is ‘0’. For remaining combinations of inputs, the output, Y is ‘1’.
The following figure shows the symbol of an OR gate, which is having two inputs A, B and one output, Y.
This OR gate produces an output (Y), which is the logical OR of two inputs A, B. Similarly, if there are ‘n’ inputs, then the OR gate produces an output, which is the logical OR of all those inputs. That means, the output of an OR gate will be ‘1’, when at least one of those inputs is ‘1’.
-
A NOT gate is a digital circuit that has single input and single output. The output of NOT gate is the logical inversion of input. Hence, the NOT gate is also called as inverter.
The following table shows the truth table of NOT gate.
A | Y=A’ |
0 | 1 |
1 | 0 |
Here A and Y are the input and output of NOT gate respectively. If the input, A is ‘0’, then the output, Y is ‘1’. Similarly, if the input, A is ‘1’, then the output, Y is ‘0’.
The following figure shows the symbol of NOT gate, which is having one input, A and one output, Y.
This NOT gate produces an output (Y), which is the complement of input, A.
Universal gates
NAND & NOR gates are called as universal gates. Because we can implement any Boolean function, which is in sum of products form by using NAND gates alone. Similarly, we can implement any Boolean function, which is in product of sums form by using NOR gates alone.
NAND gate
NAND gate is a digital circuit that has two or more inputs and produces an output, which is the inversion of logical AND of all those inputs.
The following table shows the truth table of 2-input NAND gate.
A | B | Y=(A.B)’ |
0 | 0 | 1 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
Here A, B are the inputs and Y is the output of two input NAND gate. When both inputs are ‘1’, the output, Y is ‘0’. If at least one of the input is zero, then the output, Y is ‘1’. This is just opposite to that of two input AND gate operation.
The following image shows the symbol of NAND gate, which is having two inputs A, B and one output, Y.
NAND gate operation is same as that of AND gate followed by an inverter. That’s why the NAND gate symbol is represented like that.
NOR gate
NOR gate is a digital circuit that has two or more inputs and produces an output, which is the inversion of logical OR of all those inputs.
The following table shows the truth table of 2-input NOR gate
A | B | Y=(A+B)’ |
0 | 0 | 1 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 0 |
Here A, B are the inputs and Y is the output. If both inputs are ‘0’, then the output, Y is ‘1’. If at least one of the input is ‘1’, then the output, Y is ‘0’. This is just opposite to that of two input OR gate operation.
The following figure shows the symbol of NOR gate, which is having two inputs A, B and one output, Y.
NOR gate operation is same as that of OR gate followed by an inverter. That’s why the NOR gate symbol is represented like that.
Special Gates
Ex-OR & Ex-NOR gates are called as special gates. Because, these two gates are special cases of OR & NOR gates.
Ex-OR gate
The full form of Ex-OR gate is Exclusive-OR gate. Its function is same as that of OR gate except for some cases, when the inputs having even number of ones.
The following table shows the truth table of 2-input Ex-OR gate.
A | B | Y=A⊕B |
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
Here A, B are the inputs and Y is the output of two input Ex-OR gate. The truth table of Ex-OR gate is same as that of OR gate for first three rows. The only modification is in the fourth row. That means, the output (Y) is zero instead of one, when both the inputs are one, since the inputs having even number of ones.
Therefore, the output of Ex-OR gate is ‘1’, when only one of the two inputs is ‘1’. And it is zero, when both inputs are same.
Below figure shows the symbol of Ex-OR gate, which is having two inputs A, B and one output, Y.
Ex-OR gate operation is similar to that of OR gate, except for few combination(s) of inputs. That’s why the Ex-OR gate symbol is represented like that. The output of Ex-OR gate is ‘1’, when odd number of ones present at the inputs. Hence, the output of Ex-OR gate is also called as an odd function.
Ex-NOR gate
The full form of Ex-NOR gate is Exclusive-NOR gate. Its function is same as that of NOR gate except for some cases, when the inputs having even number of ones.
The following table shows the truth table of 2-input Ex-NOR gate.
A | B | A⊙B |
0 | 0 | 1 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 1 |
Here A, B are the inputs and Y is the output. The truth table of Ex-NOR gate is same as that of NOR gate for first three rows. The only modification is in the fourth row. That means, the output is one instead of zero, when both the inputs are one.
Therefore, the output of Ex-NOR gate is ‘1’, when both inputs are same. And it is zero, when both the inputs are different.
The following figure shows the symbol of Ex-NOR gate, which is having two inputs A, B and one output, Y.
Ex-NOR gate operation is similar to that of NOR gate, except for few combination(s) of inputs. That’s why the Ex-NOR gate symbol is represented like that. The output of Ex-NOR gate is ‘1’, when even number of ones present at the inputs. Hence, the output of Ex-NOR gate is also called as an even function.
From the above truth tables of Ex-OR & Ex-NOR logic gates, we can easily notice that the Ex-NOR operation is just the logical inversion of Ex-OR operation.