Modular Pipeline Fast Fourier Transform

Technology #2003-185

Questions about this technology? Ask a Technology Manager

Download Printable PDF

Categories
Researchers
Barry K. Gilbert Ph.D.
Erik S. Daniel Ph.D.
Managed By
Bruce R. Kline
Patent Protection
US Patent Pending

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 (