Wallace Tree Multiplier

A Wallace Tree multiplier is a multiplier that is used in digital technology . The process is named after Christopher Stewart Wallace , who introduced this multiplier in 1964.

functionality

A - bit Wallace tree based like the dadda multiplier in the formula ${\displaystyle n}$

${\displaystyle \left(\sum _{k=0}^{n}a_{k}2^{k}\right)\cdot \left(\sum _{k=0}^{n}b_{k}2^{k}\right)=\sum _{k=0}^{2n}\sum _{i+j=k}a_{i}b_{j}2^{k}}$.

Here, and , are the binary representations of the two numbers to be multiplied. ${\displaystyle \sum _{k=0}^{n}a_{k}2^{k}}$ ${\displaystyle \sum _{k=0}^{n}b_{k}2^{k}}$ ${\displaystyle a_{k},b_{k}\in \{0,1\}}$

The Wallace Tree Multiplier works in three steps:

1. For each pair with and calculate the partial product . ${\displaystyle (i,j)}$ ${\displaystyle 1\leq i\leq n}$ ${\displaystyle 1\leq j\leq n}$ ${\displaystyle a_{i}\cdot b_{j}\cdot 2^{i+j}}$
2. Add the results of this calculation within the tree structure specific to the Wallace tree multiplier in stages using full and half adders until there are only two numbers left that need to be added.
3. Add these two numbers using a normal adder.

Tree structure of the Wallace tree multiplier

In step 2 of the above steps, the partial products are added in a tree structure.

The partial products are first arranged in columns, respectively so that in one column all the partial products with standing. Then you summarize the columns of the resulting table in groups of three. Each column of these groups of three is used as an input for a full adder if there are three inputs in the column, for a half adder if there are two entries, and not modified at all if there is only one entry. The more highly weighted output of the adders is then assigned to the next column. This process is repeated until there is only one group of three with only two entries in each column. These last two lines are then added using a normal adder . ${\displaystyle a_{i}\cdot b_{j}}$ ${\displaystyle i+j=k}$

Example 8-bit

Here you can see the above procedure for an 8-bit Wallace tree multiplier. The dots stand for the partial products or for the outputs of the previously used full and half adders, which are identified by the thin lines.

running time

The functionality of the Wallace tree multiplier was described above under the use of tables. Each of these tables stands for a step that an electronic signal must go through. So, to find out the runtime of the Wallace tree multiplier, let's find out how many tables there are.

Since a full adder transformed three signals into two, and possibly in a group of three (see above) less elements are needed than for a full adders do not exist is if we with the height of the j-th table, and with the number of input bits designate : ${\displaystyle w_{j}}$ ${\displaystyle n}$

${\displaystyle w_{0}=n{\text{ , }}w_{j+1}\leq 2\cdot \left\lfloor {\frac {w_{j}}{3}}\right\rfloor +(w_{j}\mod 3)}$

The following estimate can be derived from this:

${\displaystyle w_{j}\leq 2\cdot \left\lfloor {\frac {w_{j}}{3}}\right\rfloor +(w_{j}\mod 3)\leq 2\cdot \left\lfloor {\frac {w_{j}}{3}}+1\right\rfloor }$ ${\displaystyle \leq 2\cdot \left\lfloor {\frac {2\cdot \left\lfloor {\frac {w_{j-1}}{3}}+1\right\rfloor }{3}}+1\right\rfloor \leq \ldots \leq \left({\frac {2}{3}}\right)^{j+1}w_{0}+2\sum _{k=0}^{j}{\frac {2^{k}}{3^{k}}}}$ ${\displaystyle <\left({\frac {2}{3}}\right)^{j+1}w_{0}+2\sum _{k=0}^{\infty }{\frac {2^{k}}{3^{k}}}=\left({\frac {2}{3}}\right)^{j+1}w_{0}+6}$

So it follows

${\displaystyle w_{j}\leq \left({\frac {2}{3}}\right)^{j+1}w_{0}+6}$.

If you choose now , the following applies ${\displaystyle j+1=\lceil \log _{3/2}(n)\rceil \Leftrightarrow \left({\frac {3}{2}}\right)^{j+1}=n=w_{0}}$

${\displaystyle w_{j}\leq \left({\frac {2}{3}}\right)^{j+1}\cdot \left({\frac {3}{2}}\right)^{j+1}+6=7}$

However, a table with seven lines can be reduced in a constant number of steps using the above procedure. The following applies to the runtime for a constant number of steps : ${\displaystyle L=j+k}$ ${\displaystyle k\in \mathbb {N} }$

${\displaystyle L\leq \lceil \log _{3/2}(n)\rceil +k\in {\mathcal {O}}(\log(n))}$

Since the running time of an adder (the last step in the Wallace tree multiplier) is also in , the Wallace tree multiplier has the same asymptotic running time as an adder and is therefore faster than an unsigned parallel multiplier , which has an asymptotic running time of . ${\displaystyle {\mathcal {O}}(\log(n))}$ ${\displaystyle {\mathcal {O}}(\log ^{2}(n))}$

The Wallace tree multiplier is also slower in absolute terms than the Dadda tree multiplier , although both multipliers have the same asymptotic running time of . ${\displaystyle {\mathcal {O}}(\log(n))}$

literature

• Peter Pirsch : Architectures of digital signal processing . Teubner, 1996, ISBN 3-519-06157-0 .

Individual evidence

1. ^ CS Wallace: A suggestion for a fast multiplier . In: IEEE Transactions on Electronic Computers . EC-13, No. 1 , February 1964, p. 14-17 , doi : 10.1109 / PGEC.1964.263830 ( PDF ).

Web links

• Multiplication in FPGAs