Wallace Tree Multiplier

A Wallace Tree is one of the efficient ways of implementing a multiplier circuit for two integers. It was derived by one of an Australian Computer scientists Chris Wallace in 1964. The Wallace tree uses the carry save reduction method.  In this multiplier technique firstly, the multiplication takes place according to the multiplication rules i.e. using AND gate basic multiplication done by usual multiplication rule. Then after getting the partial products take the 3 rows at a time for the addition of the partial product. For the addition of the 2-bit, half adder is used and for the successive addition of the 3-bit full adder is used. Because of the use of adder, we get 2 rows as a result for the respective 3 rows of addition. After getting two rows, add the one next row with these resultant two rows. Now again we have 3 rows and our aim is to reduce them into 2 rows as mentioned earlier. This reduction and addition with the next row process continues till the last row arrives. After the one full cycle again making 3 rows and successive addition continues. After these further reduction and addition of one result we get only 2 rows remaining. These two rows are now added with the help of the half adder and we get the result.

Fig. 1: 4x4 Wallace Multiplier

Working of Wallace Tree Multiplier:

Step 1: Multiply each bit using AND gates and obtain the partial products from those bits. As it is 4×4 multiplier, all the 4 bits of multiplicand are multiplied with 4 bits of multiplier obtaining 16 partial products. As the basic multiplication rules tells us that 0*0, 1*0 and 0*1 give us output 0 whereas 1*1 gives us 1. This result shows us that the given result we can obtain using AND gate. Thus, for standard basic multiplication we use AND gate which is used for bit by bit multiplication. Here the multiplication is done by using the and gate to perform basic multiplication using binary rules.

Step 2: Reduce the number of partial products to two layers by use of full and half adder for 3bit and 2-bit reduction, respectively. The basic difference between the Carry Save reduction method and the Wallace tree method is that in the Carry save the addition of 3 rows done turn by turn one after another successively but in the Wallace tree method The partial products are divided into 3-3 rows in the first step of the working. Then according to the number of bits present in the formed layer i.e. whether it is 2 bit, or 3 bits use of full adder and half adder takes place in these respective rows. Because of the use of adder for the addition of bits in the layer of 3 we get respective 2-layer bits from the 3 layers. After all the groups of 3 rows get reduced to the 2-layer groups our 2nd layer gets formed for the next step of the addition. Once again formation of 3-3-layer rows groups takes place and reduction to the 2 rows groups occurs using adders. This reduction method is applied at each successive stage so that at the end only two rows remain. After that we must add by the half adder as only two rows remain in the final stage of the addition, and we get the result. Here all the steps occur parallelly. Thus, the time gets reduced in Wallace Tree Multiplier.

The Step 2 can be summarized by 

• Make 3 -3 rows groups which work parallelly.
• Applying a full adder to each column that contains three bits.
• Applying a half adder to each column that contains two bits.
• Passing any single bit columns to the next stage without processing

Fig. 2: 4x4 Wallace tree multiplier with partial product and various stages

Author: Utkarsh Jakate