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 function | Gates | Literals |
|---|---|---|
| Sum of products, from the 1s | 4 AND, 1 OR | 8 |
| Product of sums, from the 0s | 2 OR, 1 AND | 4 |
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 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.
| Step | Result |
|---|---|
| From the groups of 0s | f' = a'c + b'd' |
| Complement both sides | f = (a'c + b'd')' |
| De Morgan on the OR | f = (a'c)' (b'd')' |
| De Morgan on each AND | f = (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 same | Term of f' | Sum term of f |
|---|---|---|---|
| 0010, 0011, 0110, 0111 | a = 0, c = 1 | a'c | (a + c') |
| 0000, 0010, 1000, 1010 | b = 0, d = 0 | b'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.
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.
| Function | Sum of products | Product of sums | Cheaper |
|---|---|---|---|
(a + c')(b + d) | 4 terms, 8 literals | 2 sums, 4 literals | product of sums |
cd + ab | 2 terms, 4 literals | 4 sums, 8 literals | sum of products |
| "the BCD digit is prime" | 2 terms, 4 literals | 2 sums, 4 literals | a 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.
- Neutral
- Step
- Structure
- Route 1: the 1s
Group the 1s and read one product term per group.
- Route 2: the 0s
Group the 0s. Flip every literal to turn each group into a sum term.
- 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
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.
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.
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).
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 literalsRead 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
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.
// zeros where a = 0 and c = 1
assign f = (~a | c) & (b | d);// 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.