Electrical Engineering › Section S · Logic gates and Boolean algebra › Topic S.5
Karnaugh maps, Quine-McCluskey, and VHDL
Algebraic simplification depends on spotting the right steps; a Karnaugh map makes them visible, so the simplest sum-of-products or product-of-sums form can be read off a grid. This topic covers maps of up to four variables, don't-care conditions, the Quine-McCluskey method that computers use instead, and how a simplified expression is written in VHDL.
A map that shows adjacency
Simplification works by finding terms that differ in one variable, since \(X\overline{D} + XD = X\). A Karnaugh map, introduced by Maurice Karnaugh in 1953, is a truth table rearranged as a grid with one cell per minterm, ordered so that neighbouring cells differ in exactly one variable. Rows and columns therefore run in Gray-code order, 00, 01, 11, 10, not in counting order. Adjacency also wraps round: the top row is adjacent to the bottom row and the left column to the right. Cells touching only at a corner are not adjacent.
Three- and four-variable maps
A 3-variable map has 8 cells, two rows for A and four columns for BC. A 4-variable map has 16, with rows for AB and columns for CD, holding these minterm numbers:
To map a standard SOP, put a 1 in each minterm's cell and 0s elsewhere. A non-standard product term fills a whole block: \(B\overline{C}\) fills every cell with B = 1 and C = 0, that is cells 4, 5, 12 and 13.
Grouping rules
To minimise an SOP, loop the 1s into groups. 1. Each group is a rectangle of 1, 2, 4, 8 or 16 adjacent cells, wrap-around included. 2. Make every group as large as possible. 3. Use as few groups as possible, while covering every 1 at least once; groups may overlap. 4. Start with 1s that can join only one possible group. Each group gives one product term: keep the variables that have the same value throughout the group and drop those that change. A group of \(2^k\) cells in an n-variable map leaves a term of \(n - k\) literals, so bigger groups give shorter terms.
Worked example: corners and centre
Minimise the function
1. Map the 1s:
2. The four corners, cells 0, 2, 8 and 10, form one group by wrap-around; there B = 0 and D = 0 throughout, giving \(\overline{B}\,\overline{D}\). 3. The centre block, cells 5, 7, 13 and 15, has B = 1 and D = 1: BD. 4. So \(F = \overline{B}\,\overline{D} + BD\), 4 literals instead of 32. Check: F is 1 exactly when B equals D, an XNOR of B and D.
Don't-care conditions
Some input combinations can never occur. A 4-bit BCD input, for example, never takes the values 1010 to 1111. The output for such inputs does not matter, so these cells are marked X, don't care. When grouping, treat each X as a 1 if it makes a group larger, and as a 0 otherwise; never form a group of Xs alone. Don't cares often shorten the result dramatically.
Worked example: a BCD digit of 5 or more
A circuit takes a BCD digit ABCD and outputs F = 1 when the digit is 5 or more. 1. The 1s are minterms 5, 6, 7, 8 and 9; minterms 10 to 15 are don't cares. 2. Rows AB = 11 and 10, using the Xs, form a group of eight with A = 1 throughout: A. 3. Cells 5, 7, 13 and 15 form a group with B = 1, D = 1: BD. 4. Cells 6, 7, 14 and 15 give BC. 5. So \(F = A + BC + BD\). Check: without the don't cares the best result is \(\overline{A}BD + \overline{A}BC + A\overline{B}\,\overline{C}\), 9 literals against 5.
Minimising in POS form
For a product-of-sums result, group the 0s instead, with the same rules. Each group of 0s gives a sum term, using the maxterm rule: a variable that is 0 throughout the group appears plain and one that is 1 appears complemented. In the corners-and-centre map, the 0s form two groups: cells 1, 3, 9, 11 with B = 0, D = 1, and cells 4, 6, 12, 14 with B = 1, D = 0. These give \(F = (B + \overline{D})(\overline{B} + D)\). Equivalently, the 0s give \(\overline{F} = \overline{B}D + B\overline{D}\), and DeMorgan gives the same POS.
Beyond four variables: Quine-McCluskey
A 5-variable map is two 4-variable maps, one for E = 0 and one for E = 1, whose matching cells are adjacent; beyond that, maps become impractical. The Quine-McCluskey method, from Willard Quine and Edward McCluskey in the 1950s, does the job as a table that suits computers. 1. List the minterms grouped by their number of 1s. 2. Compare each term with those in the next group; if two differ in one bit, write the combined term with a dash there and tick both. 3. Repeat until nothing combines. Unticked terms are prime implicants. 4. A prime implicant chart then picks the essential ones and enough others to cover every minterm.
Worked example: Quine-McCluskey
Minimise \(F = \sum m(0, 1, 3, 7)\) in A, B, C. 1. Group by count of 1s: 000; 001; 011; 111. 2. Combine neighbours: 000 and 001 give 00–, 001 and 011 give 0–1, 011 and 111 give –11. 3. No pair combines again, since their dashes sit in different places, so the prime implicants are \(\overline{A}\,\overline{B}\), \(\overline{A}C\) and BC. 4. Minterm 0 is covered only by \(\overline{A}\,\overline{B}\) and minterm 7 only by BC, so both are essential, and together they also cover 1 and 3. So \(F = \overline{A}\,\overline{B} + BC\). For many variables, tools use heuristic minimisers such as Espresso.
Boolean expressions in VHDL
In VHDL an entity declares a design's ports and an architecture describes its behaviour. The BCD detector, \(F = A + BC + BD\), in VHDL-93:
VHDL gives and and or equal precedence and forbids mixing them unbracketed, so the brackets are required.
Common mistakes to avoid
First, labelling map rows or columns 00, 01, 10, 11 instead of 00, 01, 11, 10. Second, forgetting wrap-around, which hides groups such as the four corners. Third, making groups of 3 or 6 cells; sizes must be powers of 2. Fourth, using several small groups where one larger group fits. Fifth, grouping don't cares that cover no 1s. Sixth, in POS, using the SOP rule; for 0 groups a variable that is 0 appears plain.
Key takeaways
A Karnaugh map places minterms in Gray-code order, 00, 01, 11, 10, so adjacent cells, wrap-around included, differ in one variable. Loop 1s in the fewest, largest rectangles of 1, 2, 4, 8 or 16 cells; each group keeps only the variables that do not change. Don't cares, X, join groups only when they help. Grouping 0s gives the minimal POS. The Quine-McCluskey method combines minterms in a table to find prime implicants, then chooses essential ones; Espresso handles large problems. VHDL describes the result with an entity, an architecture and the operators and, or and not.
Flashcards
Flashcard
Truth table as a grid with adjacent cells differing in one variable
Test your understanding
Question 1 of 5
In a 4-variable Karnaugh map with rows AB and columns CD, which pair of cells is adjacent?
Question 2 of 5
A group of four 1s on a 4-variable map lies where A = 1 and C = 0, while B and D both change. What term does the group give?
Question 3 of 5
How should a don't-care cell (X) be treated when grouping 1s on a Karnaugh map?
Question 4 of 5
In Quine-McCluskey, which pair of terms can be combined in the next step?
Question 5 of 5
Why are the brackets needed in the VHDL line F <= A or (B and C) or (B and D);?
