Next: FFTRN: Multi-Dimensional Real Fourier Up: How FFTEASY works Previous: FFTCN: Multi-Dimensional Complex Fourier

## FFTR1: One-Dimensional Real Fourier Transforms

The trick to doing a DFT of real data is to once again use the DL formula. Specifically the routine begins by taking the original array and passing it as is to fftc1. Of course fftc1 treats the data as an array of complex numbers. Note, however, that the real parts of those numbers are the elements of and the imaginary parts are the elements of , so it is possible to extract the actual DFT of from the results of fftc1. Let represent the output of fftc1 and let represent the desired output, i.e. the transform of the real function . The input we gave to fftc1 was the combination so by the linearity of Fourier transforms we know that . From the DL formula we also know that . How can we extract and from in order to plug them into the DL formula? The answer lies in the symmetry relation obeyed by the Fourier transforms of real data (which includes and ), . So

 (11)

 (12)

and thus
 (13)

 (14)

Plugging these equations into the DL formula gives
 (15)

Now all that's left is to figure out where all of these terms are stored in the array. Remember that all the array indices in these formulas are complex. In the case of finding the elements is trivial because only non-negative values of are given as output so the elements are stored in order . (The case is treated separately below.) Recall, however, that is the transform of a complex size array, so its elements range from to in the wrap-around storage order described in section 2.3.2. In other words the value of is stored in the location . So
 (16)

Plugging in for in this equation and noting that gives
 (17)

Using these two equations the program steps over all the elements of the array overwriting and with and . The cases and are a little different, however, because and are both real. The function fftr1 places in the first (real) slot of the element of the array and in the second (imaginary) slot. From the formulas above, noting that by periodicity, we see that
 (18)

 (19)

Inverting this process seems like a mess but actually works out to be nearly identical. I won't reproduce all the algebra here but if you invert the formulas above to find from you will find that except for a couple of minus signs and a factor of two for the and terms the results look identical to the forward case. As a result the inverse transform simply uses the same loop to rearrange the array and then calls fftc1 to do an inverse transform and get the function back.

Next: FFTRN: Multi-Dimensional Real Fourier Up: How FFTEASY works Previous: FFTCN: Multi-Dimensional Complex Fourier