Postpone carries to the end

Adding N numbers with ordinary adders makes every addition wait for a full carry chain. A carry-save adder (CSA) takes three numbers and reduces them to two: a sum vector and a carry vector.

It uses one independent full adder per bit position, so there is no carry propagation. Only the last step needs a real carry-propagate adder.

The compressor works bitwise: at each position it adds three bits x + y + z into a sum bit (weight 1) and a carry bit (weight 2). The invariant is simply that the total value is preserved:

Follow the bit weights

For 7 x 7, the three nonzero partial-product rows are 00111, 01110 and 11100. At weight 4, three ones represent 12: the compressor emits one sum dot of weight 4 and one saved carry dot of weight 8. The next panel has three weight-8 dots; a second stage turns those 24 into a weight-8 sum and a weight-16 carry. No column consumes a carry from its neighbour within the same stage.

The last panel has at most two dots per column. One way to arrange them into two rows is 11111 (31) and 10010 (18). Only now do we propagate carries to get 110001 (49). These are unsigned bit heaps; signed multiplication also needs its sign-bit treatment.

The same invariant in vector form

x = 00111 =  7
y = 01110 = 14
z = 11100 = 28
s = x XOR y XOR z                 = 10101 = 21
c = (x AND y) OR (x AND z) OR (y AND z)
                                  = 01110 = 14
saved carry, widened then shifted = 011100 = 28
final add: 010101 + 011100         = 110001 = 49

The vector compressor groups all columns at once, so its two rows need not match the dot diagram's staged column grouping. Both preserve the same total. The unshifted c stores a carry at its source position; shift it left once, retaining the new top bit, before adding it to s. Adding s + c would incorrectly give 35.

How many levels

Each CSA level reduces the number of rows by a factor of 2/3. The most rows that k levels can reduce to two are 2, 3, 4, 6, 9, 13, 19, 28, 42, 63, ... (each is ⌊1.5 × the previous⌋). So the depth grows like log₁.₅ of the number of rows:

A Wallace tree applies this reduction as early and as aggressively as possible. A Dadda tree uses the same stage count but fewer compressors.

Both finish with a fast carry-propagate adder. Compared with an array multiplier, whose depth is proportional to N, the tree's depth is proportional to log N.

Common mistakes

Testbench

A two-level CSA reduction checked against a+b+c+d for all 65536 inputs.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

module csa #(parameter int W = 8) (
  input  logic [W-1:0] x, y, z,
  output logic [W-1:0] s, c           // value = s + (c << 1)
);
  assign s = x ^ y ^ z;                              // per-bit sum
  assign c = (x & y) | (x & z) | (y & z);            // per-bit carry (majority)
endmodule

// Four rows reduced with two CSA levels, then one ordinary add
module add4_csa (
  input  logic [3:0] a, b, c, d,
  output logic [5:0] sum
);
  logic [5:0] s1, c1, s2, c2;
  csa #(6) l1 (.x({2'b0,a}), .y({2'b0,b}), .z({2'b0,c}), .s(s1), .c(c1));
  // c1[5] is 0 here. Bits [5:4] of all three l1 inputs are zero. At full width, keep every carry bit.
  csa #(6) l2 (.x(s1), .y({c1[4:0],1'b0}), .z({2'b0,d}), .s(s2), .c(c2));
  // c2[5] is 0 here. The three bit-5 inputs (s1[5], c1[4], and the zero bit) are all 0. At full width, keep every carry bit.
  assign sum = s2 + {c2[4:0], 1'b0};                 // single carry-propagate add at the end
endmodule

module tb_csa;
  timeunit 1ns; timeprecision 1ps;
  logic [3:0] a, b, c, d;
  logic [5:0] sum;
  add4_csa dut (.*);
  int errors = 0;
  int expected;
  initial begin
    for (int i = 0; i < 65536; i++) begin            // every combination of four 4-bit rows
      {a, b, c, d} = i[15:0]; #1;
      expected = int'(a) + int'(b) + int'(c) + int'(d);
      if (sum !== expected[5:0]) begin
        errors++;
        $display("FAIL csa: a=%0d b=%0d c=%0d d=%0d expected=%0d actual=%b",
                 a, b, c, d, expected, sum);
      end
    end
    if (errors != 0) $fatal(1, "FAIL csa: %0d mismatching cases", errors);
    if (errors == 0) $display("PASS: two CSA levels plus one add equal a+b+c+d for all 65536 inputs");
    $finish;
  end
endmodule

Related topics

• Shift-add multiplier

• RTL for timing