Ripple-carry adder

WHAT is it?

The building block is the full adder (FA): a circuit that adds three single bits $a$ , $b$ , $c_{in}$ and outputs a sum bit $s$ and a carry-out bit $c_{out}$ .

WHY does it work? (Derive the full adder from scratch)

We want to add three bits: $a$ , $b$ , and $c_{in}$ . Their arithmetic sum ranges from $0$ (all zero) to $3$ (all one). In binary, values $0..3$ need two output bits:

$a + b + c_{in} = 2\cdot c_{out} + s$

Here $c_{out}$ is the "twos place" and $s$ is the "ones place". Let's build the truth table and derive each output.

$a$	$b$	$c_{in}$	sum(dec)	$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

Deriving $s$ (WHY XOR?): $s=1$ exactly when the number of 1s among the three inputs is odd. "Odd parity" is precisely what XOR computes.

$s = a \oplus b \oplus c_{in}$

Deriving $c_{out}$ (WHY majority?): $c_{out}=1$ when the sum is $\ge 2$ , i.e. when at least two of the inputs are 1. That is the majority function:

$c_{out} = ab + b\,c_{in} + a\,c_{in}$

We can simplify using the already-computed $p = a\oplus b$ : the carry is produced if both $a,b$ are 1 (generate), or if exactly one of them is 1 and $c_{in}=1$ (propagate):

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

HOW to build the n-bit adder

Chain $n$ full adders. Feed the $i$ -th bits $A_i, B_i$ and the carry from below $C_i$ into FA $_i$ ; take out $S_i$ and $C_{i+1}$ :

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

with $C_0$ as the overall carry-in, and $C_n$ the final carry-out.

Timing / cost analysis (the 80/20 that matters)

Let one full adder's carry path take delay $t_c$ . Since carry ripples through all $n$ stages:

$T_{\text{RCA}} \approx n\cdot t_c \quad\Rightarrow\quad \boxed{O(n)\ \text{delay}}$

Hardware cost: $n$ full adders $\Rightarrow \boxed{O(n)\ \text{gates}}$ — cheap and regular, but slow for large $n$ . This slowness is exactly why faster schemes (carry-lookahead) exist.

Worked example Worked example 1 — add two 4-bit numbers

Add $A = 1011_2\ (11)$ and $B = 0110_2\ (6)$ , with $C_0 = 0$ .

Go bit by bit, LSB first:

Bit 0: $A_0{=}1,B_0{=}0,C_0{=}0 \Rightarrow s=1\oplus0\oplus0=1$ , carry $=1\cdot0+\dots=0$ . So $S_0=1,\ C_1=0$ . Why this step? This is the ones column; no carry yet.
Bit 1: $A_1{=}1,B_1{=}1,C_1{=}0 \Rightarrow s=1\oplus1\oplus0=0$ , carry $=1\cdot1=1$ . So $S_1=0,\ C_2=1$ . Why? $1+1=10_2$ , write 0 carry 1.
Bit 2: $A_2{=}0,B_2{=}1,C_2{=}1 \Rightarrow s=0\oplus1\oplus1=0$ , carry $=0\cdot1+(0\oplus1)\cdot1=1$ . So $S_2=0,\ C_3=1$ . Why? $0+1+1=10_2$ .
Bit 3: $A_3{=}1,B_3{=}0,C_3{=}1 \Rightarrow s=1\oplus0\oplus1=0$ , carry $=1\cdot0+(1\oplus0)\cdot1=1$ . So $S_3=0,\ C_4=1$ . Why? $1+1=10_2$ .

Result: $S = C_4 S_3 S_2 S_1 S_0 = 1\,0001_2 = 17$ . Check: $11+6=17$ . ✓ Notice the carry rippled all the way from bit 1 to the top.

Worked example Worked example 2 — subtraction reuse (two's complement)

To compute $A - B$ , set $C_0 = 1$ and feed $B$ inverted (each bit through a NOT). Then the adder computes $A + \bar B + 1 = A + (\text{two's complement of }B) = A - B$ . Add $A=0101\ (5)$ , $\bar B$ where $B=0011\ (3)\Rightarrow\bar B=1100$ , $C_0=1$ : $0101 + 1100 + 1 = 1\,0010_2$ . Drop the extra carry-out $\to 0010_2 = 2 = 5-3$ . ✓ Why this step? Two's complement turns subtraction into addition, so the same RCA hardware does both — just add XOR gates controlled by a "subtract" line.

Common mistake Steel-manned common mistakes

Mistake A: " $c_{out} = a\oplus b\oplus c_{in}$ too." Why it feels right: the sum uses XOR of all three, so symmetry tempts you to reuse XOR for carry. The fix: carry is about magnitude reaching 2, not parity. Parity says "odd count"; carry says "at least two". Different logic → carry is majority ( $ab+bc_{in}+ac_{in}$ ), not XOR.

Mistake B: "The MSB output is ready as soon as inputs arrive." Why it feels right: all inputs $A,B,C_0$ enter simultaneously. The fix: $S_{n-1}$ depends on $C_{n-1}$ , which depends on $C_{n-2}$ , … The carry chain is serial, so the top bit only settles after $\approx n\cdot t_c$ . This delay is the whole reason RCA is "slow".

Mistake C: "Carry-out means overflow." Why it feels right: for unsigned numbers, $C_n=1$ does mean the result didn't fit. The fix: for signed two's-complement, overflow is $C_n \oplus C_{n-1}$ (carry into MSB differs from carry out of MSB), not $C_n$ alone.

Flashcards

What single-bit block is an

n

-bit ripple-carry adder built from?

n

cascaded full adders, carry-out of each feeding carry-in of the next.

Full adder sum expression?

s = a \oplus b \oplus c_{in}

(odd-parity / XOR of the three bits).

Full adder carry-out expression?

c_{out} = ab + bc_{in} + ac_{in} = ab + (a\oplus b)c_{in}

(majority function).

Why is

c_{out}

the majority function, not XOR?

Carry appears when the arithmetic sum

\ge 2

, i.e. at least two inputs are 1 — that is majority, not odd-parity.

Worst-case delay of an

n

-bit RCA?

O(n)

, about

n\cdot t_c

, because the carry must ripple serially through every stage.

Gate/area cost of an

n

-bit RCA?

O(n)

— one full adder per bit; cheap and regular.

How do you turn an RCA into a subtractor for

A-B

Invert each bit of

B

and set

C_0=1

(adds the two's complement of

B

Signed overflow condition in two's complement?

C_n \oplus C_{n-1}

(carry into MSB

\ne

carry out of MSB).

What is "generate" vs "propagate"?

Generate

=ab

(stage makes a carry itself); propagate

=a\oplus b

(stage passes an incoming carry through).

Main drawback of RCA?

Speed — linear carry-propagation delay makes it slow for wide words; motivates carry-lookahead.

Recall Feynman: explain to a 12-year-old

Imagine adding two long numbers on paper. You start from the right, add each column, and whenever a column adds up to 10 or more you carry a 1 into the next column. You can't finish the left columns until the carry from the right has traveled over. A ripple-carry adder is a row of tiny machines, one per digit (bit). Each machine adds its own two bits plus whatever carry arrives from its right neighbor, and hands its own carry to the left neighbor. The "carry" travels left like a wave — that's why it's called ripple. It's simple and cheap, but if the number is very long, you wait a while for the carry to walk all the way across.

Connections

Full adder — the repeated building block derived above.
Half adder — full adder = two half adders + an OR on the carries.
Carry-lookahead adder — fixes RCA's $O(n)$ delay using generate/propagate signals.
Two's complement — enables subtraction reuse of the same adder.
Overflow detection — $C_n\oplus C_{n-1}$ for signed arithmetic.
Combinational circuits — RCA is a canonical example (no memory, output = f(inputs)).
Propagation delay — the timing concept that makes RCA slow.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Socho tum paper pe do lambe numbers add kar rahe ho. Right side se shuru karte ho, har column add karte ho, aur jab column ka sum 10 ya usse zyada ho jaye to ek "carry" agle column me le jaate ho. Ripple-carry adder bilkul yahi kaam hardware me karta hai — bas binary me. Har bit ke liye ek chhota circuit hota hai jise full adder kehte hain, aur ye saare ek line me jude hote hain. Har full adder apne do bits aur neeche wale ka carry leta hai, apna sum banata hai aur apna carry upar (MSB ki taraf) bhej deta hai.

Full adder ke do formule yaad rakho, dono derive ho jaate hain truth table se. Sum wala part: $S = A \oplus B \oplus C_{in}$ — matlab XOR, kyunki sum tab 1 hota hai jab 1s ki ginti odd ho. Carry wala part: $C_{out} = AB + BC_{in} + AC_{in}$ — ye majority function hai, kyunki carry tab banta hai jab kam se kam do inputs 1 hon. Yahan students galti karte hain — carry ko bhi XOR samajh lete hain, jo galat hai. XOR "oddness" dekhta hai, carry "at least two" dekhta hai.

Ab problem kya hai? Carry ko ek-ek stage cross karna padta hai — LSB se MSB tak "ripple" hota hai. Isliye top bit ka answer tab tak ready nahi hota jab tak carry poore chain se guzar na jaye. Iska delay $O(n)$ hota hai — matlab jitne zyada bits, utna zyada wait. Cost sasta aur design simple, par speed slow. Isi slowness ki wajah se carry-lookahead adder invent hua. Bonus: agar $B$ ke saare bits invert kar do aur $C_0 = 1$ set kar do, to yahi adder $A - B$ (two's complement subtraction) bhi kar deta hai — same hardware, double kaam!

WHAT is it?

WHY does it work? (Derive the full adder from scratch)

HOW to build the n-bit adder

Timing / cost analysis (the 80/20 that matters)

Flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Combinational Circuits

Connections