Five- and Six-Variable Maps
Minimize a five-variable function on two maps and see how six variables use four. Then learn when to hand the job to a tool.
You Will Be Able To
- Draw a five-variable function on two four-variable maps.
- Find groups that span both maps.
- Read a six-variable function as four maps.
- Say when a map stops being the right tool.
- Lesson
- G3.4
- Time
- 30 min
- Runs on
- Your browser
- Check
- 5 questions
A mixer interlock reads five sensors. The engineer drew one map for each value of the fifth sensor and minimized each: five terms. One group was split into a half on each map, and another kept the fifth variable for no reason.
| Cover of the same function | Product terms | Literals |
|---|---|---|
| Each map minimized alone | 5 | 17 |
| Groups merged across the two maps | 4 | 11 |
Computed by the exact minimizer. The function is 1 on 18 of the 32 rows of a b c d e.
Two Maps for Five Variables
Five variables give 32 rows. Draw them as two maps of 16 cells. Here the first map holds the rows with e = 0 and the second holds the rows with e = 1.
Inside one map, the rules are those of lesson G3.1. Between the maps there is one new rule. A cell is a neighbour of the cell at the same place on the other map. Those two rows differ only in e.
Groups That Span Both Maps
A group may use both maps when it has the same shape at the same place on each. Its size doubles, and e leaves the term.
| Group | Cells where e = 0 | Cells where e = 1 | Is e in the term? |
|---|---|---|---|
c'e' | 8 | 0 | yes: it stays 0 |
ac' | 4 | 4 | no: it changes |
a'cd | 2 | 2 | no: it changes |
bcd'e | 0 | 2 | yes: it stays 1 |
A group on both maps has the same number of cells on each.
The split design of the hook kept a'cd as two groups, a'cde' and a'cde: merging them saves a term and 5 literals. It also wrote ac'e where ac' is enough, one more literal.
Four Maps for Six Variables
Six variables give 64 rows: four maps of 16 cells. Take ab as the map number, in Gray order. Each map then has rows cd and columns ef.
- Neutral
- Structure
- A group on one map
The pair
a'b'cdflives on map 00. The four cells ofab'd'flive on map 10. Both terms keepaandb. - A group on two maps
Maps 01 and 11 are neighbours. The same four cells on both form
bde: eight cells, andaleaves the term. - A group on all four maps
The same four cells hold 1s on every map. They form
c'f': sixteen cells, with neitheranorb.
Read the diagram as text
- Map ab = 00: c'f', a'b'cdf
- Map ab = 01: c'f', bde
- Map ab = 11: c'f', bde
- Map ab = 10: c'f', ab'd'f
- Map ab = 00 → Map ab = 01: b changes
- Map ab = 01 → Map ab = 11: a changes
- Map ab = 11 → Map ab = 10: b changes
- Map ab = 10 → Map ab = 00: a changes
g = c'f' + bde + ab'd'f + a'b'cdf: 4 terms and 14 literals. Maps 00 and 11 are not neighbours, and neither are 01 and 10.
| Group | Maps it uses | Cells | Literals |
|---|---|---|---|
c'f' | 00, 01, 11, 10 | 16 | 2 |
bde | 01, 11 | 8 | 3 |
ab'd'f | 10 | 4 | 4 |
a'b'cdf | 00 | 2 | 5 |
Computed for the six-variable function g. Each halving of a group adds one literal.
When to Stop and Use a Tool
Each new variable doubles the number of maps. The method still works, but finding neighbours between maps gets harder to do by eye.
| Variables | Rows | Maps of 16 cells | Use |
|---|---|---|---|
| 4 | 16 | 1 | a map |
| 5 | 32 | 2 | a map, with care |
| 6 | 64 | 4 | a map as a last resort |
| 7 | 128 | 8 | a tabular method or a tool |
| 8 | 256 | 16 | a tool |
The number of rows is 2 to the power of the number of variables.
A map is for seeing why a cover is small. Lesson G3.5 gives the same method as a table that a program can run. Synthesis tools use faster methods on real designs.
Asked in interviews
How do you draw a five-variable K-map?
As two four-variable maps, one for each value of the fifth variable. A cell is also a neighbour of the cell at the same position on the other map.
When does a group span both maps?
When it has the same shape at the same cells on each map. The fifth variable then changes inside the group and leaves the term.
Why are K-maps not used for large functions?
The picture stops helping. Six variables need four maps and seven need eight. Tabular methods and synthesis tools find the cover without a picture.
Try It
Each term is now a group of five bits in the order a b c d e. The table holds the split design: five groups, each on one map. The bench finds no wrong row among the 32.
Merge the groups that sit at the same cells of both maps. Set N = 4, CARE = {5'b01111, 5'b10110, 5'b10100, 5'b00101} and VALUE = {5'b01101, 5'b00110, 5'b10000, 5'b00000}. The bench prints minimum is 4 terms, 11 literals: reached.
Then try to merge too much: change the leftmost group, bcd'e, to bcd' by clearing its CARE bit for e. The bench prints first wrong row: abcde = 01100 (f is 0, the table gives 1).
0 of 32 rows wrong 5 terms, 17 literals minimum is 4 terms, 11 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 abcde. DC marks the don't-care rows.
localparam logic [31:0] F = 32'b00101111000011111110010111000101;
localparam logic [31:0] DC = 32'b00000000000000000000000000000000;
wire [7:0] n;
wire [39: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 [4:0] row);
logic hit;
hit = 1'b0;
for (int t = 0; t < 8; t++)
if (t < n && ((row ^ value[5*t +: 5]) & care[5*t +: 5]) == '0) hit = 1'b1;
return hit;
endfunction
initial begin
int wrong, lits;
logic [4:0] row, used;
#1; // let the table reach the wires
wrong = 0;
lits = 0;
for (int m = 0; m < 32; m++) begin
row = m[4:0];
if (!DC[m] && table_at(row) !== F[m]) begin
if (wrong == 0) $display("first wrong row: abcde = %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[5*t +: 5]; // one group's CARE bits
lits += $countones(used);
end
$display("%0d of 32 rows wrong", wrong);
$display("%0d terms, %0d literals", n, lits);
if (wrong == 0 && n == 4 && lits == 11) $display("minimum is 4 terms, 11 literals: reached");
else if (wrong == 0) $display("minimum is 4 terms, 11 literals: not reached");
end
endmodule
Check Yourself
Common Mistakes
Wrong Minimize each of the two maps on its own and add the results.
Two groups at the same cells of both maps are one group, and the split keeps the fifth variable in both terms.
Fix Compare the maps cell by cell first. Merge every pair of groups that sits at the same cells.
Wrong Join a group on one map with a group at different cells of the other map.
Cells on different maps are neighbours only at the same row and column.
Fix A group that spans both maps has the same shape at the same place on each.
Wrong Write the fifth variable into a term whose group spans both maps.
The variable changes inside that group, so it leaves the term.
Fix Keep e only for a group that lives on one map: e' on the first, e on the second.
Wrong Draw a map for seven or more variables.
The map splits into eight or more planes, and adjacency between them is easy to miss.
Fix Use the tabular method of lesson G3.5, or a tool, above six variables.
Remember
- Five variables use two maps; a cell is a neighbour of the same cell on the other map.
- A group spans both maps only with the same shape at the same place; the fifth variable then leaves the term.
- Six variables use four maps, numbered in Gray order; only maps that differ in one bit are neighbours.
- Above six variables, use a tabular method or a tool.