HOME
PDF

A simple method to do circular convolution

Nasser M. Abbasi

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 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 first sequence       |-|
x =  { 1-,2,4,5,6 } and the second sequence        |-|
h = {7,-8-,9,3} , where the square around the number indicates the time n = 0  .

We want to find y = x ⊛ h  where ⊛ is circular convolution.

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

The process to to find y[0]  is illustrated using a diagram. The first 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

PIC

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.

PIC

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′ , 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.

PIC

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

PIC

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

PIC

Since now h′ is completely under x  , the process completes.

Hence           |--|
y = {112, |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