Appendix C. FFT Code Implementation

When programming the FFT in the C language, a couple “tricks” can make the process much more simple.

First, C does not have a “built in” complex data type, so an array of N complex numbers will actually be a 2*N floating point array. With the real and imaginary parts of the complex number in interleaved elements in the floating point array. The table below shows the way we access the various parts of the complex numbers that are represented by the floating point array.

In other words, real ( C[k] ) = f[2*k] and imag( C[k] ) = f[2*k+1].

Also, when we multiply two complex numbers, we have to work all the parts. As an example we will consider the case of two numbers, reC + j imC and cw + j sw. This is similar to what will be in the example c code, where

[latex]cw = cos( \frac{2 \pi}{N} ) " and " cs = sin( \frac{2 \pi}{N} )[/latex]

The product of these would look like

( reC + j imC ) * ( cw + j sw ) = ( reC * cw – imC * sw ) + j (reC * sw + imC * cw )

Finally it can be expensive to call cos and sin, thus we want to minimize these calls. So to step our basis function we will be using the following.

[latex]e^{-j \frac{2 \pi} {N} (k+1) } = e^{-j \frac{2 \pi} {N} k } * e^{-j \frac{2 \pi} {N} }[/latex]

Thus moving from k to k+1 only requires a single complex multiply. Also when we move from N length to N/2 length transforms we can avoid the function calls again by noting that

[latex](e^{-j \frac{2 \pi} {N} })^2 = e^{-j \frac{2 \pi} {N} 2 } = e^{-j \frac{2 \pi} {\frac{N}{2}} }[/latex]

Thus by squaring the term used in the previous stepping process, we would have the term needed for the next level of butterfly’s.  All of these “tricks” will come into play in the following code that implements the FFT.

This first set of code contains support functions that implement the butterflies used in the FFT, and does a bit reversal of the data, correcting for all the frequency decimation that occurs.

Figure 6.5 Code of Support Functions

Next is the code that will use the previous functions to implement the FFT.  Note that an inverse FFT is done, by changing the terms cs and ss, to be the conjugates of the FFT implementation and including a loop to divide by 1/N.

Figure 6.6 Code Implementing the FFT and Inverse FFT.

Any software functions that are written should be tested at least to a basic functional level.  For this purpose the following code, that calls the FFT and IFFT functions, was written and executed.  The program generates a signal that has a cosine and a sine wave, which is done to demonstrate the response of the FFT to these fundamental coponents.

Figure 6.7 Code Implementing the FFT and Inverse FFT.

The results from the program are include here as a table of results and later as a plot.

As noted in the printout of the results, the FT has distinct points that match up with the frequencies of the generated signal.  The second part of the output from the program was a filtered version of the input.  The numbers for the filtered signal can’t be interpreted that easily, and would make more sense as a plot.

Figure C.1 Filtered Output Showing Only the Sine Wave at Pi/4.

The final test, although far from extensive, was intended to show that the FFT code was effective and functional.