Product of Sums from a K-Map

Group the 0s of a Karnaugh map and turn the result into a product of sums. Then choose the cheaper form.

You Will Be Able To

  • Group the 0s of a map to get the complement of a function.
  • Read a group of 0s as one sum term.
  • Compare the sum of products with the product of sums by literal count.
Lesson
G3.3
Time
25 min
Runs on
Your browser
Check
5 questions

A machine guard runs its motor from four switches. The engineer minimized the logic on a map and built four AND gates and one OR gate. A colleague grouped the 0s of the same map and built it with half the gate inputs.

Form of the same functionGatesLiterals
Sum of products, from the 1s4 AND, 1 OR8
Product of sums, from the 0s2 OR, 1 AND4

Computed for f = Σm(1, 4, 5, 9, 11, 12, 13, 14, 15). Both forms give the same output on all 16 rows.

Group the 0s to Get the Complement

A group of 1s is a product term that makes f equal to 1. A group of 0s works the same way for the complement, f'. Inside the group, f' is 1.

The interlock function: groups of 0s
ab / cd00011110
00
01
11
10

(b | d) & (a | ~c)

Minimum POS: 2 sum terms · 4 literals.

  1. Four 0s in the top rows. These cells have `a = 0` and `c = 1`. So f is 0 when `a'c` is true.
  2. The four corners. The corners have `b = 0` and `d = 0`. So f is also 0 when `b'd'` is true.

The seven 0s fall into two groups of four. So f' = a'c + b'd'.

The rules for groups do not change. A group is a rectangle of 1, 2, 4 or 8 cells. It may wrap, and it must hold no 1.

De Morgan Turns It into a Product of Sums

Complement both sides. De Morgan's theorem turns each AND into an OR and flips each literal.

StepResult
From the groups of 0sf' = a'c + b'd'
Complement both sidesf = (a'c + b'd')'
De Morgan on the ORf = (a'c)' (b'd')'
De Morgan on each ANDf = (a + c')(b + d)

Each line is the same function as the line above it.

The result is a product of sums (POS): an AND of OR terms. Each group of 0s became one sum term.

You can read a sum straight from its group. A variable that stays 0 in the group is written plain. A variable that stays 1 is written complemented.

Group of 0s (rows abcd)Stays the sameTerm of f'Sum term of f
0010, 0011, 0110, 0111a = 0, c = 1a'c(a + c')
0000, 0010, 1000, 1010b = 0, d = 0b'd'(b + d)

f = (a + c')(b + d): 2 sums and 4 literals.

Two Circuits for One Function

The product of sums is an OR-AND circuit: one OR gate per sum, then one AND gate. Click the inputs to check it against the table.

The interlock as OR gates into one AND gate
abcdf
00000
00011
00100
00110
01001
01011
01100
01110
10000
10011
10100
10111
11001
11011
11101
11111
The interlock as OR gates into one AND gateg0 · ORterm0=0g1 · NOTinv_c=1g2 · ORterm1=1g3 · ANDf=0a=0b=0c=0d=0
a=0 b=0 c=0 d=0
g0 · ORb=0, d=0 → term0=0
g1 · NOTc=0 → inv_c=1
g2 · ORa=0, inv_c=1 → term1=1
g3 · ANDterm0=0, term1=1 → f=0
Read the connections
GateKindInputsOutput
g0ORb, dterm0
g1NOTcinv_c
g2ORa, inv_cterm1
g3ANDterm0, term1f

Outputs: f. MUX inputs: d0, d1, select. Latch/flip-flop inputs: data, enable/clock. Unknown values are marked x; high impedance is folded into x in this model.

Two two-input OR gates, one two-input AND gate and one inverter for `c`.

Sum of products

assign f = (~c & d) | (b & ~c)
         | (a & d)  | (a & b);

Four AND gates and a four-input OR gate: 4 terms and 8 literals.

Product of sums

assign f = (a | ~c) & (b | d);

Two OR gates and a two-input AND gate: 2 sums and 4 literals.

Both expressions are the same function. Multiply the two sums out and you get the four product terms.

Choose by Counting Literals

Neither form always wins. Minimize the 1s, minimize the 0s, and count.

FunctionSum of productsProduct of sumsCheaper
(a + c')(b + d)4 terms, 8 literals2 sums, 4 literalsproduct of sums
cd + ab2 terms, 4 literals4 sums, 8 literalssum of products
"the BCD digit is prime"2 terms, 4 literals2 sums, 4 literalsa tie

Computed by the minimizer. The third row uses the BCD don't-cares of lesson G3.2.

Don't-cares help the 0s too. An x cell may join a group of 0s when that makes the group larger.

Is the BCD digit prime? Groups of 0s with don't-cares
ab / cd00011110
00
01
11
10

(b | c) & (~b | d)

Minimum POS: 2 sum terms · 4 literals.

f = (b + c)(b' + d). The group for `(b' + d)` holds the 0s of the digits 4 and 6 and two `x` cells.

Two Routes from One MapArrows show the order of the work. Both routes start from the same map and end at the comparison.
  • Neutral
  • Step
  • Structure
Two routes from one mapArrows show the order of the work. Both routes start from the same map and end at the comparison. neutral K-map 1s, 0s and x cells step Group the 1s terms of f neutral Sum of products AND gates, then OR step Group the 0s terms of f' neutral Product of sums OR gates, then AND step Count literals keep the cheaperform route 1readroute 2De Morgancostcost
  1. neutral K-map1s, 0s and x cells
    • route 1 → Group the 1s
    • route 2 → Group the 0s
  2. step Group the 1sterms of f
    • read → Sum of products
  3. neutral Sum of productsAND gates, then OR
    • cost → Count literals
  4. step Group the 0sterms of f'
    • De Morgan → Product of sums
  5. neutral Product of sumsOR gates, then AND
    • cost → Count literals
  6. step Count literalskeep the cheaper form
  1. Route 1: the 1s

    Group the 1s and read one product term per group.

  2. Route 2: the 0s

    Group the 0s. Flip every literal to turn each group into a sum term.

  3. Compare

    Count the literals of both results and build the smaller one.

Read the diagram as text
  • K-map: 1s, 0s and x cells
  • Group the 1s: terms of f
  • Sum of products: AND gates, then OR
  • Group the 0s: terms of f'
  • Product of sums: OR gates, then AND
  • Count literals: keep the cheaper form
  • K-map → Group the 1s: route 1
  • Group the 1s → Sum of products: read
  • K-map → Group the 0s: route 2
  • Group the 0s → Product of sums: De Morgan
  • Sum of products → Count literals: cost
  • Product of sums → Count literals: cost

An x cell may be 1 on one route and 0 on the other. Each route is still correct on every required row.

Asked in interviews
  1. How do you get a product of sums from a K-map?

    Group the 0s. Each group is a product term of the complement. Apply De Morgan: each group becomes a sum with every literal flipped, and the sums are ANDed.

  2. When is a product of sums cheaper?

    When the 0s form fewer, larger groups than the 1s. A few lone 0s are not enough: each needs a sum of every variable. The only safe test is to minimize both ways and count.

  3. What is a maxterm?

    It is a sum that holds every variable once and is 0 on exactly one row. A canonical product of sums has one maxterm for each 0 of the function.

Try It

Here each group of the table is a group of 0s. CARE marks the variables of the sum. VALUE gives the value each has inside the group, so the sum holds the opposite literal.

The table starts with one sum for each 0 of the interlock map. The bench finds no wrong row, and counts 7 sums and 28 literals.

Replace it with the two groups of 0s: N = 2, CARE = {4'b0101, 4'b1010} and VALUE = {4'b0000, 4'b0010}. The bench prints minimum is 2 sums, 4 literals: reached.

The last line gives the cost of the other form. Now set both VALUE groups to the literals themselves, {4'b0101, 4'b1000}. The bench prints first wrong row: abcd = 0000 (f is 0, the table gives 1).

RUNIcarus Verilog · in your browser
Edit the code, then run it
Expected: 0 of 16 rows wrong 7 sums, 28 literals minimum is 2 sums, 4 literals: not reached as a sum of products the minimum is 4 terms, 8 literals
Read included file: tb.sv
// tb.sv: the bench (read-only). It builds the product of sums from the table in module answer,
// compares it with f on every row that is not a don't-care, and counts sums 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'b1111101000110010;
  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 product of sums on one row: 0 when some group of 0s 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 sums, %0d literals", n, lits);
    if (wrong == 0 && n == 2 && lits == 4) $display("minimum is 2 sums, 4 literals: reached");
    else if (wrong == 0) $display("minimum is 2 sums, 4 literals: not reached");
    $display("as a sum of products the minimum is 4 terms, 8 literals");
  end
endmodule

Check Yourself

Predict the outputThe program evaluates the product of sums on four rows: 0010, 0101, 1000 and 1111. Predict the exact line it prints.
module tb;
  logic a, b, c, d;
  wire f = (a | ~c) & (b | d);
  initial begin
    {a, b, c, d} = 4'b0010; #1 $write("%b", f);
    {a, b, c, d} = 4'b0101; #1 $write("%b", f);
    {a, b, c, d} = 4'b1000; #1 $write("%b", f);
    {a, b, c, d} = 4'b1111; #1 $display("%b", f);
  end
endmodule
Spot the bugEach option is an expression for the interlock function f = Σm(1, 4, 5, 9, 11, 12, 13, 14, 15). The bench compares it with f on all 16 rows. Which one fails?
ConceptYou group the 0s of a map and get the terms a'c and b'd'. What do these two terms give when ORed?
ConceptA four-variable function is 0 on two rows only, and those rows are not neighbours. Which form has fewer literals?
ConceptFor f = ab + cd, the minimizer gives 2 terms and 4 literals as a sum of products. What does it give as a product of sums?

Common Mistakes

Wrong Read a group of 0s the same way as a group of 1s.

That gives a term of the complement; the sum term of f needs every literal flipped.

Fix In a group of 0s, write a variable plain where it stays 0 and complemented where it stays 1.

Before
// zeros where a = 0 and c = 1
assign f = (~a | c) & (b | d);
After
// zeros where a = 0 and c = 1
assign f = (a | ~c) & (b | d);

Wrong Group the 0s and then OR the terms as the answer.

The OR of the groups of 0s is f', which is 1 exactly where f must be 0.

Fix Complement the result once, with De Morgan, to get f as a product of sums.

Wrong Always use the sum of products.

A map whose 0s form fewer, larger groups than its 1s is often cheaper as a product of sums.

Fix Minimize both ways and count the literals.

Wrong Leave the don't-cares out when grouping 0s.

An x cell can make a group of 0s larger, just as it does for a group of 1s.

Fix Let each x cell join a group of 0s when that removes a literal.

Remember

  • A group of 0s is a product term of the complement f'.
  • De Morgan turns the OR of those terms into an AND of sums, with every literal flipped.
  • Read a sum from its group: plain where the variable stays 0, complemented where it stays 1.
  • Minimize the 1s and the 0s, count the literals, and build the cheaper form.

Practice

Report a problem with this page