Booth Multiplier

linus 17:21:00 2 Comments Edit

Design and Implementation of an Efficient 8,16,32-bit Multiplier using modified BOOTH's Algorithm

WE FOCUS ON:

Multiplier Architecture

Booth Algorithm

Simulation Results

Design Summary

Conclusion

1. Multiplier Architecture:

There are several Multiplier Architectures which has come into existence over recent years. Multiplier is one of the key hardware blocks in Digital Signal Processors(DSP) and microprocessors. Multiplication operations are so considerable in-order to slow down the system operations. In this present years,multiplier architectures are developed by considering minimal operational speed, area and power. An efficient Multiplier can improve the performance of Digital Signal Processors in case of filtering,spectral analysis.

The above multiplier architecture can be divided into two stages. In the first stage the Partial Products are formed by the Booth encoder and Partial Product Generator(PPG). In the second stage the partial products obtained in the above are merged to form the results. Instead of adders here the 5:2,4:2,3:2 compressors can also be used to reduce the carry propagation delay to a great extent. When the adders alone seen we can have the adder circuits such as Carry Propagation adder,carry save adders.

Prior to Multiplication, we require the two operands, a Multiplier and a Multiplicand which are to be stored in the buffer. In normal Binary Multipliers the Partial Products are generated by performing AND operation(multiplying) the bits of Multiplier with the Multiplicand bits.Thus the array of AND gates are used in normal binary multipliers for partial products generation. Here when the multiplier bit is zero then a row of zeros are summed to previous partial product. when the multiplier bit is one then the multiplicand is added once to the previous partial products with a position shift towards left.

2. Booth Algorithm:

Andrew Donald Booth proposed Booth's multiplication algorithm which can perform the multiplication operation of Two Signed Binary numbers in their respective 2's complement form. A.D. Booth's encoding technique is also called as Radix-2 Booth's encoding algorithm.

1. Radix-2 Booth's algorithm:

FLOW CHART

Here is a radix-2 booth algorithm example: Multiplication of 2 and -4. Binary form(signed) of 2 is 0010 and -4 is 1100.

Binary Number with least number of transitions (0 to 1 or 1 to 0) is selected as Multiplier and with more number of transitions is selected as Multiplicand. In the above 1100 has only one transition (1 to 0) so it is chosen as Multiplier whereas the 0010 has two possible transitions(0 to 1 & 1 to 0) so it chosen as Multiplicand.
Now, Multiplier X = 1100 and Multiplicand Y = 0010, the two's compliment of Y is denoted as ' -Y ' = 1110. Here ' -Y ' represents the two's compliment for Y,Multiplicand.
Initialize the AC = 0,X-1 = 0,then compare the LSB X0 and X-1, when' 00 'or '11' Perform Arithmetic shit operation only, when' 01 'add Multiplicand(Y) to AC or when' 10 'subtract Multiplicand(Y) from AC.
Have a look on this file for implementing the Booth's algorithm, https://drive.google.com/file/d/0B6XWO1CwqhhwMlVlMDZ4ZWxZU00/view?usp=sharing.
The Result we see is 11111000 which is ' -8 '.

RADIX-2 BOOTH RECODING

In this algorithm,the Yi and Yi-1 bits of the multiplier are examined and then recoding is done. Booth Recoding reduces the number of partial products which can reduce the hardware and improves the speed of the operation.Some considerable delay is seen during the generation of partial products.This radix-2 Booth recoding works well with serial multiplication which can tolerate variable latency operations with minimum number of serial additions.In case of parllel multiplication the worst case is seen.The worst case is a n-bit Multiplicand significantly requires n - no. of additions. Here the no. of partial products seen are also ' n '.

2. Radix-4 Booth's Algorithm:

In this Radix-4, the grouping of multiplier bits for recoding is done with 3-bits taken at a time. The first group is formed by taking the first bit as zero,and the remaining two bits are the two LSB bits of Multiplier. When forming the Second group,the first bit is considered as the MSB bit of first group and remaining two bits from multiplier.This repeats for next group formation also.The Booth Radix-4 algorithm reduces the number of Partial products by half at minimum circuit's complexity. This Radix-4 can also be called as Modified Booth Algorithm. Booth recoding is carry free and completely performed parallel to have speed.

RADIX-4 BOOTH RECODING

The Radix-4 Booth recoding works effectively for both Signed and Unsigned numbers.

Algorithm:

The Least Significant Bit(LSB) should be padded with zero(Y-1 = 0).
For Signed,the MSB must be padded with two zeros when n is even or else one zero.For Unsigned,the padding is not necessary when n is even.
Grouping of Multiplier into 3-bits must be done which in turn are overlapping.
Partial products are generated with the help of Booth's recoding table as stated above.
On adding the partial products the result can be found.

Booth's Encoder:

In this Booth's Radix-4 Multiplication, the partial products are reduced to n/2. Here,Y is the Multiplier which is encoded with the above circuit. X is Multiplicand. Y2j-1 Y2j Y2j+1 are the three alternatively Grouped bits which are encoded to {0,X,2X,-X,-2X}. In the above circuit the NEG specifies the sign for X or 2X.

Partial Product Generator:

Now,the Partial products are generated with the help of above circuit. Xi Xi-1 are the Multiplicand bits. As specified by the X,2X,NEG the partial products are generated.

3. Radix-8 Booth's Algorithm:

In this Radix-8 Booth's Algorithm the multiplier has been divided in to groups of four bits and these are overlapping groups. The first group is formed by taking the first bit as zero,and the remaining three bits are the three LSB bits of Multiplier. When forming the Second group,the first is considered as the MSB bit of first group and remaining from multiplier. This repeats for next group formation also. Now, the Partial products are then generated by the help of there group bits with the Radix-8 recoding table,below.

RADIX-8 BOOTH RECODING