Here is the detailed explanation of Multiplication Algorithms:
Multiplication algorithms are methods used to perform multiplication operations in computer arithmetic. These algorithms are designed to efficiently multiply two numbers, often represented in binary format, using various techniques.
Flowchart for Multiply Operation:
Booth Multiplication Algorithm:
Booth algorithm gives a procedure for multiplying binary integers in signed- 2’scomplement representation.
Note:- It operates on the fact that strings of 0’s in the multiplier require no addition but just shifting, and a string of 1’s in the multiplier from bit weight 2^kto weight 2^m can be treated as 2^k+1 – 2^m.
• For example: the binary number 001110 (+14) has a string 1’s from 2^3to 2^1 (k=3,m=1). The number can be represented as 2^k+1 – 2^m. = 2^4 –2^1 = 16 – 2 = 14. Therefore, the multiplication M X 14, where M is the multiplicand and 14 the multiplier, can be done as M X 2^4 – M X 2^1.
Thus the product can be obtained by shifting the binary multiplicand M four times to the left and subtracting M shifted left once.
Hardware Implementation for Booth Algorithm:
As in all multiplication schemes, booth algorithm requires examination of the multiplier bits and shifting of partial product.
Prior to the shifting, the multiplicand may be added to the partial product, subtracted from the partial, or left unchanged according to the following rules:
- The multiplicand is subtracted from the partial product upon encountering the first least significant 1 in a string of 1’s in the multiplier.
- The multiplicand is added to the partial product upon encountering the first 0 in a string of 0’s in the multiplier.
- The partial product does not change when multiplier bit is identical to the previous multiplier bit.
The algorithm works for positive or negative multipliers in 2’s complement representation.
This is because a negative multiplier ends with a string of 1’s and the last operation will be a subtraction of the appropriate weight.
The two bits of the multiplier in Qn and Qn+1 are inspected.
If the two bits are equal to 10, it means that the first 1 in a string of 1 ‘s has been encountered. This requires a subtraction of the multiplicand from the partial product in AC.
If the two bits are equal to 01, it means that the first 0 in a string of 0’s has been encountered. This requires the addition of the multiplicand to the partial product in AC.
When the two bits are equal, the partial product does not change.
Array Multiplier
An array multiplier is a hardware circuit used for multiplying two binary numbers together. It’s commonly used in digital systems, especially in microprocessors and other integrated circuits where fast multiplication operations are required.
• They are advantageous because they can perform multiplication in parallel, which makes them faster than sequential multiplication methods.
Floating Point Multiplication:
