Ripple-carry adder: Exercises — Hardware deep dive

Before we start, one reminder of the two equations that power every stage. For inputs $a$ (first bit), $b$ (second bit), $c_{in}$ (carry arriving from the right):

Level 1 — Recognition

L1.1

State the truth-table row for a full adder when $a = 1, b = 1, c_{in} = 1$ . Give $s$ and $c_{o u t}$ .

Recall Solution

Arithmetic sum $= 1 + 1 + 1 = 3$ . In binary $3 = 1 1_{2}$ , so the "twos place" is $c_{o u t} = 1$ and the "ones place" is $s = 1$ . Check with the equations: $s = 1 \oplus 1 \oplus 1$ . Fold the first pair: $1 \oplus 1 = 0$ (they match), then fold in the third: $0 \oplus 1 = 1$ (they differ). So $s = 1$ . ✓ $c_{o u t} = (1) (1) + (1) (1) + (1) (1) = 1$ . ✓ Answer: $s = 1, c_{o u t} = 1$ .

L1.2

Which single-bit block is an $n$ -bit ripple-carry adder made of, and what wire connects one stage to the next?

Recall Solution

It is made of $n$ full adders (see Full adder). The connecting wire is the carry: the carry-out $C_{i + 1}$ of stage $i$ becomes the carry-in of stage $i + 1$ . That single wire chain is what makes the carry "ripple".

L1.3

True or false: the sum bit is computed by a majority vote of the three inputs.

Recall Solution

False. The sum bit uses XOR (odd-parity): it is $1$ when an odd number of the three inputs are $1$ . The carry-out is the majority vote. Mixing these up is the single most common error — see the L1 mistake box below.

Level 2 — Application

L2.1

Add $A = 011 0_{2} (6)$ and $B = 010 1_{2} (5)$ with $C_{0} = 0$ using a 4-bit RCA. Show every stage's $s$ and carry, then the final result.

Recall Solution

Work LSB (bit 0) first. I write bits as $A_{3} A_{2} A_{1} A_{0} = 0110$ and $B_{3} B_{2} B_{1} B_{0} = 0101$ .

Bit 0: $A_{0} = 0, B_{0} = 1, C_{0} = 0$ . $s = 0 \oplus 1 \oplus 0 = 1$ . Carry $= 0 \cdot 1 + 1 \cdot 0 + 0 \cdot 0 = 0$ . → $S_{0} = 1, C_{1} = 0$ .
Bit 1: $A_{1} = 1, B_{1} = 0, C_{1} = 0$ . $s = 1 \oplus 0 \oplus 0 = 1$ . Carry $= 1 \cdot 0 + 0 \cdot 0 + 1 \cdot 0 = 0$ . → $S_{1} = 1, C_{2} = 0$ .
Bit 2: $A_{2} = 1, B_{2} = 1, C_{2} = 0$ . $s = 1 \oplus 1 \oplus 0 = 0$ . Carry $= 1 \cdot 1 = 1$ . → $S_{2} = 0, C_{3} = 1$ .
Bit 3: $A_{3} = 0, B_{3} = 0, C_{3} = 1$ . $s = 0 \oplus 0 \oplus 1 = 1$ . Carry $= 0 + 0 + 0 = 0$ . → $S_{3} = 1, C_{4} = 0$ .

Result $= C_{4} S_{3} S_{2} S_{1} S_{0} = 0101 1_{2} = 101 1_{2} = 11$ . Check $6 + 5 = 11$ . ✓

L2.2

Add $A = 111 1_{2} (15)$ and $B = 000 1_{2} (1)$ , $C_{0} = 0$ . Watch the carry ripple all the way through.

Recall Solution

$A_{3} A_{2} A_{1} A_{0} = 1111$ , $B_{3} B_{2} B_{1} B_{0} = 0001$ . I keep the variable names on every line so it stays readable.

Bit 0: $A_{0} = 1, B_{0} = 1, C_{0} = 0$ . $s = 1 \oplus 1 \oplus 0 = 0$ , carry $= 1 \cdot 1 = 1$ . → $S_{0} = 0, C_{1} = 1$ .
Bit 1: $A_{1} = 1, B_{1} = 0, C_{1} = 1$ . $s = 1 \oplus 0 \oplus 1 = 0$ , carry $= 1 \cdot 0 + 0 \cdot 1 + 1 \cdot 1 = 1$ . → $S_{1} = 0, C_{2} = 1$ .
Bit 2: $A_{2} = 1, B_{2} = 0, C_{2} = 1$ . $s = 1 \oplus 0 \oplus 1 = 0$ , carry $= 1 \cdot 0 + 0 \cdot 1 + 1 \cdot 1 = 1$ . → $S_{2} = 0, C_{3} = 1$ .
Bit 3: $A_{3} = 1, B_{3} = 0, C_{3} = 1$ . $s = 1 \oplus 0 \oplus 1 = 0$ , carry $= 1 \cdot 0 + 0 \cdot 1 + 1 \cdot 1 = 1$ . → $S_{3} = 0, C_{4} = 1$ .

Result $= 1000 0_{2} = 16$ . Check $15 + 1 = 16$ . ✓ The carry born at bit 0 travelled through all four stages — the worst-case ripple.

L2.3

Compute $A - B$ for $A = 100 0_{2} (8)$ , $B = 001 1_{2} (3)$ using the RCA-as-subtractor trick: invert $B$ , set $C_{0} = 1$ .

Recall Solution

Two's-complement subtraction (see Two's complement): $A - B = A + \overset{ˉ}{B} + 1$ . $B = 0011 \Rightarrow \overset{ˉ}{B} = 1100$ . Set $C_{0} = 1$ . Now add $A = 1000$ and $\overset{ˉ}{B} = 1100$ with carry-in $1$ .

Bit 0: $A_{0} = 0, B_{0} = 0, C_{0} = 1$ . $s = 1$ , carry $= 0$ . → $S_{0} = 1, C_{1} = 0$ .
Bit 1: $A_{1} = 0, B_{1} = 0, C_{1} = 0$ . $s = 0$ , carry $= 0$ . → $S_{1} = 0, C_{2} = 0$ .
Bit 2: $A_{2} = 0, B_{2} = 1, C_{2} = 0$ . $s = 1$ , carry $= 0$ . → $S_{2} = 1, C_{3} = 0$ .
Bit 3: $A_{3} = 1, B_{3} = 1, C_{3} = 0$ . $s = 0$ , carry $= 1$ . → $S_{3} = 0, C_{4} = 1$ .

Result bits $= 010 1_{2} = 5$ , and $C_{4} = 1$ is simply discarded in two's-complement subtraction. Check $8 - 3 = 5$ . ✓ (Here $A > B$ , so a carry did come out. The next problem shows what happens when $A < B$ .)

L2.4

Edge case $A < B$ . Compute $A - B$ for $A = 001 0_{2} (2)$ , $B = 010 1_{2} (5)$ using the same subtractor trick (invert $B$ , $C_{0} = 1$ ). What comes out, and what does the absence of a carry-out mean?

Recall Solution

$A - B = A + \overset{ˉ}{B} + 1$ . Here $B = 0101 \Rightarrow \overset{ˉ}{B} = 1010$ , and $C_{0} = 1$ . Add $A = 0010$ , $\overset{ˉ}{B} = 1010$ , carry-in $1$ .

Bit 0: $A_{0} = 0, B_{0} = 0, C_{0} = 1$ . $s = 1$ , carry $= 0$ . → $S_{0} = 1, C_{1} = 0$ .
Bit 1: $A_{1} = 1, B_{1} = 1, C_{1} = 0$ . $s = 0$ , carry $= 1$ . → $S_{1} = 0, C_{2} = 1$ .
Bit 2: $A_{2} = 0, B_{2} = 0, C_{2} = 1$ . $s = 1$ , carry $= 0$ . → $S_{2} = 1, C_{3} = 0$ .
Bit 3: $A_{3} = 0, B_{3} = 1, C_{3} = 0$ . $s = 1$ , carry $= 0$ . → $S_{3} = 1, C_{4} = 0$ .

Result bits $= 110 1_{2}$ , and this time $C_{4} = 0$ — no carry came out. Read the result as a signed two's-complement number: top bit is $1$ , so it is negative, with value $110 1_{2} - 16 = 13 - 16 = - 3$ . And indeed $2 - 5 = - 3$ . ✓ What the missing carry means: when $A \geq B$ the $+ 1$ pushes past $2^{n}$ and a carry-out appears (that $C_{n} = 1$ we discard). When $A < B$ the sum never reaches $2^{n}$ , so no carry emerges ( $C_{n} = 0$ ) — the "borrow" is expressed instead as the two's-complement negative pattern in the result bits. In hardware, $C_{n} = 0$ after a subtraction is exactly the borrow signal telling you the answer went negative.

Level 3 — Analysis

L3.1

A single full adder's carry path has delay $t_{c} = 2 ns$ , and forming a sum bit from an arrived carry takes an XOR delay $t_{s} = 1 ns$ . What is the worst-case delay of a 32-bit RCA, and which output bit is last to settle?

Recall Solution

The carry is serial: $C_{i + 1}$ cannot be right until $C_{i}$ is right (see Propagation delay). The dominant term is the carry rippling through all $32$ stages: $32 \cdot t_{c} = 32 \times 2 ns = 64 ns (the full ripple to C_{32}) .$ The MSB sum $S_{31}$ is the last data bit, and it needs $C_{31}$ (the carry into stage 31), which appears after $31$ carry stages, then one more XOR to form the sum: $T (S_{31}) \approx 31 \cdot t_{c} + t_{s} = 31 \times 2 + 1 = 63 ns .$ Why the sum-XOR delay is usually dropped: $t_{s}$ is a single constant tacked on at the very end — it does not grow with $n$ , while the carry chain grows as $n \cdot t_{c}$ . So for the scaling story we write $T_{RCA} \approx n \cdot t_{c} = O (n)$ and fold the one-time $t_{s}$ into the " $\approx$ ". Here the honest number is $63 - 64 ns$ depending on whether you time $S_{31}$ or the final $C_{32}$ ; the point is that it is linear in $n$ .

L3.2

For unsigned 4-bit addition $A = 1001 (9)$ , $B = 1000 (8)$ , $C_{0} = 0$ : does the result fit in 4 bits? What is $C_{4}$ ?

Recall Solution

True value $9 + 8 = 17$ , but 4 unsigned bits hold only $0..15$ . So it cannot fit. Run it: bit 0 $1 + 0 = 1$ ( $S_{0} = 1$ ); bit 1 $0 + 0 = 0$ ; bit 2 $0 + 0 = 0$ ; bit 3 $1 + 1 = 1 0_{2}$ → $S_{3} = 0, C_{4} = 1$ . Result bits $000 1_{2} = 1$ with $C_{4} = 1$ . For unsigned numbers $C_{4} = 1$ signals the answer overflowed the word — the true value is $C_{4} S_{3} S_{2} S_{1} S_{0} = 1000 1_{2} = 17$ . ✓

L3.3

Signed two's-complement 4-bit: add $A = 0111 (+ 7)$ and $B = 0001 (+ 1)$ , $C_{0} = 0$ . Is there signed overflow? Use $overflow = C_{4} \oplus C_{3}$ .

Recall Solution

Bit 0: $A_{0} = 1, B_{0} = 1, C_{0} = 0$ : $s = 0, C_{1} = 1$ .
Bit 1: $A_{1} = 1, B_{1} = 0, C_{1} = 1$ : $s = 0, C_{2} = 1$ .
Bit 2: $A_{2} = 1, B_{2} = 0, C_{2} = 1$ : $s = 0, C_{3} = 1$ .
Bit 3: $A_{3} = 0, B_{3} = 0, C_{3} = 1$ : $s = 1, C_{4} = 0$ .

Result bits $= 100 0_{2}$ , which as signed two's complement is $- 8$ . But $7 + 1 = + 8$ , and $+ 8$ can't be stored in 4 signed bits (range $- 8.. + 7$ ). Overflow flag $= C_{4} \oplus C_{3} = 0 \oplus 1 = 1$ → overflow, yes (see Overflow detection). Notice $C_{4} = 0$ here, so relying on carry-out alone would have missed it — that is exactly why signed overflow uses $C_{4} \oplus C_{3}$ .

Level 4 — Synthesis

L4.1

Show how to build one full adder from two half adders plus one OR gate. A half adder takes two bits $x, y$ and outputs $s_{h} = x \oplus y$ and $c_{h} = x y$ . Give the wiring and prove the outputs match the full-adder equations.

Recall Solution

See the figure. Wire it like this:

HA1 takes $a, b$ → produces $p = a \oplus b$ (partial sum) and $g = ab$ (generate carry).
HA2 takes $p$ and $c_{in}$ → produces $s = p \oplus c_{in}$ and $q = p c_{in}$ .
OR gate: $c_{o u t} = g + q$ .

Figure — full adder from two half adders (text description): On the left, inputs

a

and

b

(blue) enter the first half adder HA1. HA1 emits two wires: a green wire

p = a \oplus b

(the partial sum) that goes down into the second half adder HA2, and a red wire

g = ab

(the generate carry) that runs straight across to the OR gate on the far right. The third input

c_{in}

(orange) also enters HA2. HA2 emits two wires: a blue wire

s = p \oplus c_{in}

that exits to the right as the final sum, and an orange wire

q = p c_{in}

that bends up into the OR gate. The OR gate combines

g

and

q

into the red output

c_{o u t}

. If the image does not load, redraw exactly that: two half-adder boxes stacked,

a, b

into the top one,

c_{in}

into the lower one, and an OR fed by both half-adders' carry outputs.

Proof the sum matches: $s = p \oplus c_{in} = (a \oplus b) \oplus c_{in} = a \oplus b \oplus c_{in}$ (folding two XORs, exactly as the [!intuition] box explained). ✓ Exactly the full-adder sum.

Proof the carry matches (the one nontrivial step — let's actually prove it): we must show $ab + (a \oplus b) c_{in} = ab + b c_{in} + a c_{in} .$ Intuition first: the left side says "carry out if $a, b$ both $1$ (generate), OR if exactly one of $a, b$ is $1$ and $c_{in} = 1$ (propagate an incoming carry)." The right side is the raw majority vote. They should agree because "at least two of three are $1$ " splits into two cases: either the two $1$ s are $a, b$ themselves ( $ab$ ), or one of them is $c_{in}$ paired with exactly one of $a, b$ . Algebra: expand $a \oplus b = a \overset{ˉ}{b} + \overset{a}{ˉ} b$ , so $(a \oplus b) c_{in} = a \overset{ˉ}{b} c_{in} + \overset{a}{ˉ} b c_{in} .$ Now build the right side and compare. Take $b c_{in} + a c_{in}$ and split each on the other variable: $b c_{in} = ab c_{in} + \overset{a}{ˉ} b c_{in}, a c_{in} = ab c_{in} + a \overset{ˉ}{b} c_{in} .$ So $b c_{in} + a c_{in} = ab c_{in} + \overset{a}{ˉ} b c_{in} + a \overset{ˉ}{b} c_{in}$ (the repeated $ab c_{in}$ term merges by $x + x = x$ ). That equals $ab c_{in} + (a \oplus b) c_{in}$ . Adding the $ab$ term: $ab + b c_{in} + a c_{in} = ab + ab c_{in} + (a \oplus b) c_{in} .$ Finally $ab + ab c_{in} = ab (1 + c_{in}) = ab$ (since $1 + anything = 1$ in OR, this is absorption). Hence $ab + b c_{in} + a c_{in} = ab + (a \oplus b) c_{in} . ✓$ So two half adders (see Half adder) plus an OR reproduce a full adder exactly.

L4.2

Design a combined adder/subtractor: one control line $Sub$ where $Sub = 0$ computes $A + B$ and $Sub = 1$ computes $A - B$ . What gate do you place on each $B_{i}$ line and what do you feed to $C_{0}$ ?

Recall Solution

Put an XOR gate on each $B_{i}$ line: feed $B_{i}^{'} = B_{i} \oplus Sub$ into the adder, and set $C_{0} = Sub$ .

When $Sub = 0$ : $B_{i}^{'} = B_{i} \oplus 0 = B_{i}$ (unchanged) and $C_{0} = 0$ . The adder computes $A + B$ . ✓
When $Sub = 1$ : $B_{i}^{'} = B_{i} \oplus 1 = \overset{ˉ}{B}_{i}$ (inverted) and $C_{0} = 1$ . The adder computes $A + \overset{ˉ}{B} + 1 = A + (two’s complement of B) = A - B$ . ✓ The XOR acts as a controlled inverter — that is the elegant trick: one control line reshapes the same Ripple-carry adder into both an adder and a subtractor.

L4.3

You have two 4-bit RCAs. Chain them into an 8-bit adder. Which carry wire connects them, and what is the total worst-case delay if each full adder's carry delay is $t_{c}$ ?

Recall Solution

Connect the carry-out of the low 4-bit adder ( $C_{4}$ ) to the carry-in of the high 4-bit adder. Set the low adder's carry-in to the overall $C_{0}$ ; the high adder's carry-out is the overall $C_{8}$ . The carry now ripples through all $8$ stages in series, so: $T \approx 8 t_{c} .$ Chaining does not help speed — it is still $O (n)$ . That linear growth is precisely the limitation the Carry-lookahead adder was invented to remove.

Level 5 — Mastery

L5.1

Full trace with signed interpretation. Compute $A + B$ for $A = 1011$ , $B = 1101$ in 4-bit RCA, $C_{0} = 0$ . Report: (a) unsigned result and whether it overflows unsigned; (b) signed two's-complement values of $A, B$ and result, and whether it overflows signed via $C_{4} \oplus C_{3}$ .

Recall Solution

Run the adder:

Bit 0: $A_{0} = 1, B_{0} = 1, C_{0} = 0$ : $s = 0, C_{1} = 1$ .
Bit 1: $A_{1} = 1, B_{1} = 0, C_{1} = 1$ : $s = 0, C_{2} = 1$ .
Bit 2: $A_{2} = 0, B_{2} = 1, C_{2} = 1$ : $s = 0, C_{3} = 1$ .
Bit 3: $A_{3} = 1, B_{3} = 1, C_{3} = 1$ : $s = 1, C_{4} = 1$ .

Result bits $= 100 0_{2}$ , with $C_{3} = 1$ and $C_{4} = 1$ .

(a) Unsigned: $A = 101 1_{2} = 11$ , $B = 110 1_{2} = 13$ , true sum $= 24$ . Stored bits $100 0_{2} = 8$ , and $C_{4} = 1$ (the missing $16$ ). Since $24 > 15$ , unsigned overflow: yes ( $C_{4} = 1$ ). Reconstruct: $1100 0_{2} = 24$ . ✓

(b) Signed: $A = 1011$ has top bit $1$ → negative. Value $= 101 1_{2} - 16 = 11 - 16 = - 5$ . $B = 1101 \to 13 - 16 = - 3$ . True sum $= - 5 + - 3 = - 8$ . Result bits $100 0_{2} = 8 - 16 = - 8$ , which is in range $[- 8, 7]$ , so it is correct. Overflow flag $= C_{4} \oplus C_{3} = 1 \oplus 1 = 0$ → signed overflow: no. ✓ The punchline: same bit pattern $1000$ , but $C_{4} = 1$ flags unsigned overflow while $C_{4} \oplus C_{3} = 0$ correctly says no signed overflow. The interpretation, not the bits, decides.

L5.2

A 16-bit RCA has carry delay $t_{c} = 1.5 ns$ per stage and each stage also has a fixed sum-XOR delay of $t_{s} = 1 ns$ after its carry arrives. Estimate when the MSB sum $S_{15}$ is valid.

Recall Solution

The carry must ripple through $16$ stages to reach $C_{16}$ , but $S_{15}$ only needs $C_{15}$ (the carry into the last stage), which is produced after $15$ carry stages: $15 \times 1.5 = 22.5 ns$ . Then the last XOR forms $S_{15}$ : add $t_{s} = 1 ns$ . $T (S_{15}) \approx 15 t_{c} + t_{s} = 22.5 + 1 = 23.5 ns .$ (The final carry-out $C_{16}$ settles slightly later at $16 \times 1.5 = 24 ns$ .) Still linear in $n$ — the defining weakness of ripple carry.

L5.3

Prove that for an $n$ -bit RCA the worst-case carry-propagation is a real, achievable case, by exhibiting inputs where the carry born at bit 0 forces every higher stage to wait. Use $n = 4$ as your witness.

Recall Solution

We need each stage to be in propagate mode ( $A_{i} \oplus B_{i} = 1$ ) so it merely passes an incoming carry, and a carry that is actually generated at bit 0. Take $A = 0001$ , $B = 0111$ , $C_{0} = 0$ :

Bit 0: $A_{0} = 1, B_{0} = 1$ : generate → $C_{1} = 1$ , $S_{0} = 0$ .
Bit 1: $A_{1} = 0, B_{1} = 1$ : propagate ( $0 \oplus 1 = 1$ ), $C_{1} = 1$ in → $C_{2} = 1$ , $S_{1} = 0$ .
Bit 2: $A_{2} = 0, B_{2} = 1$ : propagate, $C_{2} = 1$ in → $C_{3} = 1$ , $S_{2} = 0$ .
Bit 3: $A_{3} = 0, B_{3} = 0$ : $A_{3} \oplus B_{3} = 0$ , incoming $C_{3} = 1$ → $s = 1$ , $C_{4} = 0$ , $S_{3} = 1$ .

The carry generated at bit 0 was propagated untouched through bits 1 and 2, and only "consumed" at bit 3. $S_{3}$ therefore could not settle until the carry crossed three stages. Result $= 0001 + 0111 = 100 0_{2} = 8$ . ✓

So what — tying the trace back to the general claim: this is not a fluke of $n = 4$ . The recipe generalises: put a generate at bit 0 (set $A_{0} = B_{0} = 1$ ) and make every middle bit a propagate (set exactly one of $A_{i}, B_{i}$ to $1$ so $A_{i} \oplus B_{i} = 1$ ). Then the single carry born at bit 0 is forced to travel through all $n - 1$ intermediate stages before any high sum bit can settle — the carry chain has length $n$ . Because such an input pattern always exists for any width $n$ , the $O (n)$ worst-case latency is genuinely achievable, not a pessimistic over-estimate. That is exactly why real machines abandon ripple carry for wide words in favour of the Carry-lookahead adder.

Connections

Ripple-carry adder — the parent note these exercises drill.
Full adder — the block traced in every stage; rebuilt in L4.1.
Half adder — combined in L4.1 to form a full adder.
Two's complement — powers the subtraction in L2.3, L2.4 and L4.2.
Overflow detection — the $C_{n} \oplus C_{n - 1}$ rule in L3.3 and L5.1.
Propagation delay — the timing analysed in L3.1, L4.3, L5.2.
Carry-lookahead adder — the fix for the $O (n)$ delay these problems expose.
Combinational circuits — the family the RCA belongs to.