# A DFT and FFT TUTORIAL

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.

Here is the even value expanded from E:

Here is the odd value expanded from E:

Here is the even value expanded form O:

Here is the odd value expanded from O:
.

And finally:

### Equation 8

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

### 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 >>