What is the circular convolution and how does it differ from the linear convolution?

### The Convolution Series

- Definition of convolution and intuition behind it
- Mathematical properties of convolution
- Convolution property of Fourier, Laplace, and z-transforms
- Identity element of the convolution
- Star notation of the convolution
**Circular vs. linear convolution**- Fast convolution
- Convolution vs. correlation
- Convolution in MATLAB, NumPy, and SciPy
- Deconvolution: Inverse convolution
- Convolution in probability: Sum of independent random variables

## Table of Contents

- Introduction
- Convolution Theorem of the DFT?
- Circular Convolution Example
- Why Is the Convolution Circular?
- Circular vs. Linear Convolution
- Periodic Convolution
- Valid Samples of Circular Convolution: The Answer
- Circular Convolution Implementation
- Summary
- Bibliography

## Introduction

Circular convolution is a term that arises in discussions about the discrete Fourier transform (DFT) and fast convolution algorithms. What is it and how does it differ from the linear convolution?

Before we answer that question we need to (somewhat surprisingly) examine the DFT more closely.

## Convolution Theorem of the DFT?

### Definition of the DFT

Let us recap the definition of the discrete Fourier transform of a finite, discrete-time signal

### Convolution Theorem of the Fourier Transform

In one of the previous articles we argued that for the continuous-time Fourier transform it holds that

i.e., the Fourier transform of a convolution equals the multiplication of the Fourier transforms of the convolved signals. A similar property holds for the Laplace and z-transforms. However, **it does not**, in general, hold for the discrete Fourier transform. Instead, multiplication of discrete Fourier transforms corresponds to the *circular convolution* of the corresponding time-domain signals [1].

### Convolution Theorem of the DFT

In mathematical terms, given two finite, discrete-time signals

the multiplication of their DFTs corresponds to their circular convolution in the time domain

### Circular Convolution Definition

Here,

where

Since both signals are of length *N-point circular convolution*.

### Linear Convolution Definition

The name “circular” distinguishes it from the *linear convolution*, as we introduced it in the previous articles

Note the absence of the modulo operation. Although we do not prove it here, **circular convolution is commutative**, exactly like the linear convolution.

## Circular Convolution Example

Let’s look at a comparison between a linear and a circular convolution.

Let’s assume we have a signal

*Figure 1. $x[n]$.*

and a discrete-time impulse delayed by 1 sample

*Figure 2. $h[n]$.*

The linear convolution between the two delays

*Figure 3. Linear convolution between $x[n]$ and $h[n]$.*

However, the circular convolution performs a **circular shift** of the signal

*Figure 4. Circular convolution between $x[n]$ and $h[n]$.*

Circular shift means that whichever samples “fall off” one end reappear at the other end of the signal vector. In other words, the excessive samples “wrap around” the signal buffer.

## Why Is the Convolution Circular?

The convolution property of the DFT results directly from the periodicity of the DFT.

The periodicity itself can be explained in at least two ways:

- From the relation of the DFT to the discrete Fourier series (DFS).
- From the sampling of the discrete-time Fourier transform around the unit circle on the z-plane.

### Discrete Fourier Transform and Discrete Fourier Series

Discrete Fourier series is a representation of a **periodic** discrete signal

where

Equation 9 is identical to Equation 1, i.e, the definition of the DFT, with the exception that the signal under the sum is periodic (denoted by the tilde) and

The same holds for the DFT coefficients

Unfortunately, the fact that **implicit**. It means we can state it but we cannot enforce it. Since the DFT uses directly the formulas of the DFS, the DFT will behave as if the signal

#### DFT Periodicity Example

Let’s say we have a signal

*Figure 5. $x[n]$.*

You may think it is defined as follows

*Figure 6. $x[n]$ as we wish it to be.*

but the DFS (and the DFT accordingly) treat it as

*Figure 7. $x[n]$ as seen by discrete Fourier series and the discrete Fourier transform.*

Analogously, in the discrete frequency domain, we can obtain the magnitude Fourier coefficients

*Figure 8. Magnitude discrete-frequency coefficients of $x[n]$.*

Again, one may assume that it is defined as follows

*Figure 9. Magnitude DFT of $x[n]$ naively visualized with zeros surrounding the 4 nonzero coefficients.*

but the inherent periodicity of the DFT results in

*Figure 10. True magnitude DFT of $x[n]$.*

### Sampling of the Fourier transform

All of the above observations are confirmed when one treats the DFT as a sampled version of the band-limited discrete-time Fourier transform (DTFT). Discrete-time Fourier transform is the z-transform evaluated on the unit circle [2]. The DFT samples the DTFT at points fixed by the sampling rate. Since we sample around a circle, after

### Aliasing in the Time Domain

Having established that the DFT is periodic, we can now explain the circular convolution phenomenon. I like to think of it as **aliasing in the time domain**.

*Note: We have discussed the notion of aliasing in the frequency domain in one of the previous articles.*

#### Output Length of Discrete Convolution

Let’s recall our signal

How does it look when we go through the DFT domain?

#### Multiplication in the DFT domain

Adopting the notation from Equations 3 and 4, let’s denote by

In order to make the index

#### Back to the time domain

We now want to find signal

We can achieve it via inverse discrete Fourier transform (iDFT)

If

Inverse DFT inherently assumes that the time domain signal is of the same length as the frequency-domain coefficient vector. Thus,

In mathematical terms,

#### An Important Conclusion

We have seen that the circular convolution somehow distorts the linear convolution. But in our example, **fast convolution** algorithms, which will be discussed in one of the following articles.

## Circular vs. Linear Convolution

The conclusion from the previous section is that

**A subset of the circular convolution result corresponds to the linear convolution result.**

The question is: which subset?

### Example: Common Samples of Linear and Circular Convolution

Figures 11 and 12 present the linear and circular convolution example, respectively, with marked matching samples. They match in terms of indices and amplitude.

*Figure 11. Linear convolution result. Samples marked in red would also be correctly calculated by the circular convolution.*

*Figure 12. Circular convolution result. Samples marked in red correspond to the linear convolution result in terms of index and amplitude.*

To understand fully which samples in the circular convolution correspond to the correct samples of the linear convolution we need to look at a concept broader than circular convolution: periodic convolution.

## Periodic Convolution

Circular convolution is an example of *periodic convolution*–a convolution of two periodic sample sequences (with the same period) evaluated over only one period [1]. It’s formula is identical to the formula of the circular convolution (Equation 6), but we assume that its output is periodic. “But in our case

Let’s compare the linear convolution and the periodic convolution. Given signals

*Figure 13. Signal $\tilde{x}$: periodic version of $x$.*

*Figure 14. Signal*$\tilde{h}$ : periodic version of $h$ .

Let’s compare the linear convolution of the original

*Figure 15. Linear convolution of $x$ and $h$. Its length is 5.*

with the periodic convolution of their periodic counterparts

*Figure 16. Periodic convolution of $\tilde{x}$ and $\tilde{h}$. Its length is 4 and it’s periodic.*

We can observe that the circular convolution is a superposition of the linear convolution shifted by 4 samples, i.e., 1 sample less than the linear convolution’s length. That is why the last sample is “eaten up”; it wraps around and is added to the initial 0 sample.

Once again:

## Valid Samples of Circular Convolution: The Answer

Let’s summarize what we have discovered so far:

- Multiplication in the DFT domain is equivalent to circular convolution in the discrete-time domain.
$N$ -point DFT treats the signals as$N$ -periodic.- Linear convolution of discrete signals of length
$M$ and$N$ has length$M+N-1$ . $N$ -point circular convolution has length$N$ .

Let’s assume that we have two signals, of length

- First, we pad the shorter signal with zeros. Now both signals have length
$M$ . - The result of the circular convolution has length
$M$ . - The samples that did not fit the linear convolution wrapped around and were added to the beginning of the output. The exact number of wrapped-around samples is
$M + N - 1 - M = N - 1.$ - The above means that the first
$N-1$ samples of the output need to be discarded. This means that the last$M - N + 1$ samples are valid, i.e., samples at indices$\{N, N+1, \dots, M-1\}$ (we start indexing from 0).

## Circular Convolution Implementation

A straightforward implementation of the circular convolution, as presented in Equation 6, is rather brute-force

```
import numpy as np
def periodic_convolution_naive(x, h):
assert x.shape == h.shape, 'Inputs to periodic convolution '\
'must be of the same period, i.e., shape.'
N = x.shape[0]
output = np.zeros_like(x)
for n in range(N):
for m in range(N):
output[n] += x[m] * h[(n - m) % N]
return output
```

This implementation has time complexity

However, the convolution property of the DFT, as presented in Equation 5, suggests a much more efficient implementation

```
import numpy as np
def periodic_convolution_fast(x, h):
assert x.shape == h.shape, 'Inputs to periodic convolution '\
'must be of the same period, i.e., shape.'
X = np.fft.fft(x)
H = np.fft.fft(h)
return np.real(np.fft.ifft(np.multiply(X, H)))
```

The complexity of the “fast” implementation is determined by the complexity of the forward and inverse DFT as implemented in the `numpy.fft`

module, which is

Equal shapes checked in the assertion can be ensured by padding the shorter signal with zeros.

The efficient circular convolution implementation via the Fast Fourier Transform (FFT) will serve as a basis when we will discuss fast linear convolution implementations.

## Summary

In this article, we looked at the difference between the circular and the linear convolution. The former treats both given sequences as periodic and is evaluated only for the number of samples corresponding to the period.

A subset of samples resulting from the circular convolution corresponds to the samples of the linear convolution.

Circular convolution can be implemented efficiently via multiplication in the DFT domain.

## Bibliography

[1] Alan V Oppenheim, Ronald W. Schafer *Discrete-Time Signal Processing*, 3rd Edition, Pearson 2010.

[2] Alan V. Oppenheim, Alan S. Willsky, with S. Hamid *Signals and Systems*, 2nd Edition, Pearson 1997.

[3] Frank Wefers *Partitioned convolution algorithms for real-time auralization*, PhD Thesis, Zugl.: Aachen, Techn. Hochsch., 2015.

Comments powered by Talkyard.