How a Wallace tree multiplier works: 4 x 4 bits, live

A Wallace tree multiplier adds the partial products of a binary multiplication in layers of full and half adders that work in parallel, reducing every column to at most two bits, and only then uses one ordinary adder to finish. This live 4 x 4 one needs 16 AND gates, two reduction layers and a final ripple adder: 7 full adders and 8 half adders in all.

Multiplying two 4-bit numbers makes 16 partial-product bits, a_i AND b_j, each worth 2^(i+j). Lined up by weight they form columns of 1, 2, 3, 4, 3, 2 and 1 bits. An array multiplier adds them row after row, so its delay grows with the number of rows. A Wallace tree instead uses full adders as 3-to-2 counters: three bits of one column become a sum bit in that column and a carry bit in the next, and nothing waits for a carry to ripple. Each layer takes every three bits of a column into a full adder and a leftover pair into a half adder, which cuts the height by about a third, so n rows need only about log base 3/2 of n layers. Chris Wallace proposed it in 1964. The adders here are the half adder and full adder saved as parts, the same way the carry-save adder adds three numbers at once. All 256 products are checked before the page is built.

Big circuit: pinch, scroll or tap + to zoom in, then drag to move around.

Live circuit: click the inputs to toggle them and watch the outputs update. It runs the real simulator, right here on the page.

Open this circuit in the lab →

What you need

16× AND: partial products a_i b_j
5× full + half adders: layer 1: 3 full adders and 2 half adders; columns of 1 2 3 4 3 2 1 bits become 1 1 2 3 2 2 2
5× full + half adders: layer 2: 1 full adder and 4 half adders; every column now holds at most 2 bits
5× full + half adders: final ripple adder over the last two rows: 3 full adders and 2 half adders

Step by step

Place inputs A3 to A0 and B3 to B0, and probes P7 to P0.
Make the 16 partial products a_i AND b_j and sort them into columns by weight i + j.
Layer 1: in every column, send each group of three bits into a full adder and a leftover pair into a half adder; sums stay in the column, carries move one column left.
Layer 2: repeat on the new columns until none holds more than two bits.
Add the final two rows with a short ripple adder. Try 1111 x 1111: P = 1110 0001, which is 225.

Worked examples

A	B	Decimal	P (8 bits)
0011	0101	3 x 5 = 15	00001111
0110	0111	6 x 7 = 42	00101010
1001	1010	9 x 10 = 90	01011010
1101	1011	13 x 11 = 143	10001111
1111	1111	15 x 15 = 225	11100001

The reduction layers have no carry chain at all, so their delay is two full-adder delays whatever the numbers are; only the final adder carries. For wider multipliers the gap grows: 16 rows need 6 Wallace layers, where an array multiplier passes through about 15 rows of adders.

You can also read the full theory in the lesson on binary multiplication in hardware. Prefer to build it yourself from scratch? Open the digiwleea lab and place the gates on the canvas, or start from the logic gate simulator.

Build more parts from gates

half adder full adder half subtractor full subtractor 2:1 multiplexer 4:1 multiplexer XOR gate from NAND gates 2-to-4 decoder SR latch D flip-flop JK flip-flop T flip-flop 4-bit shift register 4-bit ripple carry adder D latch 1-to-4 demultiplexer 4-bit magnitude comparator 4-bit ring counter 4-bit Johnson counter 4-to-2 priority encoder 4-bit synchronous counter 3-to-8 decoder 8-to-1 multiplexer 4-bit carry lookahead adder half adder from NAND gates 2-bit comparator BCD to 7-segment decoder 4-bit up/down counter decade counter 2-bit multiplier 4-bit ALU 4-bit array multiplier NOT, AND, OR and NOR from NAND NOT, OR, AND and XOR from NOR full adder from NAND gates SR latch from NAND gates parity generator and checker 4-bit adder/subtractor BCD adder 4-bit universal shift register mod-6 counter 4-bit ripple counter binary to Gray code converter half adder from NOR gates full adder from NOR gates 4-bit register with parallel load 1011 sequence detector binary to BCD converter D flip-flop from NAND gates 1-bit ALU CMOS inverter CMOS NAND gate CMOS NOR gate PISO shift register SR flip-flop from NAND gates BCD to excess-3 code converter Hamming (7,4) code encoder and corrector traffic light controller 4-bit barrel shifter CMOS AND gate CMOS OR gate CMOS XOR gate 1-bit magnitude comparator half subtractor from NAND gates full subtractor from NAND gates 8-to-3 encoder Gray to binary converter 4-to-16 decoder full adder using 4:1 multiplexers edge detector serial adder 4-bit carry-select adder 4-bit Kogge-Stone adder 4-bit carry-skip adder 8-bit adder frequency divider (by 2, 4 and 3)switch debouncer (SR latch)3-bit Gray code counter Mealy machine (1011 detector)master-slave JK flip-flop (NAND)half subtractor from NOR gates 1-to-8 demultiplexer excess-3 to BCD code converter vending machine FSM 4-bit carry-save adder 3-bit synchronous counter (JK)CMOS transmission gate tri-state buffer (CMOS)2-to-1 mux from transmission gates mod-5 counter flip-flop conversion (JK to D)8-bit ALU decimal to BCD encoder BCD to decimal decoder 4-to-1 mux from 2-to-1 muxes XOR gate from NOR gates 4-bit LFSR 74LS138 decoder BCD subtractor

Each of these is one step from a transistor to a working CPU. Build every gate from CMOS transistors and work all the way up in the free digiwleea lab, with the free theory reference alongside.

Open the 4x4 Wallace tree multiplier in the lab →

Frequently asked

What is a Wallace tree multiplier?

A hardware multiplier that adds the partial products in parallel layers of full and half adders, each acting as a counter that turns three bits of a column into a sum and a carry, until two rows remain, and then adds those two rows with a fast adder.

Why is a Wallace tree faster than an array multiplier?

An array multiplier adds the partial products one row at a time, so its delay grows linearly with the width. A Wallace tree reduces all columns at once and cuts the number of rows by about a third per layer, so the reduction takes a logarithmic number of layers, and only the final addition has a carry chain.

How many full adders does a 4x4 Wallace tree need?

This one uses 7 full adders and 8 half adders, counting the final ripple adder, plus 16 AND gates for the partial products. Variants differ slightly in how they place half adders.

What is the difference between Wallace and Dadda multipliers?

Both reduce partial products with full and half adders. Wallace reduces as much as possible in every layer, while Dadda reduces only as much as needed to reach the next target height, which uses fewer half adders at the cost of a slightly wider final adder.