Arrayable modular FFT processor
First Claim
1. A modular, arrayable, FFT processor for performing a preselected N-point FFT algorithm, comprising:
- input memory means for receiving and storing data from a plurality of input lines and for storing products and summations;
Direct Fourier Transformation (DFT) means connected to receive data from said input memory means for selectively performing R-pint direct Fourier transformations on said data according to said FFT algorithm, where R is less than eight;
arithmetic logic means connected at a first input with an output of said DFT means for performing multiplications and for accumulating complex data and multiplication products for forming positive and negative summations according to said FFT algorithm and having an output connected to said input memory for storage of intermediate products and summations for the FFT algorithm;
adjusted twiddle factor storage means connected to a second input of said arithmetic logic means for providing phase adjusting twiddle-factor coefficients for implementation of said FFT algorithm, which coefficients are preselected according to a desired size of the Fourier transformation being performed and a relative array position of the arrayable FFT processor in an array of z such processors; and
output means connected to an output of said arithmetic logic means for transferring results of said FFT algorithm to a plurality of output lines.
6 Assignments
0 Petitions
Accused Products
Abstract
A modular, arrayable, FFT processor for performing a preselected N-point FFT algorithms. The processor uses an input memory to receive and store data from a plurality of signal-input lines, and to store intermediate butterfly results. At least one Direct Fourier Transformation (DFT) element selectively performs R-point direct Fourier transformations on the stored data according to a the FFT algorithm. Arithmetic logic elements connected in series with the DFT stage perform required phase adjustment multiplications and accumulate complex data and multiplication products for transformation summations. Accumulated products and summations are transferred to the input memory for storage as intermediate butterfly results, or to an output memory for transfer to a plurality of output lines. At least one adjusted twiddle-factor storage element provides phase adjusting twiddle-factor coefficients for implementation of the FFT algorithm. The coefficients are preselected according to a desired size for the Fourier transformation and a relative array position of the arrayable FFT processor in an array of processors. The adjusted twiddle-factor coefficients are those required to compute all mixed power-of-two, power-of-three, power-of-four, and power-of-six FFTs up to a predetermined maximum-size FFT point value for the array which is equal to or greater than N.
68 Citations
40 Claims
-
1. A modular, arrayable, FFT processor for performing a preselected N-point FFT algorithm, comprising:
-
input memory means for receiving and storing data from a plurality of input lines and for storing products and summations; Direct Fourier Transformation (DFT) means connected to receive data from said input memory means for selectively performing R-pint direct Fourier transformations on said data according to said FFT algorithm, where R is less than eight; arithmetic logic means connected at a first input with an output of said DFT means for performing multiplications and for accumulating complex data and multiplication products for forming positive and negative summations according to said FFT algorithm and having an output connected to said input memory for storage of intermediate products and summations for the FFT algorithm; adjusted twiddle factor storage means connected to a second input of said arithmetic logic means for providing phase adjusting twiddle-factor coefficients for implementation of said FFT algorithm, which coefficients are preselected according to a desired size of the Fourier transformation being performed and a relative array position of the arrayable FFT processor in an array of z such processors; and output means connected to an output of said arithmetic logic means for transferring results of said FFT algorithm to a plurality of output lines. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20)
-
-
21. A programmable, arrayable, signal-processing device useful for computing N-point FFT algorithms in an array of z such devices, with 64 signal-input lines and 64 signal output lines, comprising:
-
an input formatting register connected in series with said signal-input lines being configured for converting received data into a predetermined parallel format; a 64-word plus 64-word ping-pong type input memory connected in series with said input formatting register; Direct Fourier Transformation means connected to receive data from said input memory means for performing 2-point direct Fourier transformations on said data according to said FFT algorithm; a 16-bit by 16 2'"'"'s-bit complement, fully parallel modified Booth multiplier with true rounding connected to receive data from said Direct Fourier Transformation means; a basic 64-point transform twiddle-factor coefficient memory containing coefficient values necessary to compute all power-of-two FFT'"'"'s from an 8-point FFT up to a 64-point FFT; an incremental-twiddle-factor coefficient memory containing coefficients required to incrementally adjust said basic coefficients through multiplication to generate synergist-twiddle-factor coefficients which are necessary to compute all mixed power-of-two FFT up to a maximum T-point size, where T≦
4096;transfer means connected to outputs for both said basic and incremental coefficient memories and an input of said multiplier for transferring coefficients to said multiplier; a complex accumulator connected in series with said multiplier and having an output connected to one of said ping-pong memories for transferring FFT-butterfly computations thereto; a 64-word plus 64-word ping-pong type output memory connected to receive data from said accumulator; an output formatting register configured to selectively format parallel format output data to predetermined serial or parallel formats; and control means connected to each of said input formatting register, input memory, multiplier, basic twiddle-factor storage, adjusted twiddle-factor storage, complex accumulator, transfer means, output memory and output formatting register for providing clock signals thereto for synchronizing their operations and controlling data input/output rates for said processor to interface with other apparatus, and for providing control signals which select desired values for N. - View Dependent Claims (22, 23, 24, 25, 26, 27, 28, 29)
-
-
30. A method of performing a preselected N-point FFT algorithm in an array of z FFT modules performing a T-point FFT, comprising the steps of:
-
receiving and storing data from a plurality of input lines; providing basic twiddle factors for performing mixed power-of-two and power-of-three FFTs up to a maximum value N; adjusting said basic twiddle factors for implementation of all mixed power-of-two and power-of-three FFTs up to a maximum value T using adjusting coefficients; performing preselected R-point direct Fourier transformations on said received data according to said FFT algorithm, where R less then eight; performing multiplications on the results of said direct transformations according to said FFT algorithm in a multiplier; accumulating complex data and multiplication products for forming positive and negative summations according to said FFT algorithm in an accumulator; storing and retrieving intermediate butterfly results for the FFT algorithms; and transferring results of said FFT algorithm to a plurality of output lines. - View Dependent Claims (31, 32, 33, 34, 35, 36, 37, 38, 39, 40)
-
Specification