Modular Pipeline Fast Fourier Transform

Reference #:

2003-185

Inventors/Contributors

Barry K. Gilbert, Ph.D., Erik S. Daniel

Description

The invention describes a new algorithm and hardware architecture to compute the fast Fourier transform (FFT). The new algorithm uses a divide and conquer approach to reduce an N point FFT to a plurality of sqrt(N) point FFTs arranged in a pipeline configuration. A new specialized center element joins identical, conventional pipeline FFT units together and provides the necessary control logic and data storage to compute the FFT. In the new pipeline architecture, the total bits of delay within each pipeline module is substantially reduced. The reduction of delay elements in each module also reduces the number of bit transitions and subsequently the power. In a conventional system, the power is proportional to sqrt(N). The new algorithm can reduce power in existing FFTs and permit the computation of long FFTs. The algorithm is suited to both custom and programmable logic. The new center element is composed of data memory, coefficient memory, and address generation logic. Key Characteristics: Reduced pipeline delay (< 20 microseconds in 0.25 micron CMOS). Lower power (< 2.6 W in 0.25 micron CMOS). New architecture reducing design time. Technology Status: Firm - Version 1 architecture proven in 0.25 micron CMOS.

Patent Status

Pending