Forums

Circular convolution

Started by arsalan April 24, 2011
On 4/25/2011 6:31 PM, Rune Allnor wrote:
> On Apr 25, 10:49 pm, dvsarwate<dvsarw...@yahoo.com> wrote: >> On Apr 25, 9:10 am, Jerry Avins<j...@ieee.org> wrote: >> >> >> >>> To do that, arsalan would need to understand what circular convolution >>> is. That might be too much like actually *doing* the homework. >> >> Not to do Arsalan's homework for him (her?), but >> how do comp.dsp-ers define the circular convolution >> of two sequences of different lengths (which is >> what Arsalan has in his question: lengths 4 and 3)? > > As always, I choose the more controversial approach: > > As far as I am concerned, circular convolution is an > unwanted side effect that appears if / when one implements > the 'usual' convolution by the DFT / FFT. I am not aware > of any applications where the circular convolution is desired. > > Rune
Um.. maybe with circular buffers? Fred
On 4/25/2011 4:05 PM, Jerry Avins wrote:
> > I don't agree. Occam's razor suggests that circular convolution is > merely the way the problem was assigned. > > Jerry > --
spoilsport! :-)
On Apr 26, 12:46&#2013266080;am, dbd <d...@ieee.org> wrote:

> My thought provoking approach is to ask, "What size circle?"
I suggested three alternatives (a), (b), and (c) earlier as well as a "free response" but nobody was willing to commit to any of them. I guess people are still thinking about it, Dale, or more likely, will just ignore the question. Dilip Sarwate
On Apr 25, 9:31&#2013266080;pm, Rune Allnor <all...@tele.ntnu.no> wrote:
> On Apr 25, 10:49&#2013266080;pm, dvsarwate <dvsarw...@yahoo.com> wrote: > > > On Apr 25, 9:10&#2013266080;am, Jerry Avins <j...@ieee.org> wrote: > > > > To do that, arsalan would need to understand what circular convolution > > > is. That might be too much like actually *doing* the homework. > > > Not to do Arsalan's homework for him (her?), but > > how do comp.dsp-ers define the circular convolution > > of two sequences of different lengths (which is > > what Arsalan has in his question: lengths 4 and 3)? > > As always, I choose the more controversial approach: > > As far as I am concerned, circular convolution is an > unwanted side effect that appears if / when one implements > the 'usual' convolution by the DFT / FFT. I am not aware > of any applications where the circular convolution is desired. > > Rune
Take a look at Papoulis' description of Chirp Scaling - For a digital implementation of the same thing - it explicitly requires a circular convolution. The main idea is how to get f(at) from f(t) where a is a scalar. Papoulis showed that by using a combination of blocks consisting of mixers with chirp signals and filters with chirp impulse responses you can generate f(at). This technique forms the basis of Chirp Scaling algorithms in Synthetic Aperture Radar. An alternative application allows you to generate the Fourier Transform of the signal purely in the time domain. So starting with f(t) you can come up with F(t), where t in F(t) actually represents the frequency domain. Cheers, David
On Apr 26, 7:49&#2013266080;am, dvsarwate <dvsarw...@yahoo.com> wrote:
> On Apr 26, 12:46&#2013266080;am, dbd <d...@ieee.org> wrote: > > > My thought provoking approach is to ask, "What size circle?" > > I suggested three alternatives (a), (b), and (c) earlier > as well as a "free response" but nobody was willing > to commit to any of them. &#2013266080;I guess people are still > thinking about it, Dale, or more likely, will just ignore > the question. > > Dilip Sarwate
Certainly unequal lengths in something that is "supposed" to have similar lengths throws a wrench into the process. Your version "c" at 1st blush seems like it would be good, but a little deeper exploration indicates that if the lengths are relatively prime and the sequences are periodically extended, then your resulting sequence is a sequence of constant value! I'll give some more thought to variants "a" and "b" Clay
On Apr 25, 5:38&#2013266080;pm, Fred Marshall <fmarshallxremove_th...@acm.org>
wrote:
> On 4/25/2011 1:49 PM, dvsarwate wrote: > > > > > On Apr 25, 9:10 am, Jerry Avins<j...@ieee.org> &#2013266080;wrote: > > >> To do that, arsalan would need to understand what circular convolution > >> is. That might be too much like actually *doing* the homework. > > > Not to do Arsalan's homework for him (her?), but > > how do comp.dsp-ers define the circular convolution > > of two sequences of different lengths (which is > > what Arsalan has in his question: lengths 4 and 3)? > > > (a) zero-pad the shorter sequence to have the > > same length as the longer one?
it's the result of playing the waveform defined by the longer one into a LTI filter with h[n] defined by the shorter one.
> > > (b) zero-pad both to length equal to the sum of > > the lengths (or the sum minus one for nitpickers)?
a repetition of the linear convulotion of both zero padded.
> > (c) periodically extend both to length equal to > > the least common multiple of the lengths?
well it's another periodic waveform with filter (and both are missing harmonics).
> > (d)? >
from a POV of normal, everyday communication with the DSP discipline, i would suggest it's about equal-lengthed sequences and is the result of the inverse DFT of the product of the DFTs of the two given sequences.
> > Another question that springs to mind is > > "If linear convolution is desired, why should > > circular convolution be used at all unless the > > intent is to use &#2013266080;the FFT algorithm to speed > > up the calculations?" &#2013266080;Absent the use of the > > FFT algorithm, using DFTs to compute a > > circular convolution in order to get a linear > > convolution result seems to be similar to > > scratching your left ear with your right hand > > after wrapping your arm twice around your > > head.
other than testing the whole thing. if it doesn't work, you might wanna know if it's the FFT or your connection to it.
> > &#2013266080;Heck of a way to get rid of an itch! > > Indeed a heck of a way! > > But "compute a circular convolution in order to get a linear convolution > result [of finite sequences]" is, or should almost always be, the > objective. &#2013266080;That is, I don't imagine circular convolution results that > are different than the linear convolution results - unless one of the > sequences is rather arbitrarily truncated in order to be treated as > finite. &#2013266080;Even in that case, multiple results can be combined to yield > the "continuous" result. > > So we agree that it *must* be to get speedup to be sensible and, by the > way, it's possible to get even greater speedup by performing some tricks > in frequency (as used in interpolation). >
it can't be just people who think about waveform generation for audio/ musical application. aren't there other people who have to generate periodic waveforms for speech or image or communications or something? you have to barf out a waveform into some channel, and you have some theoretical idea what the channel is gonna do to your waveform (some filter). so you time-alias the impulse response of that filter, DFT it, apply the complex reciprocal to it and multiply by the DFT of the desired waveform at the other end of the channel? i'll admit, that for me i think of a note waveform and the other end of the channel is one's eardrum or something like that. but this kind of application has to be a lot broader than musical note synthesis. r b-j
On 4/26/2011 4:49 AM, dvsarwate wrote:
> On Apr 26, 12:46 am, dbd<d...@ieee.org> wrote: > >> My thought provoking approach is to ask, "What size circle?" > > I suggested three alternatives (a), (b), and (c) earlier > as well as a "free response" but nobody was willing > to commit to any of them. I guess people are still > thinking about it, Dale, or more likely, will just ignore > the question. > > Dilip Sarwate >
Just for reference and.... Really I wasn't trying to *do* the homework. (a) zero-pad the shorter sequence to have the same length as the longer one? No. This won't do. (b) zero-pad both to length equal to the sum of the lengths (or the sum minus one for nitpickers)? This is the minimum length needed - so it can be greater. (c) periodically extend both to length equal to the least common multiple of the lengths? perhaps if one has a reason to do so ... periodically?? Fred (d)?
On 4/26/2011 9:11 AM, robert bristow-johnson wrote:
> On Apr 25, 5:38 pm, Fred Marshall<fmarshallxremove_th...@acm.org> > wrote: >> On 4/25/2011 1:49 PM, dvsarwate wrote: >> >> >> >>> On Apr 25, 9:10 am, Jerry Avins<j...@ieee.org> wrote: >> >>>> To do that, arsalan would need to understand what circular convolution >>>> is. That might be too much like actually *doing* the homework. >> >>> Not to do Arsalan's homework for him (her?), but >>> how do comp.dsp-ers define the circular convolution >>> of two sequences of different lengths (which is >>> what Arsalan has in his question: lengths 4 and 3)? >> >>> (a) zero-pad the shorter sequence to have the >>> same length as the longer one? > > it's the result of playing the waveform defined by the longer one into > a LTI filter with h[n] defined by the shorter one. > >> >>> (b) zero-pad both to length equal to the sum of >>> the lengths (or the sum minus one for nitpickers)? > > a repetition of the linear convulotion of both zero padded. > >>> (c) periodically extend both to length equal to >>> the least common multiple of the lengths? > > well it's another periodic waveform with filter (and both are missing > harmonics). > >>> (d)? >> > > from a POV of normal, everyday communication with the DSP discipline, > i would suggest it's about equal-lengthed sequences and is the result > of the inverse DFT of the product of the DFTs of the two given > sequences. > >>> Another question that springs to mind is >>> "If linear convolution is desired, why should >>> circular convolution be used at all unless the >>> intent is to use the FFT algorithm to speed >>> up the calculations?" Absent the use of the >>> FFT algorithm, using DFTs to compute a >>> circular convolution in order to get a linear >>> convolution result seems to be similar to >>> scratching your left ear with your right hand >>> after wrapping your arm twice around your >>> head. > > other than testing the whole thing. if it doesn't work, you might > wanna know if it's the FFT or your connection to it. > >>> Heck of a way to get rid of an itch! >> >> Indeed a heck of a way! >> >> But "compute a circular convolution in order to get a linear convolution >> result [of finite sequences]" is, or should almost always be, the >> objective. That is, I don't imagine circular convolution results that >> are different than the linear convolution results - unless one of the >> sequences is rather arbitrarily truncated in order to be treated as >> finite. Even in that case, multiple results can be combined to yield >> the "continuous" result. >> >> So we agree that it *must* be to get speedup to be sensible and, by the >> way, it's possible to get even greater speedup by performing some tricks >> in frequency (as used in interpolation). >> > > it can't be just people who think about waveform generation for audio/ > musical application. aren't there other people who have to generate > periodic waveforms for speech or image or communications or > something? you have to barf out a waveform into some channel, and you > have some theoretical idea what the channel is gonna do to your > waveform (some filter). so you time-alias the impulse response of > that filter, DFT it, apply the complex reciprocal to it and multiply > by the DFT of the desired waveform at the other end of the channel? > > i'll admit, that for me i think of a note waveform and the other end > of the channel is one's eardrum or something like that. but this kind > of application has to be a lot broader than musical note synthesis. > > r b-j > >
I wasn't thinking beyond the sequence-sequence convolution operation really. If one wants to generate a periodic waveform using something similar then sure.... But then I'd be thinking about a repetitive operation that goes beyond circular. Or I might be thinking that "circular" includes periodic sequences inside it. Or .... Fred Fred
On Apr 26, 10:19&#2013266080;am, Clay <c...@claysturner.com> wrote:

> Your version "c" at 1st blush seems like it would be good, but a > little deeper exploration indicates that if the lengths are relatively > prime and the sequences are periodically extended, then your resulting > sequence is a sequence of constant value!
Yes indeed. More generally, the result is periodic with period equal to the greatest common divisor of the lengths, which gcd is, of course, 1 for the relatively prime case that you considered and a sequence of period 1 has constant value. Oh well, back to the drawing board..... --Dilip Sarwate
On Apr 26, 10:04&#2013266080;pm, dvsarwate <dvsarw...@yahoo.com> wrote:
> On Apr 26, 10:19&#2013266080;am, Clay <c...@claysturner.com> wrote: > > > Your version "c" at 1st blush seems like it would be good, but a > > little deeper exploration indicates that if the lengths are relatively > > prime and the sequences are periodically extended, then your resulting > > sequence is a sequence of constant value! > > Yes indeed. &#2013266080;More generally, the result is periodic > with period equal to the greatest common divisor > of the lengths, which gcd is, of course, 1 for the > relatively prime case that you considered and a > sequence of period 1 has constant value. &#2013266080;Oh well, > back to the drawing board..... > > --Dilip Sarwate
It is a fun exercise! Clay