Dadda Multiplier

Design and Implementation of highly efficient and effective 8,16,32-bit Faster DADDA Multiplier

We will be ahead with these Topics:

Multiplier History.
DADDA Multiplier.
Faster DADDA.
Simulation Results.
Design Summary.
Results.

1. Multiplier History:

Multiplier plays an important role for performing the arithmetic operations in both Digital Signal Processors and Microprocessors. In order to enhance the performance characteristics of either the D.S.P. or the Microprocessors, the efficient and effective Multiplication Algorithm has to be adopted. In digital systems,the multiplier are the basic blocks. The Multipliers also contribute to the Computational speed and Power consumption of the digital system. So,the need for designing High speed Multiplier with minimal power dissipation is very crucial for a digital system.Thus,it can boost the efficiency of the Digital systems.

Column compression Multipliers have gained popularity because of their High-computational speed. Wallace and Dadda Multipliers are the well renowned Column compression Multipliers. The Wallace Multiplier was proposed by Chris Wallace, a Australian computer scientist in 1964. The Dadda Multiplier was proposed by Luigi Dadda,an Italian computer Engineer by altering the Wallace Multiplier. Both these Wallace and Dadda Multipliers are reduction based.The reduction is achieved by compressing the columns with a [3,2] counter(Full adder) and a [2,2] counter(Half adder). The three stages that are involved in both Wallace and Dadda Multipliers are similar.

FLOW CHART

(Illustrating the 3-staged Wallace and Dadda Multiplier)

In Wallace Multiplier the reductions are done as much as possible in the layer but in Dadda,only few reductions are done. So,due to above reason the number of [2,2] counters required for Wallace Multiplier is quite High in number. But the Dadda Multiplier doesn't require many [2,2] counters like Wallace. When a comparison is carried between them, the Dadda Multiplier requires less Hardware than the Wallace. Also, the Dadda Multiplier is slightly faster in computation than Wallace. This made the Dadda Multiplier to be focused more in the Implementation.

2. DADDA Multiplier:

Dadda proposed a method of reduction which achieves the reduced two-rowed Partial products in a minimum number of reduction stages. Dadda succeeded this, by placing the [3,2] and [2,2] counters in maximum Critical path in optimal manner. For an N-bit multiplier and multiplicand, there results a N by N partial products. These partial products are arranged in the form a Matrix. Dadda reduced these Matrix height to a two-rowed matrix, through a sequence a reduction stages.

Algorithm:

Let, us assume the final two-rowed matrix height d1 = 2, based on d1 the successive matrix heights are obtained from dj+1 = 1.5 * dj , where j = 1,2,3,4,............, Rounding of fraction in this matrix height should be done down to least. i.e, 13.5 = 13(rounded). The matrix heights will be in this fashion 2,3,4,6,9,13,19,28............. Finally the largest dj should be obtained such that derived matrix height shouldn't exceed the Matrix overall height.
In the first reduction stage, the column compression is to carried with the [3,2] and [2,2] counters such that the obtained reduced matrix height should not exceed dj.
During the compression, the sum is to be passed to same column in the next reduction stage and the carry is to be passed to the next column.
The above two steps are to be repeated until a final two-rowed reduced matrix is obtained.

Illustrating the Algorithm with 8 by 8 Multiplication:

The Partial products obtained are to be arranged in the Tree form. The Matrix heights possible are 2,3,4,6(where 6 < 8). The largest dj = 6.
In the above,1st reduction stage. The column's 0 to 5 have height not more than '6'. The column 6 height is '7' and it is reduced to 6 by a [2,2] counter. By considering the previous carry from column 6 the column height of column 7 is '9'. To reduce column 7 height to '6', a [3,2] and a [2,2] counters are used. By considering the two carry's from column 7 the column 8 requires a [3,2] and a [2,2] counter.Similarly,the column 9 requires a [3,2] counter.
The second reduction stage, maintains the reduction with height not more than '4'.
In the above, 12 - [3,2] counters and 2 - [2,2] counters are to be used to restrict the height of matrix not more than '4'.
The Third reduction stage,maintains the reduction of column's as follows.
In the above, 9 - [3,2] counters and one [2,2] counters are to be used to restrict the height of matrix not more than '3'.
The Fourth reduction stage, is as follows.
In the above, 11 - [3,2] counters and one [2,2] counters are to be used to restrict the height of matrix not more that '2'.
The final two-rowed matrix is as follows.
Now, the result can be obtained from the 14 - bit carry propagation adder(CPA).
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.

3. Faster Dadda:

The Computational speed of the Dadda Multiplier can be enhanced by partitioning the Partial products as shown below:

Here,the two parts are reduced in parallel with the same Dadda reduction procedure stated above. Due to this parallelism approach of reduction the Multiplier is very speed than the custom Dadda Multiplier.

Part 0 reductions:

This Part 0 Matrix compression takes 17 - [3,2] counters and 6 - [2,2] counters to get final two-rowed Matrix. The final stage is merged with the Carry propagation adder and a 11-bit result is obtained.

Part 1 reductions:

This Part 1 Matrix compression takes 14 - [3,2] counters and 5 - [2,2] counters to get final two-rowed Matrix. The final stage is merged with the Carry propagation adder and a 8-bit result is obtained.

Merging of Part 0 & 1 results:

Here, the first 9 bits in part 0 result is directly carried to the final result(p(0) to p(7)). The Common result part in both part 0 & 1 is added with 3-bit RCA and carried to final result(p(8) to p(10)).

Hybrid Adder