Visual walkthrough — Ripple-carry adder

---

Step 1 — What "adding one column" even means

WHAT. Look at a single column of a pen-and-paper addition. Two digits sit on top of each other, and sometimes a little carry digit sneaks in from the column to the right. We add those three things.

WHY. A circuit cannot "just add" a whole number. It only ever looks at one column at a time, exactly like your hand does on paper. So the first thing to understand is the smallest possible job: add three single binary digits.

Let me name the three inputs so we never have to point:

• $a$ — the top bit of this column (a $0$ or a $1$).
• $b$ — the bottom bit of this column ($0$ or $1$).
• $c_{in}$ — the carry-in: the little $1$ (or $0$) handed to us from the column on our right.

PICTURE. The three arrows flowing into the box are $a$, $b$, $c_{in}$. Two arrows flow out: the digit we write down, and the carry we hand leftward.

---

Step 2 — Why one output bit is not enough

WHAT. Add the three input bits as ordinary numbers. The smallest total is $0+0+0=0$. The biggest is $1+1+1=3$.

WHY. A single binary digit can only say $0$ or $1$. But our total can reach $2$ or $3$ — those need two binary digits ($2=10_2$, $3=11_2$). So one output bit is physically impossible; we are forced into two outputs.

Read the equation left to right:

$\underset{\text{top bit}}{\underbrace{a}}+\underset{\text{bottom bit}}{\underbrace{b}}+\underset{\text{carry in}}{\underbrace{c_{in}}}=\underset{\text{the "twos" place}}{\underbrace{2\cdot c_{out}}}+\underset{\text{the "ones" place}}{\underbrace{s}}$

The $2\cdot c_{out}$ term says: "every carry-out is worth 2, because it belongs in the next column, which counts double." The $s$ is the leftover ones.

PICTURE. A number line from $0$ to $3$. Below $2$ the answer fits in one bit ($c_{out}=0$); at $2$ and $3$ the total spills over the edge and $c_{out}$ must turn on.

---

Step 3 — The truth table is the whole story

WHAT. List all $2\times 2\times 2=8$ possible input combinations and, for each, compute $s$ and $c_{out}$ using $a+b+c_{in}=2c_{out}+s$.

WHY. With only 8 rows we can just enumerate every case — no case can hide from us. This is the "cover every scenario" guarantee: after this table there are no surprises.

$a$	$b$	$c_{in}$	total	$c_{out}$	$s$
0	0	0	0	0	0
0	0	1	1	0	1
0	1	0	1	0	1
0	1	1	2	1	0
1	0	0	1	0	1
1	0	1	2	1	0
1	1	0	2	1	0
1	1	1	3	1	1

PICTURE. The 8 rows drawn as coloured tiles: cyan where the output bit is $1$, dim where it is $0$. Stare at the $s$ column and the $c_{out}$ column separately — each has its own visual pattern, and those two patterns are the two things we must build.

---

Step 4 — Reading the $s$ column: it is "oddness"

WHAT. Look only at the $s$ column. It is $1$ in exactly these rows: one input on, or all three on. Count the $1$s in the inputs of every $s=1$ row: $1,1,1,3$ — always an odd count.

WHY. So $s$ answers one plain-English question: "is the number of $1$s among $a,b,c_{in}$ odd?" The gate that answers exactly that question is XOR (written $\oplus$). $x\oplus y$ is $1$ when its two inputs differ; chain three of them and you get a $1$ whenever an odd number of inputs are $1$.

Why XOR and not something else? Because we need the "odd-count" detector, and XOR is the odd-count detector — no other single primitive matches that column.

$s=\underset{\text{bit 1}}{\underbrace{a}}\oplus \underset{\text{bit 2}}{\underbrace{b}}\oplus \underset{\text{bit 3}}{\underbrace{c_{in}}}$

Each $\oplus$ flips the running answer whenever it meets a new $1$, so after all three the answer is "on" exactly for an odd tally.

PICTURE. A little parity machine: start at $0$, each $1$ input toggles a switch. Odd number of toggles ⇒ lamp on ⇒ $s=1$.

---

Step 5 — Reading the $c_{out}$ column: it is "majority"

WHAT. Now look only at $c_{out}$. It is $1$ in every row where at least two inputs are $1$.

WHY. Carry-out means "the total reached $2$ or more." Reaching $2$ requires two or more of the three bits to be $1$. That is the majority function: "do the $1$s outvote the $0$s?"

Write majority as "any two agree on $1$":

$c_{out}=\underset{\text{a AND b}}{\underbrace{ab}}+\underset{\text{b AND cin}}{\underbrace{b{c}_{in}}}+\underset{\text{a AND cin}}{\underbrace{a{c}_{in}}}$

Here juxtaposition ($ab$) means logical AND (both $1$), and $+$ means logical OR (at least one term true). Each product lights up when a specific pair is both $1$; the OR fires if any pair does — precisely "two or more."

PICTURE. Three overlapping regions ($a$, $b$, $c_{in}$). Shade every place where at least two regions overlap — that shaded area is exactly $c_{out}=1$.

---

Step 6 — Generate and propagate: the same carry, reshaped

WHAT. We rewrite the majority carry using the parity we already built. Define one helper signal: $p=a\oplus b(\text{"the two column bits differ"})$ Then the carry becomes:

$c_{out}=\underset{\text{generate }g}{\underbrace{ab}}+\underset{\text{propagate }p}{\underbrace{(a\oplus b)}}{c}_{in}$

WHY. This split has physical meaning we will need in Carry-lookahead adder later:

• $g=ab$ — generate: if both bits are $1$, this column makes a carry on its own, no matter what arrived.
• $p=a\oplus b$ — propagate: if exactly one bit is $1$, the column has no carry of its own, but it will pass an incoming carry straight through. That is why $p$ is multiplied by $c_{in}$.

This is algebraically identical to Step 5 (proof left to the verifier below), but it tells the story of the carry: "born here, or passing through."

PICTURE. Two gates feeding the carry-out: an AND making $g$ (a carry born here), and an AND of $p$ with $c_{in}$ (a carry let through), joined by an OR.

---

Step 7 — Chaining boxes: where the "ripple" is born

WHAT. Put $n$ of these boxes in a row, one per bit position $i=0,1,\dots ,n-1$. Wire the carry-out of box $i$ into the carry-in of box $i+1$.

WHY. On paper, the carry from the ones column enters the tens column. In hardware that is literally a wire from $C_{i+1}$ of one box to $C_i$ of the next. Renaming the signals per stage:

$S_i=\underset{\text{bit-i sum}}{\underbrace{A_i\oplus B_i\oplus C_i}},C_{i+1}=\underset{\text{carry into bit i+1}}{\underbrace{A_i{B}_i+(A_i\oplus B_i)C_i}}$

• $A_i,B_i$ — the $i$-th bits of the two numbers.
• $C_i$ — the carry arriving from below (with $C_0$ the overall carry-in).
• $C_n$ — the final carry out of the top box.

THE KEY OBSERVATION. $C_{i+1}$ contains $C_i$ inside it. So box $i+1$ cannot finish until box $i$ has finished. The correct carry must travel — ripple — from bit $0$ upward, one box at a time.

PICTURE. Four boxes side by side, an amber carry-wave crossing the carry wires left→right. The top sum bit is greyed "not ready yet" until the wave arrives.

---

Step 8 — How long the ripple takes (the cost of simplicity)

WHAT. Let $t_c$ be the time for one box to compute its carry-out. The wave must cross all $n$ boxes.

WHY. Because carry $i+1$ physically waits for carry $i$, the delays add, they do not overlap:

$T_{\text{RCA}}\approx \underset{\text{number of stages}}{\underbrace{n}}\cdot \underset{\text{one carry hop}}{\underbrace{t_c}}\Rightarrow O(n)\text{ delay}$

Cost in gates is also $n$ boxes $\Rightarrow O(n)$ area. Cheap and regular — but the linear delay is why wide adders switch to Carry-lookahead adder.

PICTURE. A bar of $n$ stacked $t_c$ blocks: total height grows straight-line with $n$. Beside it, the lookahead idea shown short — a preview of why the next chapter exists.

---

Step 9 — The degenerate & edge cases (nothing hides)

WHAT / WHY / PICTURE, all three cases on one figure:

1. All zeros ($A=B=0,C_0=0$): every $s=0$, every carry $0$. The ripple never starts — the smallest possible input.
2. Carry born at the bottom, dies immediately ($A_0=B_0=1$, rest $0$): $C_1=1$ but $A_1=B_1=0$ with $p=0$ kills it; no long ripple.
3. Worst case — carry crosses the whole width ($A=0\dots 01$, $B=1\dots 11$): every upper stage has $p=1$ (bits differ), so the single carry born at bit $0$ is propagated through every box to $C_n$. This is the $n\cdot t_c$ situation.
4. Subtraction reuse (see Two's complement): invert every $B_i$ and set $C_0=1$; the same hardware computes $A-B$.
5. Overflow (see Overflow detection): for unsigned, overflow $=C_n$; for signed two's-complement, overflow $=C_n\oplus C_{n-1}$ — carry into the top bit differing from carry out.

---

The one-picture summary

Everything on one blueprint: the truth table splits into two questions (odd? / majority?), which become the XOR sum and the generate-propagate carry, which fold into one box, which chains into the rippling adder whose cost is $O(n)$.

Recall Feynman: the whole walkthrough in plain words

We started with one column of a paper addition: two digits and a little carry from the right — three things. Their total can be as big as three, and three needs two digits to write, so every column machine has two outputs: what we write ($s$) and what we carry ($c_{out}$). We listed all eight cases in a tiny table. The "write" column lit up whenever an odd number of inputs were $1$ — that's the XOR gate, an oddness detector. The "carry" column lit up whenever two or more inputs were $1$ — that's the majority gate, a voting machine, definitely not XOR. We reshaped the carry into "a carry is born here if both bits are 1, or it's just passing through if the bits differ" — generate and propagate. That one box is a full adder. Line up $n$ of them and wire each carry into the next box; now the carry has to walk left, column by column, like a wave — that's the ripple. It's simple and cheap ($n$ boxes) but slow, because the top answer can't settle until the wave has crossed every box ($n$ little delays in a row). That waiting is the price of simplicity, and it's exactly the problem the carry-lookahead adder later fixes.

Recall

Why must a single-column adder have two output bits? ::: The total $a+b+c_{in}$ can reach $2$ or $3$, which need two binary digits: the sum bit $s$ and the carry $c_{out}$. Which question does $s$ answer, and which gate? ::: "Is the number of $1$ inputs odd?" — answered by XOR. Which question does $c_{out}$ answer, and which gate? ::: "Are at least two inputs $1$?" — answered by the majority function. What does "generate" mean physically? ::: $g=ab$: this column produces a carry on its own because both bits are $1$. What does "propagate" mean physically? ::: $p=a\oplus b$: the column makes no carry itself but passes an incoming carry straight through. Why does the top sum bit take $\approx n\cdot t_c$ to settle? ::: It depends on $C_{n-1}$, which depends serially on every carry below it back to $C_0$ — the delays add.

Connections

• Ripple-carry adder — the parent topic this page derives in pictures.
• Full adder — the single box built in Steps 1–6.
• Half adder — a full adder without $c_{in}$; two of them plus an OR make one full adder.
• Carry-lookahead adder — uses the generate/propagate signals of Step 6 to beat the $O(n)$ delay.
• Two's complement — makes the same adder subtract (Step 9, case 4).
• Overflow detection — $C_n$ vs $C_n\oplus C_{n-1}$ (Step 9, case 5).
• Combinational circuits — the RCA is a pure output-equals-function-of-inputs circuit.
• Propagation delay — the timing idea behind the ripple's slowness.