Dadda Tree Multiplier

A Dadda Tree multiplier is a multiplier that is characterized by a comparatively short running time and a small number of logic gates . It is named after its inventor Luigi Dadda , who introduced this multiplier in 1965.

functionality

A - bit dadda multiplier is based, like the Wallace tree on the formula ${\displaystyle n}$

${\displaystyle \left(\sum _{k=0}^{n}a_{k}2^{k}\right)\cdot \left(\sum _{k=0}^{n}b_{k}2^{k}\right)=\sum _{k=0}^{2n}\sum _{i+j=k}a_{i}b_{j}2^{k}}$.

Here, and , are the binary representations of the two numbers to be multiplied. ${\displaystyle \sum _{k=0}^{n}a_{k}2^{k}}$ ${\displaystyle \sum _{k=0}^{n}b_{k}2^{k}}$ ${\displaystyle a_{k},b_{k}\in \{0,1\}}$

The Dadda Tree multiplier works in three steps:

1. For each pair with and calculate the partial product . ${\displaystyle (i,j)}$ ${\displaystyle 1\leq i\leq n}$ ${\displaystyle 1\leq j\leq n}$ ${\displaystyle a_{i}\cdot b_{j}\cdot 2^{i+j}}$
2. Add the results of this calculation within the tree structure specific to the Dadda Tree multiplier in stages using full and half adders until there are only two numbers left that need to be added.
3. Add these two numbers using a normal adder.

Tree structure of the dadda tree multiplier

In step 2 of the above steps, the partial products are added in a tree structure.

The partial products are first arranged in columns, respectively so that in one column all the partial products with standing. ${\displaystyle a_{i}\cdot b_{j}}$ ${\displaystyle i+j=k}$

Then you look at the sequence . The symbol stands for the Gaussian bracket . The terms of the sequence are calculated up to , so that is greater than the number of elements in the largest column, but not yet. Then half and full adders are used to add the partial products in such a way that at the end there are no more columns than elements. The carry-overs are passed on to the next higher column . For this process one uses as few full and half adders as possible. If you can decide between full and half adder in order to reduce the column sufficiently, you choose the half adder, as this is a smaller component. Then repeat the process for , then for and so on up to and including . ${\displaystyle d_{1}=2,\ d_{j+1}=\left\lfloor {\tfrac {3\cdot d_{j}}{2}}\right\rfloor }$ ${\displaystyle \left\lfloor \cdot \right\rfloor }$ ${\displaystyle j}$ ${\displaystyle d_{j+1}}$ ${\displaystyle d_{j}}$ ${\displaystyle d_{j}}$ ${\displaystyle k}$ ${\displaystyle j-1}$ ${\displaystyle j-2}$ ${\displaystyle j=1}$

When you have completed the process for , all columns contain only 2 elements. Therefore, the two remaining lines can be added using an adder . ${\displaystyle j=1}$

Example 8-bit

Here you can see the above procedure for an 8-bit dadda tree multiplier. The dots stand for the partial products or for the outputs of the previously used full and half adders, which are identified by the thin lines.

running time

With the calculation rules for the rounding function and the geometric series one can derive the following estimate for : ${\displaystyle d_{j}}$

${\displaystyle d_{j}=\left\lfloor {\frac {3\cdot d_{j-1}}{2}}\right\rfloor =\left\lceil {\frac {3\cdot d_{j-1}-2+1}{2}}\right\rceil \geq {\frac {3\cdot d_{j-1}-1}{2}}={\frac {3\cdot \left\lceil {\frac {3\cdot d_{j-2}-1}{2}}\right\rceil -1}{2}}\geq {\left({\frac {3}{2}}\right)}^{2}\cdot d_{j-3}-{\frac {1}{2}}\sum _{i=0}^{1}{\left({\frac {3}{2}}\right)}^{i}\geq \ldots }$

${\displaystyle \ldots \geq {\left({\frac {3}{2}}\right)}^{j-1}\cdot d_{1}-{\frac {1}{2}}\sum _{i=0}^{j-1-1}{\left({\frac {3}{2}}\right)}^{i}=2\cdot {\left({\frac {3}{2}}\right)}^{j-1}-{\left({\frac {3}{2}}\right)}^{j-1}+1\geq {\left({\frac {3}{2}}\right)}^{j-1}}$

Let now be the length of the two entered binary numbers and , and be , the partial products. If one assigns to all partial products in columns so th k in the column all the partial products with stand, the largest column has exactly entries. ${\displaystyle n}$ ${\displaystyle \sum _{k=0}^{n}a_{k}2^{k}}$ ${\displaystyle \sum _{k=0}^{n}b_{k}2^{k}}$ ${\displaystyle a_{i}\cdot b_{j}}$ ${\displaystyle 1\leq i,j\leq n}$ ${\displaystyle a_{i}\cdot b_{j}}$ ${\displaystyle i+j=k}$ ${\displaystyle n}$

To create the Dadda Tree multiplier, as described above, we choose the one so that ${\displaystyle j}$

${\displaystyle d_{j+1}>n\geq d_{j}}$,

where, according to the mode of operation of the algorithm, the maximum number of adders an electronic signal has to pass from input to output. If you now add the above estimate for , you get: ${\displaystyle j}$ ${\displaystyle d_{j}}$

${\displaystyle {\left({\frac {3}{2}}\right)}^{j-1}\leq n}$.

If you now apply the logarithm to both sides, you get

${\displaystyle j\leq \log _{3/2}(n)+1\in {\mathcal {O}}(\log(n))}$,

where the Landau symbol represents the asymptotic upper bound. ${\displaystyle {\mathcal {O}}}$

Since the running time of an adder is also in , the Dadda Tree multiplier has the same asymptotic running time as an adder and is therefore faster than an unsigned parallel multiplier that has an asymptotic running time of . ${\displaystyle {\mathcal {O}}(\log(n))}$ ${\displaystyle {\mathcal {O}}(\log ^{2}(n))}$

The Dadda Tree multiplier is also faster than the Wallace Tree multiplier in absolute terms , although both multipliers have the same asymptotic running time of . ${\displaystyle {\mathcal {O}}(\log(n))}$

source

• W. Townsend, E. Swartzlander, J. Abraham: A Comparison of Dadda and Wallace Multiplier Delays. (PDF; 660 kB) In: SPIE Advanced Signal Processing Algorithms, Architectures, and Implementations XIII. Retrieved August 5, 2013 . 

Individual evidence

1. ^ Luigi Dadda: Some schemes for parallel multipliers . In: Alta Frequencya . Vol. 34. Dipartimento di Elettronica Politecnico di Milano, Italy, Milan 1965, p. 349 - 365 ( Online , PDF, 663 kB).