Algebraic Simplification
In the last article we saw that any truth table can be written mechanically as a sum of products. That expression is correct, and a circuit built from it will work. It is also, nearly always, far bigger than it needs to be. This article is about closing the gap between correct and good.
Take a 4-variable function that is 1 in eight rows. The canonical SOP has eight product terms of four literals each: eight 4-input AND gates, an 8-input OR gate and up to four inverters, perhaps fifty transistors. After minimisation the same function might be two 2-input ANDs and one OR, twelve transistors. A quarter of the silicon, a quarter of the power, and faster, because the critical path is shorter.
The tools
Algebraic simplification is pattern recognition. You scan the expression for one of these opportunities, apply the rule, and scan again until nothing is left.
Combining terms that differ in one variable. $$AB + AB’ = A(B + B’) = A$$ Two product terms that are identical except that one variable is complemented in one and not the other collapse into a single term without that variable.
Idempotency. $$A + A = A \qquad A \cdot A = A$$ Duplicate terms can be removed. Just as usefully, a term can be duplicated so that it can be combined with more than one partner.
Absorption. $$A + AB = A \qquad A(A + B) = A$$ If every literal of a short term also appears in a longer term, the longer term is redundant.
The absorption variant. $$A + A’B = A + B$$
Complements. $$A + A’ = 1 \qquad A \cdot A’ = 0$$
Factoring. $$AB + AC = A(B + C)$$ Pull out common literals to reduce the literal count. The reverse, expanding, is sometimes needed to expose a combination.
De Morgan. $$(AB)’ = A’ + B’ \qquad (A + B)’ = A’B’$$ Switch between AND and OR forms when a simplification is hidden in the current one.
There is no algorithm here that guarantees the smallest result. Algebraic simplification is a search guided by experience. That limitation is the reason Karnaugh maps and the Quine-McCluskey method exist, and we get to them in section 1.4.
Worked example 1: everything collapses
Simplify $F = ABC + ABC’ + AB’C + AB’C’$.
| Expression | Rule |
|---|---|
| $ABC + ABC’ + AB’C + AB’C'$ | start |
| $AB(C + C’) + AB’(C + C’)$ | factoring |
| $AB + AB'$ | complement, identity |
| $A(B + B’)$ | factoring |
| $A$ | complement, identity |
So $F = A$. The function is 1 for every combination of $B$ and $C$ as long as $A = 1$, and the four-term SOP was a long way of saying so.
| Form | AND gates | OR gates | Inverters | Total |
|---|---|---|---|---|
| Canonical SOP | 4 (3-input) | 1 (4-input) | 3 | 8 |
| Simplified | 0 | 0 | 0 | 0 |
The simplified circuit is a wire from $A$ to the output.
Worked example 2: a product of sums
Simplify $F = (A + B)(A + B’)$.
| Expression | Rule |
|---|---|
| $(A + B)(A + B’)$ | start |
| $A + BB'$ | second distributive law, reversed |
| $A + 0$ | complement |
| $A$ | identity |
Again $F = A$. When $A = 1$ both factors are 1; when $A = 0$ the factors are $B$ and $B’$, whose product is 0. This is the POS mirror image of $AB + AB’ = A$.
Worked example 3: three terms
Simplify $F = AB’C + ABC + A’BC$.
Look for pairs that differ in exactly one variable. $AB’C$ and $ABC$ differ only in $B$, so they combine to $AC$. That leaves $AC + A’BC$. Absorption does not apply directly, since $A$ and $A’$ are different literals, but factoring out $C$ gives $C(A + A’B)$, and the absorption variant turns $A + A’B$ into $A + B$.
| Expression | Rule |
|---|---|
| $AB’C + ABC + A’BC$ | start |
| $AC(B’ + B) + A’BC$ | factoring |
| $AC + A’BC$ | complement, identity |
| $C(A + A’B)$ | factoring |
| $C(A + B)$ | absorption variant |
| $AC + BC$ | expand, if you want SOP |
So $F = AC + BC$, or in factored form $F = C(A + B)$.
Spot check row 5, $A = 1, B = 0, C = 1$: the original gives $AB’C = 1$, and $AC + BC = 1 + 0 = 1$. Row 2, $A = 0, B = 1, C = 0$: every original term contains $C$, so $F = 0$, and $AC + BC = 0 + 0 = 0$.
| Form | Terms | Literals | Gates |
|---|---|---|---|
| Canonical SOP | 3 | 9 | 3 AND + 1 OR |
| Simplified SOP | 2 | 4 | 2 AND + 1 OR |
| Factored | $C(A + B)$ | 3 | 1 OR + 1 AND |
The factored form has the fewest gates. Factored forms can add a level of logic on the critical path, though, so which is better depends on whether you are short of area or short of time.
Adding a term to remove one
Sometimes the way forward is to add a term. Idempotency guarantees this is legal: adding a term that is already implied by the expression changes nothing.
Simplify $F = AB + A’C + BC$. No two terms differ in exactly one variable, so the usual move is blocked. But $BC = BC(A + A’) = ABC + A’BC$, so
$$F = AB + A’C + ABC + A’BC = AB(1 + C) + A’C(1 + B) = AB + A’C$$
The $BC$ term was the consensus of $AB$ and $A’C$ and can be dropped. Once you know the consensus theorem you can do this in one step, but the expansion is how you would discover it.
A related habit worth building: after each simplification, scan the result again. Combining two terms often creates a new opportunity that was not visible in the original, and stopping one step early is the most common way to end up with a bigger circuit than necessary.
Don’t-care conditions
So far every truth table row has had a definite 0 or 1. In real designs some input combinations never happen. In a BCD system the 4-bit input represents a decimal digit, so the patterns 1010 to 1111 never occur, and the output for those rows does not matter. We are free to choose 0 or 1 for each of them, whichever makes the expression smaller.
These are don’t-care conditions, written as $X$ or $d$ in the table:
$$F = \sum m(1, 3, 5, 7) + \sum d(8, 9, 10, 11, 12, 13, 14, 15)$$
A don’t-care that is treated as a 1 costs nothing, because that row never occurs, and it may let a product term cover more minterms. Don’t-cares are free simplification, and they are covered properly with Karnaugh maps in section 1.4.
The limitation
Algebraic simplification requires you to notice things. There is no procedure that guarantees you will find the smallest expression. You might miss a consensus term. You might not think of duplicating a term so that it can combine twice. You might arrive at something that looks irreducible and is not. With six or more variables and a dozen terms it becomes impractical by hand.
For that reason there are three more systematic methods:
- Karnaugh maps, a way of drawing the truth table so that terms that can be combined sit next to each other. Minimisation becomes visual and nearly mechanical for up to five or six variables.
- Quine-McCluskey, a tabular algorithm that finds all the largest possible terms and then chooses a minimum set of them. It is guaranteed optimal but exponential in cost.
- Espresso, a heuristic used inside CAD tools. Not guaranteed optimal, but fast and usable for dozens of variables. This is what your synthesis tool runs.
The algebra remains essential even when a tool does the work, because it is how you check that a result is valid and how you understand what the tool did when its output surprises you.
Practice Exercise
Problem 1. Simplify $F = A’B’C’ + A’BC’ + AB’C’ + ABC’$.
Solution
| Expression | Rule |
|---|---|
| $A’B’C’ + A’BC’ + AB’C’ + ABC'$ | start |
| $A’C’(B’ + B) + AC’(B’ + B)$ | factoring |
| $A’C’ + AC'$ | complement, identity |
| $C’(A’ + A)$ | factoring |
| $C'$ | complement, identity |
$F = C’$. Four AND gates and an OR gate become a single inverter, or nothing at all if $C’$ is already available.
Problem 2. Simplify $F = (A + B + C)(A + B + C’)(A + B’ + C)$.
Solution
The first two factors share $A + B$ and differ in $C$, so by the dual of the combining rule $(X + Y)(X + Y’) = X$:
$$(A + B + C)(A + B + C’) = A + B$$
Then
$$(A + B)(A + B’ + C) = A + B(B’ + C) = A + BC$$
using the second distributive law. $F = A + BC$: one AND and one OR instead of three ORs and two ANDs.
Problem 3. Simplify $F = A’B’C + A’BC + AB’C + ABC$.
Solution
| Expression | Rule |
|---|---|
| $A’B’C + A’BC + AB’C + ABC$ | start |
| $A’C(B’ + B) + AC(B’ + B)$ | factoring |
| $A’C + AC$ | complement, identity |
| $C(A’ + A)$ | factoring |
| $C$ | complement, identity |
$F = C$. The output is simply the $C$ input, and $A$ and $B$ do not matter.
That completes the Boolean algebra section. Section 1.3 moves from algebra to hardware and looks at the gates themselves; section 1.4 returns to minimisation with Karnaugh maps, which make most of what we did here by hand into a matter of drawing loops around 1s.