1. Field of the Invention
The invention described herein relates to arithmetic processing.
2. Background Art
Booth encoding is widely used in the implementation of hardware multipliers because it reduces the number of partial products in multiplication. In essence, the Booth's encoding looks at a multiplier X two bits at a time, starting with the least significant bits (LSB), and depending on the particular combination at hand, it does one of the three operations:
a) If XiXi−1=00 or 11, then shift the existing sum of partial products one bit to the right, where Xi represents the ith bit of X.
b) If XiXi−1=01 then add the multiplicand Y to the existing sum of partial products and then shift the result one bit to the right.
c) If XiXi−1=10 then subtract the multiplicand Y from the existing sum of partial products and then shift the result one bit to the right.
The process starts by appending a 0 to the right of the LSB of the multiplier X, and then looking at binary pairs. The successively considered pairs share one bit, so that in every iteration only one bit of the multiplier is processed and eliminated.