How a Dadda multiplier works: 4 x 4 bits, live

A Dadda multiplier adds partial products in layers of full and half adders, like a Wallace tree, but each layer reduces the columns only as far as it must, down a fixed sequence of heights (3, then 2 for a 4 x 4 multiplier). That uses fewer adders in the tree and leaves more for the final adder. This live 4 x 4 one uses 8 full adders and 4 half adders.

The 16 partial products a_i AND b_j sort into columns by weight i + j, with heights 1, 2, 3, 4, 3, 2 and 1. Luigi Dadda's rule works backward from the end: the last stage needs columns of height 2 (two rows for an ordinary adder), the one before can have 3, then 4, 6, 9 and so on, each about 1.5 times the last. Each stage reduces every column to the next height in that sequence and no further, using a half adder when a column is one bit over and a full adder when it is two or more over, and it counts the carries that will arrive from the column to the right. Here stage 1 (down to 3) needs only 2 half adders, in the columns of weight 3 and 4; stage 2 (down to 2) needs 3 full adders and 1 half adder; and the final ripple adder over the last two rows uses 5 full adders and 1 half adder. The Wallace tree on this site instead reduces every column as much as it can in each layer: for the same 4 x 4 multiply it uses 7 full adders and 8 half adders, 15 adders against Dadda's 12, with a shorter final adder. Both beat an array multiplier for wide words because the tree has no carry chain. 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
2× half adders: stage 1 (to height 3): the columns of weight 3 and 4
4× full + half adders: stage 2 (to height 2): 3 full adders and 1 half adder
6× full + half adders: final ripple adder over the last two rows: 5 full adders and 1 half adder

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.
Stage 1: bring every column down to 3 bits, counting the carries arriving from the right; only the weight-3 and weight-4 columns need a half adder.
Stage 2: bring every column down to 2 bits with full adders (two over) and half adders (one over).
Add the last two rows with a ripple adder. Try 1101 x 1011: P = 1000 1111, which is 143.

Dadda and Wallace, 4 x 4

	Tree stages	Adders in the tree	Final adder	Total
Dadda (this one)	2	3 full, 3 half	5 full, 1 half	8 full, 4 half
Wallace	2	4 full, 6 half	3 full, 2 half	7 full, 8 half

A full adder turns three bits of a column into one sum bit there and one carry in the next column; a half adder does the same with two bits. Dadda's heights for larger multipliers are 2, 3, 4, 6, 9, 13, 19 and so on, each the previous one times 3/2, rounded down.

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 4x4 Wallace tree multiplier 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 74181 ALU CMOS AOI gate (AOI21)D latch vs D flip-flop 74LS47 BCD to 7-segment decoder 74HC595 shift register 7400 quad NAND gate chip 7402 quad NOR gate chip 7404 hex inverter chip 7408 quad AND gate chip 7432 quad OR gate chip 7486 quad XOR gate chip 7474 dual D flip-flop 74HC165 shift register CD4017 decade counter 74LS283 4-bit adder 74LS90 decade counter 74HC161 4-bit counter 74HC151 8-to-1 multiplexer 74HC157 quad 2-to-1 multiplexer 74HC139 dual 2-to-4 decoder CD4511 BCD to 7-segment decoder 7492 divide-by-12 counter 7493 4-bit binary counter 74HC244 octal buffer Race-around condition (JK latch)74HC373 octal latch 74HC374 octal D flip-flop Turnstile state machine 1-to-2 demultiplexer half adder using 2:1 multiplexers register file (4 x 4-bit)digital PWM generator CD4013 dual D flip-flop 74LS76 dual JK flip-flop 7410 triple 3-input NAND chip 7411 triple 3-input AND chip 7420 dual 4-input NAND chip CD4011 quad 2-input NAND chip CD4001 quad 2-input NOR chip CD4081 quad 2-input AND chip CD4069 hex inverter chip 74HC164 8-bit shift register 7485 4-bit magnitude comparator 74HC125 quad tri-state buffer CD4040 12-stage binary counter CD4060 14-stage counter and oscillator 74LS193 4-bit up/down counter electronic dice circuit memory address register (MAR) and MDR hardware stack with a stack pointer direct-mapped cache 8-bit Brent-Kung adder binary clock circuit

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 Dadda multiplier in the lab →

Frequently asked

How does a Dadda multiplier work?

It forms all the partial products, then reduces the columns in stages to a fixed sequence of heights (... 6, 4, 3, 2), adding only as many full and half adders as each stage needs, and finishes with one ordinary adder over the last two rows.

What is the difference between Dadda and Wallace tree multipliers?

Both reduce partial products with layers of adders. Wallace reduces as much as possible in every layer; Dadda reduces only as much as needed to reach the next target height. Dadda usually needs fewer adders in the tree, especially half adders, but a slightly wider final adder.

How many adders does a 4x4 Dadda multiplier need?

This one uses 8 full adders and 4 half adders, counting the final ripple adder, plus the 16 AND gates for the partial products.

Who invented the Dadda multiplier?

Luigi Dadda, who described the scheme in 1965, shortly after Chris Wallace published his tree in 1964.