 FFT reduces its multiplications by utilizing the symmetry and periodicity
of twiddle factors. So I will show you how they are symmetry and periodic
and why FFT is constructed like "butterfly" by using vector images.
The following Fig.1 is the process of DFT(Discrete Fourier Transform) that
is origin of FFT. The twiddle factor of each frequency spins having its
own step. I will show you how the pattern of angle is similar, e.g. how
5kHz is similar to 1kHz.
 |
| Fig.1 8-point DFT and twiddle factors |
I wrote some PDFs to see the FFT taking the patterns of angle into account.
| (0) for 1, 3, 5 and 7kHz |
- 5kHz has similar angles to 1kHz.
- 3kHz and 7kHz are a bit different from 1kHz, so need some compensation.
|
| (1) for 0, 2, 4 and 6kHz |
- 4kHz has similar angles to 0kHz.
- 2kHz and 6kHz are a bit different from 0kHz, so need some compensation.
|
|