Adders and Carry Logic in RTL

Every ALU, every address calculation, every loop counter in a real design eventually comes down to an adder. The Digital Electronics path already derived the half adder, the full adder, ripple-carry addition, and the generate/propagate equations behind carry-lookahead addition from first principles — this lesson does not repeat that derivation. Its job is the next step in the design method this path is built around: taking an equation that is already known to be correct and turning it into synthesizable RTL that a tool can actually build, then checking that the resulting hardware really does what the equation promised.

Reading time: about 13 minutes.

9.1 Three ways to add, one job to do

Three adder architectures appear repeatedly in real designs and in interviews, and all three compute exactly the same function — n-bit addition with carry-in and carry-out. They differ only in how fast the carry gets from bit 0 to bit n−1, and in how much hardware that speed costs.

• Ripple-carry, covered in Combinational Logic Circuits: a chain of full adders, each waiting for the carry out of the one before it — simple, but its delay grows with bit width.
• Carry-lookahead, covered in Fast Adders and Carry-Lookahead: every bit's generate (G_i = A_iB_i) and propagate (P_i = A_i⊕B_i) are computed in parallel, and every carry C_i+1 = G_i + P_iC_i expands into a sum-of-products in the G's, P's and C₀ alone, so none waits on the one before it.
• Carry-select, introduced here for the first time: compute the upper half of the sum twice, once assuming the lower half's carry-out is 0 and once assuming it is 1, then select between the two precomputed answers once the real carry-out is known.

This lesson builds each architecture as a verified Verilog module, then compares how its delay scales with bit width — the question an interviewer is usually really asking when they say "design a fast adder."

9.2 Ripple-carry adder: the direct translation

A ripple-carry adder is the most literal RTL translation of the full-adder equations there is: instantiate one full adder per bit, and wire each stage's carry-out to the next stage's carry-in.

module full_adder (
    input  wire a,
    input  wire b,
    input  wire cin,
    output wire sum,
    output wire cout
);
    assign sum  = a ^ b ^ cin;
    assign cout = (a & b) | (a & cin) | (b & cin);
endmodule

module rca4 (
    input  wire [3:0] a,
    input  wire [3:0] b,
    input  wire       cin,
    output wire [3:0] sum,
    output wire       cout
);
    wire [3:0] c;
    full_adder fa0 (.a(a[0]), .b(b[0]), .cin(cin),  .sum(sum[0]), .cout(c[0]));
    full_adder fa1 (.a(a[1]), .b(b[1]), .cin(c[0]), .sum(sum[1]), .cout(c[1]));
    full_adder fa2 (.a(a[2]), .b(b[2]), .cin(c[1]), .sum(sum[2]), .cout(c[2]));
    full_adder fa3 (.a(a[3]), .b(b[3]), .cin(c[2]), .sum(sum[3]), .cout(cout));
endmodule

Every line here is a direct restatement of the sum and carry equations from the combinational-logic lesson — sum = a ^ b ^ cin is Sum = A⊕B⊕C_in, and the cout assignment is the majority function of the three inputs. The only genuinely new decision in this module is purely structural: naming the internal carry wires c[0] through c[2] and wiring each full adder's cout into the next one's cin, which is what makes this a 4-bit adder rather than four independent 1-bit adders.

A self-checking testbench printed a few sample cases, including the 11 + 6 example from the carry-lookahead lesson, then compared every one of the 512 possible input combinations (16 × 16 × 2) against the + operator's own computation:

PASS: 11+6+cin0 = 17
PASS: 15+15+cin1 = 31
PASS: 0+0+cin0 = 0
PASS: 7+9+cin0 = 16
ALL 512 RCA4 CASES PASSED (exhaustive)

Running this design through Yosys's synthesis flow (synth followed by check) reports zero problems and no inferred latches — every output here is a plain continuous assignment, so there is no storage anywhere in this circuit, exactly as a combinational adder should synthesize.

9.3 Carry-lookahead adder: the equations, directly as RTL

The carry-lookahead lesson already expanded every carry into a sum-of-products in G, P and C₀ alone. Translating that into RTL is almost mechanical: compute every G_i and P_i in one vectorized line each, then write each carry as its own continuous assignment in that expanded form, rather than as a chain of module instances.

module cla4 (
    input  wire [3:0] a,
    input  wire [3:0] b,
    input  wire       cin,
    output wire [3:0] sum,
    output wire       cout
);
    wire [3:0] g, p;
    wire [4:0] c;

    assign g = a & b;
    assign p = a ^ b;
    assign c[0] = cin;

    // Every carry is written directly in g, p and c[0]: none references c[1..3].
    assign c[1] = g[0] | (p[0] & c[0]);
    assign c[2] = g[1] | (p[1] & g[0]) | (p[1] & p[0] & c[0]);
    assign c[3] = g[2] | (p[2] & g[1]) | (p[2] & p[1] & g[0])
                | (p[2] & p[1] & p[0] & c[0]);
    assign c[4] = g[3] | (p[3] & g[2]) | (p[3] & p[2] & g[1])
                | (p[3] & p[2] & p[1] & g[0]) | (p[3] & p[2] & p[1] & p[0] & c[0]);

    assign sum  = p ^ c[3:0];
    assign cout = c[4];
endmodule

Two details here are exactly the two equations the earlier lesson derived. g = a & b and p = a ^ b compute all four bits' generate and propagate signals in one vectorized statement each, with no dependency between bits — the entire reason lookahead is fast. Each c[i+1] assignment is the expanded sum-of-products the earlier lesson wrote out algebraically, so every carry depends only on g, p and c[0] and none waits on the one before it. That matters: had the carries been written recursively, as c[i+1] = g[i] | p[i] & c[i], the RTL would describe exactly the same serial chain as ripple carry, and any lookahead structure would come only from the synthesis tool restructuring it.

The same self-checking testbench, run against cla4 instead of rca4. Each testbench prints four sample cases, then checks all 512 combinations of a, b and cin against the + operator:

PASS: 11+6+cin0 = 17
PASS: 15+15+cin1 = 31
PASS: 0+0+cin0 = 0
PASS: 7+9+cin0 = 16
ALL 512 CLA4 CASES PASSED (exhaustive)

Thus, both modules compute the identical function — established here by exhaustive simulation over all 512 inputs, and independently by a Yosys SAT equivalence proof (miter -equiv followed by sat -verify -prove-asserts, which reports SUCCESS for rca4 against both cla4 and csel4) — and both pass Yosys's check with zero problems and no inferred latches. The difference between them is invisible in simulation; it only shows up once the design is placed and timed, as section 9.5 describes.

9.4 Carry-select adder: precompute both answers, then choose

Carry-select addition starts from an observation that neither ripple-carry nor lookahead exploits directly: an n-bit addition can be split into a lower half and an upper half, and the lower half's own carry-out is a single bit with exactly two possible values. If the upper half's sum is computed twice — once for each possible value of that one bit — then the instant the real carry-out becomes available, a multiplexer can select the already-correct answer immediately, without the upper half ever waiting for the lower half to finish.

module csel4 (
    input  wire [3:0] a,
    input  wire [3:0] b,
    input  wire       cin,
    output wire [3:0] sum,
    output wire       cout
);
    // Lower half: carry-in is known already, one ripple-carry pair is enough.
    wire [1:0] sum_lo;
    wire       c0_hidden, c_lo;
    full_adder fa0 (.a(a[0]), .b(b[0]), .cin(cin),       .sum(sum_lo[0]), .cout(c0_hidden));
    full_adder fa1 (.a(a[1]), .b(b[1]), .cin(c0_hidden), .sum(sum_lo[1]), .cout(c_lo));

    // Upper nibble: computed twice in parallel with the lower nibble -- once
    // assuming its carry-in is 0, once assuming it is 1 -- so c_lo only has
    // to steer a mux, not wait for either upper-half addition to start.
    wire [1:0] sum_hi0, sum_hi1;
    wire       c2_0, c2_1, cout0, cout1;
    full_adder fa2_0 (.a(a[2]), .b(b[2]), .cin(1'b0), .sum(sum_hi0[0]), .cout(c2_0));
    full_adder fa3_0 (.a(a[3]), .b(b[3]), .cin(c2_0),  .sum(sum_hi0[1]), .cout(cout0));
    full_adder fa2_1 (.a(a[2]), .b(b[2]), .cin(1'b1), .sum(sum_hi1[0]), .cout(c2_1));
    full_adder fa3_1 (.a(a[3]), .b(b[3]), .cin(c2_1),  .sum(sum_hi1[1]), .cout(cout1));

    assign sum  = {c_lo ? sum_hi1 : sum_hi0, sum_lo};
    assign cout = c_lo ? cout1 : cout0;
endmodule

This is a genuinely different trade: it is built entirely from the same plain full adders as the ripple-carry design, with no generate/propagate equation anywhere in it, and it reduces delay by paying for a duplicated upper half rather than for lookahead logic. Note that each half is still a 2-bit ripple chain internally; what changes is that the upper half no longer waits for the lower half, so the worst-case delay is roughly one half's ripple time plus a mux rather than the full 4-bit ripple.

PASS: 11+6+cin0 = 17
PASS: 15+15+cin1 = 31
PASS: 0+0+cin0 = 0
PASS: 7+9+cin0 = 16
ALL 512 CSEL4 CASES PASSED (exhaustive)

Yosys's check again reports zero problems. The cell counts are worth measuring rather than guessing. With the hierarchy kept (synth -top csel4), each full_adder maps to 7 cells, so csel4 is 6 × 7 + 3 $_MUX_ = 45 cells against rca4's 4 × 7 = 28. Flattened (synth -flatten -top csel4), csel4 drops to 30 cells, because the constant 1'b0 and 1'b1 carry-ins let synthesis simplify the duplicated adders; rca4 stays at 28 and cla4 comes out at 20. Small widths flatter or punish every architecture unpredictably, so the 4-bit numbers say more about synthesis than about the architectures at 32 or 64 bits.

9.5 Comparing critical paths

All three adders above passed the same exhaustive check, which is exactly the point: functional correctness alone cannot distinguish them. What distinguishes them is how the worst-case delay through each one grows as n, the bit width, grows.

Ripple-carry's delay grows directly with n: the last stage cannot begin its real work until a carry has rippled all the way from bit 0. Carry-lookahead does not escape growth entirely — its own equations get wider and more gate-heavy as n grows, which is why real wide adders apply generate/propagate hierarchically, across fixed-size groups, rather than flattening one lookahead expression across a full 32-bit or 64-bit word. Carry-select sits in between. Each half is itself a ripple chain, but the upper half no longer waits for the lower half, so even a single two-way split roughly halves the ripple delay: about n/2 stages plus one mux. Chaining k blocks, each selecting its pair of guesses with the carry from the block before it, gives delay on the order of n/k + k — the block ripple plus one mux per block — which, with well-chosen (often growing) block sizes, is about O(√n).

Thus, no single architecture is simply "the fast one": ripple-carry costs the least hardware and suits narrow or non-critical adders; lookahead keeps delay growing slowly with width, at the price of lookahead logic that itself must be built hierarchically past a few bits; carry-select spends hardware on outright duplication for a moderate speed-up. Wide adders on a real critical path are most often parallel-prefix designs (Kogge-Stone, Brent-Kung, Sklansky), which organize generate/propagate as a logarithmic-depth tree, or whatever architecture the synthesis tool's datapath generator selects for the timing target.

9.6 Interview questions

Why does a carry-select adder need two copies of the upper-half addition logic? Its correct carry-in is not known until the lower half finishes, and waiting for it would reintroduce the ripple delay this architecture exists to avoid. Computing the upper half once per possible carry-in value lets both answers be ready before the real carry-out arrives, so only a mux delay is added once it does.

If a ripple-carry adder and a carry-lookahead adder are given the same two numbers, will they ever disagree? No — both compute the same function. A handful of matching test vectors would not prove that, but for a 4-bit adder all 512 inputs can be simulated, and a formal equivalence check (a Yosys miter plus SAT proof) confirms it without enumerating inputs at all. They differ only in delay, never in the answer.

Why do real 32-bit or 64-bit adders not use one flat carry-lookahead block spanning every bit? The lookahead equations themselves grow wider and more gate-heavy as bit position grows. Real wide adders apply generate/propagate hierarchically, across fixed-size groups, to keep the lookahead hardware at each level bounded.

What would a synthesized netlist show that tells you an adder is carry-select rather than ripple-carry? In a hierarchical netlist, two adder instances per bit past the split point, plus muxes selecting between the two precomputed sums and carry-outs — here 6 full_adder instances and 3 muxes (45 cells) against rca4's 4 instances (28 cells). After flattening, the duplicated copies with constant carry-ins simplify, so csel4 shrinks to 30 cells and the mux structure is the more reliable signature.