Arithmetic Circuits
Every processor is built round an adder. This volume builds one from the gates of the earlier volumes: a half adder, a full adder, then a chain of them that adds whole numbers. It turns the adder into a subtractor with two's complement, shows when the answer overflows, and measures why a ripple-carry adder is slow and how carry look-ahead makes it fast.
- How half and full adders work, and how to build a full adder from two half adders
- How a ripple-carry adder adds whole numbers, and why its delay grows with its width
- How one circuit can add and subtract using two's complement
- What overflow is, and the one-gate test that detects it
- How carry look-ahead computes every carry at once
6.1 Half and full adders
Adding two bits gives a sum bit and a carry bit. A half adder adds two bits; a full adder adds three - two bits plus the carry from the column before. Chain full adders together and you can add numbers of any length.
Volume 01 added binary numbers by hand, column by column, carrying 1 whenever a column made 2 or more. This volume builds a circuit that does exactly that. It is the heart of every processor.
The half adder
Adding two bits can give 0, 1 or 2. Written in binary, 2 is 10, so the answer needs two bits: a carry, C, and a sum, S.
| A | B | C | S |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 0 |
The C column is AND, and the S column is XOR - both from Volume 02:
A + B as a 2-bit number C S on every row: True
The full adder
In every column but the first, there are three bits to add: A, B and the carry in from the column to the right, Cin. Three bits add up to at most 3, which is 11 in binary, so two output bits are still enough: Cout and S.
| A | B | Cin | Cout | S |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 | 0 |
| 1 | 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 1 | 1 |
The sum is 1 when an odd number of inputs are 1: a three-input XOR. The carry is 1 when at least two are 1 - the majority function from Volume 03. A neat way to build it is from two half adders and an OR gate:
A + B + Cin as a 2-bit number Cout S on every row: True
A·B + Cin·(A ⊕ B) = A·B + A·Cin + B·Cin on every row: True
A full adder has A = 1, B = 1 and Cin = 1. What are Cout and S?
Show the answer
Answer: B. 1 + 1 + 1 = 3, which is 11 in binary. So the carry out is 1 and the sum bit is 1.
6.2 The ripple-carry adder
A ripple-carry adder is a row of full adders, each passing its carry to the next. It is simple and small, but slow: the carry has to ripple through every stage before the answer is ready.
Four full adders in a row
To add two 4-bit numbers, use one full adder per column. Each carry out becomes the next column's carry in, exactly as when you add by hand:
The simulator added every pair of 4-bit numbers through this very figure, with a carry in of 0 and of 1:
figure ripple4: S and C4 equal A + B + C0 on all 512 inputs: True
Here are three of those additions, including Volume 01's pair:
0110 + 0111 = 01101: 6 + 7 = 13
1011 + 0110 = 10001: 11 + 6 = 17
1111 + 0001 = 10000: 15 + 1 = 16
The carry ripples
Every gate takes a little time, and the carry must pass through two gates - an AND and an OR - in every full adder. The last sum bit cannot be right until the carry has rippled all the way along.
The worst case is 1111 + 0001, where a carry starts in bit 0 and has to pass through every stage. In Figure 6.4 every gate takes one time step:
4-bit ripple adder, worst case: the last output settles 8 steps after the inputs change
8-bit ripple adder, worst case: the last output settles 16 steps after the inputs change
16-bit ripple adder, worst case: the last output settles 32 steps after the inputs change
The delay grows in step with the number of bits: double the width, and the adder takes twice as long. A 64-bit ripple adder would be far too slow for a processor. Sub-module 6.5 shows the way out.
Why is 1111 + 0001 the slowest case for a ripple-carry adder?
Show the answer
Answer: C. The carry made in bit 0 changes the carry into bit 1, which changes bit 2, and so on. The last stage cannot settle until that carry has rippled through every full adder in turn.
6.3 Subtraction with two's complement
To subtract, add the two's complement: A - B = A + B' + 1. One adder can do both jobs if XOR gates invert B on request, and the same control line supplies the + 1 as the first carry in.
Volume 01 showed that -B is B inverted, plus 1. So a subtraction is just an addition:
7 - 5: 0111 + 1010 + 1 = 10010 -> keep 4 bits: 0010 = 2 as two's complement
5 - 7: 0101 + 1000 + 1 = 01110 -> keep 4 bits: 1110 = -2 as two's complement
12 - 3: 1100 + 1100 + 1 = 11001 -> keep 4 bits: 1001 = -7 as two's complement
The last line needs care. 12 does not fit in 4-bit two's complement, which only reaches 7, so 1100 is really -4, and -4 - 3 = -7 is right. Whether the bits mean 12 or -4 is up to whoever reads them.
One circuit for both
An XOR gate is a switchable inverter (Volume 02): B ⊕ 0 = B and B ⊕ 1 = B'. So put an XOR gate on each B input, driven by a control line, Sub. When Sub = 0 the adder adds. When Sub = 1, every bit of B is inverted, and Sub also feeds the first carry in, supplying the + 1.
4-bit adder-subtractor: S = A + B when Sub = 0 and A - B when Sub = 1, on all 512 inputs: True
In the adder-subtractor, what does the Sub line do when it is 1?
Show the answer
Answer: A. With Sub = 1, each XOR gate passes B inverted, and Sub itself is the carry into bit 0. Together they add B' + 1, which is -B, so the adder computes A - B.
6.4 Overflow
Overflow happens when the true answer does not fit in the bits available. For signed numbers there is a simple test: overflow happened if the carry into the top bit differs from the carry out of it.
Four-bit two's complement runs from -8 to 7. Add two numbers whose true sum lies outside that range, and the bits that come out read as the wrong number:
| Sum | Bits | Result bits | Reads as | True answer | Overflow |
|---|---|---|---|---|---|
| 3 + 2 | 0011 + 0010 | 0101 | 5 | 5 | no |
| 5 + 4 | 0101 + 0100 | 1001 | -7 | 9 | yes |
| -3 + -2 | 1101 + 1110 | 1011 | -5 | -5 | no |
| -6 + -5 | 1010 + 1011 | 0101 | 5 | -11 | yes |
| 6 + -3 | 0110 + 1101 | 0011 | 3 | 3 | no |
| 7 + 1 | 0111 + 0001 | 1000 | -8 | 8 | yes |
Two positive numbers gave a negative result, and two negative numbers gave a positive one. That is the first way to spot overflow: the inputs have the same sign, and the result has the other sign. Adding a positive and a negative number can never overflow.
Spotting it in hardware
Inside the adder there is a quicker test. Compare the carry into the top bit, C3, with the carry out of it, C4. If they differ, the result has overflowed. The simulator checked that both tests agree on every pair of 4-bit numbers:
overflow = C3 XOR C4 = "same signs in, other sign out" on all 256 pairs: True
So one XOR gate, V = C3 ⊕ C4, is all it takes. Processors store it as the overflow flag.
Treating the carry out as the overflow for signed numbers. For unsigned numbers, a carry out of the top bit does mean the answer was too big. For signed numbers it does not: 6 + -3 makes a carry out of the top bit, yet 3 is exactly right.
In 4-bit two's complement, which of these additions overflows?
Show the answer
Answer: D. 7 + 1 = 8, but 4-bit two's complement stops at 7. The bits come out as 1000, which reads as -8: two positive inputs, and a negative result.
6.5 Carry look-ahead: a faster adder
A carry look-ahead adder works out every carry at once, straight from the inputs, instead of waiting for it to ripple. Each column says whether it will generate a carry or propagate one, and two levels of gates combine those signals.
Generate and propagate
Look at one column on its own. It generates a carry if A and B are both 1, whatever comes in. It propagates a carry - passes an incoming carry on - if exactly one of A and B is 1:
- Generate: G = A·B
- Propagate: P = A ⊕ B
Then a carry out of a column happens if the column generates one, or if it propagates the carry coming in. Written out for the second carry, every carry becomes a formula in G, P and C0 alone:
C2 = G1 + P1·G0 + P1·P0·C0 matches the ripple carry on every row: True
gate-level look-ahead adder adds correctly on all 512 inputs: True
Read the formula as a sentence. A carry comes out of bit 1 if bit 1 generates one. It also comes out if bit 1 propagates a carry that bit 0 generated, or if both bits propagate the carry that came in.
How much faster?
Every carry now passes through the same few gates: one level for G and P, then an AND and an OR. The simulator ran the worst case, 1111 + 0001, through both designs:
1111 + 0001 with look-ahead: the carries settle C1 at 2, C2 at 3, C3 at 3, C4 at 3 steps after the inputs change
4 bits, worst case: ripple settles in 8 steps, look-ahead in 4
No carry waits for another: the last one arrives after three steps instead of eight, and the whole sum is ready in half the time. (C1 is a step quicker than the rest here only because C0 is 0, so its AND term has nothing to add.) The price is gates, and wide ones:
the widest gate in the 4-bit look-ahead adder has 5 inputs
The formula for each carry grows with the bit number, so a 64-bit adder built this way would need enormous gates. Real processors build look-ahead in blocks of four bits, then add a second level of look-ahead between the blocks.
Adding BCD digits
BCD, from Volume 01, keeps each decimal digit in four bits. Adding two BCD digits in binary goes wrong when the sum passes 9, because BCD never uses the patterns 1010 to 1111. The fix is to add 6 (0110) whenever the sum is more than 9, which skips the six unused patterns:
4 + 3: 0100 + 0011 = 00111 (7); 9 or less, so it stands
5 + 8: 0101 + 1000 = 01101 (13); more than 9, so add 0110: 10011 = BCD 0001 0011
9 + 9: 1001 + 1001 = 10010 (18); more than 9, so add 0110: 11000 = BCD 0001 1000
In a carry look-ahead adder, when does a column propagate a carry?
Show the answer
Answer: B. P = A ⊕ B. With exactly one 1 in the column, an incoming carry makes the column add to 2, so the carry passes straight on. With both 1s the column generates a carry of its own; with both 0s it absorbs one.
What you learned
- A half adder gives S = A ⊕ B and C = A·B; a full adder adds a carry in as well, with S = A ⊕ B ⊕ Cin.
- A full adder's carry out is the majority of its three inputs, and two half adders plus an OR gate build one.
- A ripple-carry adder chains full adders; its delay grows in step with the number of bits.
- Subtraction is addition of the two's complement: XOR gates invert B and the control line adds 1.
- Signed overflow means same-sign inputs gave an other-sign result; in hardware, V = C3 ⊕ C4.
- A carry out is not an overflow for signed numbers.
- Carry look-ahead computes every carry from G = A·B and P = A ⊕ B in two levels of gates, much faster than ripple.
Key words from this volume
Every word below has a plain-English entry in the glossary.
Practice
Add through the adder
What does the 4-bit ripple-carry adder give for 1011 + 0110, and what does it mean in decimal?
Show the solution
1011 + 0110 = 10001: 11 + 6 = 17
The four sum bits are 0001 and the carry out C4 is 1, so the full 5-bit answer is 10001, which is 17.
Subtract by adding
Work out 5 - 7 in 4 bits by adding the two's complement.
Show the solution
Invert 7 (0111) to get 1000, and add 1 through the carry in:
5 - 7: 0101 + 1000 + 1 = 01110 -> keep 4 bits: 1110 = -2 as two's complement
No carry comes out, and the result 1110 is -2, which is right.
Overflow or not?
In 4-bit two's complement, does -6 + -5 overflow? What do the result bits read as?
Show the solution
The true answer is -11, below the lowest value, -8. The bits come out as 0101, which reads as 5: two negative inputs and a positive result, so it overflowed.
Interview corner
Ripple carry or look-ahead?
"Why is a ripple-carry adder slow, and how does carry look-ahead fix it?"
Show the solution
"In a ripple-carry adder each full adder waits for the carry from the one before, so the delay grows linearly with the width - two gate delays per bit. Carry look-ahead computes each carry directly from generate, G = A·B, and propagate, P = A ⊕ B, signals, using a fixed two levels of gates. In the course's 4-bit simulation the worst case fell from 8 gate delays to 4. The cost is wide gates, so real designs use look-ahead in 4-bit blocks with a second level between the blocks."
How do you detect overflow?
"How does a processor detect signed overflow after an addition?"
Show the solution
"It compares the carry into the most significant bit with the carry out of it. If they differ, the signed result has overflowed: V = C(n-1) ⊕ C(n). It is the same as saying both inputs had the same sign and the result has the other sign. The carry out alone is the unsigned overflow, and it is a different flag."
Volume 07 adds the missing ingredient: memory. Circuits that remember what happened before.