seminar code
09-08-2014, 03:48 PM
Reducing the Computation Time in (Short Bit-Width) Two’s Complement Multipliers
Abstract
Two’s complement multipliers are important for a wide range of applications. In this paper, we present a technique to
reduce by one row the maximum height of the partial product array generated by a radix-4 Modified Booth Encoded multiplier, without
any increase in the delay of the partial product generation stage. This reduction may allow for a faster compression of the partial
product array and regular layouts. This technique is of particular interest in all multiplier designs, but especially in short bit-width two’s
complement multipliers for high-performance embedded cores. The proposed method is general and can be extended to higher radix
encodings, as well as to any size square and m n rectangular multipliers. We evaluated the proposed approach by comparison with
some other possible solutions; the results based on a rough theoretical analysis and on logic synthesis showed its efficiency in terms of
both area and delay.
MODIFIED BOOTH RECODED MULTIPLIERS
In general, a radix-B ¼ 2b MBE leads to a reduction of the
number of rows to about dn=be while, on the other hand, it
introduces the need to generate all the multiples of the
multiplicand X, at least from B=2 X to B=2 X. As
mentioned above, radix-4 MBE is particularly of interest
since, for radix-4, it is easy to create the multiples of the
multiplicand 0; X; 2X. In particular, 2X can be simply
obtained by single left shifting of the corresponding terms
X. It is clear that the MBE can be extended to higher
radices (see [12] among others), but the advantage of getting
a higher reduction in the number of rows is paid for by
RELATED WORK
Some approaches have been proposed aiming to add the
dn
2e þ 1 rows, possibly in the same time as the dn
2e rows. The
solution presented in [14] is based on the use of different
types of counters, that is, it operates at the level of the
PP reduction phase. Kang and Gaudiot propose a different
approach in [9], that manages to achieve the goal of
eliminating the extra row before the PP reduction phase.
This approach is based on computing the two’s complement
of the last partial product, thus eliminating the need for the
last neg signal, in a logarithmic time complexity. A special
tree structure (basically an incrementer implemented as a
prefix tree [18]) is used in order to produce the two’s
complement (Fig. 3), by decoding the MBE signals through
a 3-5 decoder (Fig. 4a). Finally, a row of 4-1 multiplexers
with implicit zero output1 is used (Fig. 4b) to produce the
last partial product row directly in two’s complement,
without the need for the neg signal. The goal is to produce
the two’s complement
BASIC IDEA
The case of n n square multipliers is quite common, as the
case of n that is a power of two. Thus, we start by focusing
our attention on square multipliers, and then present
the extension to the general case of m n rectangular
multipliers.
Square Multipliers
The proposed approach is general and, for the sake of
clarity, will be explained through the practical case of
8 8 multiplication (as in the previous figures). As briefly
outlined in the previous sections, the main goal of our
approach is to produce a partial product array with a
maximum height of dn
2e rows, without introducing any
additional delay.
Let us consider, as the starting point, the form of the
simplified array as reported in Fig. 2, for all the partial
product rows except the first one. As depicted in Fig. 6a, the
first row is temporarily considered as being split into two
subrows, the first one containing the partial product bits
(from right to left) from pp00 to pp80 and the second one with
two bits set at “one” in positions 9 and 8. Then, the bit neg3
related to the fourth partial product row, is moved to
become a part of the second subrow.
CONCLUSIONS
Two’s complement n n multipliers using radix-4 Modified
Booth Encoding produce dn
2e partial products but due to the
sign handling, the partial product array has a maximum
height of dn
2e þ 1. We presented a scheme that produces a
partial product array with a maximum height of dn
2e, without
introducing any extra delay in the partial product generation
stage. With the extra hardware of a (short) 3-bit addition, and
the simpler generation of the first partial product row, we
have been able to achieve a delay for the proposed scheme
within the bound of the delay of a standard partial product
row generation. The outcome of the above is that the
reduction of the maximum height of the partial product
array by one unit may simplify the partial product reduction
tree, both in terms of delay and regularity of the layou
Abstract
Two’s complement multipliers are important for a wide range of applications. In this paper, we present a technique to
reduce by one row the maximum height of the partial product array generated by a radix-4 Modified Booth Encoded multiplier, without
any increase in the delay of the partial product generation stage. This reduction may allow for a faster compression of the partial
product array and regular layouts. This technique is of particular interest in all multiplier designs, but especially in short bit-width two’s
complement multipliers for high-performance embedded cores. The proposed method is general and can be extended to higher radix
encodings, as well as to any size square and m n rectangular multipliers. We evaluated the proposed approach by comparison with
some other possible solutions; the results based on a rough theoretical analysis and on logic synthesis showed its efficiency in terms of
both area and delay.
MODIFIED BOOTH RECODED MULTIPLIERS
In general, a radix-B ¼ 2b MBE leads to a reduction of the
number of rows to about dn=be while, on the other hand, it
introduces the need to generate all the multiples of the
multiplicand X, at least from B=2 X to B=2 X. As
mentioned above, radix-4 MBE is particularly of interest
since, for radix-4, it is easy to create the multiples of the
multiplicand 0; X; 2X. In particular, 2X can be simply
obtained by single left shifting of the corresponding terms
X. It is clear that the MBE can be extended to higher
radices (see [12] among others), but the advantage of getting
a higher reduction in the number of rows is paid for by
RELATED WORK
Some approaches have been proposed aiming to add the
dn
2e þ 1 rows, possibly in the same time as the dn
2e rows. The
solution presented in [14] is based on the use of different
types of counters, that is, it operates at the level of the
PP reduction phase. Kang and Gaudiot propose a different
approach in [9], that manages to achieve the goal of
eliminating the extra row before the PP reduction phase.
This approach is based on computing the two’s complement
of the last partial product, thus eliminating the need for the
last neg signal, in a logarithmic time complexity. A special
tree structure (basically an incrementer implemented as a
prefix tree [18]) is used in order to produce the two’s
complement (Fig. 3), by decoding the MBE signals through
a 3-5 decoder (Fig. 4a). Finally, a row of 4-1 multiplexers
with implicit zero output1 is used (Fig. 4b) to produce the
last partial product row directly in two’s complement,
without the need for the neg signal. The goal is to produce
the two’s complement
BASIC IDEA
The case of n n square multipliers is quite common, as the
case of n that is a power of two. Thus, we start by focusing
our attention on square multipliers, and then present
the extension to the general case of m n rectangular
multipliers.
Square Multipliers
The proposed approach is general and, for the sake of
clarity, will be explained through the practical case of
8 8 multiplication (as in the previous figures). As briefly
outlined in the previous sections, the main goal of our
approach is to produce a partial product array with a
maximum height of dn
2e rows, without introducing any
additional delay.
Let us consider, as the starting point, the form of the
simplified array as reported in Fig. 2, for all the partial
product rows except the first one. As depicted in Fig. 6a, the
first row is temporarily considered as being split into two
subrows, the first one containing the partial product bits
(from right to left) from pp00 to pp80 and the second one with
two bits set at “one” in positions 9 and 8. Then, the bit neg3
related to the fourth partial product row, is moved to
become a part of the second subrow.
CONCLUSIONS
Two’s complement n n multipliers using radix-4 Modified
Booth Encoding produce dn
2e partial products but due to the
sign handling, the partial product array has a maximum
height of dn
2e þ 1. We presented a scheme that produces a
partial product array with a maximum height of dn
2e, without
introducing any extra delay in the partial product generation
stage. With the extra hardware of a (short) 3-bit addition, and
the simpler generation of the first partial product row, we
have been able to achieve a delay for the proposed scheme
within the bound of the delay of a standard partial product
row generation. The outcome of the above is that the
reduction of the maximum height of the partial product
array by one unit may simplify the partial product reduction
tree, both in terms of delay and regularity of the layou