Canonical Forms: Minterms, Maxterms and Shannon Expansion
Write a truth table as minterms or maxterms, convert between the two lists, and split a function around one variable.
You Will Be Able To
- Name the minterm and the maxterm of each row.
- Write a function as Σm and as ΠM, and convert between them.
- Tell a canonical form from a minimal one.
- Split a function around one variable by Shannon expansion.
- Lesson
- G2.8
- Time
- 25 min
- Runs on
- Your browser
- Check
- 5 questions
Two engineers wrote the same function in a review. One wrote Σm(1, 3, 4, 6). The other wrote ΠM(0, 2, 5, 7). Both lists describe one truth table.
- Cycle 0
Row 0 gives f = 0. Its number goes to the maxterm list.
- Cycle 1
Row 1 gives f = 1. Its number goes to the minterm list.
- Cycle 7
Every row lands in exactly one list. So each list is the complement of the other.
Computed from the expression and checked on Icarus.
Minterms and Maxterms
A literal is a variable or its complement: a or a'. A minterm is an AND of every variable once, each as a literal. It is 1 on exactly one row. A maxterm is an OR of every variable once. It is 0 on exactly one row.
| Row | a b c | Minterm (1 on this row only) | Maxterm (0 on this row only) |
|---|---|---|---|
| 0 | 000 | a'b'c' | (a + b + c) |
| 1 | 001 | a'b'c | (a + b + c') |
| 2 | 010 | a'bc' | (a + b' + c) |
| 3 | 011 | a'bc | (a + b' + c') |
| 4 | 100 | ab'c' | (a' + b + c) |
| 5 | 101 | ab'c | (a' + b + c') |
| 6 | 110 | abc' | (a' + b' + c) |
| 7 | 111 | abc | (a' + b' + c') |
Minterm: a 0 in the row gives a primed literal. Maxterm: a 1 in the row gives a primed literal. Each maxterm is the complement of the minterm of its row.
Sum of Minterms and Product of Maxterms
Any function is the OR of the minterms of its 1 rows. This is the canonical sum of products, written Σm with the row numbers. It is also the AND of the maxterms of its 0 rows: the canonical product of sums, written ΠM.
| Form | Written as | Built from |
|---|---|---|
| Σm | Σm(1, 3, 4, 6) | a'b'c + a'bc + ab'c' + abc' |
| ΠM | ΠM(0, 2, 5, 7) | (a + b + c)(a + b' + c)(a' + b + c')(a' + b' + c') |
Both forms of f = a'c + ac'. The two number lists split 0 to 7 between them.
To convert, list the numbers that are missing. The maxterms of f are the rows where f is 0, so they are exactly the numbers not in Σm.
The complement f' has the 0 rows of f as its minterms. So f' = Σm of the same numbers that ΠM lists for f.
Canonical Against Minimal
A canonical form uses one full term for each row in its list. It is unique: two functions are equal exactly when their Σm lists are equal.
A standard form is any sum of products or product of sums, with terms that may leave out variables. The minimal one is usually far smaller.
Canonical forms are the safe way to state a function. Minimization, in module G3, makes it cheap.
Shannon Expansion
Shannon expansion splits a function around one variable. Set a = 0 to get the cofactor f₀. Set a = 1 to get f₁. Then f = a'·f₀ + a·f₁.
- Neutral
- Datapath
- I/O
- Structure
- Data
- Set a = 0
ab and ac vanish. What is left is bc.
Follow the calls, values and waits
- data bc: f = ab + ac + bc → f₀ = f with a = 0
- Set a = 1
ab becomes b and ac becomes c. b + c + bc is b + c by absorption.
Follow the calls, values and waits
- data b + c: f = ab + ac + bc → f₁ = f with a = 1
- Join them
f = a'(bc) + a(b + c). A multiplexer on a picks the right cofactor.
Follow the calls, values and waits
- data a'(bc) + a(b + c): Select on a → f
Read the diagram as text
- f = ab + ac + bc: majority of three
- f₀ = f with a = 0: bc
- f₁ = f with a = 1: b + c
- Select on a: a'·f₀ + a·f₁
- f: the same function
- f = ab + ac + bc → f₀ = f with a = 0: a = 0
- f = ab + ac + bc → f₁ = f with a = 1: a = 1
- f₀ = f with a = 0 → Select on a: when a = 0
- f₁ = f with a = 1 → Select on a: when a = 1
- Select on a → f
The expansion is exact for every function. Lesson G4.2 builds functions from multiplexers this way.
Asked in interviews
What is the difference between a minterm and a maxterm?
A minterm is an AND of all variables that is 1 on exactly one row. A maxterm is an OR of all variables that is 0 on exactly one row. M_m is the complement of m_m.
How do you convert Σm to ΠM?
List the row numbers that are missing from Σm. Those rows are the 0s of the function, and each gives one maxterm.
What is Shannon expansion used for?
It splits a function into two smaller cofactors selected by one variable. It maps a function onto multiplexers and lookup tables, and it is the basis of decision diagrams.
Try It
The constant F = 16'h4252 sets bits 1, 4, 6, 9, 14. So the function is Σm(1, 4, 6, 9, 14).
The module sum_of_minterms has one product per minterm, but the product for row 14 is missing. The bench finds it.
Add | (a & b & c & ~d) and run again. The bench prints equal on 16 of 16.
Now write the product of maxterms instead: one sum term for each of the eleven 0 rows. The bench must print 16 of 16 again.
differ at m = 14 (abcd = 1110): table 1, sum 0 equal on 15 of 16Read included file: tb.sv
// tb.sv: compares the sum of minterms with the table on all 16 rows (read-only).
module tb;
logic a, b, c, d;
logic f, g;
int equal = 0;
from_table u_f (.a(a), .b(b), .c(c), .d(d), .f(f));
sum_of_minterms u_g (.a(a), .b(b), .c(c), .d(d), .g(g));
initial begin
for (int m = 0; m < 16; m++) begin
{a, b, c, d} = m[3:0];
#1;
if (f === g) equal++;
else $display("differ at m = %0d (abcd = %b%b%b%b): table %b, sum %b", m, a, b, c, d, f, g);
end
$display("equal on %0d of 16", equal);
end
endmodule
Check Yourself
Common Mistakes
Wrong Number the rows with the variables in the wrong order.
The minterm number is the binary value of the inputs in the stated order. a b' c d' is 1010 = 10, but read backwards it is 0101 = 5.
Fix Write the variables in order, a first, as a binary number.
Wrong Complement the literals of a minterm the wrong way when writing a maxterm.
A maxterm is 0 on exactly one row. Its literals are complemented where the row has a 1, not where it has a 0.
Fix Row 101 gives the maxterm (a' + b + c'): a 1 becomes a primed literal.
Wrong Think that canonical means minimal.
A canonical form has one full term per row. It is unique, but it is usually much larger than the minimum.
Fix Use Σm and ΠM to state a function exactly. Use minimization (module G3) to make it small.
Wrong List don't-care rows among the minterms.
A don't-care row may be 0 or 1. Listing it as a minterm fixes it to 1, which the spec never asked for.
Fix Write the don't-cares as a separate list: f = Σm(...) + d(...).
Remember
- A minterm is 1 on one row, a maxterm is 0 on one row. The row number is the inputs read as a binary number.
- Σm lists the 1 rows. ΠM lists the 0 rows. Each list is the complement of the other.
- Canonical forms are unique but large. Minimal forms are small.
- Shannon expansion: f = a'·f₀ + a·f₁, a multiplexer on a.