Computing multidimensional DFTs in FPGA

• US 6,073,154 A
• Filed: 06/26/1998
• Issued: 06/06/2000
• Est. Priority Date: 06/26/1998
• Status: Expired due to Term

• Current Assignee: Xilinx, Inc. (Advanced Micro Devices, Inc.)
• Original Assignee: Xilinx, Inc. (Advanced Micro Devices, Inc.)
• Inventors: Dick, Christopher H.
• Primary Examiner(s): Mai, Tan V.
• Application Number:
  US09/105,072
• Time in Patent Office: 711 Days
• Field of Search: 708/401, 708/403, 708/405
• US Class Current: 708/401
• CPC Class Codes: G06F 17/141 Discrete Fourier transforms

Abstract

An FPGA configured for computation of an N×N discrete Fourier transform (DFT) using polynomial transforms defined in modified rings of transforms, comprising a first buffer for ordering a set of polynomial data in a two dimensional matrix, a multiplier for multiplying each element of the two dimensional matrix by ω^-n.sbsp.2 (where ω=e^-jπ/N, e is a constant (ln(e)=1),

j=√-1, n₂ =the column index number in the matrix, and N=the transform length) to produce a premultiplication product, a polynomial transform circuit for performing a polynomial transform (PT) modulo (z^N +1), size N, root z² on the premultiplication product to produce a polynomial transform result, where z represents the unit delay operator, a reduced DFT calculator for performing N reduced DFTs of N terms on the polynomial transform result to produce a permuted output, and an address generator for reordering the permuted output to a natural order.

Claims

1. A method for computing multidimensional discrete Fourier transforms (DFTs) using a field programmable gate array (FPGA) comprising the steps of:

a. ordering a set of polynomial data in a two dimensional matrix;

b. multiplying each element of the two dimensional matrix by ω

^-n.sbsp.2 (where ω

=e^-jπ

/N, e is a constant (ln(e)=1, where In indicates the natural logarithm),

j=√

-1, n₂ =the column index number in the matrix, and

N=the transform length) to produce a premultiplication product;

c. performing a polynomial transform (PT) on the premultiplication product to produce a polynomial transform result;

d. performing N reduced DFTs of N terms on the polynomial transform result to produce a permuted output; and

e. reordering the permuted output to a natural order.

2. A method for computing multidimensional DFTs using an FPGA according to claim 1, wherein the PT recited in step (c) is modulo (z^N +1), size N, root z², where z represents the unit delay operator.

3. A method for computing multidimensional DFTs using an FPGA according to claim 1, wherein steps (a) through (e) are repeated recursively for DFTs that have more than two dimensions.

4. An apparatus for computation of an N×

N discrete Fourier transform (DFT) using polynomial transforms defined in modified rings of transforms, comprising;

a. first buffer means for ordering a set of polynomial data in a two dimensional matrix;

b. first multiplier means for multiplying each element of the two dimensional matrix by ω

^-n.sbsp.2 (where ω

=e^-jπ

/N, e is a constant (ln(e)=1, where ln indicates the natural logarithm), j=√

-1, n₂ =the column index number in the matrix, and N=the transform length) to produce a premultiplication product;

c. PT means for performing a polynomial transform (PT) modulo (z^N +1), size N, root z² on the premultiplication product to produce a polynomial transform result, where z represents the unit delay operator;

d. reduced DFT means for performing N reduced DFTs of N terms on the polynomial transform result to produce a permuted output; and

e. reordering means for reordering the permuted output to a natural order;

wherein the first buffer means, the first multiplier means, the PT means, the reduced DFT means, and the reordering means are embodied in a field programmable gate array (FPGA).

5. An apparatus for computation of an N×

N discrete Fourier transform (DFT) using polynomial transforms defined in modified rings of transforms according to claim 4, wherein the first multiplier means uses an FPGA configured as a radix-2 polynomial transform decimation-in-frequency butterfly.

6. An apparatus for computation of an N×

N discrete Fourier transform (DFT) using polynomial transforms defined in modified rings of transforms according to claim 5, wherein the first multiplier means includes a look-up table external to the FPGA for storing multipliers.

7. An apparatus for computation of an N×

N discrete Fourier transform (DFT) using polynomial transforms defined in modified rings of transforms according to claim 6, wherein the multipliers stored in the look-up table include complex constants sin (π

n₂ /N and cos (π

n₂ /N).

8. An apparatus for computing multidimensional discrete Fourier transforms (DFTs) using a field programmable gate array (FPGA) comprising:

a. means for ordering a set of polynomial data in a multi-dimensional matrix;

b. first multiplier means for multiplying each element of the multi-dimensional matrix by ω

^-n.sbsp.2 (where ω

=e^-jπ

/N, e is a constant (ln(e)=1, where In indicates the natural logarithm), j=√

-1, n₂ =the column index number in the matrix, and N=the transform length) to produce a premultiplication product;

c. PT means for performing a polynomial transform (PT) on the premultiplication product to produce a fast polynomial transform (FPT) result;

d. reduced DFT means for performing N reduced DFTs of N terms on the FPT result to produce a permuted output;

e. reordering means for reordering the permuted output to a natural order.

9. An apparatus for computing multidimensional discrete Fourier transforms (DFTs) using a field programmable gate array (FPGA) according to claim 8, further comprising:

a. a first RAM buffer on an FPGA chip formed as part of the means for ordering;

b. a first latch on the FPGA chip for latching an output of the first RAM buffer;

c. a RAM lookup table as part of the multiplier means for storing as multipliers complex constants sin (π

n₂ /N) and cos (π

n₂ /N);

d. a second latch on the FPGA chip for latching the premultiplication product;

e. a second RAM buffer on the FPGA chip interposed between the PT means and the second latch for temporarily storing the premultiplication product as well as results of intermediate calculations of the PT means;

f. a radix-2 fast polynomial transform means on the FPGA chip as part of the PT means;

g. a third RAM buffer on the FPGA chip interposed between the PT means and the reduced DFT means for temporarily storing the results of intermediate calculations of the PT means and the reduced DFT means;

h. a fourth RAM buffer on the FPGA chip for temporarily storing the permuted output of the reduced DFT means while the reordering means reorders the permuted output to a natural order.

10. An apparatus for computing multidimensional discrete Fourier transforms (DFTs) using a field programmable gate array (FPGA) according to claim 9, further comprising 2log₂ N virtual processors on the FPGA chip, wherein:

a. first through log₂ N virtual processors comprise the PT means and perform FPT butterfly ranks 0, . . . log₂ -1, respectively, wherein each of the first through log₂ N virtual processors implement one polynomial butterfly that is time division multiplexed to compute N/2 polynomial butterflies in a processing rank of the FTP;

b. log₂ N+1 through 2logN virtual processors comprise the reduced DFT means, wherein each of log₂ N+1 through 2logN virtual processors compute one of log₂ N butterfly ranks of an FFT algorithm and is a radix-2 FFT butterfly that is time division multiplexed over the N/2 butterflies in a single processing stage of the FFT.