15-11-2012, 01:11 PM
Booth's Algorithm
Booth.docx (Size: 16.57 KB / Downloads: 26)
Booth's algorithm can be implemented by repeatedly adding (with ordinary unsigned binary addition) one of two predetermined values A and S to a product P, then performing a rightward arithmetic shift on P. Let m and r be the multiplicand and multiplier, respectively; and let x and y represent the number of bits in m and r.
1. Determine the values of A and S, and the initial value of P. All of these numbers should have a length equal to (x + y + 1).
1. A: Fill the most significant (leftmost) bits with the value of m. Fill the remaining (y + 1) bits with zeros.
2. S: Fill the most significant bits with the value of (−m) in two's complement notation. Fill the remaining (y + 1) bits with zeros.
3. P: Fill the most significant x bits with zeros. To the right of this, append the value of r. Fill the least significant (rightmost) bit with a zero.
2. Determine the two least significant (rightmost) bits of P.
1. If they are 01, find the value of P + A. Ignore any overflow.
2. If they are 10, find the value of P + S. Ignore any overflow.
3. If they are 00, do nothing. Use P directly in the next step.
4. If they are 11, do nothing. Use P directly in the next step.
How it works
Consider a positive multiplier consisting of a block of 1s surrounded by 0s. For example, 00111110. The product is given by :
where M is the multiplicand. The number of operations can be reduced to two by rewriting the same as
In fact, it can be shown that any sequence of 1's in a binary number can be broken into the difference of two binary numbers:
Hence, we can actually replace the multiplication by the string of ones in the original number by simpler operations, adding the multiplier, shifting the partial product thus formed by appropriate places, and then finally subtracting the multiplier. It is making use of the fact that we do not have
to do anything but shift while we are dealing with 0s in a binary multiplier, and is similar to using the mathematical property that 99 = 100 − 1 while multiplying by 99.
This scheme can be extended to any number of blocks of 1s in a multiplier (including the case of single 1 in a block). Thus,
Booth's algorithm follows this scheme by performing an addition when it encounters the first digit of a block of ones (0 1) and a subtraction when it encounters the end of the block (1 0). This works for a negative multiplier as well. When the ones in a multiplier are grouped into long blocks, Booth's algorithm performs fewer additions and subtractions than the normal multiplication algorithm.
Booth.docx (Size: 16.57 KB / Downloads: 26)
Booth's algorithm can be implemented by repeatedly adding (with ordinary unsigned binary addition) one of two predetermined values A and S to a product P, then performing a rightward arithmetic shift on P. Let m and r be the multiplicand and multiplier, respectively; and let x and y represent the number of bits in m and r.
1. Determine the values of A and S, and the initial value of P. All of these numbers should have a length equal to (x + y + 1).
1. A: Fill the most significant (leftmost) bits with the value of m. Fill the remaining (y + 1) bits with zeros.
2. S: Fill the most significant bits with the value of (−m) in two's complement notation. Fill the remaining (y + 1) bits with zeros.
3. P: Fill the most significant x bits with zeros. To the right of this, append the value of r. Fill the least significant (rightmost) bit with a zero.
2. Determine the two least significant (rightmost) bits of P.
1. If they are 01, find the value of P + A. Ignore any overflow.
2. If they are 10, find the value of P + S. Ignore any overflow.
3. If they are 00, do nothing. Use P directly in the next step.
4. If they are 11, do nothing. Use P directly in the next step.
How it works
Consider a positive multiplier consisting of a block of 1s surrounded by 0s. For example, 00111110. The product is given by :
where M is the multiplicand. The number of operations can be reduced to two by rewriting the same as
In fact, it can be shown that any sequence of 1's in a binary number can be broken into the difference of two binary numbers:
Hence, we can actually replace the multiplication by the string of ones in the original number by simpler operations, adding the multiplier, shifting the partial product thus formed by appropriate places, and then finally subtracting the multiplier. It is making use of the fact that we do not have
to do anything but shift while we are dealing with 0s in a binary multiplier, and is similar to using the mathematical property that 99 = 100 − 1 while multiplying by 99.
This scheme can be extended to any number of blocks of 1s in a multiplier (including the case of single 1 in a block). Thus,
Booth's algorithm follows this scheme by performing an addition when it encounters the first digit of a block of ones (0 1) and a subtraction when it encounters the end of the block (1 0). This works for a negative multiplier as well. When the ones in a multiplier are grouped into long blocks, Booth's algorithm performs fewer additions and subtractions than the normal multiplication algorithm.