Hello again! Yeah, I think atleast 2 posts will be standard for some time now :P Cause, I have a lot to post! So, this time we will talk about another Simplification Method. We already did Karnaugh Maps and the knowledge from them could come handy, so check it out here again, if you haven't already! This time we will talk about the Quine McCluskey Method or Tabular Method of Function Simplification! I will start off with some Theory behind it and then we will get into an full on example. So, let's get started then!
Another representation for Functions:
Another way of representing a Function is using the Minterms. We will use it more often from now on, cause it's much easier to write down giant function like that.
So, the new way I show you now is writing the function like that:
F(A, B, C) = Σ(0, 4, 7) or Σ(000, 100, 111)
where 0, 4, 7 or 000, 100, 111 are the Minterms of our function (the Input Combinations for which the Logical Circuit/Function gives an Output of 1).
This representation helps us start the Karnaugh or Tabular Method much faster!
(Essential) Prime Implicants:
In the Tabular Method we talk about Prime Implicants that are actually Groups of Minterms! So, this method will try to match Minterms and already Grouped Minterms together to form those Groups of Minterms called Prime Implicants and when we can't group those anymore we will again check if some of those are not needed until only the Essential Prime Implicants remain. Essential Prime Implicants are those that must be included in our Logical Expression!
Grouping of Minterms:
Do you remember the Boolean Algebra Simplification Rules? Think about ABCD + ABCD'. What happens here? Well D gets cut out and we end up with ABC. Let's check that out again but write down the minterms using binary digits. ABCD + ABCD' = ABC becomes 1111 + 1110 = 111. Hmm, you can see that only the value that changes gets left out. The same happened in Karnaugh Map where I said we keep only those whose value stays the same in the whole Group. Well, what a coincidence the same will happen in the Tabular Method too! Why? Because that exactly is what creates a Minterm Group!
So, think of the Tabular Method of an continuously combining operation where we check if between 2 Minterms only one Variable changes so that we can change them into 1 new group.
Can we group ABC'D + ABCD' into one new Group? The answer is no, cause 2 Variables change in the Group. If we write down the expression in binary form 1101 + 1110 we see that 2 Values change. It's even easier to check those things if we put them vertically.
1101
1110
11!!, where the !! represent value change in the group.
That here is the right and the most essential way of grouping minterms, but this way would take so much time if we have like 7 Variables and 25 Minterms. So what now? Is that it? Will we really need like an hour for grouping? Nope, I have another even better way that made me need less then half the time in the Simplification process then most other Students! So, let's get into that way now.
Fast Grouping:
Let's now do things in my way. To explain it better let's return to the previous example.
ABCD + ABCD' = ABC or 1111 + 1110 = 111!
OK, let's see how much this too Minterms differentiate. The answer is easy and it's 1. Let's also see what the Values are of those Minterms. Well, the first one is 15 and the second one is 14 and so they again differentiate by 1. But, well using that example you can't see directly what the trick is!
So, let's do it again, having the change be some digits higher.
ABCD + AB'CD = ACD or 1111 + 1011 = 1!11
Again let's get the Minterm values and find the difference between them. So, the first one is 15 and the second one is 11. So, that means they differ by 4.
If we continue on with this process we will see that the differences will be a power of 2. In the first example that power was 2^0 = 1 and in the second one 2^2 = 4. And that also makes sense if we think again about Numeral Systems.
We said that each number can be represented as: x*2^n + ... + x * 2^1 + x * 2^0 etc.
And that exactly can give us our Solution.
So, what will we do? Well, it's easy. When checking if two Minterms can be put together we will check if the Minterms differentiate by a power of 2 (1, 2, 4, 8, 16 etc.). When checking if two already grouped Minterms and so a Minterm Group can be put together with another one we will check if each of the Minterms inside of one of the groups differentiates by the same power of 2 with one of the other Group. When the Minterms don't differentiate by a power of 2 we simply don't group them and go to the next one!
But, that's not all. Take for example 15 and 17. They differentiate by 2, but that's not enough, cause we can't group those! 15 is 01111 and 17 is 10001 and they don't differentiate by 1 Variable. So, did our trick fail? Nope, it works, but we have to put our Minterms in specific Classes called Indexes, that we will talk in a sec, when we get into the Tabular Method. So, they don't only have to differentiate by a power of 2, but we also group only those that are in sequential Indexes! Another important thing is that Groups contain only power of 2 members(1, 2, 4, 8 etc.). So, we can't have a group of 3, 7 etc.
Finally, we ended up with my fast way. To recap it really quick. We group Minterms in sequential Indexes and to group 2 Minterms they must differentiate by a power of 2. If we want to group Minterm Groups, they again have to be in sequential Indexes, but this time each Minterm must differentiate by the same power of 2 with some of those in the other Group! Lastly, a Group must contain power of 2 members.
Let's now get into the Tabular Method!
Tabular Method:
The Tabular Method has specific Steps that we must follow. I will get in depth in all of them and we will do a example at the same time!
The Steps are:
- From an Minterm Function Representation (with the new way I showed you today or the previous sum of minterms) we take our Minterms and write them with Binary Digits.
- We group them in Indexes separating them by the number of 1's they have in their Binary Representation
- We write down a List of the Minterms separating them in Indexes
- Then we start grouping Minterms from Sequential Indexes (0 with 1, 1 with 2 etc.) and the Minterm Groups will be written on a second List.
- We continue the process grouping the Minterm Groups from our second List and writing them down on an third List etc.
- When we can't group anymore we have finished the first part of the Method and end up with the Prime Implicants that cannot be grouped. It's good to put a mark on those that were grouped, so that you can see at the end which ones where not grouped.
- Lastly, we will reduce the Prime Implicants into Essential Prime Implicants, by creating a chart of Minterms and Prime Implicants
So, let's now get into all those Steps one by one on the logical function:
F(A, B, C, D) = Σ(0, 1, 2, 3, 5, 7, 8, 10, 12, 13, 15)
Group Minterms into Indexes:
We first have to write the Minterms in Binary Representation.
0 -> 0000, 1 -> 0001, 2 -> 0010, 3 -> 0011, 5 -> 0101, 7 -> 0111
8 -> 1000, 10 -> 1010, 12 -> 1100, 13 -> 1101, 15 -> 1111
Group in Indexes, depending on the number of 1's.
Index 0: 0
Index 1: 1, 2, 8
Index 2: 3, 5, 10, 12
Index 3: 7, 13
Index 4: 15
Grouping:
To start grouping we have to write the Minterms, separated in Indexes, into a List. List 1 will contain only Minterms. And the List afterwards will have Groups of 2, 4, 8 Minterms and so on.
List 1
0----- (Index Separator)128----351012----713----15As we said before we now group Minterms in sequential Indexes. To make it easier we will use the easy power of 2 way.
For example let's group Index 0 and 1.
List 1 List 2
0 Y (0, 1) // 0 and 1 differentiate by 1 (power of 2)---- (0, 2) // 0 and 2 by 2 (power of 2)1 Y (0, 8) // 0 and 8 by 8 (power of 2 again)2 Y -------8 YI also put Y's that represent that we used the Minterms in grouping.
Let's Group all of List 1 and create List 2!
List 1 List 2
0 Y (0, 1) // 0 and 1 differentiate by 1 (power of 2)---- (0, 2) // 0 and 2 by 2 (power of 2)1 Y (0, 8) // 0 and 8 by 8 (power of 2 again)2 Y -------8 Y (1, 3) // 1 and 2 differ by 2---- (1, 5) // 1 and 5 by 43 Y (2, 3) // 2 and 3 by 15 Y (2, 10) // 2 and 10 by 810 Y (8, 10) // 8 and 10 by 212 Y (8, 12) // 8 and 12 by 4---- -------7 Y (3, 7) // 3 and 7 by 413 Y (5, 7) // 5 and 7 by 2---- (5, 13) // 5 and 13 by 815 Y (12, 13) // 12 and 13 by 1 ------- (7, 15) // 7 and 15 by 8 (13, 15) // 13 and 15 by 2As you an see we grouped only those with power of 2 difference! So, let's do the same now for those to create List 3 that will contain Minterm Groups of 4 Members.
List 1 List 2 List 3
0 Y (0, 1) Y (0, 1, 2, 3) // (0,1)+(2,3) or (0,2)+(1,3) differ by 2 or 1---- (0, 2) Y (0, 2, 8, 10) // (0,2)+(8,10) or (0,8)+(2,10) differ by 8 or 21 Y (0, 8) Y ------------2 Y ------- (1, 3, 5, 7) // (1,3)+(5,7) or (1,5)+(3,7) differ by 4 or 28 Y (1, 3) Y ----------------- (1, 5) Y (5, 7, 13, 15) // (5,7)+(13,15) or (5,13)+(7,15) differ by 8 or 23 Y (2, 3) Y5 Y (2, 10) Y10 Y (8, 10) Y12 Y (8, 12) ---- -------7 Y (3, 7) Y13 Y (5, 7) Y---- (5, 13) Y15 Y (12, 13) ------- (7, 15) Y (13, 15) YYou can see that sometimes the groups may be the same, when we get into higher Lists. You can also see that we grouped most of them, but 2 members of List 2 didn't group to List 3. So, (8, 12) and (12, 13) are Prime Implicants for sure. We also can't group List 3 into List 4, to create groups of 8. So, all the members of List 3 are also Prime Implicants.
Find Essential Prime Implicants:
Our Prime Implicants are the following if you check the Binary Representations:
(8, 12) that is 1!00 or AC'D'
(12, 13) that is 110! or ABC'
(0, 1, 2, 3) that is 00!! or A'B'
(0, 2, 8, 10) that is !0!0 or B'D'
(1, 3, 5, 7) that is 0!!1 or A'D
(5, 7, 13, 15) thas is !1!1 or BD
So, our function using Prime Implicants looks like this:
F(A, B, C, D) = AC'D' + ABC' + A'B' + B'D' + A'D + BD
We will now create a chart of Minterms and Prime Implicants to find the Essential Prime Implicants! We will put X's when the Prime Implicant contains the specific Minterm.
0 1 2 3 5 7 8 10 12 13 15
AC'D' X X
ABC' X X
A'B' X X X X
B'D' X X X X
A'D X X X X
BD X X X X
Now, we search for Minterms that are present in only one Prime Implicant. We do this by looking in each Column and checking if there is only one X present.
0 1 2 3 5 7 8 10 12 13 15
AC'D' X X
ABC' X X
A'B' X X X X
B'D' X X X X
A'D X X X X
BD X X X X
EPI X X X X X X X X
We can see that B'D' and BD contain X's that aren't present in any other Prime Implicant. That means that those are Essential Prime Implicants. So, all the Minterms of those 2 Essential Prime Implicants get put into a new Helping Implicant that I noted as EPI.
Now, we only have to include enough other Prime Implicants, so that EPI contains all Minterms. It's not a problem if two Prime Implicants have the same Minterms sometimes! We also can have now many possible solutions and all of them will by right, if EPI contains all Minterms of our Function!
We can include A'B' or A'D to fill the slots of Minterm 1 and 3. 12 is also present in 2 different Prime Implicants that are AC'D' and ABC'. We are able of having all 4 possible combinations in our final function.
So, our final function can be either one of those:
F(A, B, C, D) = B'D' + BD + A'B' + AC'D'
F(A, B, C, D) = B'D' + BD + A'B' + ABC'
F(A, B, C, D) = B'D' + BD + A'D + AC'D'
F(A, B, C, D) = B'D' + BD + A'D + ABC'
If you remember from a older post, B'D' + BD are equal to an XNOR Gate. So, we can make our Final Function contain only 3 Elements inside of the sum!
Also, hopefully you remember what I told you in Karnaugh Map about the Grouping and that we end up with the same Truth Table. There we did 2 different groupings of the same Karnaugh Map and ended up with other Functions that looked similar tho. The same happened here now. But, using the Tabular Method we found all possible simple solutions for our Function!
This is actually it! Hope you enjoyed it and learned something new!
Next time in Theory I will talk about Binary Decision Diagrams (BDD's).
Until next time...Bye!