AlwaysLearn

A DFT and FFT TUTORIAL

A DFT is a "Discrete Fourier Transform". An FFT is a "Fast Fourier Transform". An FFT is a DFT, but is much faster for calculations. The whole point of the FFT is speed in calculating a DFT.

DFT and FFT

FFT

Danielson-Lanczos Lemma Observations

<< Previous Next >>

Note two things about the equations 7, 9 and 11, repeated below. First, the order of input values, x(n), is "reverse binary".For example, left to right the order for the 4 term equation is x(0), x(2), x(1) and x(3). The order for the 8 term equation is x(0), x(4), x(2), x(6), x(1), x(5), x(3), and x(7). This naturally happens when the D-L Lemma is expanded. The Butterfly Diagram makes use of this fact. The second thing to note is that the "twiddled factors",W, build up with each new expansion, so that you multiply more together. The Butterfly diagram also deals with this by the adding of "stages", which you will see later in this tutorial.

DL Lemma for 2 Inputs

Equation 7

 

DL Lemma for 4 Input Values

Equation 9

 

DL Lemma for 8 Input Values

Equation 11

 

More on the "Reverse Binary" pattern.

Here are two examples of the "reverse binary" example:

For 4 inputs:

Count from 0 to 3 in binary 00, 01, 10, 11. Now, reverse the bits of each number and you get 00, 10, 01, 11. In decimal this is 0, 2, 1, and 3.

So, the values in the D-L equation would be x(0), x(2), x(1), and x(3). This is what you see in equation 9 above.

For 8 inputs:

Count from 0 to 7 in binary 000, 001, 010, 011, 100, 101, 110, 111. Now, reverse the bits of each number and you get 000, 100, 010, 110, 001, 101, 011, 111. In decimal this sequence is 0, 4, 2, 6, 1, 5, 3, and 7.

So, the values in the D-L equation for 8 samples would be x(0), x(4), x(2), x(6), x(1), x(5), x(3), and x(7). This is what you see in equation 11 above.

The same pattern holds for all expansions of the D-L Lemma, and is made use of by the Butterfly Diagram.

Next I'll discuss the "twiddle factor" and then put it together with the Danielson-Lanczos Lemma to create the Butterfly diagram, which is the FFT in diagram form.

<< Previous Next >>