HOME
PDF

A simple method to do circular convolution

July 2, 2015 page compiled on July 2, 2015 at 5:43pm

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 points between two sequences, where 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 and the second sequence , where the square around the number indicates the time .

We want to ﬁnd where is circular convolution.

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

The process to to ﬁnd 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 is found using the same process as above, but is moved to the right by position instead of zero positions.

Notice that in the above step, we see that the origin (index ) of sequence happened to be aligned with the origin of the sequence , this means that is the origin of the since this is the index for being generated in this step.

Now is found using the same process as above, but is moved to the right by positions.

Now is found using the same process as above, but is moved to the right by positions.

Now is found using the same process as above, but is moved to the right by positions.

Since now is completely under , the process completes.

Hence . 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