Discrete and Fast Fourier Transform
Understanding DFT and FFT algorithms, their formulas, and advantages.
Discrete Fourier Transform (DFT)
For digital systems, the Fourier transform is realized by:
For complex numbers \(x_0, x_1, x_2, \dots, x_{N-1}\):
\(X[k] = \sum_{n=0}^{N-1} x_n W_N^{kn}, \quad k = 0, 1, 2, \dots, N-1\)
Where:
- \(W_N = e^{-j 2 \pi / N}\) is the \(N^{th}\) root of unity.
- \(n\) is the index of the input sample (time-domain index).
- \(k\) is the index of the output frequency bin (frequency-domain index).
- \(W_N^{kn}\) represents the complex rotation corresponding to the contribution of sample \(x_n\) to frequency \(k\).
Fast Fourier Transform (FFT)
The basic idea of a fast Fourier transform is to break up a transform of length \(N\) into two transforms of length \(N/2\).
For complex numbers \(x[n]\), \(n = 0, 1, 2, \dots, N-1\):
\[ X[k] = \sum_{n=0}^{N-1} x[n] W_N^{kn} = \sum_{r=0}^{N/2-1} x[2r] W_N^{k(2r)} + \sum_{r=0}^{N/2-1} x[2r+1] W_N^{k(2r+1)} \]
In the above transform, the length \(N\) is broken into two transforms of length \(N/2\), separating even and odd samples of \(x[n]\).
\[ X[k] = \sum_{r=0}^{N/2-1} x[2r] W_{N/2}^{kr} + W_N^k \sum_{r=0}^{N/2-1} x[2r+1] W_{N/2}^{kr} \]
Advantages of FFT over DFT
To compute the DFT of an N-point sequence, it takes \(O(N^2)\) multiplies and adds. The FFT algorithm computes the DFT using \(O(N \log N)\) multiplies and adds.
The fast Fourier transform (FFT) is a discrete Fourier transform algorithm which reduces the number of computations needed for \(N\) points from \(2N^2\) to \(2N \log_2 N\).