Monday, October 29, 2012

Electronics lessons: Quine McCluskey

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

What you may have realised is, first, binary systems become very big very fast.

But second, Boolean algebra, while useful has some pretty head churning limitations, feasibly there are no limitations, practically it's extraordinarily hard to be able to see what reductions may be created when dealing with more than three or four terms.

Karnaugh maps were a lot easier, yes they did require you to keep your wits about you whilst filling them in, the four by four map was filled logically as row 1 column1, row2 column1, row4 column 1, row 3 column 1. this carried on, but you filled column 1, then 2 then 4 then 3. so you sort of feel like you're jumping all over the place, and the logically last filled cell is at the middle of the table.

On top of that there is also the problem that karnaugh maps have a limitation on the amount of inputs that you can deal with practically, (it's difficult to use with a large number of inputs)

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

What makes this different is that it's expressed in a tabular formation. except rather than drawing boxes around the table we look for the number of ones in a given row where the output is true.

In order to demonstrate this I'm going to go back to the seven segment display. remember that first table that showed for each state 0 -15 what the 7 output segments on the 7 segment display needed to show;

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

We'll start the demonstration of Quine McCluskey by looking at the table of outputs for segment 1 of the seven segment display.

Then we draw a new table.
This table looks at the number of 1's in a state,
then the name of the state, (which is called a minterm)
and the binary representation of the state.

Now we look at the minterms and see which ones differ by only one bit.
Then we re-write these terms, using a dash to signify the bit that does not matter.

Look at minterms m14 (1110) and m15 (1111)
These are re-written as m(14 15) 111-

So you add these into that first table now, just a column along.
Mark any min term that cannot be combined, in this first case all minterms can be reduced.

OK, so now we have a table that has our first reduced minterms
It looks like we've got more work to do, yes it does look more complex than when we started, but honestly this is reducing the table!!

Now we need to combine our combined minterms.

To combine the minterms first we looked at where the states were just one bit out like m6[0110] and m14[1110]. became m(6, 14) [-110]
also m15[1111] and m7[0111] became m(7,15) [-111]

now we need to look at the conbined minterms where the dashes are in the same place and that only differ by one bit.

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

m(6, 7, 14, 15) [-11-]

We can conbine -010 and -110 or -011 or -000, as the dash is in the same place and they only differ by one bit
we can't combine -010 with -111 or -001 or -100 as there are two bits different, and we certainly can't combine -010 with -101 as that's three bit different.

We can't combine -010 with 001- as teh dash is in the wrong place for conbination

To start with just read down the chart and fill in ALL possibilities, we'll remove the repeated values later.

Now we can delete duplicates.

So the table has gotten a little smaller, and we can also see that m(5,7) is reduced as it's going to get. so we but an X next to this.

Now we start looking at the table to see where two dashes match but terms differ by only one value.

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

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

In other words all of these terms can be reduced to the expression C

When you've finished matching the pairs your table should look like this:

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

I highlighted the none combinable terms, and you can see that since we only have one term left there are no more combinations that can be made.


These minterms represent our prime implicants.
So now we draw a table listing the reduced/combined minterms from the table above.
The states, and their representations
This is called a prime implicant chart.

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

This example doesn't lead well to what needs to happen next so for a moment pretend that the chart looks like this:

Now we can see that there is minterm2 that is common to two different outputs,
the 8 in the second statement can also be covered by one of the other statements, and the 10 can be covered too.

(so the statement relating to m(2,8,10) [-0-0]{/b./d} could be ignored as it would be covered in other statements.)

In this case where we have a statement that cannot be covered then it's an essential prime implicant, statements where the output states are covered by other statements are non-essential and can be left out.

Back in the real world we do have a minterm 0 on that second statement.

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

m(5,7) = (/A . B .D) (the dash in C means C or NOT C, and as we know, A . B + A . /B = A

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: