Notes › ENGR 2341: Signals and Systems Lecture 17

Discrete Fourier Transform and Fast Fourier Transform

calendar_today March 27, 2025 article 363 words access_time 2 min replay Modified March 30, 2025

Table of Contents

DFT

Takes $x[n]$ and returns the corresponding $X[k]$, where $X[k]$ is the discrete spectrum with complex amplitudes corresponding to the discrete frequencies
Numerical method for computing DTFT over a finite number of samples

$$X[k] = X\left(e^{j\hat{\omega_{k}}}\right) = \sum_{n=0}^{N-1}x[n]e^{-\hat{\omega_{k}}n}, \hat{\omega_{k}} = 2\pi k / N$$$$X[k] = \sum_{n=0}^{N-1}x[n]e^{-j(2\pi k / N)n}, k=0, \dots, N-1$$

Frequency resolution ($\Delta \hat{\omega} = \frac{2\pi}{N}$) is proportional to $N$
First half are the complex amplitudes for $\hat{\omega_{k}} \gt 0$ and the second half are the complex amplitudes for $\hat{\omega_{k}} \lt 0$

Inverse DFT

Inverse DFT:

$$x[n] = \frac{1}{N}\sum_{k=0}^{N-1}X[k]e^{j(2 \pi k / N)n}, n \in [0, N-1]$$

Computing using DFT:

$$x[n] = \frac{1}{N}\left(\sum_{k=0}^{N-1}X^*[k]e^{-j(2 \pi k / N)n}\right)^*, n \in [0, N-1]$$

FFT

Faster way to compute DFT
Cooley-Turkey algorithm breaks an N-point DFT into smaller DFTs
DFT requires $N^2$ complex multiplications and $N^2 - N$ complex additions to compute $X[k]$ for $x[n]$
FFT requires $N\log_2(N) - N$ complex multiplications and $N\log_2(N)$ complex additions additions to compute $X[k]$ assuming $N$ is an integer power of 2

MATLAB FFT

Use fft function will pad the signal with zeros or truncate the signal to match the number of points $N$
The result is interpreted as follows:
- The frequency resolution is $2\pi / N$
- $X[k]$ is complex amplitude for $\hat{\omega}$
- The amplitudes are scaled by $1 / N$ to match the two-sided spectrum

Frequency Resolution for FFT

The waveform resolution of continuous-time frequencies is $\Delta R = 1 / T$ where T is the duration of the captured signal without padding
The FFT resolution in terms of continuous-time frequency is $\Delta R = f_s / N$
When choosing FFT size:
- The waveform resolution needs to be smaller than the minimum distance between two frequencies
- FFT resolution should be at least the waveform resolution
- The frequencies of interest should not be split among several FFT points
Zero padding can be used to make the signal length a power of 2 for better computation

Uses of FFT

Spectrum of discrete-time signals

$$X[k] = FFT(x[n])$$

Frequency response of discrete-time signals

$$H[k] = FFT(h[n])$$

System response

$$y[n] = FFT^{-1}(Y[k]) = FFT^{-1}(FFT(h[n]) \cdot FFT(x[n]))$$

Sinusoidal System Response

References

Sources

Dft and fft

Graph

mindmap ↗