Undergrad How to understand and visualize the Bufferfly diagram in FFTs

[ADDA]

Hi,

I'm attempting to understand and visualize the Fast Fourier Transform algorithm. Specifically:

https://en.wikipedia.org/wiki/Butterfly_diagram

I've made a few slow FT examples:





I could go to three dimensions, and display a log2(frame_size) series of layers, yet I do not find that appropriate. How does the bit reversal portion of the FFT algorithm actually produce the correct value? I am able to implement an FFT, yet would like to further my understanding of the process.

 

[Baluncore]

Different people view the FFT from different mathematical viewpoints. For what it is worth, here is a very crude non-mathematical generalised view.

1. Each output value can be reached from each input value via the Log(n) layers of n orderly butterflies because the wing-span of the n butterflies changes with each layer. This is a bit like a fast multiply or square, where each input term or digit, must somehow meet every other term or digit.

2. The two outputs of the butterfly have sum and difference terms, where a phase rotation, the complex multiply by sine and cosine terms from the table are applied. It is educational to follow all inputs to all outputs through the rotations and side steps for a trivial 4 input to 4 output transform. The phase rotations wind forward in the forward transform, then unwind backwards in the inverse transform, which explains why +1 or –1 can switch the direction of the transform.

3. The final values will be out of order because the efficient algorithm prefers order, add and subtract, while minimising multiplies and trig table lookups.

4. Bit reverse is a digital trick that performs an inverse interleaved addressing function. Used correctly it maps the scrambled output order inherent in the efficient FFT, into ordered terms. Bitrev can be applied within the transform, but it is usually quicker to apply it only once on exit, since when using the FFT for things like convolution, the order of the frequency components is not important, Bitrev cancels during the inverse transform. With power spectrum accumulation Bitrev only needs to be applied once to the total power as the final process.

 

[ADDA]

I sort of took a tangent in my ideas, and attempted frequency division multiplexing visuals.

addressing function

Are you referring to array indices? I sort of understand the binary log split; that each value is able to split a corresponding lower complexity transform. Maybe I should think in reverse.

There are two algorithms dit and dif (decimation in time, frequency); dit will bit reverse first and multiply in place; dif bit reverses last and needs another vector or array to store data. dit is more efficient. If I were to think about a small case and build up from there; maybe I could properly visualize the fft algortihtm as opposed to the slow ft algorithm. Follow? Baluncore