Methods and apparatus for efficient complex long multiplication and covariance matrix implementation

• US 7,072,929 B2
• Filed: 11/01/2001
• Issued: 07/04/2006
• Est. Priority Date: 11/01/2000
• Status: Expired due to Fees

• Current Assignee: Altera Corporation (Intel Corporation)
• Original Assignee: PTS Corporation
• Inventors: Pechanek, Gerald G., Rodriguez, Ricardo, Coopman, Kevin, Strube, David, Plonski, Matthew
• Primary Examiner(s): Chaki, Kakali
• Assistant Examiner(s): Do, Chat C.
• Application Number:
  US10/004,010
• Publication Number:
  US 20020169813A1
• Time in Patent Office: 1,706 Days
• Field of Search: 708620-632, 708/607, 708/501, 708/495, 708/404, 708/300, 708/523
• US Class Current: 708/622
• CPC Class Codes: G06F 17/15 Correlation function computation including computation of convolution operations arithmetic circuits for sum of products per se, e.g. multiply-accumulators G06F7/5443; digital filters, e.g. FIR, IIR, adaptive filters H03H17/00
• CPC Class Codes: G06F 17/16 Matrix or vector computation , e.g. matrix-matrix or matrix-vector multiplication, matrix factorization matrix transposition G06F7/78
• CPC Class Codes: G06F 2207/3896 Bit slicing
• CPC Class Codes: G06F 7/4812 Complex multiplication
• CPC Class Codes: G06F 9/30014 with variable precision
• CPC Class Codes: G06F 9/325 for loops, e.g. loop detection or loop counter
• CPC Class Codes: G06F 9/3885 using a plurality of independent parallel functional units

Abstract

A digital signal processor for computing various types of complex multiplication is described. The digital signal processor operates in conjunction with registers, a multiplier, an adder, and a multiplexer The Registers store first and second complex operands. The multiplier simultaneously performs multiplications to produce each combination of products between the real and imaginary terms of the first and second complex operands. The multiplexer selects which produced products are added to or subtracted from each other based on the type of complex multiplication being performed. The adder simultaneously performs additions and subtractions, if necessary, to produce both real and imaginary results depending on whether the type of complex multiplication being performed is a conjugated operation. The registers store the results of the complex multiplication.

Claims

1. An apparatus for the two cycle computation of a plurality of types of complex multiplication, the apparatus comprising:

a first storage means for storing a first complex operand and a second complex operand, the first complex operand including real component Xr and imaginary component Xi, the second complex operand including real component Yr and imaginary component Yi;

multiplier means for simultaneously performing multiplications in a first cycle of operation to produce products Xr*Yr,Yr*Yi*Yr and Xi*Yi, the multiplier means comprising an input to receive a signal indicating a type of complex multiplication to be performed;

a second storage means for storing products Xr*Yr, Xr*Yi, Xi*Yr and Xi*Yi;

adder means for simultaneously performing additions and subtractions in a second cycle of operation to produce a conjugated or nonconjugated result depending on the type of complex multiplication to be performed, said multiplier means routing produced products to the second storage means in response to the received signal indicating the type of complex multiplication to be performed and aligning the produced products in the second storage means for subsequent addition or subtraction with each other, the adder means comprising an input to receive the signal indicating the type of complex multiplication to be performed, the adder means adding or subtracting the aligned produced products in response to the received signal;

a third storage means for storing the results of said adder means;

accumulator means for simultaneously performing accumulation in the second cycle of operation to accumulate the results of said adder means with the current contents of said third storage means, wherein said third storage means is further for storing the results of said accumulator means; and

extended precision storage means for storing an interim result, wherein said accumulator means is further for simultaneously performing accumulation in the second cycle of operation to accumulate the results of said adder means with both the current contents of said third storage means and the interim result stored in said extended precision storage means,

wherein said extended precision storage means stores extended precision results of said accumulator means at the completion of the accumulation means.

2. The apparatus of claim 1 wherein:

the complex operand components Xr, Xi, Yr and Yi are each 16 bits,

the real and imaginary results are each 32 bits, and

the extended precision results are each 8 bits.

3. The apparatus of claim 1 wherein:

the complex operand components Xx, Xi, Yr and Yi are each 16 bits, and the real and imaginary results are each 32 bits.

4. The apparatus of claim 1 wherein the multiplier means is further for simultaneously performing multiplications in the second cycle of operation utilizing a second pair of operands.

5. An apparatus for the single cycle computation for a plurality of types of complex multiplication, the apparatus comprising:

a first storage means for storing a first complex operand and a second complex operand, the first complex operand including real component Xr and imaginary component Xi, the second complex operand including real component Yr and imaginary component Yi;

multiplier means for simultaneously performing multiplications in a first cycle of operation to produce products Xr*Yr, Xr*Yi Xi*Yr and Xi*Yi, the multiplier means comprising an input to receive a signal indicating a type of complex multiplication to be performed;

adder means for simultaneously performing additions and subtractions in the first cycle of operation to produce a conjugated or nonconjugated result depending on the type of complex multiplication to be performed, said multiplier means routing produced products to the second storage means in response to the received signal indicating the type of complex multiplication to be performed and aligning the produced products in the second storage means for subsequent addition or subtraction with each other, the adder means comprising an input to receive the signal indicating the type of complex multiplication to be performed, the adder means adding or subtracting the aligned produced products in response to the received signal;

a third storage means for storing the results of said adder means; and

accumulator means for simultaneously performing accumulation in the first cycle of operation to accumulate the results of said adder means with the current contents of said third storage means, wherein said third storage means is further for storing the results of said accumulator means

extended precision storage means for storing an interim result, wherein said accumulator means is further for simultaneously performing accumulation in the first cycle of operation to accumulate the results of said adder means with both the current contents of said third storage means and the interim result stored in said extended precision storage means, wherein said extended precision storage means stores extended precision results of said accumulator means at the completion of the accumulation means.

6. The apparatus of claim 5 wherein:

the complex operand components Xr, Xi, Yr and Yi are each 16 bits,

the real and imaginary results are each 32 bits, and

the extended precision results are each 8 bits.

7. The apparatus of claim 5 wherein:

the complex operand components Xr, Xi, Yr and Yi are each 16 bits, and the real and imaginary results are each 32 bits.

8. The apparatus of claim 5 wherein the multiplier means is further for simultaneously performing multiplications in a second cycle of operation utilizing a second pair of operands.

9. The apparatus of claim 5 further comprising:

a logical array coupled to the multiplier means and the adder/accumulator means, said logical array aligning the produced products to determine which produced products are added to or subtracted from each other based on the type of complex multiplication being performed.

10. An apparatus for the two cycle computation of a plurality of complex multiplication, the apparatus comprising:

a first storage register for storing a first complex operand and a second complex operand, the first complex operand including real component Xr and imaginary component Xi, the second complex operand including real component Yr and imaginary component Yi;

a multiplier for simultaneously performing multiplications in a first cycle of operation to produce products Xr*Yr, Xr*Yi, Xi*Yr and Xi*Yi, the multiplier means comprising an input to receive a signal indicating a type of complex multiplication to be performed;

a second storage register for storing products Xr*Yr, Xr*Yi, Xi*Yr and Xi*Yi;

an adder for simultaneously performing additions and subtractions in a second cycle of operation to produce a conjugated or nonconjugated result depending on the type of complex multiplication to be performed, said multiplier means routing produced products to the second storage means in response to the received signal indicating the type of complex multiplication to be performed and aligning the produced products in the second storage means for subsequent addition or subtraction with each other, the adder comprising an input to receive the signal indicating the type of complex multiplication to be performed, the adder means adding or subtracting the aligned produced products in response to the received signal;

a third storage register for storing the results of said adder means;

an accumulator for simultaneously performing accumulation in the second cycle of operation to accumulate the results of said achier with the current contents of said third storage register, wherein said third storage register is further for storing the results of said accumulator; and

an extended precision storage register for storing an interim result, wherein said accumulator is further for simultaneously performing accumulation in the second cycle of operation to accumulate the results of said adder with both the current contents of said third storage register and the interim result stored in said extended precision storage means, wherein said extended precision storage register stores extended precision results of said accumulator at the completion of the accumulator.

11. The apparatus of claim 10 wherein:

the complex operand components Xr, Xi, Yr and Yi are each 16 bits, the real and imaginary results are each 32 bits, and the extended precision results are each 8 bits.

12. The apparatus of claim 10 wherein:

the complex operand components Xr, Xi, Yr and Yi are each 16 bits, and the real and imaginary results are each 32 bits.