Chris Lomont's C# FFT - How does it work

Question

Chris Lomont was kind enough to provide us with a neat FFT implementation using C#. The source can be found here. The RealFFT(double[] data, bool forward) function is half way down, just read the function summary (it's short :)).

I am using the RealFFT function which, as stated (function summary), accepts an array of samples all of which are real valued (no imaginary component). However, it also states that The output is complex valued after the first two entries, stored in alternating real and imaginary parts.

I can't seem to get this straight. After doing FFT you always get real and imaginary component. So how can they be packed in the array that got into function as argument (which is half the size because only real numbers)?

Answer 1

From Wikipedia:

For purely real inputs, X(k) = X(N-k)*; therefore you only need to give half the components (the other half are basically the same, but their complex conjugate).

So it is efficient not to compute and store them; if you really need these values, you use the above formula to compute them on the fly.

That this is true is hinted at by the statement (in the comments of the code you linked to above):

// The first two returned entries are the real                                     
// parts of the first and last value from the conjugate symmetric                                       
// output, which are necessarily real. The length must be a power                                       
// of 2.                     

Answer 2

The LomontFFT.RealFFT(double[] data, bool forward) works this way:

• forward == true: the data are real input and complex output (FT coefficients).
• forward == false i.e. the inverse FFT: the data are complex input (FT coefficients) and real output.

I agree the documentation is a bit confusing.