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 functionProduct termsLiterals
Each map minimized alone517
Groups merged across the two maps411

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.

One function on two maps

e = 0

ab / cd00011110
00
01
11
10

e = 1

ab / cd00011110
00
01
11
10

~c & ~e | ~a & c & d | a & ~c | b & c & ~d & e

Minimum SOP: 4 terms · 11 literals.

    Rows are `ab` and columns are `cd` on both maps. Think of the second map as lying on top of the first.

    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.

    The four groups of the interlock

    e = 0

    ab / cd00011110
    00
    01
    11
    10

    e = 1

    ab / cd00011110
    00
    01
    11
    10

    ~c & ~e | ~a & c & d | a & ~c | b & c & ~d & e

    Minimum SOP: 4 terms · 11 literals.

    1. Eight cells on one map. On the map for `e = 0`, the columns `cd = 00` and `cd = 01` are full. Those eight cells are one group: `c'e'`.
    2. Four cells on each map. The same four cells of the bottom rows hold 1s on both maps. Together they are eight cells: `ac'`.
    3. Two cells on each map. The pair 0011 and 0111 is on both maps. The four cells are `a'cd`.
    4. A pair on the second map. The cells 0110 and 1110 hold 1s only where `e = 1`. That pair keeps `e`: `bcd'e`.

    f = c'e' + ac' + a'cd + bcd'e: 4 terms and 11 literals.

    GroupCells where e = 0Cells where e = 1Is e in the term?
    c'e'80yes: it stays 0
    ac'44no: it changes
    a'cd22no: it changes
    bcd'e02yes: 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.

    Six Variables: Four Maps and Their NeighboursEach box is one map of 16 cells. A line joins two maps that differ in one variable. The detail names the groups with cells on that map.
    • Neutral
    • Structure
    Six variables: four maps and their neighboursEach box is one map of 16 cells. A line joins two maps that differ in one variable. The detail names the groups with cells on that map. neutral Map ab = 00 c'f', a'b'cdf neutral Map ab = 01 c'f', bde neutral Map ab = 11 c'f', bde neutral Map ab = 10 c'f', ab'd'f b changesa changesb changesa changes
    1. neutral Map ab = 00c'f', a'b'cdf
      • b changes → Map ab = 01
    2. neutral Map ab = 10c'f', ab'd'f
      • a changes → Map ab = 00
    3. neutral Map ab = 01c'f', bde
      • a changes → Map ab = 11
    4. neutral Map ab = 11c'f', bde
      • b changes → Map ab = 10
    1. A group on one map

      The pair a'b'cdf lives on map 00. The four cells of ab'd'f live on map 10. Both terms keep a and b.

    2. A group on two maps

      Maps 01 and 11 are neighbours. The same four cells on both form bde: eight cells, and a leaves the term.

    3. A group on all four maps

      The same four cells hold 1s on every map. They form c'f': sixteen cells, with neither a nor b.

    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.

    GroupMaps it usesCellsLiterals
    c'f'00, 01, 11, 10162
    bde01, 1183
    ab'd'f1044
    a'b'cdf0025

    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.

    VariablesRowsMaps of 16 cellsUse
    4161a map
    5322a map, with care
    6644a map as a last resort
    71288a tabular method or a tool
    825616a 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
    1. 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.

    2. 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.

    3. 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).

    RUNIcarus Verilog · in your browser
    Edit the code, then run it
    Expected: 0 of 32 rows wrong 5 terms, 17 literals minimum is 4 terms, 11 literals: not reached
    Read 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

    Predict the outputThe program prints the row number of one input and the map that row is on. Predict the exact line.
    module tb;
      logic a, b, c, d, e;
      logic [4:0] row;
      initial begin
        {a, b, c, d, e} = 5'b10110;
        row = {a, b, c, d, e};
        $display("%0d on the map for e = %b", row, e);
      end
    endmodule
    Spot the bugEach option is an expression for the interlock function of this lesson. The bench compares it with the function on all 32 rows. Which one fails?
    ConceptA group has four cells on the map for e = 0 and the same four cells on the map for e = 1. How many literals does its term have?
    ConceptOn a six-variable map with ab as the map number, which two maps are neighbours?
    ConceptEach of two maps has the pair of cells 0011 and 0111. A designer writes two terms, one per map. What is lost?

    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.

    Practice

    Report a problem with this page