That feed back was to point out a mistake, I'd like to thank Dr.K.Veerabhadra Rao, for pointing out my mistake.
I'll leave the original post untouched, save to provide a link to this post to show how it should have been done.
http://ah-screwit.blogspot.co.uk/2012/10/electronics-lessons-quine-mccluskey.html
You could argue that I should edit the original to save someone getting the wrong idea, but then, surely anyone learning should read the whole thing. I want to stand by my mistakes, it's my mistakes that have gotten me when I am today!!
So here goes! So I've looked at boolean algebra, and karnaugh maps.
(I've highlight in red where this post where the original! went wrong!!)
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.
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.
so:
m(6, 14) [-110]
m(7,15) [-111]
becomes
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:
In this original example I forgot to highlight one of the terms that I was going to reduce.
This is what that chart should have looked like!
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.
m(5,7)
m(8,9,10,11)
m(8,10,12,14)
m(0,2,8,10)
m(2,3,6,7,10,11,14,15)
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.
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,9,10,11) OR m(8,10,12,14) OR 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
m(0,2,8,10) = (/B . /D)
m(8,9,10,11) = (A . /B)
m(8,10,12,14) = (A . /D)
m(2,3,6,7,10,11,14,15) = (C)
So we can write out the expression for the gates as:
Q1 = /A . B . D + /B . /D +A . /B + A . /D + C
