Let us take two finite duration sequences x₁(n) and x₂(n), having integer length as N. Their DFTs are X₁(K) and X₂(K) respectively, which is shown below −

$$X_1(K) = sum_{n = 0}^{N-1}x_1(n)e^{frac{j2Pi kn}{N}}quad k = 0,1,2…N-1$$
$$X_2(K) = sum_{n = 0}^{N-1}x_2(n)e^{frac{j2Pi kn}{N}}quad k = 0,1,2…N-1$$

Now, we will try to find the DFT of another sequence x₃(n), which is given as X₃(K)

$X_3(K) = X_1(K)times X_2(K)$

By taking the IDFT of the above we get

$x_3(n) = frac{1}{N}displaystylesumlimits_{n = 0}^{N-1}X_3(K)e^{frac{j2Pi kn}{N}}$

After solving the above equation, finally, we get

$x_3(n) = displaystylesumlimits_{m = 0}^{N-1}x_1(m)x_2[((n-m))_N]quad m = 0,1,2…N-1$

Methods of Circular Convolution

Generally, there are two methods, which are adopted to perform circular convolution and they are −

• Concentric circle method,
• Matrix multiplication method.

Concentric Circle Method

Let $x_1(n)$ and $x_2(n)$ be two given sequences. The steps followed for circular convolution of $x_1(n)$ and $x_2(n)$ are

• Take two concentric circles. Plot N samples of $x_1(n)$ on the circumference of the outer circle (maintaining equal distance successive points) in anti-clockwise direction.

• For plotting $x_2(n)$, plot N samples of $x_2(n)$ in clockwise direction on the inner circle, starting sample placed at the same point as 0^th sample of $x_1(n)$

• Multiply corresponding samples on the two circles and add them to get output.

• Rotate the inner circle anti-clockwise with one sample at a time.

Matrix Multiplication Method

Matrix method represents the two given sequence $x_1(n)$ and $x_2(n)$ in matrix form.

• One of the given sequences is repeated via circular shift of one sample at a time to form a N X N matrix.

• The other sequence is represented as column matrix.

• The multiplication of two matrices give the result of circular convolution.