Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1999-06-14
2002-06-25
Malzahn, David H. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06411979
ABSTRACT:
FIELD OF THE INVENTION
This invention is related to digital multipliers. More particularly, this invention is related to a digital multiplier which performs multiplication of complex numbers using a multi-bit recoding architecture.
BACKGROUND OF THE INVENTION
1. Multi-bit Recoding Multiplication
A widely used multiplier architecture uses multibit recoding of two's complement binary numbers to reduce the number of iterations required when performing a multiplication as a series of additions. A conventional generalized multibit recoding circuit
10
is illustrated in
FIG. 1
a
. Conventional multibit recoding techniques are described in detail in H. Sam and A. Gupta, “A Generalized Multibit Recoding of Two's Complement Binary Numbers and Its Proof with Application in Multiplier Implementations”, IEEE Trans. Comp., V. 39 #8, p. 1006, August 1990, the contents of which are hereby incorporated by reference.
In brief, to determine the product Z of a multiplier X and a multiplicand Y in this architecture, the multiplier X is provided to a recoder
12
which examines the multiplier k+1 bits at a time and generates a corresponding sequence of signed digit values. These recoded values represent the number of times the multiplicand will be added or subtracted after shifting to contribute to the final product. The signed digits have values between 0 and +/−2
k−1
, where 2
k
is the recoding radix. In conjunction with recoding the multiplier X, the multiplicand Y is input to a multiples generator
14
which produces output signals that represent multiples of the multiplicand Y from Y to 2
(k−1)
Y.
To perform the multiplication, each of the signed digits is used to select a particular multiple of Y, which is then shifted as necessary according to the “place” of the multiplier X that the signed digit represents in radix 2
k
and then summed. The summation, which is performed by a partial product summer
16
, can be in series or in parallel. Preferably, in the case of parallel summation, the shifting is hardwired.
In one implementation of the algorithm, a two's complement binary number X is recoded into a signed digit representation as follows. First, the sign bit of X is extended as many positions as necessary so that the total number of bits n in X is divisible by k. Then a 0 is appended to the right of the least-significant-bit of X, i.e., to the right of bit position 0. This appended bit is designated position −1. Next, vectors of k+1 bits are formed starting from bit x
−1
such that adjacent vectors share one bit. Each bit vector is converted into a signed digit according to the inner product of the bit vector with the vector K=[−2
k−1
2
k−2
. . . 2
1
2
0
1]. Generally, the possible inner products are predetermined and hardcoded in recoder
12
, i.e., as a look-up table or hardwired logic, using techniques known to those skilled in the art. In the particular implementation of a radix
16
multi-bit recoding multiplier, five bits of the multiplier X are examined at once and recoded to control whether multiples of from one to eight of the multiplicand get added or subtracted to contribute to the final result after shifting by the appropriate multiple of k bits. A table of the signed digit values for a 5-Bit Recoding (k=4) follows:
TABLE 1
Quintuplet
Quintuplet
Value
Signed Digit Value
Value
Signed Digit Value
00000
+0
10000
−8
00001
+1
10001
−7
00010
+1
10010
−7
00011
+2
10011
−6
00100
+2
10100
−6
00101
+3
10101
−5
00110
+3
10110
−5
00111
+4
10111
−4
01000
+4
11000
−4
01001
+5
11001
−3
01010
+5
11010
−3
01011
+6
11011
−2
01100
+6
11100
−2
01101
+7
11101
−1
01110
+7
11110
−1
01111
+8
11111
0
As also known to those of skill in the art, the multiples of the multiplicand can be determined using various techniques, such as combinations of shifts and adds. Only multiples of three, five, and seven times the multiplicand require any effort to determine since the multiples of two, four, and eight can be formed by shifts of the multiplicand, and the multiple of six can be formed by a shift of the multiple of three. In one implementation, the three, five, and seven multiples can be generated using a sequence of adders, i.e., 3Y=Y+2Y, 5Y=Y+4Y, and 7Y =8Y−Y.
In a radix
16
(i.e., k=4) multiplier circuit, a sixteen bit two's complement multiplier X gets recoded into four signed digits SD
1
-SD
4
, each of which indicates the addition or subtraction of zero or one of the eight multiples of the multiplicand. A block diagram of partial product adder
16
configured for a 16-bit multiplier and multiplicand using radix
16
encoding is illustrated in
FIG. 1
b
. The various multiples of Y output by the multiples generator
14
are input to four multiplexers
18
.
1
-
18
.
4
. Each signed digit SD
1
-SD
4
controls a respective multiplexer to select the appropriate multiple of Y (i.e., 0 to 8Y). First and second adders
20
,
22
each receive inputs from a respective pair of multiplexers, as shown. Adders
20
,
22
also receive sign control signals in accordance with the sign of the signed digits which indicate whether the inputs are added to or subtracted from the partial product. The outputs of adders
20
and
22
are themselves combined by an adder
24
which outputs the final product Z. As indicated above, the outputs of each of the multiplexers must be shifted in accordance with the “place” that signed digit represents in base
16
. This shift can be accomplished by shifting the bit positions in the hardwired connection between the output of the multiplexers and the input of the adders.
2. Complex Number Multiplication
Complex number multiplication is an increasingly common operation in Digital Signal Processing (DSP). To multiply two complex numbers, represented as X
1
+iY
1
and X
2
+iY
2
, where “i” represents the square root of −1, the programmer typically breaks the computation up into
(X
1
+i Y
1
)(X
2
+i Y
2
)=(X
1
X
2
−Y
1
Y
2
)+i(X
1
Y
2
+Y
1
X
2
) Equ. 1
In a conventional DSP which has a single fixed point multiplier available, the four multiplications are performed sequentially and sums and differences are formed. For a typical programmable DSP, an addition or subtraction can be performed in parallel to the multiplication, with each of the multiplications or additions taking a cycle. More recently, programmable DSP integrated circuits have appeared that contain two or more multipliers operating in parallel. The multipliers are typically general purpose devices and each is a replica of the other. In a conventional multi-multiplier DSP, the same computation as when a single multiplier is available is performed, only it takes less time because more than one multiplication may be performed in parallel.
Attempts have been made to optimize specific Digital Signal Processing algorithms which perform complex number multiplication in hardware. In one configuration of such an Application Specific Integrated Circuit (ASIC) designed to implement Equation 1, four parallel multipliers are provided, similar to a conventional multi-multiplier DSP. The multipliers, which are copies of each other, calculate the four cross-products (X
1
X
2
, Y
1
Y
2
, X
1
Y
2
, X
2
Y
1
) in parallel. Two adders are provided, each connected to receive the outputs of a respective pair of multipliers. The adders combine the appropriate products to generate the real and imaginary components of the output. However, since each multiplier is replicated in its entirety, such a system requires a relatively large area of space in an integrated circuit to implement.
In another attempt, the complex multiplication performed is “decomposed” to reduce the number of required multiplications from four to three according to the alternate decomposition:
(X
1
&plu
LandOfFree
Complex number multiplier circuit does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Complex number multiplier circuit, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Complex number multiplier circuit will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2936057