Circular Convolution: DFT and Distinction from Linear Convolution

Hello! Let's dive into our next lesson on the properties of the Discrete Fourier Transform.

In our previous lessons, we've often used the convolution theorem in the context of the DTFT, where multiplication of continuous spectra corresponds to linear convolution in the time domain. A natural and important question arises: what happens when we multiply two Discrete Fourier Transforms? As you know, the DFT operates on finite-length signals, which introduces some unique behaviors.

The answer is that multiplication of two N-point DFTs does not correspond to linear convolution, but to a related operation called circular convolution. Understanding this distinction is fundamental to correctly applying the DFT and FFT for filtering and system analysis.

Today, your learning outcome is to: Derive the concept of circular convolution from the DFT multiplication property and distinguish it from linear convolution.

We will first derive this property mathematically, then build an intuition for what it means physically, and finally, establish the precise conditions under which it can be made equivalent to the linear convolution you're already familiar with.

1. The Convolution Property of the DFT

Let's consider two finite-length sequences, $x [n]$ and $h [n]$ , both of length $N$ . Their N-point DFTs are $X [k]$ and $H [k]$ . We define a new sequence in the frequency domain, $Y [k]$ , by multiplying them:

$Y [k] = H [k] X [k]$

Our goal is to find the time-domain sequence, $y [n]$ , which is the Inverse DFT (IDFT) of $Y [k]$ . We start with the IDFT formula:

$y [n] = \frac{1}{N} \sum_{k = 0}^{N - 1} Y [k] e^{j \frac{2 π k n}{N}} = \frac{1}{N} \sum_{k = 0}^{N - 1} H [k] X [k] e^{j \frac{2 π k n}{N}}$

To solve this, we will substitute the DFT definitions for $H [k]$ and $X [k]$ and rearrange the summations. The following resource provides a concise and elegant derivation.

Lecture 24: Cicular Convolution

This set of lecture slides from the University of Illinois provides a clear, step-by-step derivation of the circular convolution property. It's a perfect example of the direct mathematical treatment you appreciate.

Please focus on the slide titled 'Circular convolution' (it should be slide 11 in the PDF). Follow the derivation that begins with the IDFT of Y[k] and, by substituting the DFT for X[k] and rearranging the sums, arrives at the final expression for y[n].

As the derivation shows, the resulting time-domain operation is not linear convolution. Instead, we get:

$y [n] = \sum_{m = 0}^{N - 1} x [m] h [((n - m))_{N}]$

This operation is called N-point circular convolution. The notation $((n - m))_{N}$ denotes the modulo N operation. It's this modulo on the time index that fundamentally distinguishes it from linear convolution. We often denote circular convolution with a special symbol, such as an N in a circle: $y [n] = x [n] ⊛_{N} h [n]$ .

2. What is Circular Convolution? The "Wrap-Around" Effect

The modulo operator in the circular convolution formula, $h [((n - m))_{N}]$ , means that as the index $n - m$ becomes negative or exceeds $N - 1$ , it "wraps around." You can visualize this as if the sequence $h [n]$ were plotted on a clock face or a cylinder of circumference $N$ . When you shift it past the beginning, the end wraps around to the start, and vice-versa.

But why does this happen? In the last module, we saw that sampling a signal in one domain (e.g., time) causes its transform to become periodic in the other domain (frequency). Duality applies here: the DFT samples the DTFT spectrum at discrete frequency points. This sampling in the frequency domain implies that the corresponding time-domain signal is periodic. The DFT implicitly treats finite-length signals as one period of an infinitely repeating sequence. Circular convolution is simply linear convolution of these periodic extensions.

Introduction to Circular Convolution and Filtering with the DFT

To build a strong intuition for this, let's watch a segment from a video by Prof. Barry Van Veen. It connects the act of sampling in frequency (the DFT) to the resulting periodicity in time, which is the root cause of circular convolution.

Watch from 2:51 to 5:02. The key idea here is that sampling the DTFT to get the DFT causes replications of the time-domain signal. The convolution operates on this replicated signal, leading to the 'wrap-around' effect.

This "wrap-around" is also known more formally as time aliasing. Just as sampling below the Nyquist rate in the time domain causes aliasing in the frequency spectrum, performing an N-point circular convolution can be viewed as performing a linear convolution and then having the result alias in the time domain.

Circular Convolution

These notes from an MIT OCW course formalize the connection between linear and circular convolution using the concept of time aliasing.

Read the section 'Circular Convolution as Linear Convolution with Aliasing' (starts on page 2). Focus on the equation that shows the circular convolution result, w[n], as an infinite sum of shifted versions of the linear convolution result, y[n]. This equation perfectly captures the 'wrap-around' or 'time-aliasing' effect.

3. Distinguishing Circular from Linear Convolution

Let's explicitly summarize the differences:

Property	Linear Convolution: $y_{L} [n] = x [n] * h [n]$	N-point Circular Convolution: $y_{C} [n] = x [n] ⊛_{N} h [n]$
Formula	$\sum_{m = - \infty}^{\infty} x [m] h [n - m]$	$\sum_{m = 0}^{N - 1} x [m] h [((n - m))_{N}]$
Indexing	Standard linear index $n - m$ .	Circular (modulo-N) index $((n - m))_{N}$ .
Input Support	Assumes signals are zero outside their defined length.	Implicitly treats inputs as periodic with period $N$ .
Output Length	If `x[n]` has length $L$ and `h[n]` has length $M$ , the output has length $L + M - 1$ .	If inputs are length $N$ , the output is also length $N$ . Wrap-around corrupts the result.
Transform Domain	Multiplication of DTFTs: $Y_{L} (e^{j ω}) = X (e^{j ω}) H (e^{j ω})$	Multiplication of DFTs: $Y_{C} [k] = X [k] H [k]$

Test your understanding!

Consider two sequences:
$x [n] = {1, 2, 0}$ for $n = 0, 1, 2$ . (Length $L = 3$ )
$h [n] = {2, 1}$ for $n = 0, 1$ . (Length $M = 2$ )

Calculate their linear convolution, $y_{L} [n] = x [n] * h [n]$ . What is its length?
Calculate their 3-point circular convolution, $y_{C} [n] = x [n] ⊛_{3} h [n]$ . (Assume $h [n]$ is padded with one zero to make it length 3, i.e., $h = {2, 1, 0}$ ).

Show answer

Linear Convolution:
$y_{L} [0] = x [0] h [0] = 1 \cdot 2 = 2$
$y_{L} [1] = x [0] h [1] + x [1] h [0] = 1 \cdot 1 + 2 \cdot 2 = 5$
$y_{L} [2] = x [1] h [1] + x [2] h [0] = 2 \cdot 1 + 0 \cdot 2 = 2$
$y_{L} [3] = x [2] h [1] = 0 \cdot 1 = 0$
The result is $y_{L} [n] = {2, 5, 2, 0}$ . Its length is $L + M - 1 = 3 + 2 - 1 = 4$ .
3-point Circular Convolution:
The formula is $y_{C} [n] = \sum_{m = 0}^{2} x [m] h [((n - m))_{3}]$ . Let's calculate for each $n$ :
- $y_{C} [0] = x [0] h [0] + x [1] h [(- 1)_{3}] + x [2] h [(- 2)_{3}] = x [0] h [0] + x [1] h [2] + x [2] h [1]$
  $= 1 \cdot 2 + 2 \cdot 0 + 0 \cdot 1 = 2$
- $y_{C} [1] = x [0] h [1] + x [1] h [0] + x [2] h [(- 1)_{3}] = x [0] h [1] + x [1] h [0] + x [2] h [2]$
  $= 1 \cdot 1 + 2 \cdot 2 + 0 \cdot 0 = 5$
- $y_{C} [2] = x [0] h [2] + x [1] h [1] + x [2] h [0]$
  $= 1 \cdot 0 + 2 \cdot 1 + 0 \cdot 2 = 2$
  The result is $y_{C} [n] = {2, 5, 2}$ . Notice how the linear result ${2, 5, 2, 0}$ was effectively "wrapped" and aliased, but in this case, since the last value was 0, it didn't change the values. If the inputs had been different, we would see corruption. For example, the y_L[3] term would have been added to y_L[0].

4. From Circular to Linear: The Power of Zero-Padding

The DFT multiplication property is computationally very attractive, especially when the Fast Fourier Transform (FFT) algorithm is used. How can we use this efficient process to compute the linear convolution that is so often required in LTI system analysis?

The key is to prevent time aliasing. The problem arises because the output of a linear convolution is longer ( $L + M - 1$ ) than the DFT length ( $N$ ) we are using, causing the "tail" of the result to wrap around and add to the "head".

The solution is simple: we must choose a DFT length $N$ that is large enough to hold the entire linear convolution result without any part of it wrapping around.

The condition is: $N \geq L + M - 1$

If we take our two signals of length $L$ and $M$ , pad both of them with zeros until they are both of length $N$ (where $N$ satisfies the condition above), then compute their N-point DFTs, multiply them, and take the N-point IDFT, the result will be identical to their linear convolution. The wrap-around still happens formally, but it only affects the zero-padded region, leaving the actual result uncorrupted.

Introduction to Circular Convolution and Filtering with the DFT

Let's return to Prof. Van Veen's video, as he explains this crucial final step: using zero-padding to make circular convolution produce a linear convolution result.

Watch from 5:02 to 10:08. This section clearly explains why the output of a linear convolution has length L+M-1 and how choosing a DFT length N greater than or equal to this value prevents overlap, making the two convolution types equivalent.

This technique is the foundation of "fast convolution," where the computationally efficient FFT algorithm is used to perform linear convolution on long signals.

Conclusion

In this lesson, we have unraveled a critical and nuanced property of the Discrete Fourier Transform. You have seen how the finite, discrete nature of the DFT leads to a unique type of convolution.

Key Takeaways:

Multiplication of two N-point DFTs in the frequency domain corresponds to N-point circular convolution in the time domain.
Circular convolution is defined by a modulo operation on its time indices, which causes a "wrap-around" or "time-aliasing" effect.
This behavior arises because the DFT implicitly treats time-domain signals as periodic.
Linear convolution, which corresponds to DTFT multiplication, has an output length of $L + M - 1$ . Circular convolution's output has length $N$ .
We can compute linear convolution using the DFT by zero-padding the input signals to a length $N \geq L + M - 1$ before transforming them.

Preview of the Next Lesson:

Now that we understand the theory, our next step is to put it into practice. We will focus on the practical application of this knowledge and apply zero-padding to compute linear convolution using the DFT/FFT. This will set the stage for understanding how efficient filtering is performed in real-world digital signal processing systems.

Recommended resources

1. The Convolution Property of the DFT

2. What is Circular Convolution? The "Wrap-Around" Effect

3. Distinguishing Circular from Linear Convolution

4. From Circular to Linear: The Power of Zero-Padding

Conclusion