Logic Gates: Where Software Stops and Physics Starts
A gate is a few transistors that compute one Boolean function of its inputs. Everything above — arithmetic, memory, control, the entire machine — is gates composed with other gates, and the two properties that matter are that composition is universal and that propagation takes time.
Software view, hardware view
The gap between what you wrote and what the machine does is where this whole domain lives.
Universality: NAND is enough for everything
A gate implements one Boolean function. AND, OR, NOT and XOR are the familiar ones, but the remarkable result is that a single gate type suffices: NAND is functionally complete, meaning every Boolean function can be built from NAND gates alone. NOR is too. Nothing else is needed.
The constructions are short. NOT is a NAND with both inputs tied together. AND is a NAND followed by that NOT. OR is a NAND of two inverted inputs, by De Morgan's law. Once you have those three, you have everything, because any truth table can be written as a sum of products.
This is not a party trick — it is why chip fabrication works. A process can optimise a small number of gate types very heavily and compose everything from them, rather than needing a distinct physical design per operation. The table below shows the constructions and the cost in gate delays, which is the quantity that turns into clock speed.
| Target | Construction from NAND | Gate delays |
|---|---|---|
| NOT a | NAND(a, a) | 1 |
| AND a b | NOT(NAND(a, b)) — NAND then invert | 2 |
| OR a b | NAND(NOT a, NOT b) — De Morgan | 2 (inverters in parallel) |
| XOR a b | Four NANDs in the standard arrangement | 3 |
| Any Boolean function | Sum of products: AND terms, then OR them | Depends on depth, not on input count |
Propagation delay is why clocks have a limit
A gate does not switch instantly. When an input changes, the output takes a short interval to settle — transistors must charge and discharge the capacitance of the wires and the gates they drive. That interval is the propagation delay, and it is a physical property of the process, the voltage and the load.
Delays add along a path. A circuit whose longest input-to-output path passes through twenty gates takes twenty gate delays to produce a stable answer. That longest path is the critical path, and it sets the maximum clock frequency directly: the clock period must exceed it, or the next stage will latch a value that has not finished settling.
This is the honest answer to "why not just raise the clock". You cannot, unless you shorten the critical path — by using fewer levels of logic, by splitting the work across more pipeline stages so each stage is shorter (Pipelining: Throughput Without Making Anything Faster), or by changing the circuit for one with less depth. It is also why raising voltage to switch faster runs into a thermal wall, which is where The Clock Is a Variable and The First Ten Seconds Lie take over.
Composing gates into something useful
The bridge from gates to a machine is the multiplexer — a circuit that selects one of several inputs based on a control signal. It is a handful of gates, and it is the hardware equivalent of a conditional: control drives the selector, and one input reaches the output.
That is worth pausing on, because it is where the CPU's control logic comes from. An The ALU: Where Arithmetic Actually Happens that can add, subtract, AND and OR does not choose between four circuits — it computes several results in parallel and uses a multiplexer to select which one leaves. The The Control Unit: Turning Instructions Into Actions is, at bottom, machinery for driving those selectors from the decoded instruction.
This also explains why "doing less work" does not always make hardware faster. The adder ran regardless of whether its result was selected. In software, skipping work saves time; in combinational hardware, unselected work has already happened in parallel. Speculative execution is this idea taken to its conclusion — computing things that may not be needed because the hardware to do so is already sitting there.
Key points
- A gate computes one Boolean function from a few transistors; NAND alone is sufficient to build every other function.
- Propagation delay is the time for a gate's output to settle, and delays accumulate along a path.
- The longest path through the logic — the critical path — sets the maximum clock frequency directly.
- A multiplexer selects one of several inputs, and is how conditional behaviour is built in hardware.
- Unselected results in combinational logic were still computed; skipping work does not save time the way it does in software.
Logic Gates
Change an input and watch which number moves — and which one refuses to.
| 0 | 0 | → | 0 |
| 0 | 1 | → | 0 |
| 1 | 0 | → | 0 |
| 1 | 1 | → | 1 |
One gate does almost nothing. The interesting part is that combining a few thousand of them produces arithmetic, and a few billion produces a processor.
Follow the mechanism
The path through the machine, hop by hop — and the conclusions it invites that are wrong.
- 1Input change → transistors: a voltage change causes transistors to begin switching, charging or discharging the load.
- 2Transistors → output settle: after the propagation delay the output reaches a stable, valid logic level.
- 3Gate → next gate: the settled output drives the following stage, and the delay accumulates along the path.
- 4Critical path → clock period: the longest such path determines the shortest safe clock period for the circuit.
- 5Clock edge → register: at the edge, the settled value is captured into a storage element — see Adding Memory: Combinational, Sequential and the Clock.
- • Assuming clock speed is a design choice that could be raised at will rather than a consequence of circuit depth.
- • Believing that reducing the number of operations always reduces hardware time; unselected parallel results cost nothing extra.
- • Treating gate delay as constant when it depends on load, voltage, temperature and manufacturing variation.
Consequences, controls and cost
- • Clock frequency cannot be raised beyond what the critical path allows, no matter how much power is available.
- • Reducing logic depth is the direct route to a faster clock, which is a primary motivation for pipelining.
- • Circuits that compute several results in parallel and select one are common, because the hardware exists anyway.
- • Deeper logic means fewer stages fit in a cycle, so architectural choices and achievable clock speed are coupled.
- • Almost nothing directly — this level is fixed by the time software runs. What you can do is understand why the clock is what it is.
- • Recognise that instruction throughput, not clock rate alone, determines performance ([[ipc]], [[the-clock]]).
- • Expect the CPU to compute speculatively rather than to skip work, because parallel hardware makes that cheaper than waiting.
- • Not measurable from software. The observable proxies are clock frequency under load and the effects of thermal and power limits.
- • Compare instructions retired against cycles to see how much of the clock is actually being used ([[ipc]]).
- • Watch reported frequency during a sustained benchmark; it will not stay at the nominal figure ([[frequency-scaling]]).
- • Faster circuits generally use more gates and more power — carry-look-ahead addition buys depth at a substantial area cost.
- • Deeper pipelines allow higher clocks but make each misprediction more expensive ([[branch-misprediction]]).
- • Higher voltage switches faster and generates heat superlinearly, which is where the practical ceiling comes from.
Scope
§224 — what these claims are specific to.
- SIMPLIFIEDGates are treated as ideal with a single fixed delay. Real designs account for fan-out, wire delay, clock skew, setup and hold times, and process variation.
- PLATFORM-SPECIFICAbsolute gate delays depend on the fabrication process, supply voltage and temperature, and improve with each process generation. Only the relative depths shown here transfer.