Dadda multiplier


The Dadda multiplier is a hardware multiplier design invented by computer scientist Luigi Dadda in 1965. It is similar to the Wallace multiplier, but it is slightly faster and requires fewer gates.
In fact, Dadda and Wallace multipliers have the same three steps for two bit strings and of lengths and respectively:
  1. Multiply each bit of, by each bit of, yielding results, grouped by weight in columns
  2. Reduce the number of partial products by stages of full 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 has weight.
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.

Description

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, defined by:
This yields a sequence like so:
The initial value of is chosen as the largest value such that, where and 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 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.
For each stage from, reduce each column starting at the lowest-weight column, according to these rules:
  1. If the column does not require reduction, move to column
  2. If add the top two elements in a half-adder, placing the result at the bottom of the column and the carry at the top of column, then move to column
  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 top of column, restart at step 1

    Algorithm example

The example in the adjacent image illustrates the reduction of an 8 × 8 multiplier, explained here.
The initial state is chosen as, the largest value less than 8.
Stage,
Stage,
Stage,
Stage,
Addition
The output of the last stage leaves 15 columns of height two or less which can be passed into a standard adder.