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 + aeTwo-input cellsSlowest output change (gate delays)
Flat sum of products73
Factored, balanced: a ((b + c) + (d + e))43
Factored, as a chain: a (b + (c + (d + e)))44

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.

The flat sum of products
abcdef
000000
000010
000100
000110
001000
001010
001100
001110
010000
010010
010100
010110
011000
011010
011100
011110
100000
100011
100101
100111
101001
101011
101101
101111
110001
110011
110101
110111
111001
111011
111101
111111
The flat sum of productsn3 · ANDn3=0n4 · ANDn4=0n2 · ORn2=0n5 · ANDn5=0n1 · ORn1=0n6 · ANDn6=0n0 · ORn0=0a=0b=0c=0d=0e=0
a=0 b=0 c=0 d=0 e=0
n3 · ANDa=0, b=0 → n3=0
n4 · ANDa=0, c=0 → n4=0
n2 · ORn3=0, n4=0 → n2=0
n5 · ANDa=0, d=0 → n5=0
n1 · ORn2=0, n5=0 → n1=0
n6 · ANDa=0, e=0 → n6=0
n0 · ORn1=0, n6=0 → n0=0
Read the connections
GateKindInputsOutput
n3ANDa, bn3
n4ANDa, cn4
n2ORn3, n4n2
n5ANDa, dn5
n1ORn2, n5n1
n6ANDa, en6
n0ORn1, n6n0

Outputs: n0. MUX inputs: d0, d1, select. Latch/flip-flop inputs: data, enable/clock. Unknown values are marked x; high impedance is folded into x in this model.

Four AND gates feed one OR gate: two levels.

The factored form
abcdef
000000
000010
000100
000110
001000
001010
001100
001110
010000
010010
010100
010110
011000
011010
011100
011110
100000
100011
100101
100111
101001
101011
101101
101111
110001
110011
110101
110111
111001
111011
111101
111111
The factored formn3 · ORn3=0n2 · ORn2=0n1 · ORn1=0n0 · ANDn0=0a=0b=0c=0d=0e=0
a=0 b=0 c=0 d=0 e=0
n3 · ORb=0, c=0 → n3=0
n2 · ORn3=0, d=0 → n2=0
n1 · ORn2=0, e=0 → n1=0
n0 · ANDa=0, n1=0 → n0=0
Read the connections
GateKindInputsOutput
n3ORb, cn3
n2ORn3, dn2
n1ORn2, en1
n0ANDa, n1n0

Outputs: n0. MUX inputs: d0, d1, select. Latch/flip-flop inputs: data, enable/clock. Unknown values are marked x; high impedance is folded into x in this model.

One OR gate and one AND gate: still two levels, with wide gates.

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 nCellsLevels, balancedLevels, chain
2111
3222
4323
5434
8737
1615415

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.

Three Circuits for One LampEach box is one circuit. Its detail gives cells and the slowest output change, from the lab bench.
  • Datapath
  • Step
  • Structure
Three circuits for one lampEach box is one circuit. Its detail gives cells and the slowest output change, from the lab bench. datapath Flat SOP 7 cells, 3 gate delays datapath Factored,balanced 4 cells, 3 gate delays datapath Factored, chain 4 cells, 4 gate delays step Choose fewest cells insidethe delay budget factor out aunbalance the ORsbest here
  1. datapath Flat SOP7 cells, 3 gate delays
    • factor out a → Factored, balanced
  2. datapath Factored, balanced4 cells, 3 gate delays
    • unbalance the ORs → Factored, chain
    • best here → Choose
  3. datapath Factored, chain4 cells, 4 gate delays
  4. step Choosefewest cells inside the delay budget
  1. Factor

    Pulling out a removes three AND cells. The OR tree has the same depth, so the delay stays at 3.

  2. Over-factor

    Writing the OR as a chain keeps 4 cells but adds a level: 4 gate delays.

  3. 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)CellsSlowest output change (gate delays)
Flat: ac + bc + a'b'd84
Decomposed: x = a + b, then xc + x'd54

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.

f = (Ab + c)d + e as NAND GatesEach box is one gate of the converted circuit, from the input side on the left to the output on the right. Arrows show signals.
  • Datapath
  • Data
f = (ab + c)d + e as NAND gatesEach box is one gate of the converted circuit, from the input side on the left to the output on the right. Arrows show signals. datapath NAND(a, b) was AND: outputbubble datapath NAND(c, c) inverter for c datapath NAND(n1, c') was OR: input bubbles datapath NAND(n2, d) was AND: outputbubble datapath NAND(e, e) inverter for e datapath NAND(n3, e') was OR: input bubbles bubbles cancelc'ab + cbubbles cancele'
  1. datapath NAND(a, b)was AND: output bubble
    • bubbles cancel → NAND(n1, c')
  2. datapath NAND(n2, d)was AND: output bubble
    • bubbles cancel → NAND(n3, e')
  3. datapath NAND(n1, c')was OR: input bubbles
    • ab + c → NAND(n2, d)
  4. datapath NAND(n3, e')was OR: input bubbles
  5. datapath NAND(c, c)inverter for c
    • c' → NAND(n1, c')
  6. datapath NAND(e, e)inverter for e
    • e' → NAND(n3, e')
  1. AND to NAND

    Levels 1 and 3 were AND gates. Each becomes a NAND, which puts a bubble on its output.

  2. OR to NAND

    Levels 2 and 4 were OR gates. By De Morgan, an OR is a NAND with bubbles on both inputs.

  3. Unpaired bubbles

    Inputs c and e enter 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 NAND-only circuit, with its bubbles
The NAND-only circuit, with its bubblesg1 · NANDn1=1g2 · NANDcn=0g3 · NANDn2=1g4 · NANDn3=0g5 · NANDen=1g6 · NANDy=1a=0b=1c=1d=1e=0
a=0 b=1 c=1 d=1 e=0
g1 · NANDa=0, b=1 → n1=1
g2 · NANDc=1, c=1 → cn=0
g3 · NANDn1=1, cn=0 → n2=1
g4 · NANDn2=1, d=1 → n3=0
g5 · NANDe=0, e=0 → en=1
g6 · NANDn3=0, en=1 → y=1
Read the connections
GateKindInputsOutput
g1NANDa, bn1
g2NANDc, ccn
g3NANDn1, cnn2
g4NANDn2, dn3
g5NANDe, een
g6NANDn3, eny

Outputs: y. MUX inputs: d0, d1, select. Latch/flip-flop inputs: data, enable/clock. Unknown values are marked x; high impedance is folded into x in this model.

Gate delay 14. Settled after 14 gate delays from t = 0.

Output values at each gate delay01234567891011121314yxxxx11110000001
Scroll horizontally ↔
Every computed frame
Timey
0x
1x
2x
3x
41
51
61
71
80
90
100
110
120
130
141

  1. Step 0 · Start. Here a, b and d are 1, so y is 1.
  2. Step 4 · a falls. Now n1 rises, n2 falls, n3 rises and y falls. That is four NAND delays.
  3. Step 10 · c rises. c enters through its inverter cell, then the NAND that was an OR. y rises again after four delays.

Click an input pin to change it. Each NAND output bubble cancels a bubble at the next input; c and e need their own inverters.

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 levelFormFunction of x1 to x4
AND-ORsum of productsx1 x2 + x3 x4
NAND-NANDsum of productsx1 x2 + x3 x4
OR-ANDproduct of sums(x1 + x2)(x3 + x4)
NOR-NORproduct of sums(x1 + x2)(x3 + x4)
AND-NORAND-OR-INVERT(x1 x2 + x3 x4)'
NAND-ANDAND-OR-INVERT(x1 x2 + x3 x4)'
OR-NANDOR-AND-INVERT((x1 + x2)(x3 + x4))'
NOR-OROR-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 levelCollapses to
AND-ANDone gate of the four inputs
AND-NANDone gate of the four inputs
OR-ORone gate of the four inputs
OR-NORone gate of the four inputs
NAND-ORone gate of the four inputs
NAND-NORone gate of the four inputs
NOR-ANDone gate of the four inputs
NOR-NANDone 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.

  1. Group the 0s

    For f = a' + b'c', the 0s of f give f' = ab + ac.

  2. AND-NOR

    Two AND gates for ab and ac, and one NOR: f = (ab + ac)'. Three gates.

  3. OR-NAND, the dual

    A product of sums of f' works the same way: OR gates, then one NAND.

  4. NOR only

    With a NOR2-only library, push the bubbles again. Problem G3.8.3 asks for the fewest NOR2 cells.

Asked in interviews
  1. 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.

  2. 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.

  3. 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.

RUNIcarus Verilog · in your browser
Edit the code, then run it
Expected: 0 of 32 rows wrong 7 cells slowest output change: 3 gate delays after an input change
Read 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

Predict the outputAn AND of eight inputs is built as a balanced tree of two-input cells. The program prints its cells and levels. Predict the line.
module tb;
  initial $display("%0d cells, %0d levels", 8 - 1, $clog2(8));
endmodule
Spot the bugEach option is a factored form of f = ab + ac + ad + ae. The bench compares it with f on all 32 rows. Which one fails?
ConceptWhich two-level form implements a product of sums directly, with no inverted inputs?
ConceptFactoring cut a circuit from 9 cells to 6, but its delay grew from 3 to 5 gate delays. The budget is 4. What should you do?
ConceptWhich pair of gates is degenerate as a two-level form?

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.

Practice

Report a problem with this page