The Full Adder and the Ripple

The half adder produces a carry and cannot accept one. Every column except the rightmost needs to accept one, so we need a third input.

Call it carry in. Three inputs now: A, B and the carry arriving from the column to the right.

Three inputs, eight rows

Three questions make eight cases, as Truth Tables promised. Here is the whole behaviour:

Two things to notice in that grid.

The sum column is on whenever an odd number of inputs are on. One, or all three. That is XOR again, applied to three wires instead of two.

The carry column is on whenever at least two inputs are on. A carry happens when the column overflows, and with three bits arriving it overflows the moment any two of them are 1.

Building it

Take it in two steps, because a full adder is two half adders with their carries collected.

First add A and B, exactly as before. Then add the carry in to that result. Each of those additions can throw a carry, and either one is enough to carry into the next column, so an OR collects them.

Five gates. Set all three inputs on and trace it: the first XOR goes dark because both its inputs are lit, the second XOR sees that 0 against the carry in and lights the sum, and the first AND lights the carry out.

Chaining them

One full adder handles one column. To add whole numbers, use one per bit and hand each carry out to the next adder’s carry in.

Each box is the five gates you just built. We draw them as boxes because you know what is inside, and because an eight-bit version is forty gates and nobody can read that.

This is a ripple-carry adder, and the name describes what happens. A carry out of the rightmost column becomes the carry in of the next, which may produce a carry of its own, and so on leftwards. The carry ripples along the chain.

Widen it to eight boxes and you can add any two bytes. That is the adder from Counting in Twos, the one that made 5 + 251 come out at zero when the ninth bit fell off the end. The bit that falls off is the carry out of the last box, with nowhere left to go.

What this cost

Count what you have built. A half adder is two gates. A full adder is five. An eight-bit ripple adder is eight of those, so forty gates, and it can add any two bytes on any machine in this curriculum.

Now hold that number against a real processor.

A modern one has billions of transistors on it, and a gate takes a handful of transistors. The 8-bit processors in these machines were far smaller, a few thousand transistors, but even that is hundreds of gates wired into things far less obvious than an adder.

The point is not the size. It is that there is nothing else in there. No layer you have not seen. A processor is this, repeated: parts whose whole behaviour is a small grid, wired so that the grids add up to arithmetic. You have understood one completely, and the rest is more of it.

When it’s wrong, see why

• The last carry disappeared. It did. The carry out of the leftmost column has nowhere to go, which is exactly the wrap-around from Counting in Twos.
• A sum bit is wrong further left than where you looked. Check the carry chain. A wrong carry poisons every column above it, so find the rightmost wrong bit first.
• You wired the carry into the wrong end. Carries travel from the small end to the big end, the same direction you carry on paper.

What you’ve learnt

• A full adder takes three inputs, because every column but the first receives a carry.
• Its sum is XOR of all three, and its carry is on when at least two inputs are.
• It is five gates, built as two half adders with an OR collecting the carries.
• Chaining one per bit gives a ripple-carry adder, where the carry travels along the chain.
• The carry off the end is the wrap-around you already met.

Where this leaves you

You have built the part of a processor that does the arithmetic, out of three tables you learned in an afternoon.

That is the honest bottom of the machine. Everything above it, the instructions and the registers and the screen, is more of the same, arranged with more patience than you would want to draw. When you write ADD in assembly, this is what receives it.

The road from here goes into a real machine. Meet the Machine takes the byte you have been reading all this time and shows you where it lives, and what happens when the screen comes looking for it.