The FFT computes the DFT efficiently by using two properties of the twiddle factor \(W_N = e^{-j2\pi/N}\), symmetry and periodicity; the transform it produces also has the standard DFT properties such as linearity, periodicity, shifting, conjugate symmetry, convolution and Parseval's theorem.
Twiddle-factor properties (basis of the FFT)
- Periodicity: \(W_N^{k+N} = W_N^{k}\).
- Symmetry: \(W_N^{k+N/2} = -W_N^{k}\).
- Also \(W_N^{2} = W_{N/2}\), which allows an \(N\)-point DFT to be split into two \(N/2\)-point DFTs (even and odd samples in DIT; first and second halves in DIF).
Result: the radix-2 FFT needs about \(\frac{N}{2}\log_2N\) complex multiplications and \(N\log_2N\) additions instead of \(N^2\) multiplications for the direct DFT. For \(N = 1024\): about 5,120 versus 1,048,576 multiplications. The FFT is computed in \(\log_2 N\) stages of butterflies, in place, with bit-reversed input (DIT) or output (DIF).
Properties of the DFT/FFT (for \(x(n) \leftrightarrow X(k)\), length \(N\)):
- Linearity: \(a x_1(n) + b x_2(n) \leftrightarrow aX_1(k) + bX_2(k)\).
- Periodicity: \(X(k + N) = X(k)\).
- Circular time shift: \(x((n-m))_N \leftrightarrow W_N^{km}X(k)\) (only the phase changes).
- Circular frequency shift: \(W_N^{-ln}x(n) \leftrightarrow X((k-l))_N\).
- Conjugate symmetry for real \(x(n)\): \(X(N-k) = X^*(k)\), so only about half the coefficients need to be stored.
- Circular convolution: \(x_1(n) \circledast x_2(n) \leftrightarrow X_1(k)X_2(k)\); used for fast filtering.
- Parseval's theorem: \(\sum |x(n)|^2 = \frac{1}{N}\sum |X(k)|^2\).
For 2-D images, the DFT is also separable (a 2-D FFT = 1-D FFTs on rows, then on columns), and rotating the image rotates its spectrum by the same angle.