DFT and FFT: the Fourier transform on a computer
Definition of the DFT, resolution and leakage, windows, the FFT algorithm with the butterfly and its cost, fast convolution, OFDM, compression and radar.
The Fourier transform of the Mathematical Methods lesson is an integral over a continuous, infinite signal. On a computer you have 
samples instead. The discrete Fourier transform (DFT) is the version for sampled signals, and the FFT (Fast Fourier Transform) is the algorithm that computes it efficiently. Introduced in its modern form by Cooley and Tukey in 1965, it is considered one of the most important algorithms of the twentieth century: it is in every digital oscilloscope, in Wi-Fi, 4G and 5G, in MP3 and JPEG compression, in radar.
The DFT
Given samples 
, taken at sampling frequency 
, the DFT is
![\[ X_k = \sum_{n=0}^{N-1}x_n\,e^{-2\pi i\,kn/N},\qquad k = 0, 1, \dots, N - 1 \]](https://www.electronics-engineering.com/wp-content/ql-cache/quicklatex.com-ef54ed75e73cbd6808048499764edd7a_l3.png "Rendered by QuickLaTeX.com")
and the inverse transform
![\[ x_n = \frac1N\sum_{k=0}^{N-1}X_k\,e^{2\pi i\,kn/N} \]](https://www.electronics-engineering.com/wp-content/ql-cache/quicklatex.com-3bf57ea528dda71f864307e7612fdbc0_l3.png "Rendered by QuickLaTeX.com")
The coefficient 
measures how much the signal looks like a sinusoid completing 
periods within the window of samples, that is at frequency 
. The frequency resolution is 
: telling two close frequencies apart needs long windows.
Two properties worth remembering.
- For a real signal
: the second half of the spectrum mirrors the first, and the useful frequencies run from 0 to 
(the Nyquist frequency). It is the same phenomenon as aliasing. - The DFT treats the signal as if it were periodic with period . If the window does not hold a whole number of periods, the start and end do not join up and the spectrum “spreads” over nearby bins (spectral leakage). It is reduced by multiplying the signal by a window that falls smoothly to zero at the edges (Hann, Hamming, Blackman): the “window” option of spectrum analysers and oscilloscopes.
The cost and the idea of the FFT
Computed directly, the DFT needs sums of terms: 
complex multiplications. With 
that is 
operations.
The FFT exploits the structure of the exponentials. With even, split the even- and odd-indexed samples:
![\[ X_k = \sum_{m=0}^{N/2-1}x_{2m}\,e^{-2\pi i\,km/(N/2)} + e^{-2\pi i\,k/N}\sum_{m=0}^{N/2-1}x_{2m+1}\,e^{-2\pi i\,km/(N/2)} = E_k + W^k\,O_k \]](https://www.electronics-engineering.com/wp-content/ql-cache/quicklatex.com-aa5006f9a093564b879eace99cd69fea_l3.png "Rendered by QuickLaTeX.com")
and 
are the DFTs, of length 
, of the even and odd samples, and 
. Moreover, since 
and 
have period and 
:
![\[ X_k = E_k + W^kO_k,\qquad X_{k + N/2} = E_k - W^kO_k \]](https://www.electronics-engineering.com/wp-content/ql-cache/quicklatex.com-4bf63bf7ca3c0dc24ff6eed8d89a2bb9_l3.png "Rendered by QuickLaTeX.com")
One multiplication gives two coefficients (the “butterfly”). A DFT of length becomes two DFTs of length plus multiplications; repeating down to length 1, with 
there are 
levels. The total cost is
![\[ \frac N2\log_2 N \]](https://www.electronics-engineering.com/wp-content/ql-cache/quicklatex.com-5fd73e860f02c75672059f47e480f632_l3.png "Rendered by QuickLaTeX.com")
multiplications. With (about 
): about 
instead of , a hundred thousand times fewer. It is the difference between a calculation of a few milliseconds and one of hours.
Fast convolution
Convolving two sequences of length directly costs operations. With the convolution theorem (lesson on the Fourier transform), take the FFT of both, multiply the spectra and take the inverse FFT: a cost proportional to 
. This is how very long FIR filters are applied, how reverb effects are derived from an impulse response, and how huge integers are multiplied.
Applications
- Spectrum analysis. The FFT function of digital oscilloscopes shows the harmonics of a signal: an amplifier’s distortion or 50/60 Hz mains interference is visible at once.
- OFDM. Wi-Fi, 4G, 5G and digital TV transmit data on hundreds or thousands of orthogonal subcarriers. The transmitter builds the signal with an inverse FFT, the receiver splits it with an FFT. Without a fast algorithm these techniques could not be done in a phone.
- Compression. MP3 and AAC work on a related transform (the MDCT) and discard the components the ear cannot hear; JPEG uses the discrete cosine transform on 8×8 pixel blocks.
- Radar and sonar. The range and speed of targets are found from the frequencies in the received signal, computed with the FFT: this is how 77 GHz automotive radars work.
Zero padding and resolution
Appending zeros to the samples before the FFT (zero padding) makes the spectrum denser and nicer to look at, but it does not increase the resolution: two frequencies closer than , with the number of real samples, remain indistinguishable. Separating them needs a longer observation window. It is the same time-frequency uncertainty principle seen for the continuous transform.
