Know About Modified Booth Algorithm

Modified Booth Algorithm

Generally, we perform many mathematical operations in our daily life such as addition, subtraction, multiplication, division, and so on. Let us consider the multiplication process that can be performed in different methods. Different types of algorithms can be used to perform multiplication like grid multiplication method, long multiplication, lattice multiplication, peasant or binary multiplication, and so on. Binary multiplication is usually performed in digital electronics by using an electronic circuit called as binary multiplier. These binary multipliers are implemented using different computer arithmetic techniques. Booth multiplier that works based on booth algorithm is one of the most frequently used binary multipliers.

Booth Algorithm

Booth multiplication algorithm or Booth algorithm was named after the inventor Andrew Donald Booth. It can be defined as an algorithm or method of multiplying binary numbers in two’s complement notation. It is a simple method to multiply binary numbers in which multiplication is performed with repeated addition operations by following the booth algorithm. Again this booth algorithm for multiplication operation is further modified and hence, named as modified booth algorithm.

Modified Booth Algorithm

Booth multiplication algorithm consists of three major steps as shown in the structure of booth algorithm figure that includes generation of partial product called as recoding, reducing the partial product in two rows, and addition that gives final product.

For a better understanding of modified booth algorithm & for multiplication, we must know about each block of booth algorithm for multiplication process.

Modified Booth Algorithm Encoder

This modified booth multiplier is used to perform high-speed multiplications using modified booth algorithm. This modified booth multiplier’s computation time and the logarithm of the word length of operands are proportional to each other. We can reduce half the number of partial product. Radix-4 booth algorithm used here increases the speed of multiplier and reduces the area of multiplier circuit. In this algorithm, every second column is taken and multiplied by 0 or +1 or +2 or -1 or -2 instead of multiplying with 0 or 1 after shifting and adding of every column of the booth multiplier. Thus, half of the partial product can be reduced using this booth algorithm. Based on the multiplier bits, the process of encoding the multiplicand is performed by radix-4 booth encoder.

The overlapping is used for comparing three bits at a time. This grouping is started from least significant bit (LSB), in which only two bits of the booth multiplier are used by the first block and a zero is assumed as third bit as shown in the figure.

Bit Pairing as per Booth Recoding

The figure shows the functional operation of the radix-4 booth encoder that consists of eight different types of states. The outcomes or multiplication of multiplicand with 0, -1, and -2 are consecutively obtained during these eight states.

Booth Recoding Table for Radix-4

The steps given below represent the radix-4 booth algorithm:

• Extend the sign bit 1 position if necessary to ensure that n is even.
• Append a 0 to the right of the least significant bit of the booth multiplier.
• According to the value of each vector, each partial product will be 0, +y, -y, +2y or -2y.

Booth’s Encoder

Modified booth multiplier’s (Z) digits can be defined with the following equation:

Zj = q2j + q2j-1 -2q2j+1 with q-1 = 0

The figure shows the modified booth algorithm encoder circuit. Now, the product of any digit of Z with multiplicand Y may be -2y, -y, 0, y, 2y. But, by performing left shift operation at partial products generation stage, 2y may be generated. By taking 1’s complement to this 2y, negation is done, and then one is added in appropriate 4-2 compressor. One booth encoder shown in the figure generates three output signals by taking three consecutive bit inputs so as to represent all five possibilities -2X, -X, 0, X, 2X.

Partial Product Generator

Partial Product Generator

If we take the partial product as -2y, -y, 0, y, 2y then, we have to modify the general partial product generator. Now, every partial product point consists of two inputs (consecutive bits) from multiplicand and, based on the requirement, the output will be generated and its complements also generated in case if required. The figure shows the partial product generator circuit.

The 2’s complement is taken for negative values of y. There are different types of adders such as conventional adders, ripple-carry adders, carry-look-ahead adders, and carry select adders. The carry select adders (CSLA) and carry-look-ahead adders are considered as fastest adders and are frequently used. The multiplication of y is done by after performing shift operation on y – that is – y is shifted to the left by one bit.

Hence, to design n-bit parallel multipliers only n2 partial products are generated by using booth algorithm. Thus, the propagation delay to run circuit, complexity of the circuit, and power consumption can be reduced. A simple practical example to understand modified booth algorithm is shown in the figure below.

Practical Multiplication Example using Modified Booth Algorithm

For more technical help regarding modified booth algorithm and also for designing electrical and electronics projects, you can approach us by posting your comments in the comments section below.