Multi-Level Logic, Factoring and NAND/NOR Conversion
Factor a sum of products into more levels to save gates, and watch the delay. Then convert multi-level logic to NAND or NOR only.
You Will Be Able To
- Factor a sum of products, or share a whole subexpression, and count cells and gate delays.
- Build wide gates from two-input cells and predict their depth.
- Convert multi-level AND-OR logic to NAND gates only by bubble pushing.
- Build f in AND-NOR form from its 0s, and name the eight useful two-level forms.
- Lesson
- G3.8
- Time
- 35 min
- Runs on
- Your browser
- Check
- 5 questions
A sum of products has two levels, so it is fast. It is not always small. Pulling a common factor out of the terms can halve the cell count. It can cost delay: here the balanced form does not, and the chain does.
| Circuit for f = ab + ac + ad + ae | Two-input cells | Slowest output change (gate delays) |
|---|---|---|
| Flat sum of products | 7 | 3 |
| Factored, balanced: a ((b + c) + (d + e)) | 4 | 3 |
| Factored, as a chain: a (b + (c + (d + e))) | 4 | 4 |
Measured with unit-delay cells: every cell takes one gate delay. The lab of this lesson prints the same numbers.
Factoring Saves Gates
Every term of ab + ac + ad + ae holds a. Pull it out: a(b + c + d + e). The function is the same, but a is now used once.
With wide gates, both forms have two levels. Real cell libraries limit the fan-in, often to two or three inputs. Then the picture changes.
Fan-In Limits Turn Wide Gates into Trees
With two-input cells, an n-input OR is a tree of n - 1 cells. A balanced tree has about log2(n) levels. A chain has n - 1 levels.
| Inputs n | Cells | Levels, balanced | Levels, chain |
|---|---|---|---|
| 2 | 1 | 1 | 1 |
| 3 | 2 | 2 | 2 |
| 4 | 3 | 2 | 3 |
| 5 | 4 | 3 | 4 |
| 8 | 7 | 3 | 7 |
| 16 | 15 | 4 | 15 |
Cells do not depend on the shape; the delay does.
Now count the lamp in two-input cells. The flat form needs four ANDs and three ORs. The factored form needs three ORs and one AND.
- Datapath
- Step
- Structure
- Factor
Pulling out
aremoves three AND cells. The OR tree has the same depth, so the delay stays at 3. - Over-factor
Writing the OR as a chain keeps 4 cells but adds a level: 4 gate delays.
- Pick
The balanced factored form wins on both counts here. In general, factoring and delay pull in opposite directions.
Read the diagram as text
- Flat SOP: 7 cells, 3 gate delays
- Factored, balanced: 4 cells, 3 gate delays
- Factored, chain: 4 cells, 4 gate delays
- Choose: fewest cells inside the delay budget
- Flat SOP → Factored, balanced: factor out a
- Factored, balanced → Factored, chain: unbalance the ORs
- Factored, balanced → Choose: best here
Arrows show rewrites of the same function.
Decomposition: Share a Subexpression
Factoring pulls out one literal. Decomposition goes further: it names a whole subexpression, builds it once, and uses it wherever it appears.
Take f = ac + bc + a'b'd. The first two terms share a + b, and the third term is its complement: a'b' = (a + b)'. Name x = a + b. Then f = xc + x'd.
| Circuit for f (two-input cells) | Cells | Slowest output change (gate delays) |
|---|---|---|
Flat: ac + bc + a'b'd | 8 | 4 |
Decomposed: x = a + b, then xc + x'd | 5 | 4 |
Measured with the unit-delay model of this lesson. The shared x feeds two gates, once inverted.
Synthesis tools hunt for such common subexpressions, inside one output and across outputs. It is the multi-level cousin of the shared terms of lesson G3.7.
NAND-Only by Bubble Pushing
Multi-level AND-OR logic converts to NAND gates level by level. An AND becomes a NAND with a bubble on its output. An OR becomes a NAND with bubbles on its inputs.
- Datapath
- Data
- AND to NAND
Levels 1 and 3 were AND gates. Each becomes a NAND, which puts a bubble on its output.
- OR to NAND
Levels 2 and 4 were OR gates. By De Morgan, an OR is a NAND with bubbles on both inputs.
- Unpaired bubbles
Inputs
candeenter an OR level directly. Nothing cancels their bubbles, so each needs an inverter: a NAND with both inputs tied.
Read the diagram as text
- NAND(a, b): was AND: output bubble
- NAND(c, c): inverter for c
- NAND(n1, c'): was OR: input bubbles
- NAND(n2, d): was AND: output bubble
- NAND(e, e): inverter for e
- NAND(n3, e'): was OR: input bubbles
- NAND(a, b) → NAND(n1, c'): bubbles cancel
- NAND(c, c) → NAND(n1, c'): c'
- NAND(n1, c') → NAND(n2, d): ab + c
- NAND(n2, d) → NAND(n3, e'): bubbles cancel
- NAND(e, e) → NAND(n3, e'): e'
Six NAND2 cells. With the inverter on c left out, the circuit is wrong on 6 of 32 rows.
The NOR version is the mirror image. An OR becomes a NOR with an output bubble, and an AND becomes a NOR with input bubbles. A product of sums such as (a + b)(c + d) needs only three NOR gates.
The Eight Two-Level Forms
Take two levels of gates from AND, OR, NAND and NOR. That gives 16 pairs. Eight collapse into a single gate. The other eight are useful.
| First level - second level | Form | Function of x1 to x4 |
|---|---|---|
| AND-OR | sum of products | x1 x2 + x3 x4 |
| NAND-NAND | sum of products | x1 x2 + x3 x4 |
| OR-AND | product of sums | (x1 + x2)(x3 + x4) |
| NOR-NOR | product of sums | (x1 + x2)(x3 + x4) |
| AND-NOR | AND-OR-INVERT | (x1 x2 + x3 x4)' |
| NAND-AND | AND-OR-INVERT | (x1 x2 + x3 x4)' |
| OR-NAND | OR-AND-INVERT | ((x1 + x2)(x3 + x4))' |
| NOR-OR | OR-AND-INVERT | ((x1 + x2)(x3 + x4))' |
Checked by evaluating all 16 pairs on every input. The two INVERT forms give the complement of a sum of products or of a product of sums.
Open the eight degenerate pairs
| First level - second level | Collapses to |
|---|---|
| AND-AND | one gate of the four inputs |
| AND-NAND | one gate of the four inputs |
| OR-OR | one gate of the four inputs |
| OR-NOR | one gate of the four inputs |
| NAND-OR | one gate of the four inputs |
| NAND-NOR | one gate of the four inputs |
| NOR-AND | one gate of the four inputs |
| NOR-NAND | one gate of the four inputs |
For example, AND-AND is one wide AND, and NAND-OR is one wide NAND.
The INVERT forms build f from its 0s. Minimize f' as a sum of products, then invert the final OR. AND-NOR is the direct form; NAND-AND is the same circuit after bubble pushing.
Group the 0s
For
f = a' + b'c', the 0s of f givef' = ab + ac.AND-NOR
Two AND gates for
abandac, and one NOR:f = (ab + ac)'. Three gates.OR-NAND, the dual
A product of sums of f' works the same way: OR gates, then one NAND.
NOR only
With a NOR2-only library, push the bubbles again. Problem G3.8.3 asks for the fewest NOR2 cells.
Asked in interviews
Why would you factor a sum of products?
To share a common literal or subexpression. That saves gates and literals. The cost is often extra levels, so the delay can grow.
How do you convert an AND-OR circuit to NAND only?
Replace each gate by a NAND. AND levels get output bubbles and OR levels get input bubbles. Bubbles cancel in pairs; add inverters where they do not.
Which two-level forms are degenerate?
Pairs that collapse to one gate, such as AND-AND or NAND-OR. The eight useful ones are AND-OR, NAND-NAND, OR-AND, NOR-NOR and four inverting forms.
Try It
Here you write a netlist of two-input cells from cells.sv. The bench checks all 32 rows. Then it changes one input at a time and times the output.
The flat form uses 7 cells, and its output settles within 3 gate delays.
Factor out a: two OR cells for b + c and d + e, one OR to join them, and one AND with a. The bench prints 4 cells and slowest output change: 3 gate delays after an input change.
Now chain the ORs instead: d + e, then + c, then + b. The cells stay at 4, but the bench prints slowest output change: 4 gate delays after an input change.
0 of 32 rows wrong 7 cells slowest output change: 3 gate delays after an input changeRead included file: cells.sv
// cells.sv: the unit-delay cell library (read-only).
// Every cell takes 1 time unit, whatever its fan-in. Ports are (y, inputs...): output first.
// Each cell adds 1 to the bench's cell counter when the simulation starts.
module INV (output wire y, input wire a); not #1 (y, a); initial tb.cells++; endmodule
module AND2 (output wire y, input wire a, b); and #1 (y, a, b); initial tb.cells++; endmodule
module OR2 (output wire y, input wire a, b); or #1 (y, a, b); initial tb.cells++; endmodule
module NAND2 (output wire y, input wire a, b); nand #1 (y, a, b); initial tb.cells++; endmodule
module NOR2 (output wire y, input wire a, b); nor #1 (y, a, b); initial tb.cells++; endmodule
Read included file: tb.sv
// tb.sv: the bench (read-only). It applies every input row and checks y. From every row it then
// changes one input at a time and times the last change of y, in gate delays. It also counts the cells.
module tb;
int cells; // every cell of cells.sv adds itself here
logic a = 0, b = 0, c = 0, d = 0, e = 0;
wire y;
lamp dut (.a(a), .b(b), .c(c), .d(d), .e(e), .y(y));
localparam logic [31:0] F = 32'b11111111111111100000000000000000; // bit m is f on row m
time last;
always @(y) last = $time;
initial begin
int wrong, worst;
time t0;
logic [4:0] row;
wrong = 0;
worst = 0;
for (int m = 0; m < 32; m++) begin
{a, b, c, d, e} = m[4:0];
#12;
if (y !== F[m]) wrong++;
for (int i = 0; i < 5; i++) begin
row = m[4:0];
row[i] = ~row[i];
t0 = $time;
last = t0;
{a, b, c, d, e} = row;
#12;
if (int'(last - t0) > worst) worst = int'(last - t0);
{a, b, c, d, e} = m[4:0];
#12;
end
end
$display("%0d of 32 rows wrong", wrong);
$display("%0d cells", cells);
$display("slowest output change: %0d gate delays after an input change", worst);
end
endmodule
Check Yourself
Common Mistakes
Wrong Factor as far as possible, always.
Each factoring step can add a level. A long chain of gates saves cells but is slow.
Fix Factor until the cell count is good, then check the delay against the budget.
Wrong Replace every AND by NAND and every OR by NAND, with no inverters.
The bubbles must cancel in pairs. A signal entering at an odd level needs its own inverter.
Fix Push bubbles level by level, and add an inverter where an input meets an unpaired bubble.
Wrong Count a five-input gate as one gate in a library of two-input cells.
With two-input cells, an n-input AND or OR needs n - 1 cells and several levels.
Fix Count the tree: n - 1 cells, and about log2(n) levels when it is balanced.
Remember
- Factoring shares literals and saves gates, but it can add levels and delay.
- With two-input cells, an n-input gate is a tree of n - 1 cells; balanced, it has about log2(n) levels.
- For NAND only, AND levels get output bubbles and OR levels get input bubbles; inputs at unpaired bubbles need inverters.
- Of the 16 two-level pairs, eight are useful: AND-OR, NAND-NAND, NOR-OR, OR-NAND, OR-AND, NOR-NOR, NAND-AND, AND-NOR.