More topics in Digital Signal Processing

What is the difference between linear convolution and circular convolution?

Linear Convolution

Circular Convolution

Linear convolution is a mathematical operation done to calculate the output of any Linear-Time Invariant (LTI) system given its input and impulse response. Circular convolution is essentially the same process as linear convolution. Just like linear convolution, it involves the process of folding a sequence, shifting it, multiplying it with another sequence and summing the resulting products (We’ll see what this means in a minute). However, in circular convolution, the signals are all periodic. Thus the shifting can be thought of as actually being a rotation. Since the values keep repeating because of the periodicity. Hence, it is known as circular convolution.
It is applicable for both, continuous and discrete-time signals. Circular convolution is also applicable for both, continuous and discrete-time signals.
We can represent Linear Convolution as

y(n)=x(n)*h(n)

Here, y(n) is the output (also known as convolution sum). x(n) is the input signal and h(n) is the impulse response of the LTI system.

We can represent Circular Convolution as

y(n)=x(n)⊕h(n)

Here y(n) is a periodic output, x(n) is a periodic input and h(n) is the periodic impulse response of the LTI system.

In linear convolution, both the sequences (input and impulse response) may or may not be of equal sizes. That is, they may or may not have the same number of samples. Thus the output too, may or may not have the same number of samples as any of the inputs. In circular convolution, both the sequences (input and impulse response) must be of equal sizes. They must have the same number of samples. Thus the output of a circular convolution has the same number of samples as the two inputs.
For example, consider the following signals:

x(n): [1,2,3]

h(n): [1,2,3,4,5]

As you can see, the number of samples in the input and IR signals is not the same. Still, linear convolution is possible.

Here’s how you calculate the number of samples in the output of linear convolution.

L = M + N – 1

Where M is the number of samples in x(n). N is the number of samples in h(n).

For the above example, the output will have (3+5-1) = 7 samples.

For the given example, circular convolution is possible only after modifying the signals via a method known as zero padding. In zero padding, 0s are appended to the sequence that has a lesser size to make the sizes of the two sequences equal. Thus, for the given sequence, after zero padding:

x(n) = [1,2,3,0,0]

Now both x(n) and h(n) have the same lengths. So circular convolution can take place. And the output of the circular convolution will have the same number of samples. i.e 5.

Graphically, when we perform linear convolution, there is a linear shift taking place. Check out the formula for a convolution.

 \sum_{ -\infty }^{ \infty } x(k)h(n-k)

There is a folding of the IR sequence, shifting it by n, multiplying it with another sequence (input) and summing the resulting products.

Graphically, when we perform circular convolution, there is a circular shift taking place. Alternatively, we can call it rotation.
It is possible to find the response of a filter using linear convolution. It is possible to find the response of a filter using circular convolution after zero padding. I fact, we will be doing this in overlap-save and overlap-add methods. Two important topics in our digital signal processing course.
Linear convolution may or may not result in a periodic output signal. The output of a circular convolution is always periodic and its period is specified by the periods of one of its inputs.

About The Writer

CLOSE

Leave a Reply

Your email address will not be published. Required fields are marked *