How digital systems are built from logic gates — AND, OR, NOT, NAND, NOR, XOR. The 6-step combinational design procedure. Half-adder, full-adder, half-subtractor, and full-subtractor circuits. NAND as a universal gate. Sequential circuits and flip-flops — the memory elements that store state.
All digital logic circuits fall into one of two fundamental categories:
Every digital system — from a half-adder to a billion-transistor CPU — is built from a small set of basic logic gates. Each gate implements one Boolean operation:
The six fundamental logic gates. AND, OR, NOT are the primary gates from which all Boolean functions can be built. NAND = NOT-AND (bubble on output of AND), NOR = NOT-OR (bubble on output of OR). XOR (exclusive-OR) outputs 1 only when inputs differ — it is the basis of binary addition. NAND and NOR are universal: any circuit can be built using only one gate type.
A truth table enumerates every possible input combination and the resulting output. For n inputs there are 2ⁿ rows:
Truth tables for all six gates with 2-input configurations (NOT only uses input A). AND outputs 1 only when both inputs are 1. OR outputs 1 when either or both inputs are 1. XOR outputs 1 only when exactly one input is 1. NAND and NOR are the complement of AND and OR respectively. The NOT column ignores B.
The systematic 6-step procedure for designing any combinational circuit from a verbal problem statement:
A half-adder is a combinational circuit that adds two single bits and produces a 2-bit result (sum + carry). It is the simplest arithmetic circuit:
Inputs: x (augend), y (addend). Outputs: S (sum bit), C (carry out).
| x | y | C (carry) | S (sum) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 0 |
From the truth table, by inspection:
S = x’y + xy’ = x ⊕ y C = xy
S is the XOR of x and y. C is the AND of x and y. The most compact implementation uses one XOR gate and one AND gate.
Half-adder (left): XOR gate produces sum S = x⊕y; AND gate produces carry C = xy. The minimal 2-gate circuit. Full-adder (right): built from two half-adders and an OR gate. The first half-adder computes S₁=x⊕y and C₁=xy. The second adds S₁ with the incoming carry-in z, producing the final sum S=S₁⊕z and partial carry C₂=S₁·z. The final carry-out is C₁ OR C₂.
A full-adder adds three bits: x (augend), y (addend), z (carry-in from previous stage). Two outputs: S (sum), C (carry-out). This is the building block for ripple-carry adders — chain n full-adders to add n-bit numbers.
| x | y | z (Cᵢₙ) | C (carry-out) | S (sum) |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 | 0 |
| 1 | 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 1 | 1 |
S = 1 when an odd number of inputs are 1 (1 or 3 inputs = 1). C = 1 when two or more inputs are 1.
Simplified Boolean expressions:
S = x’y’z + x’yz’ + xy’z’ + xyz
C = xy + xz + yz
A half-subtractor computes x − y, producing a difference D and a borrow B. When x < y (0 − 1), the circuit borrows from the next higher stage:
| x (minuend) | y (subtrahend) | B (borrow) | D (difference) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 0 | 0 |
Boolean expressions:
D = x’y + xy’ = x ⊕ y (same logic as S in half-adder!)
B = x’y (borrow only when x=0 and y=1)
A full-subtractor computes x − y − z, where z is the borrow-in from a lower-significance stage. Three inputs, two outputs (D and borrow-out B):
| x | y | z (Bᵢₙ) | B (borrow-out) | D (difference) |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 |
Boolean expressions:
D = x’y’z + x’yz’ + xy’z’ + xyz (same as S in full-adder)
B = x’y + x’z + yz
NAND (and NOR) are called universal gates because any Boolean function can be implemented using only NAND gates (or only NOR gates). This is practically important: NAND gates are the most efficient gate to fabricate in CMOS technology — modern standard cell libraries are built primarily from NAND gates.
NAND gate implementing the three primary operations. NOT: tie both inputs together → output = (A·A)’ = A’. AND: NAND followed by a NOT (another tied-input NAND) → ((AB)’)’ = AB. OR: invert both inputs with NOT-NANDs, then feed to a NAND → (A’·B’)’ = A+B by De Morgan’s theorem. Since NOT, AND, and OR can all be built from NAND gates, NAND alone can implement any Boolean function.
Code conversion is a classic combinational design problem. BCD (Binary Coded Decimal) represents decimal digits 0–9 using 4 bits. Excess-3 represents the same digits by adding 3 to each BCD value. A converter is needed when two systems using different codes must communicate:
Inputs: A, B, C, D (4-bit BCD, 0–9) Outputs: w, x, y, z (4-bit Excess-3)
Key entries from truth table (excerpt):
| Decimal | BCD (ABCD) | Excess-3 (wxyz) |
|---|---|---|
| 0 | 0000 | 0011 |
| 1 | 0001 | 0100 |
| 4 | 0100 | 0111 |
| 7 | 0111 | 1010 |
| 9 | 1001 | 1100 |
Don’t-care inputs: BCD combinations 1010–1111 (10–15) never occur in valid BCD → treat as don’t-cares (X) in K-map for simplification.
Simplified Boolean expressions (after K-map with don’t-cares):
z = D’
y = CD + C’D’ = CD + (C+D)’
x = B’C + B’D + BC’D’ = B'(C+D) + B(C+D)’
w = A + BC + BD = A + B(C+D)
Key insight: The OR gate producing C+D is shared by expressions for x and w — this is multi-output optimisation. The shared gate reduces total gate count from 7 AND + 3 OR (sum of products) to 4 AND + 4 OR + 1 NOT. Don’t-care conditions reduced the complexity by allowing the K-map to form larger groupings.
Sequential circuits add memory to combinational logic. The fundamental memory element is a flip-flop — a bistable circuit that stores one bit indefinitely, changing state only in response to a clock edge and control inputs.
Sequential circuit structure (left): outputs depend on both current inputs and stored state. The memory block feeds back current state to the combinational logic; the clock synchronises updates. SR NAND latch (right): two cross-coupled NAND gates. The Q output wire (green) taps mid-wire and routes back down through the feedback path to NAND2’s top input. The Q̄ output wire (red) taps mid-wire and routes back up to NAND1’s bottom input. S’=0 sets Q=1; R’=0 resets Q=0; both at 1 holds state; both at 0 is forbidden.
| Flip-flop | Inputs | Behaviour | Primary use |
|---|---|---|---|
| SR (Set-Reset) | S, R | Set Q=1 (S=1), Reset Q=0 (R=1), Hold (S=R=0). Forbidden: S=R=1 | Debouncing switches, basic latches |
| D (Data) | D | On clock edge: Q ← D. The simplest clocked flip-flop — no forbidden state | Registers, pipeline stages, shift registers |
| JK | J, K | J=K=0: hold · J=1,K=0: set · J=0,K=1: reset · J=K=1: toggle (Q̄) | Counters, frequency dividers |
| T (Toggle) | T | T=0: hold · T=1: toggle (Q ← Q̄). Derived from JK with J=K=T | Binary counters — each stage divides frequency by 2 |
Every CMOS standard cell library (TSMC, Samsung, GF, Intel) is built primarily around NAND and NOR gates because they are the most area and power efficient gates in CMOS. A NAND2 cell in 7nm TSMC typically measures ~0.04 µm² and switches in ~15 ps. When you synthesise RTL with Design Compiler or Genus, the tool maps your Boolean logic to this library. The synthesis tool applies De Morgan transformations, logic restructuring, and technology mapping to convert arbitrary Boolean expressions into networks of NAND, NOR, INV, and complex cells (AOI/OAI — AND-OR-INVERT). Understanding that NAND is universal is what lets synthesis tools take any combinational logic and implement it efficiently — the 6-step design procedure you learned here is exactly what synthesis tools automate at scale.
A 32-bit ripple-carry adder chains 32 full-adders — the carry must ripple through all 32 stages before the output is valid. With each full-adder stage adding ~200 ps of carry propagation, a 32-bit ripple-carry adder has a critical path of ~6.4 ns — far too slow for modern GHz operation. The carry-lookahead adder (CLA) computes generate (G = A·B) and propagate (P = A⊕B) signals for every bit position in parallel, then computes all carry-outs simultaneously in a two-level logic network — reducing the critical path to ~1 ns. The full-adder’s Boolean equations (S = x⊕y⊕z, C = xy+xz+yz) are the starting point for deriving the G and P signals. When you work on timing closure for a 32×32-bit multiplier or a 64-bit ALU, reducing the adder critical path is often the most impactful optimisation — and it requires understanding the basic full-adder equations from this article.
In physical design, every D flip-flop has three critical timing parameters: setup time (data must be stable this long before the clock edge — typically 50–200 ps), hold time (data must remain stable this long after the clock edge — typically 0–50 ps), and clock-to-Q delay (time from clock edge to valid output — typically 100–300 ps). Timing analysis (STA — Static Timing Analysis) checks every combinational path between flip-flop output and the next flip-flop input to ensure setup time is met. A hold time violation is worse than a setup time violation — setup violations are fixed by reducing clock frequency, but hold violations cause functional failures even at reduced frequency and require inserting delay buffers. The clock distribution network (H-tree or spine) that delivers the clock edge simultaneously to millions of flip-flops is one of the most power-intensive design challenges — clocks consume 30–40% of total dynamic power in a modern CPU. Understanding D flip-flop behaviour from first principles is the foundation of all sequential circuit design and physical timing closure work.