Logic gates and universal gates

Why it exists

A logic gate is the smallest physical building block of a digital circuit: it takes one or more bits and produces one bit as a fixed Boolean function of them. Everything in a processor, from an adder to a register, is a network of a few kinds of gates. Two questions follow, and both appear in GATE. First, which small sets of gates are enough to build every function? (NAND alone, and NOR alone.) Second, given a function, what is the cheapest network in a given gate type, measured in gates or levels? Knowing the standard conversions makes these mechanical.

Prerequisites

You need the laws of Boolean algebra, above all De Morgan and the double-complement law.

Precise definitions

Basic gates. Each output depends only on the present inputs (that is what makes a network of gates combinational).

Symbols. AND and OR are drawn with a flat and a curved back; a small circle (a bubble) on an input or output means complement. NAND is AND with an output bubble; NOR is OR with an output bubble; XOR has an extra curve on the input side of OR. The triangle is the buffer; with a bubble it is the NOT gate.

Multi-input gates. AND, OR, XOR can have $n$ inputs because they are associative. A 2-input-gate tree needs $n - 1$ gates and $\lceil \log_2 n \rceil$ levels for an $n$-input AND, OR or XOR. NAND and NOR are not associative: $(A \uparrow B) \uparrow C \ne A \uparrow (B \uparrow C)$, so a 3-input NAND is not two 2-input NANDs in a row; it equals $(ABC)'$, which needs an AND-then-invert structure.

Universal gate. A gate is universal if every Boolean function can be built using only that gate (with inputs and constant lines allowed). NAND and NOR are universal. AND, OR, XOR are not.

Constructions from NAND ($\uparrow$ denotes NAND):

• NOT: $A' = A \uparrow A$ (1 gate).
• AND: $AB = (A \uparrow B) \uparrow (A \uparrow B)$ (2 gates).
• OR: $A + B = (A \uparrow A) \uparrow (B \uparrow B)$ (3 gates).
• XOR: $N_1 = A \uparrow B$, $N_2 = A \uparrow N_1$, $N_3 = B \uparrow N_1$, $A \oplus B = N_2 \uparrow N_3$ (4 gates).

Constructions from NOR ($\downarrow$ denotes NOR): NOT $A' = A \downarrow A$; OR $A + B = (A \downarrow B) \downarrow (A \downarrow B)$; AND $AB = (A \downarrow A) \downarrow (B \downarrow B)$. By duality these mirror the NAND constructions.

Two-level realisations.

• NAND-NAND. Any SOP is implemented by NAND gates in two levels: one NAND per product term (with the literals as inputs) feeding one NAND that produces the OR. Reason: $((P_1)'(P_2)'\cdots)' = P_1 + P_2 + \cdots$ by De Morgan, where $(P_i)'$ is the output of the first-level NAND. For example $AB + CD = ((AB)'(CD)')'$.
• NOR-NOR. Any POS is implemented by NOR gates in two levels: one NOR per sum term feeding one NOR. For example $(A+B)(C+D) = ((A+B)' + (C+D)')'$.
• A single-literal product term needs only an inverter (or the literal itself) as a first-level input.

Bubble pushing. An AND gate with inverted inputs is a NOR gate, and an OR gate with inverted inputs is a NAND gate (De Morgan drawn as a symbol swap). Moving a bubble across a gate and changing the gate type preserves the function; this is the picture behind the NAND-NAND rule.

XOR and XNOR. XOR gives 1 when its inputs differ. An $n$-input XOR gives 1 when an odd number of inputs are 1 (odd parity); XNOR is its complement. Both are associative and commutative.

Cost measures. The gate count (sometimes the literal count, or the number of gate inputs), the number of levels (propagation delay is roughly proportional to the levels), and the fan-in (inputs per gate) and fan-out (gates driven by one output). In static CMOS, a NAND or NOR with $n$ inputs uses $2n$ transistors, while AND and OR need an extra inverter after the NAND or NOR, which is why NAND and NOR are the natural gates.

How it works

Step through the 4-gate XOR built from NAND gates. The columns are the outputs of the gates $N_1, N_2, N_3, N_4$ and the XOR of the inputs; the last two columns are compared. Then step through the table that shows NAND is not associative.

Method for converting a circuit to NAND only: first write the SOP (minimal if possible). Replace every AND by a NAND and the final OR by a NAND. Put an inverter on any single-literal term that enters the second level uncomplemented (a literal $x$ entering the output NAND needs its complement $x'$ at the first level). Count the gates: one per product term of two or more literals, one for the output, and one inverter per literal that needs one.

Worked examples

#include <stdio.h>
 
static int nand(int a, int b) { return !(a && b); }
static int not_(int a) { return nand(a, a); }
static int and_(int a, int b) { return not_(nand(a, b)); }
static int or_(int a, int b) { return nand(not_(a), not_(b)); }
static int xor_(int a, int b) {
    int n1 = nand(a, b);
    return nand(nand(a, n1), nand(b, n1));
}
 
int main(void) {
    printf("A B | NOT A  AND  OR  XOR  (built from NAND only)\n");
    for (int a = 0; a < 2; a++)
        for (int b = 0; b < 2; b++)
            printf("%d %d |   %d     %d    %d    %d\n", a, b, not_(a), and_(a, b), or_(a, b), xor_(a, b));
    int same = 0;
    for (int i = 0; i < 16; i++) {
        int a = (i >> 3) & 1, b = (i >> 2) & 1, c = (i >> 1) & 1, d = i & 1;
        same += nand(nand(a, b), nand(c, d)) == ((a && b) || (c && d));
    }
    printf("NAND-NAND matches AB+CD on %d of 16 rows\n", same);
    int differ = 0;
    for (int i = 0; i < 8; i++) {
        int a = (i >> 2) & 1, b = (i >> 1) & 1, c = i & 1;
        differ += nand(nand(a, b), c) != nand(a, nand(b, c));
    }
    printf("(A nand B) nand C differs from A nand (B nand C) on %d of 8 rows\n", differ);
    return 0;
}

A B | NOT A  AND  OR  XOR  (built from NAND only)
0 0 |   1     0    0    0
0 1 |   1     0    1    1
1 0 |   0     0    1    1
1 1 |   0     1    1    0
NAND-NAND matches AB+CD on 16 of 16 rows
(A nand B) nand C differs from A nand (B nand C) on 4 of 8 rows

Cheat box

Traps and GATE patterns

Connections

Universality is formalised in functional completeness and duality. The expressions come from minterm and maxterm forms, and the whole design flow from specification to gates is in combinational design. The adder cell in adders and subtractors is two XOR gates and a majority circuit.

PYQs

Which one of the following expressions does NOT
represent exclusive NOR of x and y?

Which one of the following circuits is NOT
equivalent to a 2-input XNOR (exclusive NOR) gate?

What is the boolean expression for the output of the
combinational logic circuit of NOR gates given
below?

What is the minimum number of gates required to
implement the Boolean function (AB+C) if we
have to use only 2-input NOR gates?

The following expression was to be realized using
2-input AND and OR gates. However, during the
fabrication all 2-input AND gates were mistakenly
substituted by 2-input NAND gates.

(a.b).c + (a'.c).d + (b.c).d + a.d . What is the
function finally realized?

Consider the following logic circuit diagram.

Which is/are the CORRECT option(s) for the output
function F?

Self-check

Revision card

References