HOME
PDF (letter size)
PDF (legal size)

## A simple method to do circular convolution

November 2, 2018   Compiled on May 23, 2020 at 2:56am

This describes a simple method I found to do circular convolution, which I think is simpler than the method I saw in Digital Signal Processing, by Proakis, Manolakis.

This is a method to compute the circular convolution for $$N$$ points between two sequences, where $$N$$ is the length of the longer of the two sequences (or the length of the sequences if they are of equal length).

Let the ﬁrst sequence $$x=\{\fbox{1},2,4,5,6\}$$ and the second sequence $$h=\{7,\fbox{8},9,3\}$$, where the square around the number indicates the time $$n=0$$.

We want to ﬁnd $$y=x\circledast h$$ where $$\circledast$$ is circular convolution.

The process requires as many steps as there are entries in the longer sequence $$x$$.

The process to to ﬁnd $$y[0]$$ is illustrated using a diagram. The ﬁrst step is to pad the smaller sequence by zeros so that it is the same length as the longer sequence. The method is explained in the diagrams

Now $$y[1]$$ is found using the same process as above, but $$h$$ is moved to the right by $$1$$ position instead of zero positions.

Notice that in the above step, we see that the origin (index $$n=0$$) of sequence $$x$$ happened to be aligned with the origin of the sequence $$h^{\prime }$$, this means that $$y[1]$$ is the origin of the $$y$$ since this is the index for $$y$$ being generated in this step.

Now $$y[2]$$ is found using the same process as above, but $$h$$ is moved to the right by $$2$$ positions.

Now $$y[3]$$ is found using the same process as above, but $$h$$ is moved to the right by $$3$$ positions.

Now $$y[4]$$ is found using the same process as above, but $$h$$ is moved to the right by $$4$$ positions.

Since now $$h^{\prime }$$ is completely under $$x$$, the process completes.

Hence $$y=\{112,\fbox{91},71,88,124\}$$. To verify

octave-3.2.4:39> x=[1 2 4 5 6];
octave-3.2.4:40> h=[7 8 9 3 0];
octave-3.2.4:41> X=fft(x); H=fft(h); y=ifft(X.*H)
y =

112    91    71    88   124