Electrical Engineering › Section T · Combinational logic › Topic T.2
Half, full, ripple-carry, and look-ahead adders
A modern processor adds billions of numbers a second, and it does so with the small circuits in this topic. Adding one column of bits is easy; the real engineering lies in passing the carry along quickly.
Adding one column of bits
Binary addition, as in "Binary numbers, conversion, and arithmetic", works column by column: add the bits, write down the sum bit and carry 1 into the next column if the total is 2 or more. A circuit that does this for one column is an adder cell. The rightmost column has only two bits to add. Every other column has three: two data bits and the carry that came in from the right. These two cases give the two basic cells, the half adder and the full adder.
The half adder
A half adder adds two bits A and B and produces a sum S and a carry-out C. Of the four input combinations, only 1 + 1 makes a carry, and the sum is 1 exactly when the inputs differ:
So the whole circuit is one XOR gate and one AND gate sharing the same two inputs. It is called half an adder because it has no input for a carry arriving from a lower column, so on its own it can only serve the least significant bit.
The full adder
A full adder adds A, B and an input carry \(C_{in}\). The total is 0 to 3, written as the two-bit number \(C_{out}S\):
The sum is 1 when an odd number of inputs are 1, and a carry appears when at least two are:
The carry is the majority function of the three inputs, written in a form that reuses the XOR.
A full adder from two half adders
The equations show how to build a full adder from parts already met. The first half adder adds A and B, giving \(A \oplus B\) and the carry \(AB\). The second half adder adds that partial sum to \(C_{in}\), giving the final sum \(A \oplus B \oplus C_{in}\) and a second carry \(C_{in}(A \oplus B)\). An OR gate combines the two carries into \(C_{out}\). The two carries can never both be 1, because if A and B are both 1 the partial sum is 0. Alternatively, the carry can be built as two-level AND-OR logic, \(AB + AC_{in} + BC_{in}\).
Parallel adders
To add two n-bit numbers, line up n full adders, one per bit position, and connect the carry-out of each stage to the carry-in of the next. The least significant stage gets \(C_{in} = 0\), or a half adder, and the final carry-out becomes the extra most significant bit of the result. The 74HC283 is a common 4-bit parallel adder, with the look-ahead carry described below built in: it takes two 4-bit numbers and an input carry and produces a 4-bit sum and an output carry. For 8 bits, connect the carry-out of the low-order chip to the carry-in of the high-order chip.
Worked example: 1011 plus 0110
Add \(A = 1011_2\) (11) and \(B = 0110_2\) (6) in a 4-bit parallel adder, stage 0 being the least significant. 1. Stage 0: 1 + 0 + 0 gives \(S_0 = 1\), carry 0. 2. Stage 1: 1 + 1 + 0 gives \(S_1 = 0\), carry 1. 3. Stage 2: 0 + 1 + 1 gives \(S_2 = 0\), carry 1. 4. Stage 3: 1 + 0 + 1 gives \(S_3 = 0\), carry 1. 5. The result is \(C_{out} = 1\) and sum \(0001\), so the 5-bit answer is \(10001_2 = 17\). 6. Check: 11 + 6 = 17. In 4 bits alone the answer would read 1, which is why the output carry matters.
Ripple carry and its delay
In the chain just described, each stage must wait for the carry from the stage before, so the carry ripples from right to left. The worst case is a carry made in stage 0 that must pass through every stage, as in \(1001_2 + 0111_2 = 10000_2\). Assume, for illustration, 8 ns from carry-in to carry-out per stage. Then a 4-bit ripple adder can take 32 ns to settle and a 16-bit one 128 ns. The delay grows in proportion to the number of bits, which is far too slow for a wide adder in a fast processor.
Look-ahead carry
A look-ahead adder computes every carry directly from the inputs instead of waiting. Each stage i has two signals. It generates a carry, whatever comes in, when \(G_i = A_iB_i = 1\). It propagates an incoming carry when \(P_i = A_i \oplus B_i = 1\); the OR \(A_i + B_i\) also works for the carry. So \(C_{i+1} = G_i + P_iC_i\). Substituting each carry into the next removes the chain:
Every carry is now two-level AND-OR logic, so all appear after the same short delay. The cost is gates: the expressions grow with each stage.
Worked example: look-ahead for 1011 plus 0110
Find the carries for the same addition with look-ahead logic, \(C_0 = 0\). 1. Generate bits, \(G_i = A_iB_i\), for stages 0 to 3: 0, 1, 0, 0. 2. Propagate bits, \(P_i = A_i \oplus B_i\): 1, 0, 1, 1. 3. \(C_1 = G_0 + P_0C_0\), which is \(0 + 1 \cdot 0 = 0\). 4. \(C_2 = 1\), from the \(G_1\) term alone. 5. Expanding \(C_3\) gives \(G_2 + P_2G_1 + \dots = 1\), through \(P_2G_1\), and likewise \(C_4 = 1\) through \(P_3P_2G_1\). 6. Check: these carries, 0, 1, 1, 1, match the ripple example, but here each comes straight from A and B. Each sum bit is then \(S_i = P_i \oplus C_i\).
Subtraction with the same adder
An adder also subtracts, using two's complement from "Complements and signed numbers": \(A - B = A + \overline{B} + 1\). Pass each bit of B through an XOR gate whose other input is a control line, and also feed that line to the adder's \(C_0\). With the control at 0 the circuit adds; at 1 it inverts B and adds 1, so it subtracts. For \(0110_2 - 0011_2\): \(0110 + 1100 + 1 = 1\,0011\), and dropping the final carry leaves \(0011_2 = 3\).
Common mistakes to avoid
First, using a half adder in a middle stage, which throws away the incoming carry. Second, writing the full-adder sum as \(A \oplus B\) and forgetting \(C_{in}\). Third, ignoring the final carry-out, which makes 11 + 6 look like 1 in a 4-bit result. Fourth, swapping generate and propagate: generate is AND, which makes a carry whatever arrives, while propagate passes one along. Fifth, assuming cascaded 4-bit look-ahead chips are look-ahead throughout: the carry still ripples from one package to the next.
Key takeaways
Half adder: \(S = A \oplus B\), \(C = AB\). Full adder: \(S = A \oplus B \oplus C_{in}\) and \(C_{out} = AB + C_{in}(A \oplus B)\), buildable from two half adders and an OR gate. Chaining full adders gives an n-bit ripple-carry adder whose delay grows with n. Look-ahead logic uses \(G_i = A_iB_i\), \(P_i = A_i \oplus B_i\) and \(C_{i+1} = G_i + P_iC_i\), expanded so every carry is two-level logic. XOR gates on B and a carry-in of 1 turn the adder into a two's-complement subtractor.
Flashcards
Flashcard
S = A ⊕ B, C = AB
Test your understanding
Question 1 of 5
A full adder has A = 1, B = 0 and Cin = 1. What are Cout and S?
Question 2 of 5
Why can a half adder not be used for the second bit of a 4-bit adder?
Question 3 of 5
In look-ahead carry logic, which pair of definitions is correct for stage i?
Question 4 of 5
Assume each stage of a ripple-carry adder takes 8 ns from carry-in to carry-out. What is the worst-case carry delay for 16 bits?
Question 5 of 5
An adder-subtractor computes 0101₂ − 0010₂ by adding A, the inverted B and a carry-in of 1. What 4-bit result remains after the final carry is dropped?
