Dadda Multiplier in Verilog: Fast Partial-Product Reduction

// Half adder: sum = a^b, carry = a&b
module ha(input a, input b, output s, output c);
  assign s = a ^ b;
  assign c = a & b;
endmodule

// Full adder: sum = a^b^cin, carry = majority(a,b,cin)
module fa(input a, input b, input cin, output s, output c);
  assign s = a ^ b ^ cin;
  assign c = (a & b) | (b & cin) | (a & cin);
endmodule

// Unsigned 4x4 Dadda tree multiplier.
// Partial-product matrix column heights: 1,2,3,4,3,2,1 (max = 4).
// Dadda reduction schedule: 4 -> 3 -> 2, then a final carry-propagate adder.
module dadda4(input [3:0] a, input [3:0] b, output [7:0] p);

  // --- Partial products pp_ij = a[i] & b[j], weight 2^(i+j) ---
  wire pp00 = a[0] & b[0];
  wire pp01 = a[0] & b[1];
  wire pp02 = a[0] & b[2];
  wire pp03 = a[0] & b[3];
  wire pp10 = a[1] & b[0];
  wire pp11 = a[1] & b[1];
  wire pp12 = a[1] & b[2];
  wire pp13 = a[1] & b[3];
  wire pp20 = a[2] & b[0];
  wire pp21 = a[2] & b[1];
  wire pp22 = a[2] & b[2];
  wire pp23 = a[2] & b[3];
  wire pp30 = a[3] & b[0];
  wire pp31 = a[3] & b[1];
  wire pp32 = a[3] & b[2];
  wire pp33 = a[3] & b[3];

  // --- Stage 1: reduce max height 4 -> 3 ---
  // col3 has height 4: one HA on (pp03,pp12); carry c1_3 goes to col4.
  wire s1_3, c1_3;
  ha u_s1c3 (.a(pp03), .b(pp12), .s(s1_3), .c(c1_3));
  // col4 becomes {pp13,pp22,pp31,c1_3}=4: one HA on (pp13,pp22); carry c1_4 to col5.
  wire s1_4, c1_4;
  ha u_s1c4 (.a(pp13), .b(pp22), .s(s1_4), .c(c1_4));

  // Heights after stage 1:
  // c0:1  c1:2  c2:3  c3:{s1_3,pp21,pp30}  c4:{s1_4,pp31,c1_3}  c5:{pp23,pp32,c1_4}  c6:1

  // --- Stage 2: reduce height 3 -> 2 (LSB first so carries are absorbed) ---
  // col2 (3): HA on (pp02,pp11); carry c2_2 to col3.
  wire s2_2, c2_2;
  ha u_s2c2 (.a(pp02), .b(pp11), .s(s2_2), .c(c2_2));
  // col3 becomes 4 -> FA on (s1_3,pp21,pp30); carry c2_3 to col4.
  wire s2_3, c2_3;
  fa u_s2c3 (.a(s1_3), .b(pp21), .cin(pp30), .s(s2_3), .c(c2_3));
  // col4 becomes 4 -> FA on (s1_4,pp31,c1_3); carry c2_4 to col5.
  wire s2_4, c2_4;
  fa u_s2c4 (.a(s1_4), .b(pp31), .cin(c1_3), .s(s2_4), .c(c2_4));
  // col5 becomes 4 -> FA on (pp23,pp32,c1_4); carry c2_5 to col6.
  wire s2_5, c2_5;
  fa u_s2c5 (.a(pp23), .b(pp32), .cin(c1_4), .s(s2_5), .c(c2_5));

  // Two height-2 rows feed the final carry-propagate adder.
  wire [7:0] rowA = {1'b0, pp33,  s2_5, s2_4, s2_3, s2_2, pp01, pp00};
  wire [7:0] rowB = {1'b0, c2_5,  c2_4, c2_3, c2_2, pp20, pp10, 1'b0};

  assign p = rowA + rowB;   // final carry-propagate adder
endmodule

module tb;
  reg  [3:0] a, b;
  wire [7:0] p;
  integer i, j, errors;

  dadda4 dut (.a(a), .b(b), .p(p));

  initial begin
    errors = 0;
    for (i = 0; i < 16; i = i + 1) begin
      for (j = 0; j < 16; j = j + 1) begin
        a = i[3:0]; b = j[3:0];
        #1;
        if (p !== (i * j)) begin
          errors = errors + 1;
          $display("FAIL %0d x %0d : expected %0d got %0d", i, j, i*j, p);
        end
      end
    end

    // A few explicit checks the reader can match against the product table.
    a = 4'd15; b = 4'd15; #1;
    if (p === 8'd225) $display("PASS 15 x 15 = 225"); else $display("FAIL 15x15 got %0d", p);
    a = 4'd10; b = 4'd6;  #1;
    if (p === 8'd60)  $display("PASS 10 x 6 = 60");  else $display("FAIL 10x6 got %0d", p);
    a = 4'd7;  b = 4'd9;  #1;
    if (p === 8'd63)  $display("PASS 7 x 9 = 63");   else $display("FAIL 7x9 got %0d", p);
    a = 4'd13; b = 4'd0;  #1;
    if (p === 8'd0)   $display("PASS 13 x 0 = 0");   else $display("FAIL 13x0 got %0d", p);

    if (errors == 0)
      $display("ALL 256 PRODUCTS PASSED (exhaustive 4x4 sweep)");
    else
      $display("TOTAL FAILURES: %0d", errors);
    $finish;
  end
endmodule

PASS 15 x 15 = 225
PASS 10 x 6 = 60
PASS 7 x 9 = 63
PASS 13 x 0 = 0
ALL 256 PRODUCTS PASSED (exhaustive 4x4 sweep)
The log shows the four spot-check products and the line ALL 256 PRODUCTS PASSED, which means the hand-built adder tree reproduces a*b for every one of the 16×16 input combinations — a single mis-wired half or full adder would surface as a FAIL line.

This variant is width-parameterized. It builds the partial-product matrix, computes the Dadda height sequence for the given W, and compresses each column stage by stage with full adders (3:2) and half adders down to height 2, then adds the two surviving rows. Here it is instantiated at W = 8 and verified over the full 8×8 product space.
dadda_mult.vSimulation log
// Parameterized unsigned Dadda-tree multiplier (any width W).
// The partial-product matrix is compressed following the Dadda height
// schedule (2,3,4,6,9,13,...): at each stage a column is reduced only as
// far as the current target height, using full adders (3:2) and at most
// the half adders needed, with carries rippling to the next column. The
// surviving two rows are summed by a final carry-propagate adder (the "+").
module dadda_mult #(parameter W = 8) (
  input  [W-1:0]   a,
  input  [W-1:0]   b,
  output reg [2*W-1:0] p
);
  localparam COLS = 2*W;
  localparam DEPTH = 4*W;         // generous per-column bit storage

  integer i, j, c, st, k, t, h;
  integer cnt   [0:COLS-1];       // live bit count per column
  reg     mat   [0:COLS-1][0:DEPTH-1];
  integer dd    [0:63];           // Dadda number sequence
  reg x0, x1, x2, sbit, cbit;
  reg [2*W-1:0] rowA, rowB;

  always @(*) begin
    // 1) zero the column counts
    for (c = 0; c < COLS; c = c + 1) cnt[c] = 0;

    // 2) generate the W*W partial products into their weight columns
    for (i = 0; i < W; i = i + 1)
      for (j = 0; j < W; j = j + 1) begin
        mat[i+j][cnt[i+j]] = a[i] & b[j];
        cnt[i+j] = cnt[i+j] + 1;
      end

    // 3) build Dadda numbers: 2,3,4,6,9,... until one reaches the max height W
    dd[0] = 2; k = 0;
    while (dd[k] < W) begin
      dd[k+1] = (3 * dd[k]) / 2;
      k = k + 1;
    end
    // dd[k] >= W ; stage targets are dd[k-1], dd[k-2], ... , dd[0]=2

    // 4) reduction stages, largest Dadda target first
    for (st = k - 1; st >= 0; st = st - 1) begin
      t = dd[st];
      for (c = 0; c < COLS; c = c + 1) begin
        while (cnt[c] > t) begin
          h = cnt[c];
          if ((h - t) >= 2) begin
            // full adder on the three top-most bits of this column
            x0 = mat[c][h-1]; x1 = mat[c][h-2]; x2 = mat[c][h-3];
            sbit = x0 ^ x1 ^ x2;
            cbit = (x0 & x1) | (x1 & x2) | (x0 & x2);
            cnt[c] = h - 3;
          end else begin
            // half adder on the two top-most bits
            x0 = mat[c][h-1]; x1 = mat[c][h-2];
            sbit = x0 ^ x1;
            cbit = x0 & x1;
            cnt[c] = h - 2;
          end
          mat[c][cnt[c]] = sbit;            // sum stays in this column
          cnt[c] = cnt[c] + 1;
          mat[c+1][cnt[c+1]] = cbit;        // carry moves one column up
          cnt[c+1] = cnt[c+1] + 1;
        end
      end
    end

    // 5) final carry-propagate adder over the two surviving rows
    rowA = {2*W{1'b0}};
    rowB = {2*W{1'b0}};
    for (c = 0; c < COLS; c = c + 1) begin
      if (cnt[c] >= 1) rowA[c] = mat[c][0];
      if (cnt[c] >= 2) rowB[c] = mat[c][1];
    end
    p = rowA + rowB;
  end
endmodule

module tb;
  localparam W = 8;
  reg  [W-1:0]   a, b;
  wire [2*W-1:0] p;
  integer i, j, errors;

  dadda_mult #(.W(W)) dut (.a(a), .b(b), .p(p));

  initial begin
    errors = 0;
    // Exhaustive 8x8 self-check: all 65536 products against a*b.
    for (i = 0; i < 256; i = i + 1) begin
      for (j = 0; j < 256; j = j + 1) begin
        a = i[W-1:0]; b = j[W-1:0];
        #1;
        if (p !== (i * j)) begin
          errors = errors + 1;
          if (errors <= 10)
            $display("FAIL %0d x %0d : expected %0d got %0d", i, j, i*j, p);
        end
      end
    end

    // A few explicit checks across the range.
    a = 8'd255; b = 8'd255; #1;
    if (p === 16'd65025) $display("PASS 255 x 255 = 65025"); else $display("FAIL 255x255 got %0d", p);
    a = 8'd13;  b = 8'd201; #1;
    if (p === 16'd2613)  $display("PASS 13 x 201 = 2613");   else $display("FAIL 13x201 got %0d", p);
    a = 8'd128; b = 8'd2;   #1;
    if (p === 16'd256)   $display("PASS 128 x 2 = 256");     else $display("FAIL 128x2 got %0d", p);
    a = 8'd45;  b = 8'd45;  #1;
    if (p === 16'd2025)  $display("PASS 45 x 45 = 2025");    else $display("FAIL 45x45 got %0d", p);

    if (errors == 0)
      $display("ALL 65536 PRODUCTS PASSED (exhaustive 8x8 sweep)");
    else
      $display("TOTAL FAILURES: %0d", errors);
    $finish;
  end
endmodule
PASS 255 x 255 = 65025

PASS 13 x 201 = 2613

PASS 128 x 2 = 256

PASS 45 x 45 = 2025

ALL 65536 PRODUCTS PASSED (exhaustive 8x8 sweep)
ALL 65536 PRODUCTS PASSED confirms the parameterized reduction is correct across the entire 8×8 input space, not just a sample. Because the compression preserves the weighted bit sum at every step, the exhaustive sweep is a complete functional proof for this width.
How a Dadda multiplier works
Multiplication of two W-bit unsigned numbers starts by generating a W×W grid of partial-product bits, where bit a[i] & b[j] has weight 2i+j. Collecting bits by weight gives columns whose heights rise to a peak of W in the middle and fall off at both ends. The job of the reduction tree is to compress every column to at most two bits so an ordinary adder can finish the job.
The Dadda height sequence
Dadda defined a sequence of maximum stage heights d1=2, d2=3, and dj+1=⌊1.5·dj⌋, giving 2, 3, 4, 6, 9, 13, 19, … The first stage targets the largest sequence value below the peak height, and each later stage targets the next value down, ending at 2. For an 8-bit multiplier the peak is 8, so the stages are 8 → 6 → 4 → 3 → 2.
Counters: half and full adders
Each column is compressed with full adders (3:2 counters — three bits in, one sum bit staying in the column and one carry bit moving to the next higher column) and half adders (2:2 counters). Dadda's key idea is to apply the minimum number of counters needed to hit the stage target, rather than compressing maximally at every opportunity as Wallace does. A full adder removes two bits from a column per instance, a half adder removes one, and both push a carry into the next column — which is why the reduction is processed from the least-significant column upward, so incoming carries are counted before a column is reduced.
Dadda vs Wallace reduction
Dadda and Wallace trees both reach roughly the same critical-path depth, so their delay is comparable. The difference is in how much they compress at each stage.
Wallace compresses every column as much as possible in each stage, grouping bits into as many full adders as will fit. This front-loads the adders and tends to produce a wider, more irregular final adder.
Dadda compresses each column only enough to meet the stage's target height. Deferring work means fewer half and full adders overall and a narrower final carry-propagate adder, at the cost of a slightly wider final adder stage than one might first expect.
In practice a Dadda multiplier uses fewer counter cells than a Wallace multiplier of the same width, which usually means less area and lower power for the same speed. That is the main reason Dadda trees are a common choice in datapath design and a frequent VLSI interview topic.
Common mistakes
Reducing columns in the wrong order. Carries flow from lower-weight columns to higher ones. If you reduce a column before absorbing the carries coming into it, the stage target is computed against the wrong height. Always process from the LSB column upward within a stage.
Over-compressing like Wallace. Pushing every column to height 2 in one pass still yields a correct product, but it is a Wallace tree, not a Dadda tree, and it spends extra adders. Honour the per-stage targets.
Forgetting the final adder. The reduction tree only gets you to two rows; you still need a carry-propagate adder (shown here as the + operator) to combine them. Omitting it, or sizing it too narrowly, loses the top product bits.
Dropping carries off the top column. The most-significant column can still emit a carry; make sure the result vector is wide enough (2W bits) to hold it.
Synthesis notes
The explicit 4×4 design maps directly to gates: each ha/fa instance is a small combinational cell and the final + infers a carry-propagate adder, so synthesis is straightforward and the structure is exactly what you drew.
The parameterized version describes the same hardware but computes the reduction schedule in an always @(*) block. Its loop bounds depend only on the structural column heights (a function of W), never on the data values, so the while and for loops have statically determinable trip counts and unroll to pure combinational logic. Most modern synthesis tools accept this, but if your tool objects to the data-independent while loops you can rewrite them as bounded for loops or fall back to generate-based structural instantiation. For timing, remember the whole multiplier is combinational — register the inputs and output (or pipeline the reduction stages) when you need it to meet a clock in a real datapath.
FAQ
Is a Dadda multiplier faster than an array multiplier?
Yes. An array multiplier's delay grows linearly with width because carries ripple through a regular grid, while a Dadda tree's reduction depth grows logarithmically, so it is markedly faster for wide operands.
Does this handle signed multiplication?
The code here is unsigned. For two's-complement operands you extend it with Baugh-Wooley sign handling or a modified-Booth front end that generates signed partial products before the same Dadda reduction runs.
Why verify exhaustively?
For 4- and 8-bit operands the entire input space is small (256 and 65,536 cases), so an exhaustive self-check against a*b is a complete functional proof rather than a sample. Any single-bit wiring or scheduling error anywhere in the tree would produce a mismatch and a FAIL line.
Have questions about this topic?
Share your question in comments or talk to our mentor team for batch guidance.
▶ Try it in the ChipXpert Lab
Open this design in the free in-browser simulator — edit, compile and see the waveform/log instantly.
Run it in the Lab
Learn Verilog with mentors, labs and placement support
This free series is maintained by the ChipXpert training team in Hyderabad & Bengaluru. Go deeper with instructor-led courses on real EDA tools.
Explore VLSI Courses