Zero-Padding for DFT-based Linear Convolution

Hello! Welcome to our next lesson.

In our previous session, we established a crucial theoretical link: while multiplying DFTs results in circular convolution, we can force this operation to yield a linear convolution result. The key, as we discovered, is to prevent time-domain aliasing by zero-padding the signals to a sufficient length, specifically $N \geq L + M - 1$ , where $L$ and $M$ are the lengths of our input signals.

Today, we transition from theory to application. Your learning outcome is to apply zero-padding to compute linear convolution using the DFT/FFT. We will formalize the procedure that allows us to leverage the computational efficiency of the Fast Fourier Transform (FFT) to perform linear convolution, a method widely known as "fast convolution." This technique is a cornerstone of efficient digital filtering and system simulation in practice.

1. The "Fast Convolution" Algorithm

The convolution theorem for the DTFT, $y [n] = x [n] * h [n] \leftrightarrow Y (e^{j ω}) = X (e^{j ω}) H (e^{j ω})$ , is elegant but not directly computable, as $e^{j ω}$ is a continuous variable. The DFT provides a computational tool to perform a similar operation. By using the zero-padding strategy we derived, we can create a step-by-step algorithm to compute linear convolution using the DFT.

The following resource provides a concise summary of this procedure.

Discrete Fourier Transform (DFT)

This document outlines the practical steps for performing linear filtering (convolution) using the DFT. It directly addresses our learning goal for today.

Please read the section titled '3.6 Linear filtering through DFT (FFT)' on page 13 of the PDF. Focus on the step-by-step method described. Note the assumptions made about the signal lengths (P and M in the document correspond to our L and M).

Based on this resource and our previous discussion, we can formalize the algorithm as follows:

Let's say we want to compute the linear convolution $y [n] = x [n] * h [n]$ , where $x [n]$ has length $L$ and $h [n]$ has length $M$ .

Determine Output Length: Calculate the length of the linear convolution result, which is $N_{o u t} = L + M - 1$ .
Choose DFT Size (N): Select a DFT size $N$ such that $N \geq N_{o u t}$ . For computational efficiency, $N$ is almost always chosen to be the next power of 2 greater than or equal to $N_{o u t}$ . This allows the use of highly optimized Radix-2 FFT algorithms.
Zero-Pad Signals: Create two new sequences, $x_{p} [n]$ and $h_{p} [n]$ , by appending zeros to $x [n]$ and $h [n]$ so that they both have length $N$ .
- $x_{p} [n] = {x [0], x [1], ..., x [L - 1], 0, 0, ..., 0}$
- $h_{p} [n] = {h [0], h [1], ..., h [M - 1], 0, 0, ..., 0}$
Compute DFTs: Compute the N-point DFTs of the padded sequences, typically using an FFT algorithm.
- $X_{p} [k] = FFT (x_{p} [n])$
- $H_{p} [k] = FFT (h_{p} [n])$
Multiply in Frequency Domain: Multiply the two DFTs element by element.
- $Y_{p} [k] = X_{p} [k] \cdot H_{p} [k]$
Compute Inverse DFT: Compute the N-point Inverse DFT of the product, again using an efficient IFFT (Inverse FFT) algorithm.
- $y_{p} [n] = IFFT (Y_{p} [k])$
Extract Result: The resulting sequence $y_{p} [n]$ of length $N$ contains the linear convolution. The first $L + M - 1$ samples of $y_{p} [n]$ are the desired output $y [n]$ . The remaining $N - (L + M - 1)$ samples will be approximately zero.

2. The Role of Zero-Padding: A Deeper Look

You now know the procedure and the fundamental reason it works: padding to $N \geq L + M - 1$ provides enough "space" to prevent the time-aliasing inherent in circular convolution from corrupting the result.

However, zero-padding has another interpretation that's very insightful, especially from a signal processing perspective. What effect does appending zeros in the time domain have on the frequency domain representation?

Fourier transform frequencies and zero-padding

This video from Mike X Cohen explains the effect of zero-padding on the Fourier transform. It introduces a crucial concept: zero-padding increases frequency resolution, which is key to why our fast convolution method works.

Please watch from 30:12 to 38:35. Pay close attention to these three points: The definition of zero-padding (30:12 - 32:01). The visual effect in the frequency domain: the spectrum becomes 'smoother' because the DFT is computed at more frequency points (32:01 - 37:32). The speaker correctly identifies this as sinc interpolation. The third motivation for zero-padding given at 37:32, which is precisely our topic today: matching lengths for convolution.

As the video explains, padding a time-domain signal with zeros and taking a longer DFT is equivalent to evaluating the signal's underlying DTFT at a finer grid of frequencies. It doesn't add new information to the signal (the precision is unchanged), but it increases the resolution of our spectral view.

When we perform fast convolution, we are essentially doing the following:

By padding $x [n]$ and $h [n]$ to length $N$ , we are finely sampling their respective DTFTs, $X (e^{j ω})$ and $H (e^{j ω})$ , at the frequencies $ω_{k} = \frac{2 π k}{N}$ .
The multiplication $X_{p} [k] H_{p} [k]$ gives us $N$ samples of the product spectrum $Y (e^{j ω}) = X (e^{j ω}) H (e^{j ω})$ .
Because we took a sufficient number of samples ( $N \geq L + M - 1$ ), the IFFT can perfectly reconstruct the time-domain signal $y [n]$ from these frequency samples without time-aliasing. This is a direct application of the concepts we discussed when deriving the DFT from sampling the DTFT.

Test your understanding!

Let's apply this procedure to the signals from our last lesson:
$x [n] = {1, 2}$ for $n = 0, 1$ (so $L = 2$ )
$h [n] = {2, 1, 3}$ for $n = 0, 1, 2$ (so $M = 3$ )

Your task is to outline the steps to compute their linear convolution using the fast convolution method. You don't need to compute the actual DFT values, just describe the process and the dimensions of the signals at each stage.

What is the length of the linear convolution output?
What is a suitable power-of-2 choice for the DFT size, $N$ ?
Write out the zero-padded sequences $x_{p} [n]$ and $h_{p} [n]$ using your chosen $N$ .
After performing the FFTs, multiplication, and IFFT, what will be the length of the final output sequence $y_{p} [n]$ ? How many of its samples constitute the actual linear convolution result?

Show answer

Output Length: The linear convolution result will have length $L + M - 1 = 2 + 3 - 1 = 4$ .
DFT Size: We need $N \geq 4$ . The smallest power of 2 that satisfies this is $N = 4$ . However, to better illustrate the "extra" zeros in the final output, let's choose the next power of 2, which is $N = 8$ . (In practice, both are valid choices, with $N = 4$ being slightly more efficient).
Zero-Padded Sequences (for N=8):
- $x_{p} [n] = {1, 2, 0, 0, 0, 0, 0, 0}$
- $h_{p} [n] = {2, 1, 3, 0, 0, 0, 0, 0}$
Final Output: The IFFT will produce a sequence $y_{p} [n]$ of length $N = 8$ . The first $L + M - 1 = 4$ samples will be the non-zero linear convolution result. The remaining $8 - 4 = 4$ samples will be zero (or numerically very close to it). For reference, the linear convolution is ${2, 5, 5, 6}$ , so we would expect $y_{p} [n] \approx {2, 5, 5, 6, 0, 0, 0, 0}$ .

Conclusion

Today, you have translated the theoretical requirement of zero-padding into a concrete, practical algorithm for computing linear convolution. This "fast convolution" method is not just an academic exercise; it is fundamental to the performance of countless real-world DSP applications, from audio processing to communications and image filtering. Its efficiency gain over direct convolution is so substantial that it enables filtering operations that would be computationally prohibitive otherwise.

Key Takeaways:

Linear convolution of sequences with lengths $L$ and $M$ can be computed via the DFT/FFT.
The required procedure involves choosing a transform length $N \geq L + M - 1$ , zero-padding both signals to length $N$ , performing the FFT, multiplying the spectra, and performing an IFFT.
The choice of $N$ as a power of 2 is not for correctness but for computational efficiency by enabling Radix-2 FFT algorithms.
Zero-padding in the time domain corresponds to finer sampling (interpolation) in the frequency domain, providing enough spectral points to reconstruct the full linear convolution result without time-domain aliasing.

Preview of the Next Lesson:

We have repeatedly mentioned the efficiency of the "Fast Fourier Transform" as the motivation for this entire procedure. But what exactly is the FFT, and why is it so much faster than the direct computation of the DFT? In our next lesson, we will finally pull back the curtain and derive the decimation-in-time (DIT) FFT algorithm and analyze its computational complexity compared to the direct DFT. You will see how a clever decomposition of the DFT calculation dramatically reduces the number of required operations.

Recommended resources

1. The "Fast Convolution" Algorithm

2. The Role of Zero-Padding: A Deeper Look

Conclusion