Patent ID: 6041340
Filing Date: 2000-03-21
Classification: G06F

Abstract:
A method of configuring a field programmable gate array (FPGA) for carrying out a fast Fourier transform (FFT) computation implemented by a complex multiplication (X+jy)e.sup.-j.theta. which can be expressed as sums of transform partial products, each term having a trigonometric coefficient and sums and differences of real and imaginary input variables X and Y, the FPGA having an array of look-up-tables in respective logic blocks; the method comprising the steps of:a) loading said look-up-tables with the arithmetic sums of said transform partial products;b) applying said input variables to respective parallel-to-serial registers;c) inputting sums and differences of serial register stored input variables as address inputs to the look-up-tables;d) storing real and imaginary outputs of said look-up-tables in respective registers;e) scaling and accumulating said outputs as a stare computational output; andf) repeating steps a) through e) for a plurality of subsequent stages of progressively smaller increments of .theta. and transferring the computational output of each such stare to the next successive stage as the input thereto.