wire / wire-format / multiplier

Hardware multiplier (shift-and-add, Booth, Wallace tree)

A hardware multiplier computes the product of two n-bit integers. Methods: shift-and-add (O(n^2) gate delay), Booth's algorithm (handles signed, reduces partial products), Wallace tree (parallel reduction of partial products, O(log n) delay), Dadda tree (similar, fewer gates). Modern CPUs use modified Booth encoding + Wallace/Dadda tree + carry-propagate adder.

wire-format kind wire-format status standard verification verified tier B wire-format@1

aka: Hardware multiplier (shift-and-add, Booth, Wallace tree)

wire format

spec: Digital arithmetic

A hardware multiplier computes the product of two n-bit integers. Methods: shift-and-add (O(n^2) gate delay), Booth's algorithm (handles signed, reduces partial products), Wallace tree (parallel reduction of partial products, O(log n) delay), Dadda tree (similar, fewer gates). Modern CPUs use modified Booth encoding + Wallace/Dadda tree + carry-propagate adder.

fieldsizemeaning
Partial productsn x nn partial products, each shifted by its position. E.g., for 4-bit: 4 partial products of 4 bits.
Shift-and-addO(n) iterationsIterative: if multiplier bit is 1, add multiplicand to accumulator; shift right. O(n) cycles.
Booth's algorithmO(n) iterationsEncodes pairs of multiplier bits: 00/11 -> 0, 01 -> +multiplicand, 10 -> -multiplicand. Reduces partial products for signed multiplication.
Modified Booth (radix-4)O(n/2) iterationsEncodes triples of multiplier bits. Fewer partial products (n/2 instead of n). Most common in modern CPUs.
Wallace treeO(log n) delayParallel reduction: 3:2 compressors (full adders) reduce partial products in a tree structure. Fast but area-intensive.
Dadda treeO(log n) delaySimilar to Wallace but minimizes the number of adders. Slightly slower but smaller.
Result2n bitsProduct of two n-bit integers is 2n bits.

example:

00 00 00 00

Multiplier (placeholder)


provenance

agent: curl -H 'accept: application/json' wire.phall.io/wire-format/multiplier or /wire-format/multiplier.json