How a computer minimises
The Quine-McCluskey method: the map's merging rule as a procedure that works for any number of inputs.
Where the map runs out
A Karnaugh map works because you can see which cells are neighbours. With five inputs you need two 4 by 4 maps stacked, with cells in the same place on both counting as neighbours, and with six you need four. Past that, nobody can see the loops, and a map of twenty inputs is out of the question. Real circuits routinely have that many. So the minimising has to be done by a program, and a program cannot "spot" anything. It needs a procedure: a fixed list of steps that reaches the answer without judgement. The Quine-McCluskey method, worked out by Willard Quine in 1952 and refined by Edward McCluskey in 1956, is exactly that, and it is the method the tools on this site run.
The same idea, as a list of steps
The method uses the one rule you already have: two terms that differ in exactly one input merge into one term without that input. Instead of looking for neighbours on a picture, it writes every minterm as a binary code and compares codes. It has three steps.
Step 1: group by the number of 1s. Write each minterm of the function in binary and sort the codes into groups by how many 1s they contain. Two codes that differ in exactly one bit must have counts of 1s that differ by exactly one, so a code only ever needs comparing with the group next to its own, which is what keeps the work down.
Step 2: merge. Compare every code in a group with every code in the group below. Whenever two differ in a single bit, write a new term with a dash in that position, meaning "this input has dropped out", and put a tick against both originals to record that they have been absorbed into something bigger. When every pair has been tried, do the same again with the new dashed terms, merging only terms whose dashes are in the same place, and keep going until a pass produces nothing. Any term that never got a tick could not be merged with anything, so it is a prime implicant: a loop that cannot be made bigger, just as on the map.
Step 3: choose. Draw a chart with one row per prime implicant and one column per minterm, and put a mark wherever the row's term covers the column's minterm. A column with a single mark can only be covered by that one row, so that row is essential and goes straight into the answer. Cross off every column it covers. If columns are left, pick the fewest remaining rows that cover them. The answer is the OR of the chosen terms.
Worked example. Minimise f(a, b, c) = Σm(1, 3, 5, 6, 7) with the Quine-McCluskey method.
Step 1, group. In binary, sorted by their number of 1s: 1 one: 001 (m1, ticked); 2 ones: 011 (m3, ticked), 101 (m5, ticked), 110 (m6, ticked); 3 ones: 111 (m7, ticked).
Step 2, pass 1. Compare neighbouring groups and merge every pair that differs in one bit, writing a dash where the bit was: 1 one: 0–1 (m1, m3, ticked), –01 (m1, m5, ticked); 2 ones: –11 (m3, m7, ticked), 1–1 (m5, m7, ticked), 11– (m6, m7, prime).
Step 2, pass 2. Merge the dashed terms whose dashes are in the same place and which differ in one bit: 1 one: ––1 (m1, m3, m5, m7, prime).
Step 3, choose. The unticked terms are the prime implicants: 11–, which reads as a·b and covers m6, m7; ––1, which reads as c and covers m1, m3, m5, m7. On the chart, c is the only prime covering m1, m3, m5, and a·b is the only prime covering m6, so both are essential. Between them they cover every column, so nothing is left to choose. The answer is f = c + a·b, and a map would have given the same two loops.
Common mistake: merging terms whose dashes do not line up
In the second and later passes, two terms may only merge if their dashes are in the same positions and the rest differs in one bit. 0–1 and 01– look close but cannot merge: together they cover m1, m3, m2 and m3, which is three cells, and three is never a loop. The same goes for codes that differ in two bits, however alike they look. Count the differing positions every time.
Watch it run
The function below has four inputs and eight minterms, and its chart needs a real choice at the end: two prime implicants are essential, and each of the two minterms they leave uncovered can be picked up by more than one of the rest, so the last step is to find the single prime that covers both. Click through one pass at a time and check a merge or two by hand.
Why?: why do real tools not use this either?
Quine-McCluskey always finds a minimal answer, but the number of prime implicants can grow very fast with the number of inputs, and choosing the best cover from a huge chart is one of the problems computers are known to be slow at. For the sizes you would ever do by hand it is instant. For a chip with hundreds of inputs, design tools use methods that settle for a very good answer rather than a provably smallest one. The idea underneath is still the same merging of neighbours.
What to remember
- Karnaugh maps stop being readable at five or six inputs, so bigger functions need a procedure.
- Quine-McCluskey is the map's merging rule done on binary codes: group by 1s, merge pairs differing in one bit.
- A merged term gets a dash where the input dropped out; a term that never merges is a prime implicant.
- The prime implicant chart picks the cover: essential rows first, then the fewest others that finish the job.
- It gives the same answer as a map, works for any number of inputs, and suits a computer.
Check yourself
Get 5 right in a row and the lesson is done. A wrong answer costs the run, not the lesson.
m0 (0000) and m4 (0100) differ in one bit, so they merge. Which term do they make?
0000 and 0100
Already know this? and come back to the quiz any time.