Universal Gates: NAND-Only and NOR-Only Logic
Build NOT, AND, OR and XNOR from one kind of gate, and count the gates each one needs.
You Will Be Able To
- Build NOT, AND and OR from NAND gates and from NOR gates.
- Turn a sum of products into NAND-NAND and a product of sums into NOR-NOR.
- Build XNOR from four NOR gates.
- Count the gates of a one-kind netlist against the known minimum.
- Lesson
- G2.6
- Time
- 25 min
- Runs on
- Your browser
- Check
- 5 questions
A test chip has room for one kind of logic cell: a two-input NAND. The block still needs OR, XOR and a majority vote. Three NAND gates make an OR.
- Cycle 0
Both inputs are 0. Both inverters give 1, and the NAND of 1 and 1 is 0.
- Cycle 1
b is 1, so b' is 0. A NAND with a 0 input gives 1.
- Cycle 3
The output column is 0111: the column of OR.
Computed from the three gates and confirmed by the lab below on Icarus.
One Gate Is Enough
A set of gates is complete when it can build every function. AND, OR and NOT together are complete. So a gate that can build those three is complete on its own. NAND and NOR are such universal gates.
- Datapath
- Structure
- NOT
Tie both inputs of a NAND to a. The output is (aa)' = a'.
Follow the calls, values and waits
- data (aa)' = a': NAND → NOT
- AND and OR
AND is a NAND followed by NOT. OR is a NAND of the two inverted inputs.
Follow the calls, values and waits
- data ab: NOT → AND
- data a + b: NOT → OR
- Every function
With AND, OR and NOT you can write any truth table as a sum of products. So NAND alone builds it.
Read the diagram as text
- NAND: the only cell
- NOT: inputs tied: 1 cell
- AND: NAND then NOT: 2 cells
- OR: NOT on each input, then NAND: 3 cells
- Any function: a sum of products
- NAND → NOT: tie inputs
- NOT → AND: invert a NAND
- NOT → OR: invert the inputs
- AND → Any function: products
- OR → Any function: sum
NOR works the same way with the roles of AND and OR swapped.
| Function | From NAND | From NOR |
|---|---|---|
| NOT a | (aa)' | (a + a)' |
| a AND b | ((ab)')' : a NAND, then a NAND used as NOT | (a' + b')' : NOR of the two inverted inputs |
| a OR b | (a'b')' : NAND of the two inverted inputs | ((a + b)')' : a NOR, then a NOR used as NOT |
Tie the two inputs of a NAND or a NOR together and it is an inverter.
| Function | Fewest NAND2 gates | Fewest NOR2 gates |
|---|---|---|
| NOT | 1 | 1 |
| AND | 2 | 3 |
| OR | 3 | 2 |
| NAND | 1 | 4 |
| NOR | 4 | 1 |
| XOR | 4 | 5 |
| XNOR | 5 | 4 |
| majority of three | 6 | 6 |
| half adder: sum and carry together | 5 | 5 |
Found by trying every netlist of two-input gates, smallest first. The inputs are available only in true form.
The table has a pattern. Swap NAND with NOR and AND with OR, and the counts swap too. That is duality again: a NAND circuit for f becomes a NOR circuit for the dual of f.
AND-OR Is NAND-NAND, OR-AND Is NOR-NOR
A sum of products is a level of AND gates feeding one OR gate. Push a pair of bubbles onto every wire between the levels. Every gate becomes a NAND, and the function stays the same.
A product of sums is OR gates feeding one AND gate. The same move makes every gate a NOR.
XNOR from Four NOR Gates
XNOR is 1 when its two inputs are equal. With NOR gates alone it needs four, and no netlist does it with three.
Read the middle gates as products. n2 = a'b and n3 = ab', so y = (a'b + ab')', the complement of XOR.
Asked in interviews
Why are NAND and NOR called universal gates?
Each one alone can build NOT, AND and OR, and those three build every function. Tie both inputs together for NOT, then add bubbles for AND and OR.
How many NAND gates does an XOR need?
Four. An exhaustive search over every netlist of two-input NAND gates shows that three are not enough. XNOR needs five: an XOR plus an inverter is five, and the search finds nothing smaller.
Why do standard-cell libraries favour NAND over NOR?
In CMOS a NAND has its NMOS in series and its PMOS in parallel. A NOR stacks the slower PMOS in series, so it needs wider transistors for the same speed. Lesson G9.2 measures it.
Try It
The cell library in cells.sv has six cells. Each one adds itself to a counter in the bench, so the bench can report what a netlist uses.
AND takes two NAND cells and OR takes three. The bench prints both columns and the count, 5.
Change or_n to the wrong guess: NAND2 u1 (t, a, b); followed by NAND2 u2 (y, t, t);. The OR column becomes 0001.
Build NOR from NAND cells in a third module. The exhaustive search says four cells is the fewest. The bench counts yours.
AND from NAND2: 0001 OR from NAND2: 0111 NAND2 cells: 5, other cells: 0Read included file: cells.sv
// cells.sv: the cell library (read-only). Every cell takes 2 time units.
// Ports are (y, inputs...): output first. Each cell adds 1 to its own counter in the bench.
// While the bench sets poison to 1, every cell output is x.
module INV (output wire y, input wire a); wire g; not #2 (g, a); assign y = tb.poison ? 1'bx : g; initial tb.n_inv++; always @(tb.recount) tb.n_inv++; endmodule
module NAND2 (output wire y, input wire a, b); wire g; nand #2 (g, a, b); assign y = tb.poison ? 1'bx : g; initial tb.n_nand2++; always @(tb.recount) tb.n_nand2++; endmodule
module NOR2 (output wire y, input wire a, b); wire g; nor #2 (g, a, b); assign y = tb.poison ? 1'bx : g; initial tb.n_nor2++; always @(tb.recount) tb.n_nor2++; endmodule
module NAND3 (output wire y, input wire a, b, c); wire g; nand #2 (g, a, b, c); assign y = tb.poison ? 1'bx : g; initial tb.n_nand3++; always @(tb.recount) tb.n_nand3++; endmodule
module NOR3 (output wire y, input wire a, b, c); wire g; nor #2 (g, a, b, c); assign y = tb.poison ? 1'bx : g; initial tb.n_nor3++; always @(tb.recount) tb.n_nor3++; endmodule
module XOR2 (output wire y, input wire a, b); wire g; xor #2 (g, a, b); assign y = tb.poison ? 1'bx : g; initial tb.n_xor2++; always @(tb.recount) tb.n_xor2++; endmodule
Read included file: tb.sv
// tb.sv: the bench (read-only). It prints the output columns and counts the cells.
module tb;
int n_inv, n_nand2, n_nor2, n_nand3, n_nor3, n_xor2; // the cells add themselves here
logic poison = 0; // 1 forces every cell output to x
event recount; // makes every cell add itself again
logic a, b;
wire y_and, y_or;
string col_and = "", col_or = "";
and_n u_and (.a(a), .b(b), .y(y_and));
or_n u_or (.a(a), .b(b), .y(y_or));
initial begin
for (int i = 0; i < 4; i++) begin
{a, b} = i[1:0];
#10; // five cell delays: enough to settle
col_and = {col_and, y_and ? "1" : "0"};
col_or = {col_or, y_or ? "1" : "0"};
end
$display("AND from NAND2: %s", col_and);
$display("OR from NAND2: %s", col_or);
$display("NAND2 cells: %0d, other cells: %0d", n_nand2, n_inv + n_nor2 + n_nand3 + n_nor3 + n_xor2);
end
endmodule
Check Yourself
Common Mistakes
Wrong Map AND-OR to NOR-NOR, or OR-AND to NAND-NAND.
Bubble pushing pairs AND-OR with NAND-NAND, and OR-AND with NOR-NOR. The other pairing gives the dual function.
Fix A sum of products becomes NAND-NAND. A product of sums becomes NOR-NOR.
Wrong Forget the inverter for a single input that enters the second level.
In NAND-NAND, a lone literal x feeds the output NAND. That gate inverts it, so it needs x' at its input.
Fix Feed a single literal through a NAND with its inputs tied, or use its complement directly.
Wrong Build OR as NAND followed by an inverter.
NAND then NOT is AND. OR needs the inverters on the inputs: (a'b')' = a + b.
Fix Invert each input with a NAND, then NAND the two results: three gates.
NAND2 u1 (t, a, b);
NAND2 u2 (y, t, t); // AND: 0001NAND2 u1 (na, a, a);
NAND2 u2 (nb, b, b);
NAND2 u3 (y, na, nb); // OR: 0111Wrong Count only the gates of the textbook drawing.
An inverter made from a NAND is one more NAND. Every gate in the netlist counts.
Fix Count every instance. The exhaustive search gives the minimum to compare with.
Remember
- NAND alone and NOR alone are each complete. Tie the inputs together for NOT.
- AND-OR becomes NAND-NAND, and OR-AND becomes NOR-NOR, by bubble pushing.
- Fewest gates: OR from NAND 3, AND from NOR 3, XOR from NAND 4, XNOR from NOR 4.
- Swapping NAND with NOR gives the dual function, and dual circuits have the same size.