19-03-2014, 04:34 PM
A Modified Booth Algorithm for High Radix Fixed-point Multiplication
[attachment=60272]
Abstract
The Booth multiplication algorithm produces incorrect re-
sults for some word sizes, when it is extended for higher radix, fixed-point
multiplication. We present a modification of the Booth algorithm that
produces correct results when the radix is any power of 2 and the
multipliers are of any size.
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 111dexribes 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. The
result of the original Booth algorithm is incorrect as the correct
product has an odd number of bits to the right of the binary point.
The correct product actually has ( n m ) bits to the right of the
binary point. This problem can be solved if the partial product in
the 1"' pas? is sign extended to contain ( n ~n - ( i - 1) x 2)
bits. This ensures that the product size is correct and therefore
results in the correct answer. If the radix is r , the number of bits
eliminated in each pass is log, T .
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.
[attachment=60272]
Abstract
The Booth multiplication algorithm produces incorrect re-
sults for some word sizes, when it is extended for higher radix, fixed-point
multiplication. We present a modification of the Booth algorithm that
produces correct results when the radix is any power of 2 and the
multipliers are of any size.
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 111dexribes 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. The
result of the original Booth algorithm is incorrect as the correct
product has an odd number of bits to the right of the binary point.
The correct product actually has ( n m ) bits to the right of the
binary point. This problem can be solved if the partial product in
the 1"' pas? is sign extended to contain ( n ~n - ( i - 1) x 2)
bits. This ensures that the product size is correct and therefore
results in the correct answer. If the radix is r , the number of bits
eliminated in each pass is log, T .
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.