Fundamentals of Digital Signal Processing/

...

/

Circular Convolution

Circular Convolution

Learn about the difference between linear and circular convolution and its importance in the context of the DFT.

We'll cover the following...

When a complex sinusoid is given as an input to an LTI system, the output should be the same complex sinusoid scaled by the magnitude response of the system and phase-shifted by the phase response. This did not happen. Why?

DFT periodicity

Recall that sampling a signal in the time domain gives rise to spectral aliases in the frequency domain. Similarly, when we sample the spectrum in the frequency domain, time-domain aliases arise that actually make the signal periodic. This is why simple convolution, in which the output length is larger than both signals, cannot generate the correct answer.

Consider the process of convolution with a periodic signal as shown in the figure below. As soon as the one period ends, there is a short duration during which the convolving sequence overlaps with both the original signal and its copy in the time domain. These are the points a linear convolution cannot replicate.

Press + to interact
Periodic convolution
Periodic convolution

For this purpose, circular convolution is devised in a simple manner. It is very much like the linear convolution, except that the signal flipping and time shifting occur in a circular fashion. Therefore, circular convolution is the same as the periodic convolution shown above.

Example

Let’s go back to the same example. Only now, we perform the circular convolution instead of linear convolution and check the results.

Press + to interact
import numpy as np
import matplotlib.pyplot as pl
figWidth = 20
figHeight = 10
# Generating the signal
fs = 120 # sample rate
Ts = 1/fs # sample time
f = 30
T = 0.1
A = 1
phi = -20*np.pi/180
t = np.arange(0, T, Ts)
x = A*np.exp(1j*(2*np.pi*f*t + phi)) 
h = np.array([1, -3, 1, 2, -1])
n = x.shape[0]
y = np.convolve(np.tile(x, 2), h)[n:2*n] # circular convolution through repeating twice and selecting
# Plotting the signal
fig, axs = pl.subplots(2, figsize=(figWidth, figHeight))
nfft = n
xf = np.fft.fft(y,nfft) # from 0 to 2pi
xf = np.fft.fftshift(xf) # from -pi to pi
k = np.arange(-nfft/2,nfft/2,1)
axs[0].vlines(k, ymin=np.abs(xf), ymax=0, color='b', linewidth=2)
axs[0].plot(k, np.abs(xf), 'o', color='b', markersize=16, zorder=10, clip_on=False)
phase = np.angle(xf)*180/np.pi
phase[0:9]=0 # removing random phases from numerical imprecisions
phase[10:]=0
axs[1].vlines(k, ymin=phase, ymax=0, color='b', linewidth=2)
axs[1].plot(k, phase, 'o', color='b', markersize=16, zorder=10, clip_on=False)
for ax in axs:
  ax.axhline(y=0, color='k', linewidth=1)
  ax.axvline(x=0, color='k', linewidth=1)
  ax.set_xlim(min(k),max(k)+1)
  ax.set_xticks(np.arange(min(k),max(k)+1,1))
  ax.set_xlabel('$k$', fontsize=18)
  ax.grid()
axs[0].set_ylim(0, 71)
axs[0].set_yticks(np.arange(0, 71, 10))
axs[1].set_ylim(-60, 121)
axs[1].set_yticks(np.arange(-60, 121, 30))
axs[0].set_ylabel("$|Y[k]|$", fontsize=18)
axs[1].set_ylabel("$\measuredangle Y[k]$", fontsize=18)
axs[0].tick_params(labelsize=18)
axs[1].tick_params(labelsize=18)
fig.tight_layout()
pl.savefig('output/circular-convolution-output.png', bbox_inches='tight')

It’s clear from the code above that the output y[n]y[n] has the magnitude and phase values as:

∣Y[3]∣≈60∡Y[3]≈80∘\begin{align*} |Y[3]|&\approx 60\\ \measuredangle Y[3]&\approx 80^\circ \end{align*} ...