Appendix C: Efficient Hardware Implementations of FFT Engines
Mitra Nasserbakht · 2001
Efficient algorithms for computing the discrete fourier transform (DFT) have enabled widespread access to Fourier analysis in numerous fields. These application areas span diverse disciplines such as applied mechanics and structural modeling to biomedical engineering. In the signal-processing arena, Fourier theory has been widely used for signal recognition, estimation, and spectral analysis. Fourier analysis has been at the core of many communication system subblocks, such as those used for echo cancellation, filtering, coding, and compression. The ability to compute DFT in realtime and with minimal hardware is the key to the successful implementation of many of these complex systems. The fast fourier transform (FFT) is an efficient algorithm for computing the DFT of time-domain signals. The focus of this chapter is on the necessary ingredients for the design of FFT processing engines capable of handling data of a real-time nature found in most digital signal processing and telecommunications applications. This appendix starts with a brief overview of the FFT and its computation. Top-level system requirements, addressing, arithmetic processing, memory subsystem, and data ordering are discussed. A section is devoted to a discussion of implementation issues for a representative FFT processing engine.