TheDadda multiplier is a hardwarebinary multiplier design invented by computer scientistLuigi Dadda in 1965.^[1] It uses a selection offull and half adders to sum the partial products in stages (theDadda tree orDadda reduction) until two numbers are left. The design is similar to theWallace multiplier, but the different reduction tree reduces the required number ofgates (for all but the smallest operand sizes) and makes it slightly faster (for all operand sizes).^[2]

Both Dadda and Wallace multipliers have the same three steps for two bit strings${\displaystyle w_1}$ and${\displaystyle w_2}$ of lengths${\displaystyle {\ell }_1}$ and${\displaystyle {\ell }_2}$ respectively:

1. Multiply (logical AND) each bit of${\displaystyle w_1}$, by each bit of${\displaystyle w_2}$, yielding${\displaystyle {\ell }_1\cdot {\ell }_2}$ results, grouped by weight in columns
2. Reduce the number of partial products by stages offull and half adders until we are left with at most two bits of each weight.
3. Add the final result with a conventional adder.

As with the Wallace multiplier, the multiplication products of the first step carry different weights reflecting the magnitude of the original bit values in the multiplication. For example, the product of bits${\displaystyle a_n{b}_m}$ has weight${\displaystyle n+m}$.

Unlike Wallace multipliers that reduce as much as possible on each layer, Dadda multipliers attempt to minimize the number of gates used, as well as input/output delay. Because of this, Dadda multipliers have a less expensive reduction phase, but the final numbers may be a few bits longer, thus requiring slightly bigger adders.

To achieve a more optimal final product, the structure of the reduction process is governed by slightly more complex rules than in Wallace multipliers.

The progression of the reduction is controlled by a maximum-height sequence${\displaystyle d_j}$, defined by:

${\displaystyle d_1=2}$, and${\displaystyle d_{j+1}=\mathrm{floor}(1.5d_j).}$

This yields a sequence like so:

${\displaystyle d_1=2,d_2=3,d_3=4,d_4=6,d_5=9,d_6=13,\dots }$

The initial value of${\displaystyle j}$ is chosen as the largest value such that, where${\displaystyle n_1}$ and${\displaystyle n_2}$ are the number of bits in the input multiplicand and multiplier. The lesser of the two bit lengths will be the maximum height of each column of weights after the first stage of multiplication. For each stage${\displaystyle j}$ of the reduction, the goal of the algorithm is the reduce the height of each column so that it is less than or equal to the value of${\displaystyle d_j}$.

For each stage from${\displaystyle ,\dots ,1}$, reduce each column starting at the lowest-weight column,${\displaystyle c_0}$ according to these rules:

1. If${\displaystyle \mathrm{height}(c_i)⩽d_j}$ the column does not require reduction, move to column${\displaystyle c_{i+1}}$
2. If${\displaystyle \mathrm{height}(c_i)=d_j+1}$ add the top two elements in a half-adder, placing the result at the bottom of the column and the carry at the bottom of column${\displaystyle c_{i+1}}$, then move to column${\displaystyle c_{i+1}}$
3. Else, add the top three elements in a full-adder, placing the result at the bottom of the column and the carry at the bottom of column${\displaystyle c_{i+1}}$, restart${\displaystyle c_i}$at step 1

The example in the adjacent image illustrates the reduction of an 8 × 8 multiplier, explained here.

The initial state${\displaystyle j=4}$ is chosen as${\displaystyle d_4=6}$, the largest value less than 8.

Stage${\displaystyle j=4}$,${\displaystyle d_4=6}$

• ${\displaystyle \mathrm{height}(c_0\cdots c_5)}$ are all less than or equal to six bits in height, so no changes are made
• ${\displaystyle \mathrm{height}(c_6)=d_4+1=7}$, so a half-adder is applied, reducing it to six bits and adding its carry bit to${\displaystyle c_7}$
• ${\displaystyle \mathrm{height}(c_7)=9}$ including the carry bit from${\displaystyle c_6}$, so we apply a full-adder and a half-adder to reduce it to six bits
• ${\displaystyle \mathrm{height}(c_8)=9}$ including two carry bits from${\displaystyle c_7}$, so we again apply a full-adder and a half-adder to reduce it to six bits
• ${\displaystyle \mathrm{height}(c_9)=8}$ including two carry bits from${\displaystyle c_8}$, so we apply a single full-adder and reduce it to six bits
• ${\displaystyle \mathrm{height}(c_{10}\cdots c_{14})}$ are all less than or equal to six bits in height including carry bits, so no changes are made

Stage${\displaystyle j=3}$,${\displaystyle d_3=4}$

• ${\displaystyle \mathrm{height}(c_0\cdots c_3)}$ are all less than or equal to four bits in height, so no changes are made
• ${\displaystyle \mathrm{height}(c_4)=d_3+1=5}$, so a half-adder is applied, reducing it to four bits and adding its carry bit to${\displaystyle c_5}$
• ${\displaystyle \mathrm{height}(c_5)=7}$ including the carry bit from${\displaystyle c_4}$, so we apply a full-adder and a half-adder to reduce it to four bits
• ${\displaystyle \mathrm{height}(c_6\cdots c_{10})=8}$ including previous carry bits, so we apply two full-adders to reduce them to four bits
• ${\displaystyle \mathrm{height}(c_{11})=6}$ including previous carry bits, so we apply a full-adder to reduce it to four bits
• ${\displaystyle \mathrm{height}(c_{12}\cdots c_{14})}$ are all less than or equal to four bits in height including carry bits, so no changes are made

Stage${\displaystyle j=2}$,${\displaystyle d_2=3}$

• ${\displaystyle \mathrm{height}(c_0\cdots c_2)}$ are all less than or equal to three bits in height, so no changes are made
• ${\displaystyle \mathrm{height}(c_3)=d_2+1=4}$, so a half-adder is applied, reducing it to three bits and adding its carry bit to${\displaystyle c_4}$
• ${\displaystyle \mathrm{height}(c_4\cdots c_{12})=5}$ including previous carry bits, so we apply one full-adder to reduce them to three bits
• ${\displaystyle \mathrm{height}(c_{13}\cdots c_{14})}$ are all less than or equal to three bits in height including carry bits, so no changes are made

Stage${\displaystyle j=1}$,${\displaystyle d_1=2}$

• ${\displaystyle \mathrm{height}(c_0\cdots c_1)}$ are all less than or equal to two bits in height, so no changes are made
• ${\displaystyle \mathrm{height}(c_2)=d_1+1=3}$, so a half-adder is applied, reducing it to two bits and adding its carry bit to${\displaystyle c_3}$
• ${\displaystyle \mathrm{height}(c_3\cdots c_{13})=4}$ including previous carry bits, so we apply one full-adder to reduce them to two bits
• ${\displaystyle \mathrm{height}(c_{14})=2}$ including the carry bit from${\displaystyle c_{13}}$, so no changes are made

Addition

The output of the last stage leaves 15 columns of height two or less which can be passed into a standard adder.

• Booth's multiplication algorithm
• Fused multiply–add
• Wallace tree
• BKM algorithm for complex logarithms and exponentials
• Kochanski multiplication formodular multiplication

• Savard, John J. G. (2018) [2006]."Advanced Arithmetic Techniques".quadibloc.Archived from the original on 2018-07-03. Retrieved2018-07-16.

• Arithmetic logic circuits
• Computer arithmetic
• Multiplication
• 1965 introductions
• 1965 in computing

• Articles with short description
• Short description matches Wikidata