Wallace Tree Multiplier Verilog Code (4×4, Carry-Save)
A Wallace tree multiplier is a fast parallel multiplier that shrinks a grid of partial products into two numbers using layers of carry-save adders, then adds those two numbers once with an ordinary carry-propagate adder. The trick is that carry-save addition never waits for a carry to ripple across the word, so the reduction depth grows only logarithmically with the operand width. This page gives you complete, runnable wallace tree multiplier verilog code for a 4×4 unit, a testbench that checks every product, and a plain explanation of how each reduction layer works.
The design below is written in Verilog-2005 and builds with iverilog -g2005 -o sim wallace_mult_4x4.v && vvp sim. It uses small ha (half adder) and fa (full adder) cells so you can see the carry-save structure instead of hiding it behind a * operator.
Full 4×4 Wallace tree multiplier in Verilog
The multiplier forms sixteen partial-product bits, reduces them in two carry-save stages until no column has more than two bits, and finishes with an 8-bit adder. The testbench prints a few sample products and then self-checks all 256 input combinations.
// Wallace tree multiplier (4x4), Verilog-2005
// Partial products reduced with half adders and full adders (carry-save),
// then a final carry-propagate adder produces the 8-bit product.
module ha (input a, input b, output sum, output cout);
assign sum = a ^ b;
assign cout = a & b;
endmodule
module fa (input a, input b, input cin, output sum, output cout);
assign sum = a ^ b ^ cin;
assign cout = (a & b) | (a & cin) | (b & cin);
endmodule
module wallace_mult_4x4 (input [3:0] a, input [3:0] b, output [7:0] p);
// --- Partial product bits: txy = a[x] & b[y], weight = x + y ---
wire t00 = a[0] & b[0]; // w0
wire t10 = a[1] & b[0], t01 = a[0] & b[1]; // w1
wire t20 = a[2] & b[0], t11 = a[1] & b[1], t02 = a[0] & b[2]; // w2
wire t30 = a[3] & b[0], t21 = a[2] & b[1], t12 = a[1] & b[2], t03 = a[0] & b[3]; // w3
wire t31 = a[3] & b[1], t22 = a[2] & b[2], t13 = a[1] & b[3]; // w4
wire t32 = a[3] & b[2], t23 = a[2] & b[3]; // w5
wire t33 = a[3] & b[3]; // w6
// --- Stage A: first carry-save reduction layer ---
wire s1, c1; ha u_w1a (t10, t01, s1, c1); // w1 -> s1(w1), c1(w2)
wire s2, c2; fa u_w2a (t20, t11, t02, s2, c2); // w2 -> s2(w2), c2(w3)
wire s3, c3; fa u_w3a (t30, t21, t12, s3, c3); // w3 (t03 kept)
wire s4, c4; fa u_w4a (t31, t22, t13, s4, c4); // w4
wire s5, c5; ha u_w5a (t32, t23, s5, c5); // w5
// --- Stage B: reduce every column to at most two dots ---
wire s2b, c2b; ha u_w2b (s2, c1, s2b, c2b); // w2
wire s3b, c3b; fa u_w3b (s3, c2, t03, s3b, c3b); // w3
wire s4b, c4b; ha u_w4b (s4, c3, s4b, c4b); // w4
wire s5b, c5b; ha u_w5b (s5, c4, s5b, c5b); // w5
wire s6b, c6b; ha u_w6b (t33, c5, s6b, c6b); // w6
// --- Two residual rows feeding the carry-propagate adder ---
wire [7:0] row_sum = {1'b0, s6b, s5b, s4b, s3b, s2b, s1, t00};
wire [7:0] row_carry = {c6b, c5b, c4b, c3b, c2b, 1'b0, 1'b0, 1'b0};
assign p = row_sum + row_carry; // final CPA
endmodule
// --------------------- Testbench ---------------------
module tb_wallace;
reg [3:0] a, b;
wire [7:0] p;
integer i, j, errors;
wallace_mult_4x4 dut (.a(a), .b(b), .p(p));
initial begin
errors = 0;
// A few representative products
a = 4'd3; b = 4'd5; #5 $display(" 3 x 5 = %0d (expected %0d)", p, 3*5);
a = 4'd9; b = 4'd7; #5 $display(" 9 x 7 = %0d (expected %0d)", p, 9*7);
a = 4'd15; b = 4'd15; #5 $display(" 15 x 15 = %0d (expected %0d)", p, 15*15);
a = 4'd12; b = 4'd0; #5 $display(" 12 x 0 = %0d (expected %0d)", p, 12*0);
// Exhaustive self-check over all 256 input combinations
for (i = 0; i < 16; i = i + 1)
for (j = 0; j < 16; j = j + 1) begin
a = i[3:0]; b = j[3:0]; #2;
if (p !== (i*j)) begin
errors = errors + 1;
$display(" MISMATCH %0d x %0d -> got %0d", i, j, p);
end
end
if (errors == 0) $display("RESULT: all 256 products correct");
else $display("RESULT: %0d mismatches", errors);
$finish;
end
endmodule3 x 5 = 15 (expected 15) 9 x 7 = 63 (expected 63) 15 x 15 = 225 (expected 225) 12 x 0 = 0 (expected 0) RESULT: all 256 products correct /var/folders/l0/gs5hnkm56g54bmxg32r6nnwr0000gn/T/tmpz7ozjf2j/wallace_mult_4x4.v:74: $finish called at 532 (1s)
How the reduction works, column by column
Every product bit lives in a column whose weight is the sum of the two bit indices. The bit txy = a[x] & b[y] sits in column x + y. Counting bits per column gives the familiar triangle: column 0 has one bit, column 3 (the center) has four, and the outer columns taper back to one. Reduction is the process of squeezing each column down until only two bits remain anywhere, because a normal adder can only consume two operands at a time.
Half adders and full adders as compressors
A full adder takes three bits of equal weight and produces one sum bit (same weight) plus one cout bit (next weight up). A half adder does the same for two bits. That is why a full adder is often called a 3:2 compressor: three dots in a column become one dot in that column and one dot in the column to its left. The Wallace tree simply applies these compressors to every tall column, in parallel, over and over.
The carry-save primitive on vectors
To make the idea concrete, the next snippet shows the same compressor applied across a 4-bit vector: it adds three numbers and returns a sum vector and a carry vector without ever propagating a carry. The true total is recovered only at the end with sum + (carry << 1). This is exactly what each Wallace stage does, just on partial-product columns.
// 3-to-2 carry-save adder (compressor) over 4-bit vectors, Verilog-2005.
// Demonstrates the core operation a Wallace tree repeats: three rows of dots
// collapse into one sum vector and one carry vector, with NO carry propagation.
module csa4 (input [3:0] x, input [3:0] y, input [3:0] z,
output [3:0] s, // bitwise sum (same weight)
output [3:0] c); // bitwise carry (one weight higher)
assign s = x ^ y ^ z; // full-adder sum, per bit
assign c = (x & y) | (x & z) | (y & z); // full-adder carry, per bit
endmodule
// --------------------- Testbench ---------------------
module tb_csa;
reg [3:0] x, y, z;
wire [3:0] s, c;
wire [5:0] total;
integer k, errors;
csa4 dut (.x(x), .y(y), .z(z), .s(s), .c(c));
// Recombine the two saved vectors: total = s + (c << 1)
assign total = s + (c << 1);
initial begin
errors = 0;
x = 4'd6; y = 4'd5; z = 4'd3;
#5 $display(" x=%0d y=%0d z=%0d -> sum=%b carry=%b total=%0d (expected %0d)",
x, y, z, s, c, total, 6+5+3);
x = 4'd15; y = 4'd15; z = 4'd15;
#5 $display(" x=%0d y=%0d z=%0d -> sum=%b carry=%b total=%0d (expected %0d)",
x, y, z, s, c, total, 15+15+15);
// Random self-check: carry-save must preserve the true sum
for (k = 0; k < 40; k = k + 1) begin
x = $random; y = $random; z = $random; #2;
if (total !== (x + y + z)) begin
errors = errors + 1;
$display(" MISMATCH %0d+%0d+%0d -> %0d", x, y, z, total);
end
end
if (errors == 0) $display("RESULT: carry-save preserved every sum");
else $display("RESULT: %0d mismatches", errors);
$finish;
end
endmodulex=6 y=5 z=3 -> sum=0000 carry=0111 total=14 (expected 14) x=15 y=15 z=15 -> sum=1111 carry=1111 total=45 (expected 45) RESULT: carry-save preserved every sum /var/folders/l0/gs5hnkm56g54bmxg32r6nnwr0000gn/T/tmp71bcbe5u/csa.v:44: $finish called at 90 (1s)
Mapping stages back to the multiplier
In the 4×4 design, Stage A hits the three tallest columns (weights 2, 3, 4) with full adders and the two 2-bit columns (weights 1, 5) with half adders. Each carry out is routed into the column one weight higher, which is why c1 lands in weight 2, c2 in weight 3, and so on. After Stage A a couple of columns still hold three bits, so Stage B compresses them again until every column has at most two bits. Those two surviving rows become row_sum and row_carry, and a single + performs the final carry-propagate addition. The exhaustive test confirms the whole network equals a*b for all 256 cases.
Common mistakes
- Weighting the carry wrong. A full adder’s carry belongs in the next higher column. If you feed it back into the same column, products silently drift by powers of two. Label every wire with its weight, as the comments do.
- Undersizing the final sum. The maximum 4×4 product is 225, so the output must be 8 bits. Declaring
pas 7 bits truncates large products such as 15 x 15. - Treating carry-save totals as final. The
sumandcarryvectors are not the answer on their own; you must still add them withcarryshifted left by one. Forgetting the shift is the single most common bug. - Checking only a few vectors. A reduction wiring error can pass for 3 x 5 yet fail for 11 x 13. Always run an exhaustive or large random self-check, as both testbenches here do.
- Using
=in the testbench loop body. Drive stimulus with blocking assignments and insert a small delay (#2) before sampling combinational outputs, or you will read stale values.
Quick check
Why is a full adder called a 3:2 compressor in a Wallace tree?
It takes three bits of the same weight and produces two output bits: a sum bit at the same weight and a carry bit at the next higher weight, reducing three dots in a column to one dot in that column plus one in the neighbor.
How many output bits does a 4×4 unsigned multiplier need, and why?
Eight bits. The largest operands are 15 and 15, whose product is 225, and 225 needs 8 bits. Anything narrower truncates the top products.
What distinguishes carry-save addition from carry-propagate addition?
Carry-save addition keeps the carries in a separate vector instead of propagating them along the word, so each stage has constant delay. A carry-propagate adder resolves all carries and is used only once, at the very end.
After the two reduction stages, how is the final product formed?
The two remaining rows, row_sum and row_carry (already weighted), are added together with a single carry-propagate adder: p = row_sum + row_carry.
Share your question in comments or talk to our mentor team for batch guidance.
Open this design in the free in-browser simulator — edit, compile and see the waveform/log instantly.
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