Joint optimization of modified-booth encoder and partial...

Details Joint optimization of modified-booth encoder and partial... Joint optimization of modified-booth encoder and partial...

1998-08-20

2001-01-09

Malzahn, David H. (Department: 2287)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

Reexamination Certificate

active

06173304

ABSTRACT:

FIELD OF THE INVENTION
This invention relates generally to the field of encoder and partial product generator circuits in a Booth-MacSorley (“modified-Booth”) encoded multiplier, and specifically to a process of optimizing the modified-Booth multiplier array to improve the overall speed of the multiplier.
BACKGROUND OF INVENTION
Multipliers are used in many digital signal processing operations, such as correlations, convolution, filtering and frequency analysis, to perform multiplications. The most basic form of multiplication consists of forming the product of two positive binary numbers. This can be accomplished through the traditional technique of successive additions and shifts in which each addition is conditional on one of the multiplier bits. Thus, the multiplication process may be viewed as consisting of the following two steps:
1. Evaluation of partial products.
2. Accumulation of the shifted partial products.
It should be noted that binary multiplication is equivalent to a logical AND operation. Thus, evaluation of partial products consists of the logical ANDing of the multiplicand and the relevant multiplier bits. Each column of partial products must then be added and, if necessary, any carry values passed to the next column. There are a number of techniques that may be used to perform multiplication.
One such technique is the Radix-n Multiplication system. A Radix-2 system computes the partial products by observing one bit of the multiplicand at a time. Higher radix multipliers can be designed to reduce the number of adders and hence the delay required to compute the partial sums. The best known method is the Booth's algorithm which is a Radix-4 multiplication scheme. Booth's algorithm for a signed binary multiplication technique, as modified by MacSorley, is widely used to design fast multipliers in computer hardware. Reference is made to
FIG. 2
which describes the operations required by the modified-Booth algorithm as known in the art.
A multiplier implemented in VLSI typically contains a linear array of modified-Booth encoders, and a quadratic array of partial product generators. Reference is now made to
FIG. 1
which depicts a typical implementation of an array generally indicated as 1 in a modified-Booth multiplier. Modified-Booth array
1
includes a modified-Booth encoder
10
which receives and encodes the multiplier input information
23
and includes an array of partial product generators generally referred to at
17
. Multiplier input information
23
entering modified-Booth encoder
10
includes multiplier bits
21
. Multiplicand inputs Y
0
-Yn are applied to partial product generator array
17
. After encoding multiplier input information
23
, modified-Booth encoder
10
sends information to the linear array of partial product generators generally indicated as
17
.
In a typical implementation of modified-Booth encoder array
1
, multiplier bits
21
, represented in
FIG. 1
as X(j−1,j,j+1), get converted by modified-Booth encoder
10
to form “n” control signals
24
, where “n” represents a number between 3 and 5. In a typical prior art design, there are n=3 control signals
24
. Reference is now made to
FIG. 4
which depicts the truth table for modified-Booth encoder
10
as known in the art. Control signals
24
are represented in
FIG. 4
by column headings POS (Positive), TWO and ONE.
Partial product generators
17
decode the information received from modified-Booth encoder
10
and multiplicand inputs
170
to generate the appropriate partial product bits. Partial product generators
17
represent only a part of the entire partial product generator array of the multiplier. Partial product generators
17
as known in the prior art and as depicted in
FIG. 1
include a first partial product generator
11
, a second partial product generator
12
, a third partial product generator
13
, a fourth partial product generator
14
, a fifth partial product generator
15
and a sixth partial product generator
16
. First partial product generator
11
, second partial product generator
12
and third partial product generator
13
represent the first three partial product generators to the left of the modified-Booth encoder in the j
th
row of modified-Booth encoder. Fourth partial product generator
14
, Fifth partial product generator
15
and Sixth partial product generator
16
represent the fourth, fifth and sixth partial product generators to the left of the modified-Booth encoder in the j−2
nd
row of modified-Booth encoder. Control signals
24
, converted from multiplier bits
21
, X(j−1,j,j+1), get applied to the corresponding j
th
row of partial product generators
17
. Additionally, input Y
0
is applied to first partial product generator
11
, input Y
1
is applied to second partial product generator
12
, input Y
2
is applied to third partial product generator
13
and fourth partial product generator
14
, input Y
3
is applied to fifth partial product generator
15
and input Y
4
is applied to sixth partial product generator
16
.
Subsequently, the output of the partial product generator in the first column of the j
th
row (represented as PP(0,j)
28
in
FIG. 1
) gets added to the output of the partial product generator in the third column of the j−2
nd
row (represented by PP(2,j−2)
27
in FIG.
1
). Thus, referring again to
FIG. 1
, the output of first partial product generator
11
, Y
0
receiving partial product
28
, gets added to the output of fourth partial product generator
14
, Y
2
receiving partial product
27
by the full adder
30
. Additionally, the carry in output signal
29
(C
in
) of modified-Booth encoder
10
is also used as a carry in to full adder
30
to get a resultant intermediate partial product PP
31
and an intermediate carry out C
out
32
. This entire operation is depicted inside box A of FIG.
1
.
Reference is now made to
FIG. 3
which is a digital circuit diagram representation of second partial product generator
12
as known in the prior art. Input ZO
i
is provided by first partial product generator
11
to second partial product generator
12
. Output ZI
i
is provided by second partial product generator
12
to the next partial product generator in the sequence, in this case, third partial product generator
13
.
In the prior art implementation of modified-Booth algorithm, carry in output signal C
in
29
of modified-Booth encoder
10
can be represented by the following equation as known in the art (see also FIG.
4
):
C
in
=X
j+1
({overscore (
X
j
)}+{overscore (
X
j−1
)})
Expressing C
in
in POS, ONE, TWO terms as illustrated in
FIG. 4
results in the following equation:
C
in
={overscore (POS)}·(ONE+TWO)  (1)
Y
0
receiving partial product
28
in an inverted representation can be expressed in the prior art by the following equation:
{overscore (PP
j,0
)}=((POS⊕
Y
0
)·ONE)+(POS·TWO)+({overscore (ONE)}·{overscore (TWO)})  (2)
The output of full adder
30
is a summation of carry in output signal C
in
29
, Y
0
receiving partial product PP(0,j)
28
and Y
2
receiving partial product PP(2,j−2)
27
. This summation results in intermediate partial product PP
31
and intermediate carry out C
out
32
. Intermediate partial product PP
31
can be represented by the following equation:
 
PP=P
j,0
⊕PP
j−2,2
⊕C
in
  (3)
Intermediate carry out C
out
32
can be represented by the following equation:
C
out
=(
PP
j,0
⊕PP
j−2,2
)·
C
in
+(
PP
j,0
⊕PP
j−2,2
)·
PP
j,0
  (4)
By combining equation (1) and (2) it can be shown that the intermediate term for generation of intermediate partial product PP
31
is simplified as follows:
C
in
⊕PP
j,0
=Y
0
·ONE  (5)
The critical path through modified-Booth encoder array
1
begins with multiplier bits
21
input into modified-Booth encoder
10
, followed by “n” control signals
24
output by modified-Booth encoder

Affiliated with

Also associated with

Rating

Joint optimization of modified-booth encoder and partial... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Joint optimization of modified-booth encoder and partial..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Joint optimization of modified-booth encoder and partial... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2511070