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

Expansion of the Danielson-Lanczos to Four Terms

<< Previous Next >>

For N = 4 samples, the equation must be expanded again to four terms. Below is the expansion to four terms. As with the first level expansion, substitute 2k into k and reduce the summation by half for the even terms and substitute 2k+1 into k and reduce the summation by half for the odd terms. The E and O below refer to equation 5.

DL Lemma 4 Term Expansion part 1

Here is the even value expanded from E:

DL Lemma EE

 

Here is the odd value expanded from E:

DL Lemma EO

 

Here is the even value expanded form O:

DL Lemma OE

 

Here is the odd value expanded from O:
.

DL Lemma OO

And finally:

DL Lemma 4 Terms Final Solution

Equation 8

Now, N = 4 samples, and using the same procedure as was used for two samples, equation 8 becomes:

DL Lemma for 4 Input Values

Equation 9

Once again, as with N=2, the summations have been reduced to unity, and all you have remaining are "twiddle factors" and the input values, x(0), x(1), x(2), and x(3).

The next example will be an 8 term expansion, shown but not worked through.

<< Previous Next >>