The binary adder

The binary adder

The circuit below is an adder for binary numbers encoded serially, least-significant bit first. (Fans of big-endian architectures are invited to try to design one that works with incoming data presented most-significant bit first.) We’ve added dots of copper alongside the input and output wires to make it easier to see what is happening: these dots don’t contribute to the operation of the adder. At generation 0 the top input to the adder is ‘011’ (which is 3 in decimal) and the bottom input to the adder is ‘110’ (6 in decimal). Forty-eight generations later the result ‘1001’ (9 in decimal) appears at the output.

How does it work?

Just below the centre of the device is a flip-flop. This stores the current state of the carry; call this C. Call the lower input to the adder A and the upper input B.

The leftmost component of the adder is an exclusive-OR gate. This calculates A EOR B. The output of this gate goes to a (simple) AND-NOT gate just below, whose other input is A. The output of this AND-NOT gate is thus A AND NOT (A EOR B), which (as you may verify by considering separately the cases where A is 0 and where A is 1) is the same as A AND B. This signal is used to set the carry flip-flop.

There is a second AND-NOT gate, right in the middle of the device. One input is A EOR B and the other is fed by a continuous stream of ones generated by a small loop just to its north-east; its output is thus NOT (A EOR B). This signal is used to clear the flip-flop. The timing of the signals to the flip-flop is arranged so that if both set and clear signals are active, the set takes priority.

The overall effect on the flip-flop state is thus as follows.

If both A and B are zero, there is definitely no carry from this bit into the next; if exactly one of A and B is one, the carry out of this bit is the same as the carry in to it; and if both A and B are one, there is definitely a carry out of this bit.

The final step is to exclusive-OR the carry state C with A EOR B to give one bit of result.

The adder structure described here is called a ‘propagate-generate adder’: A AND B generates a carry from the current bit, and A EOR B propagates a carry through it. Many fast adders implemented on real integrated circuits use exactly this technique. The simpler ‘ripple carry’ structure, where each bit explicitly computes sum and carry outputs as direct functions of its inputs A and B and the carry output from the previous bit, are generally slower. This is especially true in Wireworld, where such a design would imply a long feedback loop in the circuit, greatly limiting the maximum speed of operation.

Next we shall start building the computer proper.

<Previous page  Wireworld index  Next page>