When implementing the fft, you always include a bit reverse at the end of the process to put the data in the correct order. It seems to be because the fft proceeds by decimating the input array into odd/even sections (for radix-2 algorithms, for other algorithms e.g. prime factor you have to do a radix reverse), the final stage of the algorithm involves multiplications (by several exponential factors) on the individual array members. These can be labelled by a series of EOEEO etc (E = even, O=odd) depending on the process of decimation and whether the subarray was an odd/even decimate. Why does replacing E with 1 and O with 0 result in the bins requiring a final permutation. This has always bothered me about the fft.
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
You might want to look at:
Tran-Thong, “Algebraic Formulation of the Fast Fourier Transform,” IEEE Circuits and Systems magazine, vol. 3, no. 2, June 1981, pp. 9-19.
The author describes 16 'basic' FFT algorithms – 8 Decimation-in-Time and 8 Decimation-in-Frequency, also classified by: input order, output order, and characteristics (or geometry: in-place, same output, same input, or isogeometric). It should be evident that bit reversal is NOT always required at the end (or beginning) of an FFT.
In addition, there are other FFT algorithms which cannot be neatly defined by the scheme above, such as some shown in Chapter 10 of Rabiner and Gold's book: “Theory and Application of Digital Signal Processing,” Englewood Cliffs, NJ, Prentice-Hall, 1975.
Furthermore, it is possible to derive other algorithms which would defy ANY form of simple classification.
And yet, despite the many differences (which strongly affect implementation), there are some simple, basic ideas which can be gleaned from the Tran-Thong paper. For instance, starting with any one of the graphs in that paper, it is easy to show that all the other graphs of the same decimation type can be derived by simple graphical manipulations. Similarly, decimations can be changed by factoring twiddles into common factors (eg: twiddle 3 = twiddle 1 times twiddle 2), and then moving common twiddle factors on input legs of a butterfly to an output (or vice-versa). Likewise, it is easy to see how four connected radix-2 butterflies can be re-drawn as a single radix-4 butterfly (with appropriate output ordering, of course).
The FFT is a very graphic thing. Too often, some authors transmogrify it into something ugly and difficult. It isn't.
One reason typical implementations of a radix-2 FFT require a permutation at the beginning or end is to reduce the use of any temporary memory when using a procedural/sequential processing engine. When using a single complex array, larger than, say, the CPUs register set, for both the input, output and intermediate results, the intermediate butterfly results have to go somewhere in that array. But the place most appropriate for a non-permuted result might still be occupied by unprocessed input data. So you could either use more memory to save the unprocessed inputs somewhere else, use more memory to put the intermediate results somewhere else, or just put the results in an array location where the input data is no longer needed (e.g. the butterfly input locations).
If you allocate a full new array for each FFT radix-2 layer, no post-shuffling will be required. You could also ping-pong 2 arrays, but that's still double the memory.
If you had enough parallel ALU units that no temporary result are required, and the entire FFT result is available at once at the ALU outputs, then you could also write out the FFT result without any permutation.