Monday, October 29, 2012

Electronics lessons: Quine McCluskey

So I've looked at boolean algebra, and karnaugh maps.





Now I'm going to briefly cover a algorithm called Quine McCluskey.



0 = 0000 = 1 2 3    5 6 7
1 = 0001 =       3          7
2 = 0010 = 1    3 4 5 6
3 = 0011 = 1    3 4    6 7
4 = 0100 =    2 3 4       7
5 = 0101 = 1 2    4    6 7
6 = 0110 = 1 2    4 5 6 7
7 = 0111 = 1    3          7
8 = 1000 = 1 2 3 4 5 6 7
9 = 1001 = 1 2 3 4    6 7
a = 1010 = 1 2 3 4 5    7
b = 1011 = 1 2    4 5 6 7
c = 1100 = 1 2       5 6
d = 1101 =       3 4 5 6 7
e = 1110 = 1 2    4 5 6
f =  1111 = 1 2    4 5


Then we draw a new table.
and the binary representation of the state.


Look at minterms m14 (1110) and m15 (1111)



Now we need to combine our combined minterms.



m(6, 14) [-110]
m(7,15) [-111]





Now we can delete duplicates.



m(2,6,10,14) = [- - 1    0]
m(3,7,11,15) = [- - 1 1]




now you can see that

m(2,3,6,7,10,11,14,15) - - 1 -
m(2,3,10,11,6,7,14,15) - - 1 - =>m(2,3,6,7,10,11,14,15) - - 1 -
m(2,6,10,14,3,7,11,15) - - 1 - =>m(2,3,6,7,10,11,14,15) - - 1 -

When we organise the minterms in numerical order



These minterms represent our prime implicants.
The states, and their representations
This is called a prime implicant chart.

What this chart represents is the states that must be true.






So it looks like they are ALL essential prime implicants.

so our output is m(5,7) OR m(0,2,8,10) OR m(8,10,12,14) + m(2,3,6,7,10,11,14,15)
looking at the values at the end this makes


So we can write out the expression for the gates as:
Q1 = /A . B . D + /B . /D + A . /D + C


Dr.K.Veerabhadra Rao said...

I am a retired scientist from DRDO, Presently, I am working as a professor in Muffakam Jah College of Engineering & Technology..
To explain the Quine-McClusky method I took this example of ‘7-segment
I adapted a duo-binary type of representation and wrote a programme in Matlab and obtained 5 min-terms (containing all the 4 min-terms given in this paper plus one one extra min-term.. The extra min-term is ” AB’ “.). Thinking that your answer was correct and I analyzed my programme in detail and as I could not locate any mistake, I started analyzing this paper , carefully.
The author of this paper has made a ‘blunder’ in the first ‘Prime-Implicant chart’
He did not notice the ’absence’ of ‘x’ in under the display of digit-9. From this point of chart, he carried the same mistake till the end of the paper.
Thus the correct answer contains the following 5 min-terms
Pl incorporate these changes in the above paper.

Dr.K.Veerabhadra Rao,

Danny said...

I've added a corrected update here: