The adder computes. Most of the other circuits in a CPU route: they pick one value out of several, turn a number into a "select this one" signal, or check whether two values are equal. They're all combinational circuits — their outputs depend only on their current inputs, with no memory. Memory comes in the next chapter.
The multiplexer: choosing one input
A multiplexer (mux) has several data inputs, one output, and select lines that say which input goes through. The smallest has two data inputs and one select line:
| D0 | D1 | S | Y |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
Y = S ? D1 : D0. The select line opens exactly one AND gate; the OR merges the two paths. This is the hardware form of an if/else. Try D0 = D1 = 1 and flip S from 1 to 0: the inverter adds one delay, so for an instant neither AND is open and Y glitches to 0.
Unit-delay model: every gate takes one step to react. With auto off, toggle switches and press step to watch the change travel gate by gate.
Y = S ? D1 : D0. The select line opens exactly one of the two AND gates, and the OR merges the two paths. It's the hardware form of if/else, or of C's ?: operator. x86's cmov is essentially a multiplexer whose select line comes from the flags.
It also shows a real hardware hazard. Set D0 = D1 = 1, so Y should stay 1 whatever S is. Now turn auto off, flip S from 1 to 0 and step. The inverter on the select line adds one gate delay, so for an instant neither AND gate is open and Y glitches to 0 before coming back to 1. Glitches like this are harmless in a clocked design, where values are only captured once they've settled, but they're why the timing of every path matters.
Wider multiplexers follow the same pattern: 2ⁿ data inputs need n select lines. A 4-to-1 mux can be built from three 2-to-1 muxes in a tree, or from four AND gates, each opened by one combination of the select lines, feeding one OR.
Multiplexers are everywhere in a CPU:
- the ALU's output mux picks the result of the selected operation;
- the datapath uses muxes to choose which register feeds each ALU input, and where results go;
- forwarding in a pipeline is a mux in front of each ALU input, choosing between the register file and a newer result.
A multiplexer can compute anything
Wire the data inputs of an 8-to-1 mux to fixed 0s and 1s, and use the select lines as three variables: the mux outputs whatever you wired to the input numbered by those three bits. Wire input i to row i of a truth table, and the mux is that function. For the majority function from the gates chapter, D0…D7 = 0, 0, 0, 1, 0, 1, 1, 1.
This is exactly how FPGAs work. Their basic element is a lookup table (LUT): a small memory holding a truth table, read out through a multiplexer driven by the inputs. By loading different tables, the same chip becomes any circuit.
The reverse circuit, a demultiplexer, sends one input to one of several outputs, chosen by the select lines.
The decoder: turning a number into a selection
A decoder takes an n-bit number and sets exactly one of its 2ⁿ outputs to 1: output k for input k.
| A1 | A0 | Y0 | Y1 | Y2 | Y3 |
|---|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 | 0 | 1 |
Exactly one output is 1: output number A. The true and inverted input rails feed one AND per combination. Address decoders like this select one memory row or one register out of many.
Unit-delay model: every gate takes one step to react. With auto off, toggle switches and press step to watch the change travel gate by gate.
Each output is an AND gate enabled by one combination of the inputs (and their inversions). Decoders are how a CPU selects things by number:
- memory: the high bits of an address pick which chip or bank answers, and the chip's own decoders pick the row;
- registers: the 4-bit register number in an instruction selects one of 16 registers. The datapath chapter showed how encoding a bus source as a small number, then decoding it, guarantees that only one register drives the bus;
- instruction decoding: the opcode is turned into the control lines of the operation to perform.
The opposite circuit, an encoder, outputs the number of whichever input is 1. A priority encoder outputs the number of the highest input that's 1 when several are. That's how a CPU picks the most urgent interrupt, and it's the circuit behind instructions like bsr and lzcnt.
The comparator
Checking two numbers for equality takes one XOR per bit pair (1 where they differ) and a final NOR (1 only if no bit differs):
Each XOR outputs 1 where the two bits differ; the NOR outputs 1 only if no bit differs. Wider comparators just add XORs. Checking A − B for zero with the ALU (what cmp does) gives the same answer through ZF.
Unit-delay model: every gate takes one step to react. With auto off, toggle switches and press step to watch the change travel gate by gate.
Set A and B to the same value and A = B lights up. Change any single bit and it goes out. A CPU's cmp reaches the same answer another way: it subtracts in the ALU and tests the result for zero, which is ZF, and it gets less-than and greater-than from the other flags at the same time.
Buses: sharing wires
A bus is a set of wires shared by several sources. The rule is that only one source may drive it at a time: two outputs pushing different values onto the same wire create a short circuit. There are two ways to enforce the rule:
- A multiplexer: every source goes into a mux, and the select lines choose which one reaches the bus. Inside modern chips, buses are built this way.
- Tri-state buffers: each source connects through a buffer that outputs 0, 1, or a third state, high impedance, which electrically disconnects it. A decoder enables exactly one buffer at a time. That's how external buses with many devices were traditionally built, and how a memory chip's data pins let go of the bus when the chip isn't selected.
Either way, a decoder and some select lines decide who talks, and the system bus of the microarchitecture level is this idea scaled up.
Takeaways
- Combinational circuits have outputs that depend only on their current inputs.
- A multiplexer chooses one of 2ⁿ inputs with n select lines. It's the hardware
?:, and wired to a truth table it computes any function — the principle of FPGA lookup tables. - A decoder turns an n-bit number into one active line out of 2ⁿ. It selects memory chips, registers and operations.
- A comparator checks equality with XORs and a NOR. The CPU usually gets the same answer from the ALU's ZF.
- A bus is shared wiring, driven by one source at a time, chosen by a multiplexer or by tri-state buffers enabled by a decoder.