Accession Number : ADD013067

Title :   Pipelined FFT Processor.

Descriptive Note : Patent, Filed 10 May 82, patented 6 Aug 85,

Corporate Author : DEPARTMENT OF THE NAVY WASHINGTON DC

Personal Author(s) : McGee,Kevin J

Report Date : 06 Aug 1985

Pagination or Media Count : 7

Abstract : A pipelined Fast Fourier Transform (FFT) processor is described for processing continuous sets of N samples in a highly efficient manner. Within a single set of N inputs, the samples arrive in pairs (sample 0, and 1, 2 and 3, 4 and 5, etc). This input sequence can be obtained from a sequential stream of inputs (sample 0 followed by samples 1, 2, 3, 4, etc.) by delaying the even numbered sample by one time unit. Alternately, the device could be made to operate on sequential samples within a set of N samples by internal pipelining of the arithmetic units. The device achieves high arithmetic unit efficiency while minimizing the memory required by allowing each arithmetic unit in the pipeline, with the exception of the last, to operate on the even or odd numbered samples first, after which it will operate on the remaining samples, which have been appropriately delayed and switched through shift registers and switches. The structure of the device, through its novel arrangement of shift registers and switches, allows an internal reordering of the data such that 100 percent arithmetic unit efficiency can be obtained, while requiring by 2(N-1)-(N/2) memory locations.

Descriptors :   *PATENTS, *ARITHMETIC UNITS, *FAST FOURIER TRANSFORMS, *SAMPLING, EFFICIENCY, HIGH RATE, MEMORY DEVICES, POSITION(LOCATION), PROCESSING, SEQUENCES, STREAMS, INPUT, SHIFT REGISTERS

Subject Categories : Computer Systems

Distribution Statement : APPROVED FOR PUBLIC RELEASE