Dadda multiplier

A Dadda Tree multiplier is a multiplier, which is characterized by a comparatively low maturity, and a small number of logic gates. It is named after its inventor, Luigi Dadda, which these multipliers introduced in 1965.

Operation

A bit Dadda tree multipliers based, like the Wallace tree multiplier on the formula

Here, and, the binary representations of the two numbers to be multiplied.

The Dadda Tree multiplier goes in three steps:

Tree structure of the Dadda tree multiplier

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

First, the partial products are arranged in columns so that in one column in each case all partial products are with.

Then you look at the result. The symbol stands for the integer function. It calculates the terms of the sequence up to the so is greater than the number of elements in the largest cleft, but not. Then be used to half and full adders for adding the partial products in such a way that in the end do not include more columns than the elements. The carries are passed on to each of the column of the next higher. For this procedure you used any more than full and half adders as possible. Can you to reduce the column sufficiently to decide between full and half adders, choose the half adder, since this is a smaller component. Then repeat the same operations for, then go for and so on up to and including.

When you have completed the process for all the columns contain only 2 elements. Therefore, one can add the two remaining lines by an adder.

For example 8-bit

Here you can see the above procedure for an 8 -bit Dadda Tree multiplier. The dots stand for the partial or for the outputs of the former used full-and half-adder, which are characterized by the thin lines.

Term

Using the calculation rules for the rounding function and the geometric series can derive the following estimate for:

Now let the length of the two input binary numbers, and be, the partial products. If one arranges all now in partial columns, so that in the k-th column, all the partial products associated with, the largest column has exactly entries.

To create the Dadda tree multiplier we choose so, as described above, so that

Wherein after the operation of the algorithm, the number of adders is that needs an electronic signal from input to output through a maximum. Referring now to the above estimate for add, we obtain:

If one applies the logarithm on both sides, one obtains

Where the Landau symbol for the asymptotic upper bound represents.

Since the running time of an adder is also within, the Dadda tree multiplier has the same asymptotic running time as an adder and is faster than an unsigned parallel multiplier, which has an asymptotic running time of.

Dadda the tree multiplier is also faster than the absolute terms Wallace tree multiplier, although both have the same multiplier asymptotic duration of.

Source

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