In this article we will cover Quine Mccluskey method with examples. I will show you the simplification of Boolean expression by Quine Mccluskey method. This process is lengthy Read this full article in desktop view, I am sure you will get a clear concept.
Quine Mccluskey method is also known as tabular method or the method of prime implicants.
Generally, we use K Map ( Karnaugh Map ) to simplify a Boolean function. K Map can easily simplify Boolean functions with less variable. The Quine Mccluskey method can simplify greater number of variables than K Map. Quine Mccluskey method provides a symmetrical approach that are easily programmed into a computer for digital simplification.
For accurate use of Quine Mccluskey method the expression needs to be in SOP form.
Quine Mccluskey method is easy but make sure you have a clear concept about –
- Min term ( SOP ) and max term ( POS )
- Decimal to binary conversion.
- BCD to expression conversion.
Question
Simplify the following 4 variable Boolean function using Quine Mccluskey method.
Y = Σ m = ( 2, 4, 5, 9, 12, 13 )
Convert these decimals to Binary Coded Decimal
Decimal | Binary | |||
| A | B | C | D |
2 | 0 | 0 | 1 | 0 |
4 | 0 | 1 | 0 | 0 |
5 | 0 | 1 | 0 | 1 |
9 | 1 | 0 | 0 | 1 |
12 | 1 | 1 | 0 | 0 |
13 | 1 | 1 | 0 | 1 |
Now make a group of decimals that contains logic 1 only once. As shown in table below –
Min Term | A | B | C | D |
m_{2} | 0 | 0 | 1 | 0 |
m_{4} | 0 | 1 | 0 | 0 |
Again make a group of decimals that contains logic 1 twice. As shown in table below –
Min Term | A | B | C | D |
m_{5} | 0 | 1 | 0 | 1 |
m_{9} | 1 | 0 | 0 | 1 |
m_{12} | 1 | 1 | 0 | 0 |
Again make a group of decimals that contains logic 1 thrice. As shown in table below –
Min Term | A | B | C | D |
m_{13} | 1 | 1 | 0 | 1 |
This process is done until all the decimal numbers given in question are covered. So now we have covered all the decimals given in question.
The combined table of above three groups is shown below. You directly need to write the combined table. I separated it to explain.
Group | Min Term | A | B | C | D |
G 1 | m_{2} | 0 | 0 | 1 | 0 |
m_{4} | 0 | 1 | 0 | 0 | |
G 2 | m_{5} | 0 | 1 | 0 | 1 |
m_{9} | 1 | 0 | 0 | 1 | |
m_{12} | 1 | 1 | 0 | 0 | |
G 3 | m_{13} | 1 | 1 | 0 | 1 |
Now we compare group 1 and 2 then 2 and 3.
First to compare group 1 with 2. Compare m_{2} with m_{5}, m_{9}, m_{12}. A new table will be made and comparison will only be noted when there is difference in only one bit. The comparison of
0, 0 will give 0
1, 1 will give 1
0,1 will give X
1, 0 will give X
X, X will give X
During comparison similar digits input will give similar output and different digits input will give X.
When m_{2 }and m_{5 }is compared, more than 1 bit B, C & D are different so output will not be noted.
Again when m_{2 }and m_{9 }is compared, more than 1 bit A, C & D are different so output will not be noted.
Now when m_{2 }and m_{12 }is compared, again more than 1 bit A, B & C are different so the output will not be noted.
Now we compare m_{4} with m_{5}, m_{9}, m_{12}.
When m_{4 }is compared with m_{5}. Only one bit D is different. So the output will be noted as shown in table below.
Min Term | A | B | C | D |
m_{4} – m_{5} | 0 | 1 | 0 | X |
Again we will compare m_{4} with m_{9}. More than one bit A,B & D are different. so the output will not be noted.
Lastly, we will compare m_{4} with m_{12}. Only one bit A is different. So the output will be noted as shown in table below.
Min Term | A | B | C | D |
m_{4} – m_{12} | X | 1 | 0 | 0 |
Comparison between group 1 and 2 is now complete. Now we will compare group 2 and 3. That means m_{5}, m_{9}, m_{12} will be compared with m_{13}.
When m_{5} and m_{13} is compared. Only bit A is different so comparison will be noted as shown in figure below.
Min Term | A | B | C | D |
m_{5} – m_{13} | X | 1 | 0 | 1 |
When m_{9} and m_{13} is compared. Only bit B is different so comparison will be noted as shown in figure below.
Min Term | A | B | C | D |
m_{9} – m_{13} | 1 | X | 0 | 1 |
When m_{12} and m_{13} is compared. Only bit D is different so comparison will be noted as shown in figure below.
Min Term | A | B | C | D |
m_{12} – m_{13} | 1 | 1 | 0 | X |
The combined table of above 5 noted comparisons is shown below. You directly need to write the combined table. I separated it to explain.
Group | Min Term | A | B | C | D |
4 | m_{4} – m_{5} | 0 | 1 | 0 | X |
m_{4} – m_{12} | X | 1 | 0 | 0 | |
5 | m_{5} – m_{13} | X | 1 | 0 | 1 |
m_{9} – m_{13} | 1 | X | 0 | 1 | |
m_{12} – m_{13} | 1 | 1 | 0 | X |
We will again compare group 4 and 5 as we have done above. For other questions these process of making and comparing groups goes on until no group is formed.
First we will compare ( m_{4} – m_{5 }) with ( m_{5} – m_{13} ), ( m_{9} – m_{13 }) & ( m_{12} – m_{13 }).
There is more than 1 bit difference when ( m_{4} – m_{5 }) is compared with ( m_{5} – m_{13} ), ( m_{9} – m_{13 }). So comparison will not be noted.
There is only one bit difference when ( m_{4} – m_{5 }) is compared with ( m_{12} – m_{13 }). So comparison will be noted as shown in table below.
Min Term | A | B | C | D |
m_{4} – m_{5 – }m_{12} – m_{13} | X | 1 | 0 | X |
Again we will compare ( m_{4} – m_{12 }) with ( m_{5} – m_{13} ), ( m_{9} – m_{13 }) & ( m_{12} – m_{13 }).
There is more than 1 bit difference when ( m_{4} – m_{12 }) is compared with ( m_{9} – m_{13} ), ( m_{12} – m_{13 }). So comparison will not be noted.
There is only one bit difference in ( m_{4} – m_{12 }) & ( m_{5} – m_{13} ). So again comparison will be noted as shown in table below.
Min Term | A | B | C | D |
m_{4} _{– }m_{12} – m_{5 }– m_{13} | X | 1 | 0 | X |
The combined table of above two noted comparison is shown in table below. With their expression ( E ) in SOP form.
Min Term | A | B | C | D | E |
m_{4} – m_{5 }-m_{12} – m_{13} | X | 1 | 0 | X | BC’ |
m_{4} _{– }m_{12} – m_{5 }– m_{13} | X | 1 | 0 | X | BC’ |
We get BC’ two times in the output.
The output reduced expression can be written as –
Y = BC’
Prime and essential prime implicant
The prime implicant and essential prime implicant is shown in the table below.
The last table of comparison contains m_{4}, m_{5}, m_{12} & m_{13}. So cross for essential prime implicant is made under 4, 5, 12 & 13.
Group | Min Term | |||||
| 2 | 4 | 5 | 9 | 12 | 13 |
BC’ | X | X | X | X | ||
Prime Implicant | Essential Prime Implicant |
The advantage of Quine Mccluskey method over K Map is – this method can solve a large number of inputs where as K Map gets too long or near impossible.
1 thought on “Quine mccluskey method”