4-bit ripple carry adder and its problems

A ripple carry adder (RCA) is a parallel adder made of full adders in cascade, where the carry out of each stage is the carry in of the next, so the carry "ripples" from LSB to MSB.

4-bit RCA (block diagram)

  A3 B3      A2 B2      A1 B1      A0 B0
   | |        | |        | |        | |
 +-----+    +-----+    +-----+    +-----+
 | FA3 |<C3-| FA2 |<C2-| FA1 |<C1-| FA0 |<- C0
 +-----+    +-----+    +-----+    +-----+
  |   |        |          |          |
 C4   S3       S2         S1         S0

$$S_i = A_i \oplus B_i \oplus C_i, \qquad C_{i+1} = A_iB_i + C_i(A_i \oplus B_i)$$

Problems with RCA

1. Carry propagation delay: stage $i$ cannot give a correct sum until $C_i$ arrives. In the worst case (e.g. $1111 + 0001$) the carry passes through all stages, so the total delay is about $n \times t_{carry}$. For a 32-bit adder this is very slow.
2. Delay grows linearly with word length, so the RCA limits the speed of the ALU and processor clock.
3. Glitches: outputs change several times while the carry ripples, giving temporary wrong values and extra power use.

Eliminating the problems: carry look-ahead adder (CLA)

The CLA generates every carry directly from the inputs, without waiting for the previous stage. Define for each bit

$$G_i = A_iB_i \ (\text{generate}), \qquad P_i = A_i \oplus B_i \ (\text{propagate})$$

Then $C_{i+1} = G_i + P_iC_i$. Expanding:

$$\begin{aligned} C_1 &= G_0 + P_0C_0 \\ C_2 &= G_1 + P_1G_0 + P_1P_0C_0 \\ C_3 &= G_2 + P_2G_1 + P_2P_1G_0 + P_2P_1P_0C_0 \\ C_4 &= G_3 + P_3G_2 + P_3P_2G_1 + P_3P_2P_1G_0 + P_3P_2P_1P_0C_0 \end{aligned}$$ $$S_i = P_i \oplus C_i$$

 A,B -> [P,G gen] -> [Carry look-ahead] -> C1..C4
             |                               |
             +---------> [XOR: S = P xor C] <+

All carries are two-level AND-OR functions of $G$, $P$ and $C_0$, so every carry appears after a fixed delay (about 2 gate delays after $P$, $G$), independent of $n$. IC 74182 is a carry look-ahead generator. Other methods: carry-select and carry-skip adders, and grouping 4-bit CLA blocks with a second level of look-ahead for wide adders.