Circular Convolution - Discrete Fourier Transform | Digital Signal Processing - Electronics and Communication Engineering (ECE) PDF Download

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 −

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

By taking the IDFT of the above we get

After solving the above equation, finally, we get

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₁(n) and x₂(n) be two given sequences. The steps followed for circular convolution of x₁(n) and x₂(n) are

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

• For plotting x₂(n), plot N samples of x₂(n) in clockwise direction on the inner circle, starting sample placed at the same point as 0^thsample of x₁(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₁(n) and x₂(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.