Ripple-carry Adder

Gate-Level CPU Simulator

To add two $n$ -bit numbers, line up $n$ full-adders side by side. The carry-out of bit $i$ wires into the carry-in of bit $i + 1$ . The carry-in of bit 0 is hard-wired to 0 (no incoming carry yet). The final carry-out of bit $n - 1$ becomes the $(n + 1)$ -th bit of the sum — overflow detection lives there.

def ripple_carry_add(A, B):
    """Add two n-bit numbers (LSB-first lists of 0/1). Returns the
    (n+1)-bit sum, also LSB-first."""
    assert len(A) == len(B)
    n = len(A)
    result = []
    carry = 0
    for i in range(n):
        s, carry = full_adder(A[i], B[i], carry)
        result.append(s)
    result.append(carry)             # final carry-out is the top bit
    return result

Ripple-carry adder (4-bit)A = 13, B = 3 → A + B = 16

demo:

flip any A or B bit, then pulse — watch the carry ripple right→left through the chain (LSB on right, MSB on left)

Where does "ripple" come from?

Each FA's carry-out is the next FA's carry-in. So FA[3] can't settle until FA[2] has, which can't until FA[1], all the way back to FA[0]. The carry walks across the chain one stage at a time, and that walk is the ripple. The 15 + 1 = 16 demo is the worst case: a single carry generated at the LSB has to travel through every single FA before the answer is right. Watch the green light propagate end to end.

Why is this the critical path?

For an n-bit ripple-carry adder, the longest chain of dependent gate-delays is the carry chain itself — roughly n FAs in series. For 32-bit addition that's about 32 gate-delays one after the other, which in many CPUs is what caps the clock speed. Carry-lookahead adders break the dependency: compute per-bit "generate" and "propagate" signals in parallel, then combine them in O(log n) depth. More gates, less latency — the trade-off you make once clock frequency starts to matter.

Why is there a second animation below?

The schematic above shows structure — what's wired to what. The animation below shows the same algorithm with bit values drawn at every stage, so you can read the carry sequence column by column. The schematic for "where do the wires go," the animation for "what's actually flowing through them."

The name "ripple-carry" describes the timing: a change in bit 0's inputs has to ripple through every full-adder before bit $n - 1$ settles. That's $n$ gate delays in the worst case. For 32-bit addition that's about 32 gate delays serially, which is the entire critical path of single-cycle arithmetic. (See the performance page for why this matters and what carry-lookahead does instead.)