Dadda Multiplier

 Array multiplier has more power consumption and propagation delay compared to other multipliers. Wallace multiplier has huge area wastage issue because of the irregularity in the structure. Dadda multiplier is proposed to overcome these disadvantages in the existing multipliers.

Dadda multiplier is a fast parallel multiplier. It was presented by Luigi Dadda in 1965. It is a refinement of Wallace multiplier so its algorithm also has three general stages. The procedure of the three stages is same for Dadda multiplier as that for Wallace multiplier. But in Dadda multiplier, the row reduction processed by placing adders at maximum heights of matrix in the most optimal manner possible. Thus it requires less adders as compared to Wallace multiplier.

Fig. 1: 4x4 Dadda Multiplier

The algorithm of Dadda multiplier is 

1. Let d1 = 2 and di+1 = |15.di|.Di is the height of the matrix for the ith stage. Repeat until the maximum ith stage is reached in which the original matrix of height N contains at least one column which has more than di dots.

2. Place (3, 2) and (2, 2) counters as required in the ith stage from the end to achieve a reduced matrix. Only columns with more than di dots or those who will have more than di dots as they receive carries from less significant (3, 2) and (2, 2) counters are reduced.

3. Let i = i - 1 and repeat step 2 until a matrix with a height of two is generated. This should occur when i=1.

Illustrating the algorithm with 8 by 8 multiplication

1. The partial products that are obtained are to be arranged in the tree form. The matrix heights possible are 2, 3, 4 and 6 where 6 < 8. The largest di = 6.

2. In the above first reduction stage. The columns 0 to 5 have height not exceeding '6'. The column 6's height is '7' and it is reduced to 6 by a (2, 2) counter. By taking into consideration the previous carry from column 6 the column height of column 7 is '9'. To reduce height of column 7 to '6', a (3, 2) and a (2, 2) counters are used. By considering the two carries from column 7, the column 8 requires a (3 ,2) and a (2 ,2) counter. On the similar basis, the column 9 requires a (3, 2) counter.

The second reduction stage, maintains the reduction with maximum height 4.

3. In the above figure, 12 - (3, 2) counters and 2 - (2, 2) counters are to be used to restrict the height of matrix not more than 4.

4. In the above figure, 12 - [3,2] counters and 2 - [2,2] counters are to be used to restrict the height of the matrix not more than '4'.

5. The third reduction stage, maintains the reduction of columns as follows.

6. In the above figure, 9 - (3, 2) counters and one (2, 2) counters are to be used to restrict the height of matrix not more than 3.

7. The Fourth reduction stage, is as follows.

8. In the above figure, 11 - (3, 2) counters and one (2, 2) counters are to be used to restrict the height of matrix not more that 2.

9. The final two-rowed matrix is as follows.

10. Now, the output can be obtained from the 14 - bit carry propagation adder.

11. In generalized form, for N by N case, the total number of (3,3) counters are (N*N) - 4*N+3. The number of (2,2) counters are N-1.

Author: Dhananjay Joijode