How does circular convolution work?

[bee]

How does circular convolution work?
Can you please explain with example i.e. x = [1 2 3 2 1] and h = [3 2 1].

I know the asnwer from matlab of circular convolving the x and h is [7 9 14 14 10]. But HOW????


waiting.....

 

[bee]

thanks a lot!!!

 

[ajayparmar904]

can you tell me how circular convolution is done?i dont want formulas but want practical explanation..like convolution can be consider as a invert one of the function then slide through the other function by time t and integrate over the overlapping region..

 

[ckshivaram]

**broken link removed**

http://www.ceri.memphis.edu/people/smalley/ESCI7355/ESCI7355-circular-convolution.pdf

 

[Dp_DSP]

Hi,
One of the methods to find circular convolution....

In circular convolution the length of the output sequence will be equal to length of the input sequence ie.

length=length(x)

So first perform linear convolution using any of the methods u find easier.

If m is the length of 'x' and n is the length of the 'h' then length of 'yl' from linear conv is m+n-1.

Since length of output from circular conv is m, we will bring the last n-1 terms from 'yl' and add them to first n-1 terms.
So the obtained output is circularly convoluted output.

For eg. if x= 1, 2, 3, 4 and h= 2,3,1

lin conv op ie. yl= 2,7,13,19,15,4

bring last two (n-1) terms to first two terms

so circularly convluted op is yc= 17, 11,13,19


Hope you got it :smile: !!! take different examples and verify...

 

[W_Heisenberg]

ok, finally , i got the reference for your question,

see below:
https://cnx.org/content/m13893/latest/

it is matrix calculation

 

[permute]

Yes, and this is the key realization in using the FFT for processing.

for example, lets say you want to make a filter. It would seem like you could simply take 256 point blocks of data, do an FFT, and then set the coefficients associated with "filtered" frequencies to 0, and then do an inverse FFT to get the 256 points. This ends up being false for two reasons.

the first, unrelated issue is that you would be setting the frequency response to exactly 0 only at a finite number of exact frequencies. This doesn't mean that frequencies between the 256 FFT frequencies would be equal to 0, nor does it mean the entire passband would be flat.

The second, relevant issue is that taking 256 points in a block and then filtering them with an FFT and then getting 256 points back out would mean there would be no possible way to represent a time delay. At best, you could represent a cyclical shift. This is where the "overlap and save" and "overlap and add" algorithms come into play. Without these, the filters would have cyclic shifts, and because the data is put into blocks, this would result in periodic distortion -- the filter would not be linear-time-invariant.

For a second application, consider OFDM's "cyclic prefix", which plays a key role in frequency-domain equalization. In this case, assume that data is transmitted but is received with echos of itself. This cause each transmitted symbol to affect one or more other symbols at the receiver. The cyclic prefix takes the last symbols from a block of data and simply transmits them a second time, but before the normal start of a block. eg, efabcdef. symbols e and f now can affect symbols a and b. And now an FFT can correctly estimate the frequency response because the channel appears to be performing a cyclic convolution -- symbol a seems to affect b and c, b affects c and d, ... e affects f and a, and f affects a and b.

 

[W_Heisenberg]

there is not a really fast way to calculate DFT

say if we have [1 1 1 1 1]

find its DFT for 5 point and 10 point

the math now makes people feeling bad

though, there is also another matrix for this, does not help too much

calculation still so big.