Factoring pulls a common literal out of several product terms. Collapsing does the reverse: it substitutes one expression into another to expose new simplifications.
The running example is the 3-input majority function. Its sum of products uses 6 literals; the factored form below uses 5.
Form | Expression | Literals |
|---|---|---|
Sum of products |
| 6 |
Factored |
| 5 |
Collapsed then refactored | Same factored form here | 5 |
Sharing implements one repeated sub-expression once and reuses its output. The inputs b and c are shared here: each drives two gates, the OR that forms b + c and the AND that forms bc.
Areas are library units of the fictional teaching library course.lib: AND2 and OR2 cost 3 units each. The calc block prices both forms.
original ab + ac + bc: 3 AND2 + 2 OR2 (3-input OR from two OR2)
area = 3 x 3 + 2 x 3 = 9 + 6 = 15 area units
factored a(b + c) + bc: 2 AND2 + 2 OR2
area = 2 x 3 + 2 x 3 = 6 + 6 = 12 area units
saving = 15 - 12 = 3 area units = 3 / 15 = 20%The program below checks all 8 input rows for equality. It also counts literals from the expression trees and requires the factored form to be smaller.
import sys
def f_orig(a, b, c):
return (a and b) or (a and c) or (b and c)
def f_fact(a, b, c):
return (a and (b or c)) or (b and c)
def count_lits(node):
if isinstance(node, str):
return 1
return sum(count_lits(k) for k in node[1:])
ORIG = ("or", ("and", "a", "b"), ("and", "a", "c"), ("and", "b", "c"))
FACT = ("or", ("and", "a", ("or", "b", "c")), ("and", "b", "c"))
rows = 0
diff = 0
for a in (0, 1):
for b in (0, 1):
for c in (0, 1):
rows += 1
if bool(f_orig(a, b, c)) != bool(f_fact(a, b, c)):
diff += 1
no = count_lits(ORIG)
nf = count_lits(FACT)
if rows != 8:
print("FAIL: walked " + str(rows) + " rows, want 8")
sys.exit(1)
if diff != 0:
print("FAIL: " + str(diff) + " rows differ")
sys.exit(1)
if no != 6:
print("FAIL: original counts " + str(no) + " literals, want 6")
sys.exit(1)
if nf != 5:
print("FAIL: factored counts " + str(nf) + " literals, want 5")
sys.exit(1)
if not nf < no:
print("FAIL: factored form is not smaller")
sys.exit(1)
print("PASS: factored form agrees on 8 of 8 rows with 5 literals against 6")Fewer literals need not mean less area or delay. Factoring can add levels, and collapsing can duplicate terms before anything improves.
The inputs b and c are shared. Each drives the OR forming b + c and the AND forming bc.
They compute the same 3-input function. Every input combination gives the same output.