0
$\begingroup$

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} & 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.

Question

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

My attempt so far

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

BR Rickard

$\endgroup$
0
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Wow, the best explanation I have been provided with on Stack Exchange so far. It almost seems "too easy", and I will definitely go for this wrapping method. I also tried another method but the answer I got didn't make me feel to confident: like the following {9,5,6,6,6}. And thanks a bunch for the extra information about the zero padding for the FFT! $\endgroup$ – ricksson Aug 24 '15 at 17:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.