↑ arvau

Wikipedia / Dadda multiplier

The Dadda multiplier is a hardware binary multiplier design invented by computer scientist Luigi Dadda in 1965. It uses a selection of full and half adders to sum the partial products in stages (the Dadda tree or Dadda reduction) until two numbers are left. The design is similar to the Wallace multiplier, but the different reduction tree reduces the required number of gates (for all but the smallest operand sizes) and makes it slightly faster (for all operand sizes).

respectively:

  1. Multiply (logical AND 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.

.

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.

, defined by:

This yields a sequence like so:

.

according to these rules:

  1. at step 1

Algorithm example

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

, the largest value less than 8.

  • are all less than or equal to six bits in height, so no changes are made

  • , so we apply a full-adder and a half-adder to reduce it to six bits

  • , so we again apply a full-adder and a half-adder to reduce it to six bits

  • , so we apply a single full-adder and reduce it to six bits

  • are all less than or equal to six bits in height including carry bits, so no changes are made

  • are all less than or equal to four bits in height, so no changes are made

  • , so we apply a full-adder and a half-adder to reduce it to four bits

  • including previous carry bits, so we apply two full-adders to reduce them to four bits

  • including previous carry bits, so we apply a full-adder to reduce it to four bits

  • are all less than or equal to four bits in height including carry bits, so no changes are made

  • are all less than or equal to three bits in height, so no changes are made

  • including previous carry bits, so we apply one full-adder to reduce them to three bits

  • are all less than or equal to three bits in height including carry bits, so no changes are made

  • are all less than or equal to two bits in height, so no changes are made

  • including previous carry bits, so we apply one full-adder to reduce them to two bits

  • , 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.

See also

References

Further reading