04-06-2012, 12:02 PM
A Modified Booth Algorithm for High Radix Fixed-point Multiplication
A Modified Booth Algorithm.pdf (Size: 256.8 KB / Downloads: 60)
INTRODUCTION
Andrew Booth presented an algorithm to multiply two signed,
two's complement numbers [I]. This algorithm has been extended
for higher radix operands for computational speedup. However. for
certain size operands, correction shifts have to be performed on
the product produced by the Booth algorithm in order to obtain
a correct product. This paper presents a modification of the Booth
algorithm that does not need any correction shifts for any operand
size and for any radix that is a power of 2. In [2] a modified
Booth algorithm is presented for operand sizes that are a power
of 2. This modified algorithm requires correction cycles after the
original Booth algorithm has completed. The algorithm presented in
this paper is not restricted to operand sizes thut are powers of 2
and it rlequires no correction cycles. Section I1 dexribes the standard
Booth multiplication algorithm arid Section 111 dexribes the modified
Booth algorithm. Section V explains the modified algorithm via two
examples.
CORRECTNESS OF THE ALGORITHM
If the radix is 4, three bits are inspected in each cycle and two
bits are eliminated from the multiplier in each pass of the algorithm.
Let us assume that the multiplier has an odd number of bits n after
the binary point. Then the number of passes through the algorithm
is (n + 1)/2. Let the number of bits to the right of the binary point
in the multiplicand be m. Let us assume that m is even. In this
case the original Booth algorithm will always result in a product
that has an even number of bits to the right of the binary point.
This is because the number of passes in the algorithm is (n + 1)/2
which is even and the number of bit-shifts in each pass is 2.
CONCLUSION
We have presented a modification to the Boolh multiplication
algorithm. This modification produces correct results for higher radix.
fixed point multiplication when the radix is a power of 2. Unlike
previous modifications our modification eliminates all correction
cycles and is applicable to any operand sizes.