Booth and Modified Booth Multiplier

This multiplier comes under the class of array multiplier. Booth multiplier is a powerful algorithm for multiplication of signed numbers, which treats both positive and negative numbers uniformly.

Booth’s Multiplication Algorithm is an algorithm  that use to multiply two signed binary numbers by the method of  two’s complement for binary. Andrew Donald Booth invented the algorithm in 1950. This invention takes place when the Andrew booth doing research on crystallography in London. To check the speed Andrew used the desk calculators which not fast for adding purpose compare to the shifting purpose  from where algorithm is generated.

Each multiplier bit generates one multiple which is added to the partial product for the standard operation add-shift,. If we take a large multiplier, then addition takes place in the large number of multiplicand. Basically the number of additions gives us the delay of the multiplier. But if we reduce the number of additions in the steps then the performance will increase.

Booth multiplier reduces the number of iteration steps which is used for multiplication perform as compare to conventional steps. Booth algorithm ‘scans’ the multiplier operand and skips algorithm chains which can  reduce the number of additions required to produce the result compared to conventional multiplication algorithm, where the multiplier and the multiplicand multiplied bitwise and the partial products are then added.

 

Fig. 1: Architecture of Booth Multiplier

So talking about booth algorithm it is a method that will reduce the number of multiplicand multiples.

For talking about a given range of numbers, a higher representation radix leads to fewer digits. Since for a k-bit binary number radix-4 number can be interpreted as K/2-digit number, similarly for radix-8 number, this can be interpreted as K/3 digit number and so on, it can also deal with more than one bit of the multiplier in each cycle by using high radix multiplication. The below example shows radix-4 calculation

Multiplicand A = ● ● ● ●

Multiplier B = (●●)(●●)

Partial product bits    ● ● ● ●    (B1B0)2 A40

● ● ● ●    (B1B0)2 A40

Product    P = ● ● ● ● ● ● ● ● 

                        Radix-4 multiplication in dot notation

Implementation

Fig. 2: Booth Multiplier using full adder

Comparison of Booth and shift and add methods

Example for booth multiplier algorithm

let's take multiplicand as 6 and multiplier as 2. Also M be the variable for multiplicand and Q be the variable for the multiplier.

 Converting the numbers in the binary form

thus we get 

M=  0110

Q= 0010 

lets assign the bits of Q as Q3 , Q2, Q1, Q0

Booth's algorithm calculates the product in the n steps. Here n is the number of bits used for representing the number.

Conditions for the Booth Multiplication

1. If Q0 and Q-1 are terms are same means if they are 00 or 11 then the right shift of arithmetic logic done by 1 bit

2.    But if Q0 and Q-1 is 1 and 0 respectively them perform A-M to A and then the arithmetic right shift occurs

3.    Also if Q0 and Q-1 is 0 and 1 respectively then perform A+M to A and then right shift as above.

Modified Booth Multiplier (4 bit):

To generate the partial products for implementation of large parallel multipliers the modified booth algorithm is widely used, which adopts the parallel encoding scheme. There  are 2 drawbacks in the original version of Booth’s algorithm mainly contain: The number operations of add and subtract and the in designing parallel multipliers  number of shift operations. If there are isolated 1’s present in the problem the algorithm becomes insufficient. The Modified booth algorithm overcomes this problem.  There  are three major steps in the modified booth algorithm: as in the Booth algorithm figure where the partial products are generated called as recording, partial product reduction in two rows, and addition that gives the final product. The number of partial products are reduced  by half, by using the technique of radix-4 Booth recording. So, instead of shifting and adding for every column of multiplier term and multiplying by 1 or 0, every second column is added, and multiply by + (or ) - 1,+ (or) -2,or 0,to obtain the same results.Radix-4 Booth encoder performs the process of encoding the multiplicand based on multiplier bits. It will compare 3 bits at a time with overlapping technique. Grouping starts from the LSB, and the first block only uses two bits of the multiplier and assumes a zero for the third bit.

                               

                                            

Example:

13*(-6) 

13=01101=> 001101 

6=0110 => 000110

where (-6) becomes 1010=> 111001

      

Radix-4 Booth algorithm is given below 

1. Extend the sign bit 1 position if necessary to ensure that n is even.

2. Append a 0 to the right of the LSB of the multiplier.

3. Partial Product becomes 0, +y, –y, +2y or –2y according to the value of each vector

The negative values of y are made by taking the 2’s complement. The negative values of y are made by taking the 2’s complement and Carry-look-ahead (CLA) fast adders are used

Conclusion: 

Now after analyzing the booth multiplier and comparing their characteristics in the form of multiplication speed, no of computations required, no of hardware, we come to the conclusion that booth multipliers of radix 4 is better than booth multipliers of Radix-2 . By implementing both of these multipliers we analyze that Radix -4 multiplier computation speed is higher than Radix-2.

Author: Chinmay Jangle