# Wallace tree

Wallace tree

A Wallace tree is an efficient hardware implementation of a digital circuit that multiplies two integers.

The Wallace tree has three steps:
# Multiply (that is - AND) each bit of one of the arguments, by each bit of the other, yielding $n^2$ results. Depending on position of the multiplied bits, the wires carry different weights, for example wire of bit carrying result of $a_2 b_3$ is 32 (see explanation of weights below).
# Reduce the number of partial products to two by layers of full and half adders.
# Group the wires in two numbers, and add them with a conventional adder.

The second phase works as follows. As long as there are three or more wires with the same weight add a following layer:
* Take any three wires with the same weights and input them into a full adder. The result will be an output wire of the same weight and an output wire with a higher weight for each three input wires.
* If there are two wires of the same weight left, input them into a half adder.
* If there is just one wire left, connect it to the next layer.

The benefit of the Wallace tree is that there are only $O\left(log n\right)$ reduction layers, and each layer has $O\left(1\right)$ propagation delay. As making the partial products is $O\left(1\right)$ and the final addition is $O\left(log n\right)$,the multiplication is only $O\left(log n\right)$, not much slower than addition (however, much more expensive in the gate count). Naively adding partial products with regular adders would require $O\left(log n\right)^2$ time. From a complexity theoretic perspective, the Wallace tree algorithm puts multiplication in the class NC1.

These computations only consider gate delays and don't deal with wire delays, which can also be very substantial.

The Wallace tree can be also represented by a tree of 3/2 or 4/2 adders.

It is sometimes combined with Booth encoding.

Weights Explained

2 to the power of the index, so
$a_0b_0$ - both have index of 0; $2^0 * 2^0 = 1$, so the weight is 1.
$a_3b_2$ - have indexes of 3 and 2; $2^3 * 2^2 = 32$, so the weight is 32.

Example

$n=4$, multiplying $a_3a_2a_1a_0$ by $b_3b_2b_1b_0$:

# First we multiply every bit by every bit:
#* weight 1 - $a_0b_0$
#* weight 2 - $a_0b_1$, $a_1b_0$
#* weight 4 - $a_0b_2$, $a_1b_1$, $a_2b_0$
#* weight 8 - $a_0b_3$, $a_1b_2$, $a_2b_1$, $a_3b_0$
#* weight 16 - $a_1b_3$, $a_2b_2$, $a_3b_1$
#* weight 32 - $a_2b_3$, $a_3b_2$
#* weight 64 - $a_3b_3$
# Reduction layer 1:
#* Pass the only weight-1 wire through, output: 1 weight-1 wire
#* Add a half adder for weight 2, outputs: 1 weight-2 wire, 1 weight-4 wire
#* Add a full adder for weight 4, outputs: 1 weight-4 wire, 1 weight-8 wire
#* Add a full adder for weight 8, and pass the remaining wire through, outputs: 2 weight-8 wires, 1 weight-16 wire
#* Add a full adder for weight 16, outputs: 1 weight-16 wire, 1 weight-32 wire
#* Add a half adder for weight 32, outputs: 1 weight-32 wire, 1 weight-64 wire
#* Pass the only weight-64 wire through, output: 1 weight-64 wire
# Wires at the output of reduction layer 1:
#* weight 1 - 1
#* weight 2 - 1
#* weight 4 - 2
#* weight 8 - 3
#* weight 16 - 2
#* weight 32 - 2
#* weight 64 - 2
# Reduction layer 2:
#* Add a full adder for weight 8, and half adders for weights 4, 16, 32, 64
# Outputs:
#* weight 1 - 1
#* weight 2 - 1
#* weight 4 - 1
#* weight 8 - 2
#* weight 16 - 2
#* weight 32 - 2
#* weight 64 - 2
#* weight 128 - 1
# Group the wires into a pair integers and an adder to add them.

ee also

Wikimedia Foundation. 2010.

### Look at other dictionaries:

• Wallace-Tree-Multiplizierer — Der Wallace Tree Multiplizierer ist in der Digitaltechnik eine Schaltung zur effizienten Multiplikation zweier Binärzahlen. Im Wallace Tree erfolgt die Multiplikation über mehrere Stufen. In der ersten werden alle Bits der beiden Faktoren… …   Deutsch Wikipedia

• Wallace — may refer to:PeoplePeople with the surname Wallace: *Wallace (surname)Fictional people with Wallace as the full name: * Wallace, a character on The Wire * Wallace, the principal character in the British animated series Wallace and Gromit *Wallace …   Wikipedia

• Wallace Stevens — (Reading (Pensilvania), 2 de octubre de 1879 – Hartford (Connecticut), 2 de agosto de 1955) fue un poeta estadounidense, adscrito, como T. S. Eliot, a la corriente vanguardista (modernism: modernismo anglosajón) en lengua inglesa. Trabajó toda su …   Wikipedia Español

• Wallace fountain — Wallace fountains are public drinking fountains that appear in the form of small cast iron sculptures scattered throughout the city of Paris, France. mainly along the most frequented sidewalks. They are named after the Englishman Richard Wallace …   Wikipedia

• Wallace Beery — vers 1914 à Chicago Données clés Nom de naissance Wallace Fitzgerald Beery …   Wikipédia en Français

• Wallace Chafe — (born 1927) is an American linguist.Born in Cambridge, Massachusetts, and graduating the Yale University where he obtained his doctorate in 1958, he further worked in the University of California, Berkeley until 1986 and later in the University… …   Wikipedia

• Wallace Stevens — Infobox Writer name = Wallace Stevens imagesize = 144px caption = pseudonym = birthname = birthdate = Birth date|1879|10|2 birthplace = Reading, Pennsylvania, United States deathdate = Death date and age|1955|8|2|1879|10|2 deathplace = Hartford,… …   Wikipedia

• Tree Hill — Les Frères Scott Pour les articles homonymes, voir Scott. Les Frères Scott Titre original One Tree Hill Genre Série dramatique, pour adolescents Créateur(s) Mark Schwahn Production Brian Robbins Greg …   Wikipédia en Français

• Wallace Wolodarsky — Infobox Celebrity name = Wallace Wolodarsky imagesize = 200px caption = Wallace Wolodarsky on the set of Sorority Boys . birth date = Unknown birth place = Unknown death date = death place = occupation = Director Screenwriter salary = networth =… …   Wikipedia

• Tree Martin — Taxobox name = Tree Martin status = LC | status system = IUCN3.1 regnum = Animalia phylum = Chordata classis = Aves ordo = Passeriformes familia = Hirundinidae genus = Petrochelidon species = P. nigricans binomial = Petrochelidon nigricans… …   Wikipedia