Adders and the Ripple-Carry Adder

A half adder is a combinational circuit with two single-bit inputs, $A$ and $B$, and two single-bit outputs: `Sum` and `Carry`. It computes the two-bit binary result of $A + B$, where `Sum` is the low-order bit and `Carry` is the high-order bit. Its truth table has four rows, and inspection shows `Sum` is the XOR of the inputs while `Carry` is their AND:

The half adder's limitation is structural, not incidental: it has no input for a carry arriving from a less-significant bit position. As soon as you try to add numbers wider than one bit, position $i$ may need to absorb a carry generated at position $i-1$. A half adder simply has no wire for that. A full adder fixes this by taking three single-bit inputs — $A$, $B$, and $C_{in}$ (carry-in) — and producing two outputs, `Sum` and $C_{out}$ (carry-out). It is, precisely, a circuit that adds three bits together and expresses the result as a two-bit number ($C_{out}$ is the high bit, `Sum` is the low bit). Its equations, derivable directly from the eight-row truth table, are:

The carry-out equation is a majority function: $C_{out}$ is 1 exactly when at least two of the three inputs are 1. This makes intuitive sense — a carry is generated whenever "enough" of the bits being summed are 1 to push the total to 2 or 3, which needs to be represented in the next bit position. A ripple-carry adder (RCA) is what you get by instantiating $n$ full adders — one per bit position — and wiring the $C_{out}$ of stage $i$ directly into the $C_{in}$ of stage $i+1$, for $i = 0, \dots, n-2$. The carry-in of stage 0 is normally tied to 0 (or used to implement subtraction via Two's Complement Integers, by feeding in 1 and complementing $B$). The name describes the behavior exactly: the carry signal must physically "ripple" up through the chain, one stage at a time, before the most significant bits are guaranteed correct.

Building the full adder from half adders. A standard implementation composes two half adders and an OR gate. First combine $A$ and $B$ with a half adder to get a partial sum and partial carry; then combine that partial sum with $C_{in}$ using a second half adder to get the final `Sum` and a second partial carry; finally OR the two partial carries together to get $C_{out}$. This works because addition is associative: $(A+B)+C_{in}$ groups the same way whether you add $A+B$ first or $B+C_{in}$ first, and a carry can be generated by either grouping, never both simultaneously (which is why OR, not XOR, combines the two partial carries).

Chaining into an $n$-bit adder. Given two $n$-bit binary numbers $A = A_{n-1}\dots A_1 A_0$ and $B = B_{n-1}\dots B_1 B_0$, the ripple-carry adder computes $S = A + B$ (an $n+1$-bit result, since addition can overflow into a new carry-out bit) as follows. ``` function RIPPLE_CARRY_ADDER(A[0..n-1], B[0..n-1], Cin0): // A, B: n-bit operands, bit 0 = least significant // Cin0: initial carry-in (0 for plain addition) carry = Cin0 for i = 0 to n-1: Sum[i], carry = FULL_ADDER(A[i], B[i], carry) Cout = carry // final carry-out; overflow flag for unsigned add return Sum[0..n-1], Cout function FULL_ADDER(a, b, cin): sum = a XOR b XOR cin cout = (a AND b) OR (b AND cin) OR (a AND cin) return sum, cout function HALF_ADDER(a, b): sum = a XOR b cout = a AND b return sum, cout ``` Note that `FULL_ADDER` is a pure combinational function — no state, no clock — and `RIPPLE_CARRY_ADDER` is simply $n$ copies of it wired in series. The "for loop" in the pseudocode is a description of the wiring, not a sequence of clock cycles: in hardware, all $n$ full adders exist simultaneously and continuously compute, but the carry signal takes real physical time to settle at each stage, so the last stage's outputs are only valid after the signal has rippled all the way from stage 0.

Space / gate complexity. Each full adder uses a constant number of gates: with the two-half-adder construction that is 2 XOR, 2 AND, 1 OR — five 2-input gates (a direct two-level sum-of-products implementation of $C_{out}$ uses slightly different but still constant gate counts). An $n$-bit ripple-carry adder is $n$ copies of this cell, so total gate count is $\Theta(n)$: linear in the number of bits, with a small constant factor. This is optimal up to constants — you cannot represent $n$ independent bit positions of input with fewer than $\Theta(n)$ gates, since every input bit must at minimum reach some gate.

Time complexity (critical path). This is the subtler and more important quantity. Let $d$ be the propagation delay of one full adder (the time from a change at its inputs to a stable, correct output at `Sum`/$C_{out}$ — itself $O(1)$, roughly 2–3 gate delays for the standard implementation). Stage $i$'s carry-in is not available until stage $i-1$ has finished computing, because $C_{out}$ of stage $i-1$ is wired directly to $C_{in}$ of stage $i$. So stage $i$ cannot even begin its carry computation until time $i \cdot d$ has elapsed, and it finishes at $(i+1)\cdot d$. The final carry-out, $C_n$, is only guaranteed correct at time

This is a hard lower bound for this particular topology, not a pessimistic worst case: the most-significant sum bit genuinely depends on the least-significant carry in the worst case (e.g., adding $0\ldots01$ to $1\ldots11$, where a single incoming carry must ripple through every stage to flip every sum bit). No amount of clever gate-level optimization within this ripple topology can beat $\Theta(n)$, because the carry dependency chain is structurally $n$ long — this is exactly the limitation that motivates carry-lookahead and other adders used in real Arithmetic Logic Units, which restructure the dependency graph, not just the gates, to shorten this chain to $O(\log n)$.

Correctness — proof sketch by induction on bit position. Claim: after signals settle, for every $i$, the pair $(\text{Sum}_i, C_{i+1})$ produced by stage $i$ satisfies

i.e., stage $i$ correctly adds its two bits plus whatever true carry arrived from below, and $C_{i+1}$ is exactly the true carry that should propagate to position $i+1$.

• Base case ($i=0$): $C_0$ is tied to the initial carry-in (0, or 1 for two's-complement subtraction). A full adder is defined to satisfy $A_0+B_0+C_0 = \text{Sum}_0 + 2C_1$ by its truth table (verified directly since it has only 8 rows) — so this holds by construction.
• Inductive step: assume $C_i$ delivered to stage $i$ is exactly the correct running carry out of all bits $0,\dots,i-1$ (this is the induction hypothesis). Then, again by the full-adder truth table, stage $i$ computes $A_i+B_i+C_i = \text{Sum}_i + 2C_{i+1}$ correctly, and in particular $C_{i+1}$ is exactly the true carry that a decimal-style long-addition would produce out of position $i$.
• Conclusion: by induction, every stage's sum bit is correct once its inputs (including its carry-in) are stable, and summing the identity above over all $i$ from $0$ to $n-1$, weighted by $2^i$, telescopes to $A + B = S$ (the $n$-bit sum plus the final carry-out as the overflow/extra bit).

The only physical subtlety is timing, not logic: the equations are correct instantaneously as a Boolean identity, but a real circuit needs $T(n)=\Theta(n)$ time for the signals to reach the values the equations predict, because $C_i$ used in stage $i$'s equation is itself the output of stage $i-1$'s equation.

Tradeoffs, stated honestly. Ripple-carry's virtue is that it is the simplest possible correct multi-bit adder: one repeated cell, trivial to design, verify, and lay out, with $\Theta(n)$ gates — asymptotically minimal area. Its cost is $\Theta(n)$ delay, which becomes the dominant bottleneck for wide adders (64-bit integer ALUs, floating-point mantissas). This is precisely why production CPUs rarely use pure ripple-carry for wide arithmetic, instead using carry-lookahead, carry-select, or hybrid adders that trade extra gates (area) for an $O(\log n)$ critical path — a tradeoff you can only appreciate once you know exactly where ripple-carry's linear delay comes from.

Add the 4-bit unsigned numbers $A = 0111_2$ (7) and $B = 0101_2$ (5), expecting $7+5=12=1100_2$, which needs 5 bits including carry-out — so watch for overflow of the 4-bit field. Bit indices are numbered 0 (least significant) to 3 (most significant). $C_0 = 0$ (no initial carry-in).

Reading the `Sum` column from stage 3 down to stage 0 gives $S = 1100_2$. The final carry-out $C_4 = 0$, confirming no overflow occurred (correct — 12 fits in 4 bits with room to spare, and indeed $1100_2 = 12$). Note stage 2 is the critical one: it only produces the correct carry-out (1) once $C_2$ (from stage 1) has arrived; if you tried to read stage 3's carry-out before stage 0's carry has rippled through stages 1 and 2, you would read a stale, incorrect value. This is exactly the $\Theta(n)$ ripple delay made concrete: stage 3's correct output is only guaranteed after three full-adder delays have elapsed, not zero. As a second check, trace a case that forces a long carry chain — add $A=0001_2$ (1) to $B=1111_2$ (15), expecting $16 = 10000_2$, i.e., overflow of the 4-bit field into $C_4=1$.

Every stage generates a carry, so the single carry-in at stage 0 ripples all the way to $C_4=1$, and the sum bits are all 0 — exactly $1+15=16=10000_2$ (Sum$=0000$, Cout$=1$). This is the worst-case input for a ripple-carry adder: it forces the carry to traverse every one of the $n$ stages before the topmost bit stabilizes, realizing the full $\Theta(n)$ critical-path delay in practice, not just in the abstract bound.

The full adder and ripple-carry adder are not attributed to a single inventor in the way an algorithm might be; they emerged from the broader mid-20th-century convergence of Boolean algebra and switching-circuit engineering that made digital computers possible. The key intellectual leap — that binary arithmetic could be realized directly as relay or gate networks obeying Boolean algebra — is usually traced to Claude Shannon's demonstration that switching circuits implement Boolean logic, which underlies every adder circuit ever built.

Ripple-carry adders (or their carry-lookahead successors, which reuse the exact same full-adder equations at each bit while restructuring the carry network) sit at the arithmetic core of every Arithmetic Logic Unit in a CPU. Program counter increments, array index computation, stack pointer adjustment, and the integer add/subtract instructions in every instruction set architecture all bottom out in some variant of this circuit. Compilers, when they lower integer addition in source code to machine instructions, are ultimately relying on hardware whose correctness rests on exactly the inductive argument given above. Floating-point units use adder chains internally to align and add mantissas. Even simple embedded microcontrollers, where area matters more than speed, often use plain ripple-carry adders because their small bit-width (8 or 16 bits) makes the $\Theta(n)$ delay negligible — a direct, practical illustration of the area/speed tradeoff discussed above. Understanding this circuit is also the necessary first step before studying carry-lookahead, carry-select, and carry-save adders, all of which are explicitly designed to shorten the critical path this article derives.

Ask the tutor: How does a carry-lookahead adder use generate/propagate signals to break the linear ripple-carry dependency chain?