SymmetricalDataSecurity: Wallace Tree

Monday, February 17, 2020

Wallace Tree

basic principle known from manual multiplication. Image shows a manual example of multiplying 345(top) by 12(side).

Example of reduction on an 8x8 multiplier.

A Wallace tree is an efficient hardware implementation of a digital circuit that multiplies two integers, devised by Australian Computer Scientist Chris Wallace in 1964.^[1]

The Wallace tree has three steps:

Multiply (that is – AND) each bit of one of the arguments, by each bit of the other, yielding $n2{\displaystyle n^{2}}$ $n^{2}$ results. Depending on position of the multiplied bits, the wires carry different weights, for example wire of bit carrying result of $a4b3{\displaystyle a_{4}b_{3}}$ $a_{4}b_{3}$ is 128 (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.^[2]

The second step 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(log⁡n){\displaystyle O(\log n)}$ $O(\log n)$ reduction layers, and each layer has $O(1){\displaystyle O(1)}$ $O(1)$ propagation delay. As making the partial products is $O(1){\displaystyle O(1)}$ $O(1)$ and the final addition is $O(log⁡n){\displaystyle O(\log n)}$ $O(\log n)$ , the multiplication is only $O(log⁡n){\displaystyle O(\log n)}$ $O(\log n)$ , not much slower than addition (however, much more expensive in the gate count). Naively adding partial products with regular adders would require $O(log2⁡n){\displaystyle O(\log ^{2}n)}$ $O(\log^2n)$ time. From a complexity theoretic perspective, the Wallace tree algorithm puts multiplication in the class NC¹.

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.^[3]^[4]

Weights explained

The weight of a wire is the radix (to base 2) of the digit that the wire carries. In general, $anbm{\displaystyle a_{n}b_{m}}$ $a_{n}b_{m}$ – have indexes of $n{\displaystyle n}$ $n$ and $m{\displaystyle m}$ $m$ ; and since $2n2m=2n+m{\displaystyle 2^{n}2^{m}=2^{n+m}}$ $2^{n}2^{m}=2^$ the weight of $anbm{\displaystyle a_{n}b_{m}}$ $a_{n}b_{m}$ is $2n+m{\displaystyle 2^{n+m}}$ $2^$ .

Example

$n=4{\displaystyle n=4}$ $n=4$ , multiplying $a3a2a1a0{\displaystyle a_{3}a_{2}a_{1}a_{0}}$ $a_{3}a_{2}a_{1}a_{0}$ by $b3b2b1b0{\displaystyle b_{3}b_{2}b_{1}b_{0}}$ $b_{3}b_{2}b_{1}b_{0}$ :

First we multiply every bit by every bit:
- weight 1 – $a0b0{\displaystyle a_{0}b_{0}}$ $a_{0}b_{0}$
- weight 2 – $a0b1{\displaystyle a_{0}b_{1}}$ $a_{0}b_{1}$ , $a1b0{\displaystyle a_{1}b_{0}}$ $a_{1}b_{0}$
- weight 4 – $a0b2{\displaystyle a_{0}b_{2}}$ $a_{0}b_{2}$ , $a1b1{\displaystyle a_{1}b_{1}}$ $a_{1}b_{1}$ , $a2b0{\displaystyle a_{2}b_{0}}$ $a_{2}b_{0}$
- weight 8 – $a0b3{\displaystyle a_{0}b_{3}}$ $a_{0}b_{3}$ , $a1b2{\displaystyle a_{1}b_{2}}$ $a_{1}b_{2}$ , $a2b1{\displaystyle a_{2}b_{1}}$ $a_{2}b_{1}$ , $a3b0{\displaystyle a_{3}b_{0}}$ $a_{3}b_{0}$
- weight 16 – $a1b3{\displaystyle a_{1}b_{3}}$ $a_{1}b_{3}$ , $a2b2{\displaystyle a_{2}b_{2}}$ $a_{2}b_{2}$ , $a3b1{\displaystyle a_{3}b_{1}}$ $a_{3}b_{1}$
- weight 32 – $a2b3{\displaystyle a_{2}b_{3}}$ $a_{2}b_{3}$ , $a3b2{\displaystyle a_{3}b_{2}}$ $a_{3}b_{2}$
- weight 64 – $a3b3{\displaystyle a_{3}b_{3}}$ $a_{3}b_{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 of integers and an adder to add them.