Booth Flipper

<p>In Binary multiplications, the number of ones in the multiplier indicates how many addition operations are needed. Instead of using all the ones in the multiplier, Booth algorithm uses only the bit transitions. Any string of consecutive ones has two bit transitions; one transition at the least significant bit and the second one follows the most significant bit of the stirng. Booth algorithm converts any string of ones in the multiplier into two operations; a subtraction of the multiplicand shifted to the least significant bit of the string followed by an addition at the zero bit that terminates the string, regardless of the string length. Booth algorithm performance is excellent when the number of bit transitions is small. However, the performance of Booth algorithm deteriorates when the binary string contains double transitions; either a single one between two zeros or single zero between two ones. Applying Booth algorithm in this case requires two operations; an addition and a subtraction instead of one operation in comparison to the binary multiplier.</p> <p>A new method is described here that avoids using the algorithm for double-transition strings by flipping the bits of the leading transition thus reducing the double transition string into single transition. The flipping achieves the same outcome of Booth algorithm while saving half the number of partial products. Experimental results show the effectiveness of this approach in overcoming the drawbacks of the traditional Booth algorithm, while maintaining its decoding simplicity in comparison to radix-4 algorithm. The proposed algorithm is guaranteed to reduce the number of partial products to no more than N/2 for N bit operands. The proposed algorithm has been realized with considerable saving in hardware complexity in comparison to Radix-4 Booth lagorithm.</p>