Wallace tree

A Wallace tree multiplier is a multiplier which is used in the digital technique. The method is named after Chris Wallace, who this multiplier introduced in 1964.

Operation

One-bit Wallace tree multiplier based as Dadda tree multiplier on the formula

Here, and, the binary representations of the two numbers to be multiplied.

The Wallace tree multiplier is in three steps:

Tree structure of the Wallace tree multiplier

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

First, the partial products are arranged in columns so that in one column in each case all partial products are with. Then we group the columns of the resulting table together in groups of three. Each column of these three groups is used as an input for a full adder, provided in the column are three inputs, for a half-adder, if two entries are present and not modified, as long as only one entry is present. The higher weighted output of the adder is then assigned to each of the next column. This process is repeated until only a triad is still present, in the only two entries in each column. These last two lines are then added by means of a normal adder.

For example 8-bit

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

Term

Above, the functionality of the Wallace tree multiplier has been described with use of tables. Each of these tables stands for a step that must go through an electronic signal. To determine the duration of the Wallace tree multiplier, therefore, we find out how many tables there are.

Since a full adder three signals turned into two, and possibly in a group of three (see above) fewer elements than are needed for a full adder do not exist is if we denote the height of the j-th table and with the number of input bits:

From this one can derive the following estimate:

It thus follows

If you choose well, then applies

A table with seven lines can, however, reduce by the above procedure in a constant number of steps. Thus, valid for the duration of a constant number of steps:

Since the running time of an adder is (the last step in the Wallace tree multiplier ) in which Wallace tree multiplier has the same asymptotic running time as an adder and is faster than an unsigned parallel multiplier, the asymptotic running time of having.

The Wallace tree multiplier is further slower than in absolute terms Dadda tree multiplier, although both have the same multiplier asymptotic maturity.