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

## FFTC1: One-Dimensional Complex Fourier Transforms

Whether you prove them to yourself or take my word for them the formulas given above should be enough for you to follow what the routine fftc1 does. The first section takes an array of points and rearranges them into bit-reversed order. This is done by noting that if you know the bit-reversal of a binary number it is easy to find the bit-reversal of the number . To add to you start at the right and replace every with a until you reach the first , which you replace with a . So to go from to you do the bit-reverse of this process, starting at the left and replacing every with a until you reach the first , which you replace with a .

The next part of the routine implements the DL formula on successively larger blocks, beginning with combining transforms into transforms. Each time the routine calculates a transform of size the first elements represent and the next half represent . These are then used to calculate and . Note that in the DL formula , , and , so the only difference between the formulas for and is the sign of . Finally, the inner loop over the variable iterates over all the transforms of size in the entire array, so if you are transforming an array of data you first have to calculate  transforms, then  transforms, and so on.

Note that the formulas for the real and imaginary parts of are nothing but and . They could have simply been calculated directly but for the sake of efficiency they are calculated instead using a recursion formula each time is incremented. This formula can be verified simply using the addition rules for sines and cosines.

Note that the end result of this process is a transform with the results in sequential order from to , which by the periodicity of is exactly the storage scheme described in section 2.3.2.

The reverse transform is exactly identical except the sign of the exponential is reversed and the final output is divided by .

The argument is used in case the elements of the input array are not sequential but evenly spaced in some larger array. To do a one-dimensional transform you would almost always want to set to one, but this option allows fftc1 to be used by fftcn, which does transforms of multi-dimensional arrays. For all but the last array index the one-dimensional transforms used by fftcn are not of sequential data.   Next: FFTCN: Multi-Dimensional Complex Fourier Up: How FFTEASY works Previous: How FFTEASY works