Fourier transforms are one of the fundamental operations in signal processing. In digital computations, Discrete Fourier Transforms (DFT) are used to describe, represent, and analyze discrete-time signals. However, direct implementation of DFT is computationally very inefficient. Of the various available high speed algorithms to compute DFT, the Cooley-Tukey algorithm is the simplest and most commonly used. These efficient algorithms, used to
compute DFTs, are called Fast Fourier Transforms (FFTs).
This application note provides the source code to compute FFTs using a PIC17C42. The theory behind the FFT algorithms is well established and described in literature and hence not described in this application note. A Radix-2 Cooley-Tukey FFT is implemented with
no limits on the length of the FFT. The length is only limited by the amount of available program memory space. All computations are performed using double precision
arithmetic.