Digital Logic Design: Gates That Decide, Flip-Flops That Remember

Press the button at a pedestrian crossing. Nothing happens. The cars keep going, and you wait, and then some seconds later the light changes for you. Between your press and the light, something held on to the fact that you had pressed. You are not holding the button down; the press was a moment, and the circuit kept it.

That act of remembering is what separates a calculator from a pile of switches. A circuit whose output depends only on its inputs right now is combinational: it decides. A circuit whose output also depends on what happened earlier is sequential: it has memory, so it has a past. Strip any digital chip down and you find only those two kinds, joined in loops, with a clock keeping the loops honest.

Boolean algebra: three gates, and NAND builds the rest

A wire is high or low, 1 or 0. A gate combines wires: AND outputs 1 only if both inputs are 1, OR outputs 1 if either is, NOT flips one. George Boole published the algebra of such true-or-false quantities in 1854, in An Investigation of the Laws of Thought. In 1937 Claude Shannon's MIT master's thesis showed that the same algebra describes networks of relay switches, which is the day logic became engineering.

The rule graduates carry is De Morgan's law: NOT (A AND B) equals (NOT A) OR (NOT B), and swapping AND and OR gives the other half. In words: "not both" means "at least one is missing". It lets you push inverters through a circuit and change one kind of gate into another.

A consequence surprises almost everyone: one gate type is enough. NAND (AND followed by NOT) can be wired as NOT, AND, OR and XOR. NOT is a NAND with both inputs tied together. AND is a NAND followed by that NOT. OR comes straight from De Morgan: NAND the two inverted inputs. XOR takes four.

Choose XOR and flip A and B. Each NAND in the list shows the value on its output wire; the last one is the answer. The check line runs all four input combinations against the real XOR.

Karnaugh maps: simplifying by finding neighbours

Many circuits that give the right answer are bigger than they need to be. The identity behind all shrinking is small: A·B + A·B′ = A. If a result is 1 both when B is 1 and when B is 0, then B does not matter, and the wire for B can be cut.

A Karnaugh map turns hunting for such pairs into looking. Lay the truth table out as a grid whose rows and columns are numbered 00, 01, 11, 10 (one bit changes at each step, so neighbours differ in exactly one variable). Then any block of 1s that is 2, 4 or 8 cells, rectangular, can be written as one short product term; each time the block doubles, one variable drops out. The grid also wraps around its edges. Veitch drew the chart in 1952 and Karnaugh refined it in 1953.

A worked case: the carry out of a full adder is 1 when at least two of A, B, C are 1 (the majority). Its map groups into three pairs, giving AB + AC + BC, instead of four terms of three variables each. Cells you will never see in practice can be marked don't care (X): the minimiser may treat them as 1 if that makes a bigger block. The program here is a real Quine–McCluskey minimiser.

Try "Majority of A, B, C": four terms collapse to three pairs. Try "Odd number of 1s": the 1s sit on a checkerboard, no two touch, and nothing simplifies: parity genuinely costs 8 terms. Last, "BCD digit is 5 or more" uses X for the six codes (10 to 15) that a decimal digit never takes; with them marked X the answer drops to A + BC + BD, three terms, against A′BC + A′BD + AB′C′ if you insist they be 0. Free choice in the inputs buys a smaller circuit.

Combinational blocks: a multiplexer is a lookup table

Three blocks do most of the deciding in a chip. A decoder takes an n-bit number and lights exactly one of 2ⁿ output lines; it is how a memory finds one row out of thousands. A multiplexer (mux) does the reverse job: n select wires choose which of 2ⁿ data inputs reaches the output. All are combinational: the output is a pure function of the inputs.

The idea worth keeping is hidden in the mux. Take an 8-to-1 mux and use A, B, C as the select wires. Now tie each of the eight data inputs to a fixed 0 or 1. The output is whatever you wrote on the data inputs, for each of the eight input combinations: the data inputs are the truth table. Change the eight bits and the same hardware computes a different function. That is a lookup table (LUT), and a k-input LUT holds 2^k bits and can be any of 2^{(2^k)} functions.

Press "Majority" and set A B C to 1 1 0: the output is 1, because two of three are high. Press "Parity" and the same select values give 0: nothing was rewired, only the stored bits changed. This is exactly what an FPGA is: a sea of such LUTs, each with a flip-flop beside it, joined by wiring that can also be programmed. The first commercial FPGA, Xilinx's XC2064 of 1985, had 64 configurable blocks, each computing a function of four inputs; modern ones commonly use 4 to 6. A 6-input LUT can be any of 2⁶⁴, about 1.8 × 10¹⁹, functions.

Timing: gates take time, and the slowest path sets the clock

Gates in diagrams answer instantly. Real gates take a short time, the propagation delay, because a transistor must charge a wire. Chain gates together and the delays add. Two things follow. First, the answer is wrong for a moment while signals race through different paths. Second, whatever reads the answer must wait until the slowest path has finished: the critical path.

The wrong-for-a-moment effect is a glitch (or hazard). Take A·B + A′·C with B = C = 1: the output should stay 1 whether A is 0 or 1. But when A flips, the inverter that makes A′ is a little late, so for an instant both terms are 0 and the output dips. On a Karnaugh map it is two blocks that touch without overlapping. Add the redundant term B·C to bridge them and the dip vanishes.

The critical path sets how fast the clock can run. Between two flip-flops the signal needs the flip-flop's own delay to launch, then the logic, then a small setup margin before the next edge:

Take the adder from Computer Architecture (34/25). In an N-bit ripple adder the last sum bit sits 2N gate levels from the inputs. The cure is carry-lookahead. For each column, g = a·b says "this column makes a carry by itself" and p = a⊕b says "this column passes a carry along". Then each carry unrolls into one flat expression, for example c₃ = g₂ + p₂g₁ + p₂p₁g₀ + p₂p₁p₀c₀, which is two gate levels no matter how wide the adder. The price is fan-in: the carry into the top bit needs a gate with about N inputs, and the carry logic grows roughly with the cube of N. Real designs look ahead in groups of four.

At 32 bits and 50 ps per gate, the ripple adder is 64 levels deep and its clock can be no faster than about 300 MHz; the lookahead version is 4 levels and could reach about 2.9 GHz, but needs a 32-input gate that does not exist. Slide the width down to 4 and the two nearly tie. Fast digital design is that trade: more hardware, shallower paths.

Flip-flops and the clock: how a wire remembers

Memory comes from a loop. Cross-couple two NOR gates, each one's output feeding the other's input, and the pair has two stable states: Q = 1 or Q = 0. Pulse Set and it goes to 1; pulse Reset and it goes to 0; release both and it stays, because each gate is holding the other in place. That is the SR latch, the smallest memory. Raise Set and Reset together and both outputs drop to 0; release them at the same moment and the result depends on which gate is faster, so the latch lands unpredictably.

A latch changes whenever its inputs do, which makes big circuits hard to reason about. The fix: let memory change only at one instant, an edge of a shared clock. A D flip-flop copies its D input to Q at the rising edge and ignores D at all other times (two latches back to back, open on opposite clock phases). Now the whole chip is a set of snapshots: between ticks the logic settles, at the tick every flip-flop captures its input together. That is why timing, above, is the clock's only constraint.

The catch is the setup window. If D changes too close to the edge, the flip-flop can end up halfway: neither 0 nor 1 for an unpredictable time, called metastability. It cannot be designed out, only made very unlikely; signals crossing between unrelated clocks pass through two flip-flops in a row for that reason.

Try Set on, then off: Q stays 1, which is memory. Then switch both on, then both off, and the latch reports an unknown state. In the flip-flop, change D freely and watch Q refuse to move until the edge. Then press "Change D just before the edge" and Q becomes "?".

Put several flip-flops side by side on one clock and you have a register: n bits captured at once. Feed a register's output through an incrementer and back into its input and you have a counter: each tick adds one. Feed each flip-flop from its neighbour and you have a shift register, which moves bits sideways. A counter is also a frequency divider: the lowest bit toggles every tick, the next every two, so each bit runs at half the speed of the one below. A watch crystal oscillates at 32,768 Hz, which is 2¹⁵, so fifteen divide-by-two stages leave exactly one pulse per second.

State machines: a vending machine you can step through

A register plus combinational logic that computes its next value from its current value and the inputs is a finite-state machine (FSM). The register holds the state (the machine's whole memory of its past). Each tick, logic reads the state and the inputs and decides the next state and the outputs. A crossing light is one: Green, Yellow, Red, and the button press moves it from "waiting" to "scheduled to change". Lifts, microwaves, protocol handlers and the control unit inside a processor are all FSMs.

Design recipe: list the situations (states), draw an arrow for every input that leaves each one, write the table, then pick a binary code for each state and turn the table into equations, which is what the Karnaugh map was for. n states need at least ⌈log₂ n⌉ flip-flops.

Our machine sells one item for 15 cents. It accepts nickels (N, 5¢) and dimes (D, 10¢), one coin per tick. It needs to remember how much money is in: three situations, 0¢, 5¢, 10¢, so two flip-flops. At 10¢ a dime makes 20¢, so it also returns one nickel. Outputs here depend on the state and the input (a "Mealy" machine); a crossing light whose outputs depend on state alone is a "Moore" machine.

Code the states 0¢ = 00, 5¢ = 01, 10¢ = 10, and call the two flip-flops S1 and S0. The code 11 never occurs, and a nickel and a dime never arrive together: those are don't-cares. Run the Karnaugh minimiser on the table (the same one in the map above) and the whole machine collapses to four short equations. Next state: S1′ = S1′·S0′·D + S1·N′·D′ + S0·N and S0′ = S1′·S0′·N + S0·N′·D′. Outputs: item = S1·N + S1·D + S0·D and change = S1·D.

Writing hardware: Verilog, VHDL and FPGAs

Nobody draws a million gates. Engineers write a hardware description language and let a tool, the synthesizer, turn it into gates, LUTs and flip-flops. The two main languages are Verilog (created by Phil Moorby at Gateway Design Automation in the mid-1980s, an IEEE standard since 1995) and VHDL (born from a US Department of Defense programme, an IEEE standard since 1987); SystemVerilog is Verilog's later extension.

The mental switch is hard: a program runs line by line, but a hardware description is a circuit, and all of it exists at once. Here is a free-running counter that drives an LED, the "hello world" of FPGA boards:

module blink(input clk, output led);
  reg [25:0] count = 0;
  always @(posedge clk)
    count <= count + 1;
  assign led = count[25];
endmodule

reg [25:0] asks for 26 flip-flops. The always @(posedge clk) block means "capture on the rising edge"; the <= means every register updates at the same instant; the adder after it is combinational, as in the sections above. Bit k of a counter toggles every 2^k ticks, so the LED, on bit 25, changes state every 2²⁵ ticks and completes a full blink in 2²⁶.

The answer is 2²⁶ ÷ 50,000,000 = 1.34 seconds per blink. With a 12 MHz clock the same code takes 11 seconds; pick a lower bit to blink faster.

An FPGA is not the only target. On an ASIC (a custom chip) the same code becomes fixed gates: much faster and smaller per function, and cheap per chip only when millions are made, because the masks cost a fortune. An FPGA is reprogrammable by loading a new bit-pattern, so it suits prototypes, low volumes and algorithms that may change.

What a graduate just sees

• A circuit either decides from the present (combinational) or also uses the past (sequential); every chip is both, joined by a clock.
• NAND alone is enough, and De Morgan lets you trade ANDs for ORs by moving inversions.
• If an output is 1 for both values of a variable, that variable is not needed: look for neighbours.
• Any truth table is a memory: a mux with the answers stored on its data inputs. That is a LUT, and an FPGA is a sea of them.
• Delays add along a path; the slowest path sets the clock; a wide, shallow circuit buys speed with fan-in.
• A flip-flop samples at the clock edge; if the input changes inside the setup window the result can be neither 0 nor 1.
• A counter divides frequency by two per bit; a register plus next-state logic is a state machine.
• State count sets flip-flop count: n states need ⌈log₂ n⌉ bits, and unused codes are free don't-cares.
• Hardware code describes a circuit that exists all at once, not a sequence of steps.

Where it shows up next

• Embedded Systems (34/41): the timers, counters and serial ports inside a microcontroller are the registers, dividers and state machines from this piece, fixed in silicon.
• Computer Architecture (34/25): the processor's arithmetic unit is combinational, its registers are flip-flops, and its control unit is a state machine; the pipeline stages are separated by registers exactly because of the clock rule above.
• Signals & Systems (34/37) and Communication Systems (34/40): filters and modems are often built on FPGAs, using the same LUTs, counters and shift registers.

If you want to go deeper

• 📘 Textbook: Sarah Harris and David Harris, Digital Design and Computer Architecture, RISC-V Edition (Morgan Kaufmann, 2021). Covers gates through to a processor, with SystemVerilog and VHDL side by side.
• 📘 Textbook: M. Morris Mano and Michael Ciletti, Digital Design: With an Introduction to the Verilog HDL, VHDL, and SystemVerilog (6th ed., Pearson). A standard second-year course text, strong on state machines and Karnaugh maps.
• 📘 Gentler: Charles Petzold, Code (2nd ed.), and Ben Eater's free video series building an 8-bit computer from logic gates on breadboards (eater.net/8bit).
• 🌐 Free course: MIT OpenCourseWare 6.111 Introductory Digital Systems Laboratory (Spring 2006): lectures, a traffic-light controller lab, and Verilog on an FPGA.
• 🌐 Free, hands-on: Nand2Tetris: build a computer from a NAND gate upwards.