Quine-McCluskey
Notes
- This is Carpanelli, chapter 2
- This algorithm works for more inputs, and is the basis for programs that optimise truth tables.
- The basic idea came from Hugh McColl in 1878!
- Origianl Algorithm Quine, 1952
- Revision McCluskey, 1956.
- For the or-of-ands version
- Build a table of the minterms
- Order and group by the number of ones
- These are called implicants
- Generate combination terms
- This can take multiple steps
- It continues until no combinations are left
- These are called prime implicants.
- Select the remaining terms that are needed.
- Build a table of the minterms
- A two input example
- Truth table
-
a b f 0 0 1 0 1 0 1 0 1 1 1 1 - f = Σ(0,2,3)
-
- Build the list of implicants
-
00 ---- 10 ---- 11
- Note that these are sorted by number of bits.
- The lines represent different groups.
-
- Generate combination terms.
- This is done by groups.
-
While there are "Uncircled" entries in the list From the first group to the last group For each entry in the current group Check against each entry in the next group if they differ by one bit mark each pattern as used generate a new pattern, put an x in the location where the bit differs If an entry in this group is not used, circle it
- So let's try
-
00 ---- 10 ---- 11 First group 00 or patterns with no bits. 00 and 10 differ in the first bit check each Generate a new term x0 00 ✓ ---- 10 ✓ x0 ---- 11 Next group 10 10 and 11 differ by the last bit check each (no need to check 10) Generate a new term 1x 00 ✓ ---- 10 ✓ x0 ---- 11 ✓ 1x
-
- We have a new list (x0 and 1x) and nothing is circled, so we need to perform another round
-
x0 ---- 1x In the comparisons x will not match 0 or 1, but only x x0 and 1x don't have any single bit flipped x1 is not a flip 1x is not a flip So we can't combine terms Nothing is checked, so "circle" both - Everything is circled, so we have the "prime" implicants.
- In some cases, not all prime implicants are needed
- We want to make sure that all of the minterms are covered
- so form a table
- Columns are the minterms
- Rows are the prime implicants
- Entry is if the bit pattern is covered.
-
Prime Implicant\Minterm 00 10 11 x0 ✓ ✓ 1x ✓ ✓ - Both prime implicants are needed in this case to "cover" the minterms
- x0 corresponds to b
- 1x corresponds to a
- f = a + b
-
a b f b a + b 0 0 1 1 1 0 1 0 0 0 1 0 1 1 1 1 1 1 0 1
- Truth table