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=\{\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 find \(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 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
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