Discrete Fourier Transform

Introduction

The Discrete Fourier Transform (DFT) is the computational workhorse of signal processing. While the continuous Fourier transform and the DTFT are mathematically elegant, they cannot be computed directly on a digital computer because they involve either continuous-time signals or infinite-length sequences. The DFT solves this problem by operating on a finite-length sequence of $N$ samples and producing a finite-length sequence of $N$ frequency values. It is what you actually compute when you perform spectral analysis on real data.

Every spectrum analyzer app, every audio equalizer display, every MRI reconstruction, and every OFDM communication system uses the DFT (implemented efficiently as the FFT). For B.Tech students, the DFT is where theory meets practice.

Definition

For a finite-length sequence $x[n]$ of $N$ samples, the DFT is defined as:

$$X[k] = \sum_{n=0}^{N-1} x[n] \cdot e^{-j2\pi kn/N} = \sum_{n=0}^{N-1} x[n] W_N^{kn}$$

where $W_N = e^{-j2\pi/N}$ is the $N$th root of unity (twiddle factor), and $k = 0, 1, \ldots, N-1$.

The Inverse DFT (IDFT):

$$x[n] = \frac{1}{N}\sum_{k=0}^{N-1} X[k] \cdot e^{j2\pi kn/N} = \frac{1}{N}\sum_{k=0}^{N-1} X[k] W_N^{-kn}$$

The DFT and IDFT form a transform pair — no information is lost. The $N$ time samples contain exactly the same information as the $N$ frequency samples.

Interpretation

Each DFT coefficient $X[k]$ represents the content of the signal at frequency:

$$f_k = \frac{k \cdot f_s}{N} \text{ Hz}, \quad \omega_k = \frac{2\pi k}{N} \text{ rad/sample}$$

where $f_s$ is the sampling frequency.

• $X[0]$: DC component (sum of all samples)
• $X[1]$ through $X[N/2-1]$: positive frequencies
• $X[N/2]$: Nyquist frequency (for even $N$)
• $X[N/2+1]$ through $X[N-1]$: negative frequencies (aliased positive frequencies)

Frequency resolution: $\Delta f = f_s/N$. To improve resolution, increase $N$ (use more samples or zero-pad).

Key Properties

Linearity

$$\alpha x_1[n] + \beta x_2[n] \xleftrightarrow{DFT} \alpha X_1[k] + \beta X_2[k]$$

Circular Time Shift

$$x[(n-m)_N] \xleftrightarrow{DFT} X[k] \cdot W_N^{km}$$

Note: The DFT assumes periodicity — shifting is circular (wraps around).

Circular Frequency Shift

$$x[n] \cdot W_N^{-ln} \xleftrightarrow{DFT} X[(k-l)_N]$$

Circular Convolution Theorem

$$x_1[n] \circledast x_2[n] \xleftrightarrow{DFT} X_1[k] \cdot X_2[k]$$

Multiplication in the frequency domain corresponds to circular convolution in time (not linear convolution!). This distinction is critical.

Parseval's Theorem

$$\sum_{n=0}^{N-1}|x[n]|^2 = \frac{1}{N}\sum_{k=0}^{N-1}|X[k]|^2$$

Circular vs Linear Convolution

The DFT computes circular convolution, but we usually want linear convolution for filtering. To use the DFT for linear convolution of sequences of length $L$ and $M$:

1. Zero-pad both sequences to length $N \geq L + M - 1$
2. Compute DFTs of both padded sequences
3. Multiply the DFTs: $Y[k] = X_1[k] \cdot X_2[k]$
4. Compute IDFT: $y[n] = \text{IDFT}\{Y[k]\}$

The result equals the linear convolution (no circular aliasing) because the zero-padding prevents wrap-around overlap.

Relationship to Other Transforms

• DTFT: The DFT samples the DTFT at $N$ equally spaced points: $X[k] = X(e^{j\omega})|_{\omega = 2\pi k/N}$
• Fourier Series: The DFT coefficients are the Fourier series coefficients of the periodically extended sequence
• z-Transform: The DFT samples the z-transform on the unit circle: $X[k] = X(z)|_{z = e^{j2\pi k/N}}$

Zero-Padding and Interpolation

Appending zeros to a sequence before taking the DFT interpolates its DTFT — it gives a finer-grained view of the spectrum. However, zero-padding does NOT improve actual frequency resolution (it doesn't add information). It just makes the spectral display smoother.

True resolution improvement requires more actual data samples (longer observation time).

Spectral Leakage and Windowing

When the signal frequency doesn't coincide with a DFT bin frequency, energy "leaks" into neighboring bins. This spectral leakage is caused by the implicit rectangular windowing. Solutions:

• Apply a smooth window (Hamming, Hanning, Blackman) before the DFT
• Windows reduce leakage at the cost of wider main lobe (reduced resolution)

Worked Example

Problem: Compute the 4-point DFT of $x[n] = \{1, 2, 3, 4\}$.

$$X[0] = 1 + 2 + 3 + 4 = 10$$ $$X[1] = 1 + 2e^{-j\pi/2} + 3e^{-j\pi} + 4e^{-j3\pi/2} = 1 - 2j - 3 + 4j = -2 + 2j$$ $$X[2] = 1 + 2e^{-j\pi} + 3e^{-j2\pi} + 4e^{-j3\pi} = 1 - 2 + 3 - 4 = -2$$ $$X[3] = 1 + 2e^{-j3\pi/2} + 3e^{-j3\pi} + 4e^{-j9\pi/2} = 1 + 2j - 3 - 4j = -2 - 2j$$

Result: $X = \{10, -2+2j, -2, -2-2j\}$

Verify Parseval's: $|x|^2 = 1+4+9+16 = 30$. $\frac{1}{4}|X|^2 = \frac{1}{4}(100+8+4+8) = 30$ ✓

Key Takeaways

• The DFT transforms $N$ time samples into $N$ frequency samples — fully invertible
• Frequency resolution is $f_s/N$ — more samples or lower sample rate gives finer resolution
• The DFT assumes circular (periodic) structure — circular convolution, not linear
• For linear convolution via DFT: zero-pad to length $\geq L+M-1$
• Zero-padding interpolates the spectrum but doesn't improve true resolution
• Windowing reduces spectral leakage at the cost of broader main lobe
• The FFT algorithm computes the DFT efficiently in $O(N\log N)$ operations