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 (for all operand sizes) and requires fewer gates (for all but the smallest operand sizes).
In fact, Dadda and Wallace multipliers have the same three steps for two bit strings formula_1 and formula_2 of lengths formula_3 and formula_4 respectively:
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 formula_8 has weight formula_9.
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 formula_10, defined by:
This yields a sequence like so:
The initial value of formula_13 is chosen as the largest value such that formula_14, where formula_15 and formula_16 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 formula_13 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 formula_10. 
For each stage from formula_19, reduce each column starting at the lowest-weight column, formula_20 according to these rules:
Algorithm example.
The example in the adjacent image illustrates the reduction of an 8 × 8 multiplier, explained here.
The initial state formula_28 is chosen as formula_29, the largest value less than 8.
Stage formula_30, formula_29
Stage formula_42, formula_43
Stage formula_52, formula_53
Stage formula_59, formula_60
Addition
The output of the last stage leaves 15 columns of height two or less which can be passed into a standard adder.