Take the 2-minute tour ×
Signal Processing Stack Exchange is a question and answer site for practitioners of the art and science of signal, image and video processing. It's 100% free, no registration required.

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.

share|improve this question
3  
This is a programming issue, not a algorithm issue. The FFT computation can be thought of as a serial computation of matrix-vector products $X = A_nA_{n-1}\cdots A_2A_1x$, that is, vector $x$ is replaced by $A_1x$ which is replaced by $A_2(A_1x)$ and so on. If the computation is done in-place, it is convenient to modify the mathematical statement above to say that $x$ is replaced by a permuted version of $A_1x$: the computation is faster and no temporary storage is needed. The net effect of these permutations leads to the final result appearing in radix-reversed order of addresses. –  Dilip Sarwate Nov 7 '12 at 14:26

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer
    
Thanks! That's exactly what I was looking for. –  Tom Kealy Nov 10 '12 at 17:26

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.