Circular Convolution of h(n)*x(n) So I understand how Convolution works but Circular convolution seems a bit messy to me, all the examples seems to have even series of number like h(n)={1,2,3,4} &amp;  x(n)={1,2,3,4} and they are all starting from n=0.

This is from my last exam and I'm trying to figure out e)
(My exam is tomorrow and I just realized I had missed to study on this, hence I won't have time to respond with Latex etc since I don't remember that and figuring it out would mean that I won't have time to study for my exam.



My attempt so far, but I don't know if I need to do zero padding (as I understand you only need to do it if you want to do the FFT). And I don't know if you are supposed to start from x(0)*h(-1)..



Grateful for all help, I have tried to search on the forum and to google it and searching on youtube.

BR Rickard
The circular convolution is actually mainly an artefact from the Fast Convolution algorithm, that is calculating the convolution via the FFT. I am not aware of any use of the circular convolution at all. Now, to efficiently calculate the convolution between x and h, you will often use the FFT, as a multiplication in the frequency domain equals a convolution in the time domain (and inversely). The algorithm is then:

conv(x,h) = ifft( fft(x) .* fft(h) )


where .* denotes an element-wise multiplication. You will have to use a zero-padding so both vectors have the same length and you can do the multiplication. This way to calculate the convolution is faster than the direct way in the time domain. However, as fft(x), fft(h) and thus also ifft(...) have the same length (here, the length of x) you cannot express the "real", linear convolution, which would be a longer vector. What happens is, that the result of the linear convolution gets "wrapped around" as you indicate in your drawings.

Let me show you that using your example. The linear convolution is (without proof)

conv(x,h) = [2, 5, 8, 8, 5, 4, 4]


Now as in the circular convolution, the vectors are only 5 long, the last 2 entries of the result will be added in the front, so

circ_conv(x,h) = [2+4, 5+4, 8, 8, 5] = [6, 9, 8, 8, 5]


is the circular convolution. The easiest way (imho) is to first calculate the linear convolution and then wrap around that result to achieve the circular convolution.

If you want to calculate the linear convolution with the FFT, you only have to zero-pad both vectors such that the linear convolution fits into these vectors, i.e. to a length of 7 in your example.