Adding Two Numbers in Hardware

This is the first article of Module 2, and it starts with what looks like the easiest problem in the module: adding two numbers. You have AND, OR, XOR and NOT gates, wires, and voltage levels meaning 0 and 1. From those you have to produce 17 + 25 = 42. It sounds simple. Hidden inside it is a sequential dependency that has kept adder designers busy for sixty years, and it shapes the datapath of every processor made today. This article is about that dependency. The rest of the section is about getting round it.

Addition by hand

When you add 17 and 25 on paper you work column by column from the right:

Ones: 7 + 5 = 12, write 2, carry 1. Tens: 1 + 2 + 1 = 4. The important thing is the carry. The tens column could not finish until the ones column had finished and handed its carry across. The columns are not independent; they are sequential.

Binary is the same with smaller digits. 17 is 00010001 and 25 is 00011001. Each column takes two input bits and whatever carry arrived from the right, and produces one sum bit and one carry to the left.

One column

Strip it down to a single column. The inputs are a bit from each number, $A_i$ and $B_i$, and a carry-in $C_{in}$ from the column to the right. The outputs are the sum bit $S_i$ and a carry-out $C_{out}$ to the left. Three inputs, two outputs. An $N$-bit adder is this circuit repeated $N$ times with each carry-out wired to the next carry-in. That part is simple. The complication is in the chain.

The carry chain

To compute the sum at position $i$ you need the carry into position $i$. That carry is the carry out of position $i-1$, which needs the carry out of $i-2$, and so on back to position 0. The carry ripples from right to left, and every bit above bit 0 has to wait for it.

In a 64-bit adder, bit 63 cannot produce its sum until the carry from bit 62 arrives, which cannot happen until bit 61 has finished, and so on down. In the worst case, all 64 positions are involved in passing one carry from the bottom to the top, one after another.

What that costs

A desktop processor runs at 3 to 5 GHz. At 3 GHz a clock period is about 333 ps, and a 64-bit addition has to complete inside it. A gate delay in a modern process is something like 20 to 50 ps; call it 30.

The obvious adder, where each carry waits for the previous one, has a carry path of around 130 gate delays for 64 bits (we do the exact arithmetic in the third article). At 30 ps each that is about 3.9 ns, more than ten times the clock period. This is not a theoretical concern. It is the reason the rest of this section exists.

Processor companies have whole teams working on adders. The synthesis tool that turns A + B in your Verilog into gates spends real effort choosing and tuning an adder structure to meet the timing you gave it. The 4-bit adders you build in this section are the ancestors of all of them, with the same generate and propagate signals scaled up.

Three ways to be faster

Every fast adder attacks the same bottleneck, the carry chain, and there are three broad strategies.

Do not wait. Can the carry into position $i$ be computed directly from the inputs $A$ and $B$, without waiting for it to pass through positions 0 to $i-1$? Yes. This is carry lookahead, and it makes the carry computation a small fixed number of gate delays.

Guess both ways. Can a block of bits compute two results at once, one assuming its carry-in will be 0 and one assuming 1, and pick the right one when the carry arrives? Yes. This is carry select, and it buys speed with extra hardware.

Skip. For some inputs a block of bits just passes the carry through unchanged. Can that be detected and the block bypassed? Yes. This is carry skip, a moderate speed-up for a small cost.

Each makes a different trade between gate count, wiring and delay.

The plan for this section

Half adder and full adder: the one-column circuit, derived from truth tables and built from gates.
Ripple-carry adder: $N$ full adders in a chain. Correct, simple, and slow in a way we can calculate exactly.
Carry-lookahead adder: generate and propagate, and delay that grows with $\log N$ instead of $N$.
Carry-select adder: compute both outcomes and choose. Delay grows with $\sqrt{N}$.
Trade-offs: all of them side by side, the FPGA against the ASIC, and what synthesis tools actually do.

The idea underneath all the fast adders is the same: rewrite the problem so that each intermediate result depends on the original inputs rather than on the previous intermediate result. The carry chain is a dependency graph and the job is to flatten it. That same idea comes back in out-of-order execution, branch prediction and prefetching. Adder designers just met it first.

In the next article we build the two smallest arithmetic circuits, the half adder and the full adder, from their truth tables.