Zero Padding and its Effect on the Discrete Fourier Transform

May 24, 2024 · Luciano Muratore

Expanding on our exploration of the Discrete Fourier Transform (DFT), we now examine Zero Padding, a common technique used to improve the visual resolution of a signal’s spectrum and facilitate longer DFT computations without altering the original signal’s content.

Zero Padding: Definition and Intuition

Zero Padding is the process of extending a finite-length discrete-time sequence by appending zeros to the end of the original samples.

Given an original sequence $x[n]$ of length $N$: $x[n] = \begin{cases} \text{original samples}, & 0 \le n \le N-1 \\ 0, & \text{otherwise} \end{cases}$

A zero-padded sequence $x_z[n]$ of length $M$ (where $M > N$) is defined as: $x_z[n] = \begin{cases} x[n], & 0 \le n < N \\ 0, & N \le n < M \end{cases}$

Key Insights:

• The signal contains only $N$ meaningful samples.
• Zero padding does not modify $x[n]$ or introduce new information.
• It simply embeds $x[n]$ into a longer sequence to enable a longer DFT.

Effect on the Spectrum

Zero padding changes the sampling grid of the DFT, which has significant visual and computational implications.

• Standard DFT (Length $N$): The sampling grid is $f_k = \frac{k}{N}$, with a spacing of $\Delta f_N = \frac{1}{N}$.
• Zero-Padded DFT (Length $M$): The sampling grid becomes $f_k = \frac{k}{M}$, with a narrower spacing of $\Delta f_M = \frac{1}{M} < \Delta f_N$.

The Core Result

Zero padding increases the number of frequency samples, which interpolates the spectrum. This results in a smoother and more detailed spectral plot, making peaks easier to locate. However, it is vital to note that:

• The true spectral resolution (the ability to distinguish two close frequencies) remains the same.
• Only the visual resolution improves.
• It does not create new frequencies.

DFT Computation via Matrices

The standard $N$-point DFT is represented as $X = W_N x$, where $W_N$ is the $N \times N$ DFT matrix with elements: $[W_N]_{k,n} = e^{-j2\pi kn/N}$

The full matrix structure for $W_N$ is: $W_N = \begin{bmatrix} 1 & 1 & \dots & 1 \\ \vdots & \vdots & \ddots & \vdots \\ 1 & e^{-j2\pi(N-1)/N} & \dots & e^{-j2\pi(N-1)^2/N} \end{bmatrix}$

Computing Zero-Padded DFTs

When computing the DFT for a zero-padded sequence of length $M > N$, the transform $X^{(M)}$ can be computed directly using a modified matrix: $X^{(M)} = W'_M x$

In this case, $W'_M$ consists only of the first $N$ columns of the full $M \times M$ DFT matrix. This allows the computation of the interpolated spectrum directly from the $N$ original signal samples.