1.2 — From Gates to Machines

In 1.1 we earned a switch, and from switches, gates: NOT, AND, OR, NAND. But a gate has amnesia. The instant its inputs change, its output changes — it holds nothing. A machine built only of gates can react, never remember, and a computer that can't remember can't add two numbers, run a loop, or hold a single pixel on screen.

This chapter closes two gaps. First, combinational logic: wiring gates so their arrangement computes arithmetic — we'll build an adder that genuinely adds. Second, and deeper, memory and time: coaxing a loop of gates into holding a bit, then marching those bits forward under a drumbeat called the clock. By the end you'll have every ingredient of a CPU except the blueprint, which is 1.5.

1. Combinational logic — arrangement is computation

A combinational circuit is any network of gates whose output depends only on its current inputs — no memory, no history. Feed it the same inputs, always get the same outputs, after a tiny settling delay. All of arithmetic lives here.

Take the simplest sum in the universe: one bit plus one bit. Binary says 0+0=0, 0+1=1, 1+0=1, and 1+1=10 — that's zero, carry one. So adding two bits produces two outputs: a sum bit and a carry bit. Write the truth table and stare:

A	B	Carry	Sum
0	0	0	0
0	1	0	1
1	0	0	1
1	1	1	0

The Sum column is 1 exactly when the inputs differ — that's XOR (exclusive-OR), the "one or the other but not both" gate. The Carry column is 1 exactly when both are 1 — that's AND. So:

\text{Sum} = A \oplus B \qquad \text{Carry} = A \cdot B

Two gates, and you've built a machine that adds. It's called a half adder, "half" because it can't accept a carry coming in from a lower column.

Figure 1 — The half adder. XOR produces the sum bit, AND produces the carry. Arrangement is computation: no memory, just gates wired to mirror binary addition.

To add real multi-bit numbers you need to accept a carry from the column to your right. Chain the logic into a full adder (three inputs: A, B, carry-in; two outputs: sum, carry-out), then wire n of them in a row — each one's carry-out feeding the next one's carry-in — and you have a ripple-carry adder that adds two n-bit numbers. That column-by-column carry is exactly how you add on paper, now in silicon. (The catch — each column must wait for the carry to "ripple" up from the previous one, so a 64-bit ripple adder is slow; real CPUs use cleverer carry-lookahead adders that compute carries in parallel. The idea is the same; only the speed differs.)

The same recipe — write the truth table, read off the gates — builds every combinational block:

• A multiplexer (mux) is a selector: several data inputs, a few "select" control lines, one output. The select lines choose which input reaches the output — a data traffic switch, the hardware if/switch. Its opposite, the demultiplexer, routes one input to a chosen output.
• Decoders turn an n-bit number into "activate line number n" — how a memory address picks one row out of millions.
• Comparators, shifters, the ALU (arithmetic-logic unit — the CPU's calculator that adds, subtracts, ANDs, ORs, shifts on command) are all just larger combinational networks.

Everything so far is memoryless. Time to break that.

2. The feedback trick — a circuit that remembers

Here's the leap that feels like magic the first time. Take two NOR gates and wire each one's output back into the other's input — a loop. (Recall NOR: output is 1 only when both inputs are 0.)

Figure 2 — The SR latch. Two cross-coupled NOR gates. The feedback loop lets the pair settle into one of two stable states and stay there — the first circuit with memory.

Call the outputs Q and Q̄ (Q-bar, its opposite). With both inputs at 0, the loop has two self-consistent solutions: Q=1 holding itself up, or Q=0 holding itself down. It latches onto whichever it's in and stays — that stored value is one bit of memory. Pulse the Set input to force Q=1; pulse Reset to force Q=0. Release both, and it remembers the last command. This is the SR latch, and every memory cell descends from this cross-coupled loop. Memory isn't a new kind of physics — it's the same gates, bent into a circle so a value can hold itself up by its own bootstraps.

But a raw latch is twitchy: it reacts to its inputs the moment they wiggle, and in a chip with billions of signals settling at slightly different times, "the moment" is chaos. We need to control when memory is allowed to change.

3. The clock — a heartbeat for the machine

Add a control input — an enable — so the latch listens only when enabled and ignores its inputs otherwise. Now drive that enable with a clock: a signal that flips 0-1-0-1 at a fixed rate, the machine's heartbeat. A "3 GHz" CPU has a clock ticking three billion times per second.

One refinement makes it bulletproof. A latch that's "open" for the whole half-cycle can still let changes race through. So we build the flip-flop: a cell that samples its input only on the clock's edge — the sharp instant the clock rises from 0 to 1 — and holds that value rock-steady until the next rising edge. A D flip-flop ("D" for data) is the workhorse: whatever D is at the tick, Q becomes, and stays.

Figure 3 — Edge-triggered timing. The flip-flop samples D only at each rising clock edge and holds the result until the next. Between ticks, the world can churn; the stored value doesn't move.

This is the discipline that tames a billion-transistor chip: nothing that matters changes except at a clock edge. Between ticks, combinational logic churns and settles; on the tick, flip-flops snapshot the settled answer all at once. Line up several D flip-flops sharing one clock and you have a register — a small box that holds an n-bit number (say 32 or 64 bits) and updates as a unit. Registers are the CPU's hands: the fastest storage in the machine, where numbers sit while being worked on.

Two timing facts fall out, and they rule all of hardware:

• Setup and hold time. The input must be stable for a sliver before and after the edge. Violate that window — catch the signal mid-flight — and the flip-flop can go metastable, hovering between 0 and 1 (the ghost promised in 1.1). It resolves, but the when is unpredictable, which is exactly why crossing signals between two different clocks needs special care.
• The clock can't outrun the logic. Between two ticks, the signal must race through all the combinational gates and settle before the next edge samples it. The slowest such path — the critical path — sets the maximum clock speed. Want a faster chip? Shorten the longest path. This is why CPU frequency isn't a free dial: physics, not marketing, sets the ceiling.

4. Finite state machines — logic that has a past

Now combine the two halves — combinational logic that computes and registers that remember — and you get the most important pattern in all of digital design: the finite state machine (FSM). A register holds the current state; combinational logic looks at that state plus the inputs and computes two things: the outputs, and the next state, which the clock loads back into the register on the tick.

Figure 4 — The finite state machine. State remembered in a register; combinational logic decides outputs and the next state; the clock closes the loop. Every controller, protocol, and CPU is this diagram scaled up.

This little loop is startlingly universal. A traffic light is an FSM (states: green → yellow → red, advancing each tick). So is a vending machine (states track coins inserted), a USB controller, a network protocol handshake, the lock screen on your phone — and, at the summit, the control unit of a CPU, whose states are fetch → decode → execute, stepping through instructions one clock edge at a time. When you meet the CPU in 1.5, you'll recognize it instantly: it is this exact figure, wearing a crown.

FSMs are also where software and hardware rhyme. The switch-on-a-status-field you write to model an order moving through placed → paid → shipped → delivered is a finite state machine in code — same idea, same discipline of "given state and input, compute next state." (That software pattern gets its own serious treatment in Part 9.5.) Learn the shape once here, in gates, and you see it everywhere for the rest of your career.

5. The expert lens

Synchronous design is a civilization-scale bargain. Nothing forces a chip to use a global clock — asynchronous (clockless) circuits exist and can be faster and lower-power. But reasoning about a billion signals with no shared "now" is brutally hard, so the entire industry accepted one simplifying tyranny: a global heartbeat, and the rule that state changes only on the edge. Almost every chip you'll ever touch is synchronous because that bargain makes design tractable — a recurring theme you'll see again in distributed systems (Part 10), where the absence of a shared clock across machines is precisely what makes them hard.

The clock is also the enemy. That \alpha C V^2 f from 1.1 has f in it — every clock tick, the clock signal itself switches every flip-flop's enable across the whole chip, burning power even when no useful work happens. Modern chips spend enormous effort on clock gating (switching off the clock to idle regions) precisely because the heartbeat is one of the biggest power draws. The thing that makes the machine tractable is also the thing eating its battery.

Registers are why "cache-friendly" will matter. The register is the top of a memory hierarchy you'll build in 1.6: a handful of registers (sub-nanosecond) → caches → RAM → disk, each ~10–100× slower than the last. Every performance story in this book — from tight loops to database indexes — is ultimately about keeping the data you need close to those flip-flops.

Next chapter: we've been saying "an n-bit number" on faith. 1.3 makes it precise — how bits actually encode numbers (including negative ones), why adders overflow, and the byte, the nibble, and the hexadecimal shorthand every engineer reads in their sleep.

Recall

• Combinational logic has no memory: output depends only on current inputs. Writing a truth table and reading off gates builds adders, multiplexers, decoders — the ALU.
• A half adder is Sum = A ⊕ B, Carry = A · B; chaining full adders makes a multi-bit adder (carry ripples up the columns).
• Cross-couple two NOR gates and the feedback loop holds a bit — the SR latch, ancestor of all memory.
• A clock gates when memory may change; an edge-triggered flip-flop samples its input on the tick and holds it; several together make a register. Setup/hold violations cause metastability; the critical path caps clock speed.
• Combinational logic + a state register = a finite state machine: given state and inputs, compute outputs and the next state. Every controller — up to a CPU's fetch-decode-execute — is an FSM.

Self-test: Which gate gives the sum bit, which gives the carry, and why? How do two NOR gates remember a bit? What does a rising clock edge do to a D flip-flop? What two pieces make an FSM, and what flows around its loop?

Quiz Bank

FoundationalWhat's the difference between combinational and sequential logic?

Combinational logic's output depends only on its current inputs — no memory (adders, muxes, decoders). Sequential logic contains memory (latches, flip-flops, registers), so its output depends on inputs and stored history. The bridge between them is the clock: combinational logic computes, sequential elements remember the result on each edge.

FoundationalBuild a half adder from gates and explain each output.

Two one-bit inputs A, B. Sum = A ⊕ B (XOR: 1 when they differ) and Carry = A · B (AND: 1 only when both are 1). It's a "half" adder because it has no carry-in; a full adder adds that third input so adders can be chained into multi-bit ripple-carry units.

AppliedWhy do real CPUs avoid plain ripple-carry adders for wide numbers?

In a ripple-carry adder each bit's carry-out must settle before the next bit can finalize, so worst-case delay grows linearly with width — a 64-bit add would wait for a carry to ripple through 64 stages, lengthening the critical path and capping clock speed. CPUs use carry-lookahead (and hybrids) that compute carries in parallel from the inputs, trading more gates for much shorter delay.

AppliedWhat is a register, and why is it the fastest storage in a computer?

A register is a group of D flip-flops sharing a clock, holding an n-bit value that updates as a unit on the edge. It's fastest because it's right next to the logic that uses it — no addressing, no bus, sub-nanosecond access — which is why it sits at the very top of the memory hierarchy (1.6) and why compilers work hard to keep hot variables "in registers."

InterviewExplain metastability and give one real situation where it bites.

If a flip-flop's input changes inside its setup/hold window (too close to the clock edge), the cell can enter a metastable state — output hovering between 0 and 1 — and take an unpredictable time to resolve. It bites when a signal crosses from one clock domain to another (different, unrelated clocks): the receiving flip-flop can't guarantee the input is stable at its edge. The standard defense is a synchronizer (two flip-flops in series) to make an unresolved state astronomically unlikely by the time the signal is used.

InterviewWhat sets the maximum clock frequency of a synchronous chip?

The critical path: the longest combinational delay between any two registers. Within one clock period the signal must leave a register, propagate through all intervening logic, and settle (meeting the next register's setup time) before the edge samples it. Max frequency ≈ 1 / (critical-path delay + setup + clock overhead). To go faster you shorten the longest path — often by pipelining, inserting registers to break it into shorter stages (Chapter 1.5).

StaffWhy did the whole industry standardize on synchronous (clocked) design despite asynchronous circuits sometimes being faster and lower-power?

Tractability. A global clock imposes a shared notion of "now": state changes only on the edge, so a designer reasons about discrete steps instead of a continuous race among a billion signals with independent timing. That makes timing analysis, verification, and tooling feasible at scale. Asynchronous design can win on paper but the reasoning and verification cost is enormous, so it stays niche. It's the same theme that makes distributed systems hard in Part 10 — there, machines genuinely have no shared clock, and you pay for it in complexity.

Flashcards

FlashSum and carry of a half adder

Sum = A ⊕ B (XOR); Carry = A · B (AND).

FlashWhat a multiplexer does

Selects one of several data inputs to pass to its single output, chosen by control (select) lines — the hardware if/switch.

FlashSimplest memory circuit

The SR latch — two cross-coupled NOR (or NAND) gates whose feedback loop holds one bit.

FlashWhat a D flip-flop does on a clock edge

Samples input D at the rising edge and holds that value on Q until the next edge (edge-triggered).

FlashRegister

A row of D flip-flops on a shared clock, holding an n-bit value that updates as a unit.

FlashFinite state machine = ?

State register + combinational next-state/output logic, looped through the clock: (state, inputs) → (outputs, next state).

FlashCritical path

The longest combinational delay between registers; it caps the clock frequency.

Scenario Drill

DrillYou're modeling an e-commerce order that moves placed → paid → shipped → delivered, with rules about which transitions are legal. A teammate wants a tangle of boolean flags (isPaid, isShipped…). Argue for an FSM instead, borrowing this chapter's vocabulary.

Independent flags let illegal combinations exist (isShipped=true while isPaid=false) and scatter the transition rules across the code. Model it as a finite state machine: one state field is the current state (the "register"), and a single transition function is the combinational "next-state logic" — given (state, event) it returns the next state or rejects the move. Benefits mirror the hardware: illegal states become unrepresentable, every transition lives in one place, and the whole thing is trivially diagrammable and testable. It's the same pattern you just built in gates — a register holding state, logic deciding the next one — which is why the discipline transfers directly. (Part 9.5 develops this into the production "status-driven pipeline" pattern.)