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.