In a previous post, we have explained the importance of the convolution operation for signal processing and signal analysis. We have described the convolution integral and illustrated the involved functions.

In this post we will focus on an operation called *Circular convolution* which is strongly related to the conventional convolution (also called *linear convolution*) we have described before. Let us reconsider the normal, *linear convolution* in the discrete domain. Given two sequences $x[n]$ and $h[n]$, their convolution is given by

The linear convolution lets one one sequence slide over the other and sums the overlapping parts. The circular convolution of two sequences $x[n], h[n]$ is now considering a wrap-around of the sequences after a period of N samples. So, the circular convolution is defined by

$$(x\otimes h)[n]=\sum_{n'=0}^{N-1}x[n']\cdot h[(n'-n)_N], \quad n=0,\dots,N-1,$$where $(n'-n)_N$ gives the remainder of $n'-n$ divided by $N$. For example, $(-1)_N=N-1$. This means, if the index for $x[(n'-n)_N]$ would leave the range $0,\dots,N-1$ to the left, it would wrap around and come in from the right again. This means that the circular convolution is periodic with length $N$.

In discrete domain, the convolution theorem actually holds only for the circular convolution: Let $X[k]$ and $H[k]$ be the N-point DFT of $x[n]$ and $h[n]$. Then the convolution theorem in discrete domain states

$$X[k]H[k]=\text{DFT}_N\{x[n]\otimes h[n]\}.$$However, we can emulate a linear convolution by performing an appropriate zero-padding to both sequences and perform longer DFTs.

Let us now try to describe the circular convolution in pictures. First, we generate some random signal that we use to demonstrate the convolution.

```
N = 128 # the sequence length
# Generate some random sequence we use for the convolution
x = abs(N*np.fft.ifft(np.random.randn(5)+1j*np.random.randn(5), N))
# use some exponential sequence for the second function
h = np.exp(-0.1*np.arange(N))
plt.plot(x, label='$x[n]$');
plt.plot(h, label='$h[n]$');
```

Let us now perform the circular convolution according to the formula of the convolution sum:

```
def showCircularConvolution(n0):
n = np.arange(N)
plt.subplot(211)
plt.plot(n, x[n], label='$x[n]$')
plt.plot(n, h[(n0-n)%N], label='$h[(n_0-n)_N]$')
plt.plot(n, x[n] * h[(n0-n)%N], label=r'$x[n]\cdot h[(n_0-n)_N]$')
plt.subplot(212)
hx = np.fft.ifft(np.fft.fft(x[n]) * np.fft.fft(h[n])) # use convolution theorem
plt.plot(n, abs(hx[n]))
current = sum(x[np] * h[(n0-np) % N] for np in n) # direct calculation for the convolution
plt.plot(n0, current, 'ro')
```

```
```

- The circular convolution is defined on
time-limited sequencesof length $N$.- The circular convolution is
periodic with period $N$.- In the circular convolution, the
shifted sequence wraps aroundthe summation window, when it would leave the region.- In the
finite discrete domain, theconvolution theoremholds for thecircular convolution, not for the linear convolution. Linear convolution can be obtained by appropriate zero-padding of the sequences.

Do you have questions or comments? Let's dicuss below!