Karnaugh Maps for Two to Four Variables
Draw a Karnaugh map for up to four variables, group its 1s, and read the smallest sum of products from the groups.
You Will Be Able To
- Fill a map whose rows and columns are in Gray order.
- Draw groups of 1, 2, 4 or 8 cells, with wrap-around.
- Read each group as one product term.
- Tell a prime implicant from an essential one.
- Lesson
- G3.1
- Time
- 30 min
- Runs on
- Your browser
- Check
- 5 questions
A vending machine lights a lamp from four sensor bits. The first design used one AND gate for each row of the truth table that holds a 1. It worked, and it used eight wide gates where three small ones are enough.
| Design | Product terms | Literals |
|---|---|---|
| One term for each 1 of the table | 8 | 32 |
| Read from the Karnaugh map | 3 | 7 |
Computed for f = Σm(0, 2, 4, 5, 6, 8, 10, 13). A literal is one variable in one term: one input of that term's AND gate.
A Truth Table Folded so That Neighbours Differ in One Bit
A Karnaugh map (K-map) is a truth table drawn as a grid. Each cell is one row of the table. The cell holds the output for that row.
The labels are in Gray order: 00, 01, 11, 10. Each label differs from the next in one bit. So two cells that touch differ in one variable.
That is the whole trick. Two terms that differ in one variable merge: a'bc + abc = bc. On the map, such terms are neighbours.
Groups of 1, 2, 4 and 8, with Wrap-Around
A group is a rectangle of 1s whose size is a power of two. Each time a group doubles, one more variable leaves the term.
Rectangles only
A group is 1, 2, 4 or 8 cells in a rectangle. A diagonal or an L shape is two groups.
As large as possible
A larger group is a shorter term. Grow each group until it would take in a 0.
Edges wrap
The map is a tube in both directions. The first and last row are neighbours, and so are the first and last column.
Overlap is free
A cell may sit in several groups. Reusing a 1 never changes the function.
Reading a Group as a Term
Look at each variable inside the group. If it changes, leave it out. If it stays 1, write it. If it stays 0, write its complement.
Group (rows abcd) | a | b | c | d | Term |
|---|---|---|---|---|---|
| 0000, 0010, 1000, 1010 | changes | stays 0 | changes | stays 0 | b'd' |
| 0000, 0010, 0100, 0110 | stays 0 | changes | changes | stays 0 | a'd' |
| 0101, 1101 | changes | stays 1 | stays 0 | stays 1 | bc'd |
The three groups of the lamp function. Together: f = b'd' + a'd' + bc'd, which is 3 terms and 7 literals.
A group of two cells drops one variable. A group of four drops two. A group of eight drops three.
Implicants, Prime Implicants and Essential Primes
An implicant is any group that holds only 1s. A prime implicant is a group that cannot grow any more. An essential prime implicant is a prime that covers some 1 which no other prime covers.
| Prime implicant | Cells | Essential? |
|---|---|---|
b'd' | 0, 2, 8, 10 | yes |
bc'd | 5, 13 | yes |
a'd' | 0, 2, 4, 6 | yes |
a'bc' | 4, 5 | no: every cell is covered by another prime |
Computed by the minimizer for the lamp function.
- Neutral
- Structure
- Fill and group
Copy each row of the table into its cell. Then find every group that cannot grow.
- Take what you must
Find each 1 that only one prime covers. That prime is essential, so take it.
- Cover the rest and read
If some 1s remain, add the fewest primes that cover them. Then read one term per group.
Read the diagram as text
- Truth table: one row per input
- K-map: rows in Gray order
- Prime implicants: largest groups
- Essential primes: the only cover of a 1
- Remaining 1s: fewest extra groups
- Sum of products: one AND per group
- Truth table → K-map: fill
- K-map → Prime implicants: group
- Prime implicants → Essential primes: must have
- Essential primes → Remaining 1s: then cover
- Remaining 1s → Sum of products: read terms
For the lamp function, nothing remains after the essential primes.
Solve One Yourself
Group the 1s of the map below. Select two corners of a rectangle to draw a group. The status line counts your terms and literals.
Asked in interviews
Why does a K-map use Gray order?
Two product terms merge when they differ in one variable. Gray order puts every such pair in cells that touch, so a merge shows as a rectangle.
What is an essential prime implicant?
A prime implicant is a group that cannot grow. It is essential when it covers a 1 that no other prime covers. Every minimum cover holds all essential primes.
Is the minimum cover always unique?
No. After the essential primes, several choices may cover the remaining 1s at the same cost. The lamp function has one minimum; lesson G3.6 shows a function with two.
Try It
The table is the answer format of this module. Each term is a group of four bits in the order a b c d. CARE marks the variables the term uses. VALUE gives the value each must have.
The table starts with one term for each 1 of the lamp map. The bench finds no wrong row, and reports 8 terms and 32 literals.
Replace it with the three groups: set N = 3, CARE = {4'b0111, 4'b1001, 4'b0101} and VALUE = {4'b0101, 4'b0000, 4'b0000}. The bench then prints minimum is 3 terms, 7 literals: reached.
Now grow the pair to four cells: change its CARE to 4'b0101. The bench prints first wrong row: abcd = 0111 (f is 0, the table gives 1). The group took in a 0.
0 of 16 rows wrong 8 terms, 32 literals minimum is 3 terms, 7 literals: not reachedRead included file: tb.sv
// tb.sv: the bench (read-only). It builds the sum of products from the table in module answer,
// compares it with f on every row that is not a don't-care, and counts terms and literals.
module tb;
// Bit m of F is f on row m, where m is the binary value of abcd. DC marks the don't-care rows.
localparam logic [15:0] F = 16'b0010010101110101;
localparam logic [15:0] DC = 16'b0000000000000000;
wire [7:0] n;
wire [31:0] care, value;
answer ans (.n(n), .care(care), .value(value));
// The sum of products on one row: 1 when some term of the table holds the row.
function automatic logic table_at(input logic [3:0] row);
logic hit;
hit = 1'b0;
for (int t = 0; t < 8; t++)
if (t < n && ((row ^ value[4*t +: 4]) & care[4*t +: 4]) == '0) hit = 1'b1;
return hit;
endfunction
initial begin
int wrong, lits;
logic [3:0] row, used;
#1; // let the table reach the wires
wrong = 0;
lits = 0;
for (int m = 0; m < 16; m++) begin
row = m[3:0];
if (!DC[m] && table_at(row) !== F[m]) begin
if (wrong == 0) $display("first wrong row: abcd = %b (f is %b, the table gives %b)", row, F[m], table_at(row));
wrong++;
end
end
for (int t = 0; t < 8; t++) if (t < n) begin
used = care[4*t +: 4]; // one group's CARE bits
lits += $countones(used);
end
$display("%0d of 16 rows wrong", wrong);
$display("%0d terms, %0d literals", n, lits);
if (wrong == 0 && n == 3 && lits == 7) $display("minimum is 3 terms, 7 literals: reached");
else if (wrong == 0) $display("minimum is 3 terms, 7 literals: not reached");
end
endmodule
Check Yourself
Common Mistakes
Wrong Label the columns 00, 01, 10, 11.
Then columns 01 and 10 are neighbours, but they differ in two bits, so their cells do not merge.
Fix Use Gray order: 00, 01, 11, 10. Each step changes one bit.
Wrong Draw a group of three or six cells, or a diagonal pair.
Only a rectangle of 1, 2, 4 or 8 cells is one product term.
Fix Split the shape into rectangles whose sizes are powers of two. They may overlap.
Wrong Stop at the edge of the map.
The left and right columns are neighbours, and so are the top and bottom rows.
Fix Look for groups that wrap. The four corners form one group of four.
Wrong Keep every large group you can find.
A group whose cells are all inside other chosen groups adds a gate and covers nothing new.
Fix Take the essential groups first. Add another group only for a 1 that is still uncovered.
Remember
- A K-map is a truth table in Gray order, so cells that touch differ in one variable.
- A group is a rectangle of 1, 2, 4 or 8 cells; it may wrap around the edges and overlap others.
- Read a group by keeping the variables that stay the same inside it.
- A prime implicant cannot grow; an essential prime is the only cover of some 1.
- Take the essential primes first, then the fewest groups for the 1s that remain.