Arithmetic Circuits: Adders & Multipliers

Datapaths are built from adders and multipliers. Learn half and full adders, ripple-carry adders, generate/propagate, carry-lookahead, carry-select and parallel-prefix adders (Kogge-Stone, Brent-Kung), subtraction and overflow, array and Wallace-tree multipliers and Booth encoding — with Verilog that is formally proven correct.

An adder's speed is set by how fast the carry travels from the least to the most significant bit. The simple ripple-carry adder passes it bit by bit — cheap but slow. Faster adders compute carries in parallel from 'generate' and 'propagate' signals, trading area for speed.

Multipliers generate many partial products and add them; the art is reducing them quickly (Booth encoding halves them, Wallace/Dadda trees add them in logarithmic depth). CPUs, GPUs, DSPs and AI accelerators are dominated by these circuits.

An analogy

Ripple carry is like a queue passing a message person to person; carry-lookahead is a manager who sees everyone's situation at once and tells each person the answer directly.

Half adder, full adder, ripple carry

A half adder adds two bits (sum = XOR, carry = AND). A full adder also accepts a carry-in. Chaining N full adders gives an N-bit ripple-carry adder: simple and small, but the carry may have to travel through all N stages.

Generate and propagate

A bit position generates a carry when both inputs are 1, and propagates an incoming carry when exactly one is 1. The carry recurrence c_{i+1} = gᵢ + pᵢcᵢ can be expanded so every carry depends only on g, p and c₀ — computed in parallel (carry-lookahead). Group g/p signals combine hierarchically for wider adders.

Fast adder families

Different area/speed/wiring trade-offs:

Multipliers

An N×N multiplier forms N partial products (AND gates) and sums them. Radix-4 Booth encoding recodes the multiplier into digits {−2…+2}, halving the partial products. Wallace or Dadda trees of carry-save adders (3:2 compressors) reduce them in O(log N) depth, and a fast final adder produces the result. Fused multiply-add (FMA) units power floating-point and AI hardware.

Formulas

Worked example: Adding by hand

Given: a = 1010 (10), b = 1100 (12), c_in = 0

Find: sum, c_out.

Answer: sum = 0110, c_out = 1

Worked example: Ripple vs prefix delay

Given: 32-bit adder, 2 gate delays per carry stage

Find: Critical path.

Answer: ≈ 64 vs ≈ 7 gate delays

Worked example: Booth partial products

Given: 32 × 32 multiplier

Find: Partial products.

Answer: ≈ 17 partial products with radix-4 Booth

Ripple-carry and carry-lookahead adders in Verilog

// 1-bit full adder
module full_adder (
    input  wire a, b, cin,
    output wire sum, cout
);
    assign sum  = a ^ b ^ cin;
    assign cout = (a & b) | (cin & (a ^ b));
endmodule

// N-bit ripple-carry adder built from full adders
module rca #(parameter N = 4) (
    input  wire [N-1:0] a, b,
    input  wire         cin,
    output wire [N-1:0] sum,
    output wire         cout
);
    wire [N:0] c;
    assign c[0] = cin;
    genvar i;
    generate
        for (i = 0; i < N; i = i + 1) begin : g_fa
            full_adder fa (.a(a[i]), .b(b[i]), .cin(c[i]), .sum(sum[i]), .cout(c[i+1]));
        end
    endgenerate
    assign cout = c[N];
endmodule

// 4-bit carry-lookahead adder: all carries computed from generate/propagate
module cla4 (
    input  wire [3:0] a, b,
    input  wire       cin,
    output wire [3:0] sum,
    output wire       cout
);
    wire [3:0] g = a & b;   // generate
    wire [3:0] p = a ^ b;   // propagate
    wire [4:0] c;
    assign c[0] = cin;
    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

Both describe the same function; the CLA computes every carry in two logic levels instead of waiting for the ripple. Synthesised with Yosys (generic gates), the 4-bit RCA uses 24 cells and the CLA 29 — more area for less delay.

Formal proof that both adders are correct for every input

// adder_check.v - both implementations must equal a + b + cin
module adder_check (input wire [3:0] a, b, input wire cin);
    wire [3:0] s_rca, s_cla;
    wire c_rca, c_cla;
    rca #(.N(4)) u_rca (.a(a), .b(b), .cin(cin), .sum(s_rca), .cout(c_rca));
    cla4 u_cla (.a(a), .b(b), .cin(cin), .sum(s_cla), .cout(c_cla));
    always @(*) begin
        assert ({c_rca, s_rca} == a + b + cin);
        assert ({c_cla, s_cla} == a + b + cin);
    end
endmodule

// Yosys script:
//   read_verilog adders.v
//   read_verilog -formal adder_check.v
//   prep -top adder_check; flatten; chformal -lower
//   sat -prove-asserts -verify
// Result: "SAT proof finished - no model found: SUCCESS!"

Instead of testing a few vectors, a SAT solver proves the assertions hold for all 2⁹ input combinations. This is formal equivalence checking — the same idea tools use to prove a synthesised netlist matches the RTL.

Common mistakes

Applications

Key takeaways

Going further