DSP - DFT Circular Convolution

Advertisements

Previous Page
Next Page  

Let us take two finite duration sequences x1(n) and x2(n), having integer length as N. Their DFTs are X1(K) and X2(K) respectively, which is shown below −

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

Now, we will try to find the DFT of another sequence x3(n), which is given as X3(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}\displaystyle\sum\limits_{n = 0}^{N-1}X_3(K)e^{\frac{j2\Pi kn}{N}}$

After solving the above equation, finally, we get

$x_3(n) = \displaystyle\sum\limits_{m = 0}^{N-1}x_1(m)x_2[((n-m))_N]\quad m = 0,1,2...N-1$

Comparison points Linear Convolution Circular Convolution
Shifting Linear shifting Circular shifting
Samples in the convolution result $N_1+N_2−1$ $Max(N_1,N_2)$
Finding response of a filter Possible Possible with zero padding

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 0th 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.

Advertisements