Learn › Topic 5
The Quine-McCluskey method step by step
7 min read · bitGateLab Team
The Karnaugh map is fast for four variables, but it relies on your eye and stops being practical with five or more. The Quine-McCluskey method does the same job with tables and mechanical rules: it requires no intuition, it always finds all the prime implicants and it is the basis of the programs that simplify logic functions. Here you will understand its two stages, identify the essential prime implicants and work through a complete four-variable example.
Vocabulary: implicants and primes
- An implicant of F is a product term that, when it is 1, guarantees that F is 1. Every minterm of F is an implicant, and so is any valid group on a Karnaugh map.
- A prime implicant is an implicant that cannot be made any larger; if you remove a variable from it, it covers some row where F is 0. It is equivalent to a maximal group on the map.
- An essential prime implicant is a prime that covers at least one minterm that no other prime covers. It has to appear in every minimal solution.
The method has two stages: first it finds all the prime implicants by combining terms; then it chooses the smallest set of primes that covers all the minterms.
Stage 1: combining terms
Each term is written in binary, and the position of an eliminated variable is marked with a dash. For example, with variables A, B, C, D, the term 0-11 means ACD (B was eliminated).
- Group the minterms by the number of ones in their binary code.
- Compare every term in one group with every term in the next group. If they differ in a single bit, combine them by putting a dash in that position, and mark both originals as used.
- Repeat with the new list. Only terms that have their dashes in the same positions can be combined.
- When nothing more can be combined, the terms that were never marked are the prime implicants.
Stage 2: the prime implicant chart
Build a table with one row for each prime implicant and one column for each minterm of the function (don't-care conditions get no column). Mark which minterms each prime covers. Then:
- Look for columns with a single mark. The prime in that row is essential: select it and cross out every column it covers.
- For the columns that remain, choose the smallest number of primes that covers them. If two primes cover the same columns, either one will do; prefer the one with fewer literals.
Complete example. Simplify F(A, B, C, D) = Σm(0, 2, 3, 5, 7, 8, 10, 11, 13, 15).
Step 1. Group by number of ones.
| Ones | Minterms |
|---|---|
| 0 | 0 (0000) |
| 1 | 2 (0010), 8 (1000) |
| 2 | 3 (0011), 5 (0101), 10 (1010) |
| 3 | 7 (0111), 11 (1011), 13 (1101) |
| 4 | 15 (1111) |
Step 2. First combination (pairs). Neighboring groups are compared. The 8 does not combine with the 3 or with the 5 because they differ in more than one bit.
| Groups | Pairs formed |
|---|---|
| 0 and 1 | (0,2) 00-0; (0,8) -000 |
| 1 and 2 | (2,3) 001-; (2,10) -010; (8,10) 10-0 |
| 2 and 3 | (3,7) 0-11; (3,11) -011; (5,7) 01-1; (5,13) -101; (10,11) 101- |
| 3 and 4 | (7,15) -111; (11,15) 1-11; (13,15) 11-1 |
All ten minterms have been marked as used; there are 13 pairs.
Step 3. Second combination (quads). Pairs with the dash in the same position that differ in one bit are combined:
- (0,2) with (8,10), or else (0,8) with (2,10): -0-0, covers 0, 2, 8, 10.
- (2,3) with (10,11), or (2,10) with (3,11): -01-, covers 2, 3, 10, 11.
- (3,7) with (11,15), or (3,11) with (7,15): --11, covers 3, 7, 11, 15.
- (5,7) with (13,15), or (5,13) with (7,15): -1-1, covers 5, 7, 13, 15.
All 13 pairs were used in some quad. The four quads cannot be combined with one another (no two of them have their dashes in the same positions and differ in a single bit). Therefore, the prime implicants are:
- P1 = -0-0 = BD
- P2 = -01- = BC
- P3 = --11 = CD
- P4 = -1-1 = BD
Step 4. Prime implicant chart.
| Prime | 0 | 2 | 3 | 5 | 7 | 8 | 10 | 11 | 13 | 15 |
|---|---|---|---|---|---|---|---|---|---|---|
| P1 BD | ✔ | ✔ | ✔ | ✔ | ||||||
| P2 BC | ✔ | ✔ | ✔ | ✔ | ||||||
| P3 CD | ✔ | ✔ | ✔ | ✔ | ||||||
| P4 BD | ✔ | ✔ | ✔ | ✔ |
Step 5. Essentials. Columns 0 and 8 have a mark only in P1, so P1 is essential. Columns 5 and 13 have a mark only in P4, so P4 is essential too. Together they cover 0, 2, 5, 7, 8, 10, 13 and 15.
Step 6. Cover the rest. Minterms 3 and 11 are still missing. P2 covers both, and so does P3. Either one completes the solution with the same number of literals.
Result: F = BD + BD + BC, or else F = BD + BD + CD. Both have three terms and six literals.
If you draw this function on a Karnaugh map, P1 is the four corners, P4 is the center block, P2 is columns 11 and 10 of rows 00 and 10 (joined across the edge) and P3 is the whole 11 column. The tabular method reaches the same result without any need to look at the map.
Don't-care conditions and cyclic charts
X conditions are included in stage 1 as if they were ones, because they can help form larger implicants. In stage 2 they are left out: they get no column, since covering them is not required. A prime made up only of X's is never needed.
Sometimes, after choosing the essentials, or right from the start, every column has at least two marks and there is no obvious way to decide. That situation is called a cyclic chart. It is solved by trial: you pick a prime, remove what it covers and repeat, comparing the solutions that come out. For large charts there is an algebraic procedure (Petrick's method) that enumerates all the possible covers.
Common mistakes
- Combining terms with dashes in different positions, such as 0-01 with 00-1. It is not valid even though they seem to differ in one bit.
- Forgetting to mark both terms of each combination as used, and then listing as prime something that is not.
- Adding columns for the X conditions to the prime implicant chart, which forces you to cover them needlessly.
- Choosing non-essential primes before the essential ones. Secure the essentials first; then decide the rest.
- Writing the term wrongly from its code: in -0-1, B is complemented (it is 0), D is uncomplemented (it is 1), and A and C disappear.
Try it in the simulator
The simulator simplifies functions with this kind of procedure, so you can use it to check each stage of your work by hand.
- Create a four-variable truth table and set the minterms from the example to 1.
- Do stages 1 and 2 on paper and write down your result.
- Look at the minimal expression the tool gives and at its Karnaugh map; identify which group corresponds to each prime implicant.
- Convert the two possible solutions to circuits on the same canvas and toggle the inputs to confirm that they always give the same output.
Exercises
- Find the prime implicants and the minimal expression of F(A, B, C, D) = Σm(0, 1, 3, 7, 8, 9, 11, 15).
Answer
Primes: -00- (BC), -0-1 (BD) and --11 (CD). Column 0 is covered only by BC, and column 7 only by CD: both are essential and together they cover everything. F = BC + CD. The prime BD is redundant.
- Solve F(A, B, C) = Σm(0, 1, 2, 5, 6, 7). Are there any essential primes?
Answer
The pairs are 00-, 0-0, -01, -10, 1-1 and 11-, and none of them combine into a quad: there are six primes. Each minterm is covered by exactly two of them, so there are no essentials (cyclic chart). Two minimal solutions: AB + BC + AC, or AC + BC + AB.
- Simplify F(A, B, C, D) = Σm(2, 3, 7, 9, 11, 13) + d(1, 10, 15).
Answer
Including the X's in stage 1 yields four primes: -0-1 (BD), -01- (BC), --11 (CD) and 1--1 (AD). In the chart, with no columns for 1, 10 and 15: minterm 2 is covered only by BC, minterm 7 only by CD and minterm 13 only by AD. All three are essential and they also cover 3, 9 and 11. F = BC + CD + AD.
- Why is the group with a single one not compared against the group with three ones in stage 1?
Answer
Because two codes with one and three ones differ in at least two bits, and to be combined they must differ in exactly one.