On 12 Aug, 06:59, robert bristow-johnson <r...@audioimagination.com> wrote:> On Aug 11, 10:28 pm, "Mani007" <thugulys...@hotmail.com> wrote:...> > I know how to compute the linear convolution, but I am stuck as to how to > > do the circular convolution.. > > circular convolution is what happens naturally when you DFT (or FFT) > two equal-length sequences, pointwise multiply those results together, > and inverse DFT the product sequence.Circular convolution is seldom a desired result (I can't think of a single example where it is), but rather a numerical effect one wants to avoid. I would approach circular convolution with the aim to understand where and why it occurs naturally (with naive use of the DFT to convolve two sequences), and then try and recognize (and handle) those situations during practical work. Rune
Please help with Circular Convolution!
Started by ●August 11, 2008
Reply by ●August 13, 20082008-08-13
Reply by ●August 13, 20082008-08-13
Rune Allnor wrote:> Circular convolution is seldom a desired result (I can't think of > a single example where it is),What if the OP has an image that is a 360� panorama that he needs to filter. -jim ----== Posted via Pronews.Com - Unlimited-Unrestricted-Secure Usenet News==---- http://www.pronews.com The #1 Newsgroup Service in the World! >100,000 Newsgroups ---= - Total Privacy via Encryption =---
Reply by ●August 13, 20082008-08-13
On Aug 13, 5:49�pm, jim <"sjedgingN0sp"@m...@mwt.net> wrote:> Rune Allnor wrote: > > Circular convolution is seldom a desired result (I can't think of > > a single example where it is), > > What if the OP has an image that is a 360� panorama that he needs to > filter. > > -jim > > ---- Posted via Pronews.Com - Unlimited-Unrestricted-Secure Usenet News----http://www.pronews.comThe #1 Newsgroup Service in the World! >100,000 Newsgroups > --- - Total Privacy via Encryption ---Rune did say "seldom" :-) Dirk
Reply by ●August 14, 20082008-08-14
"Rune Allnor" <allnor@tele.ntnu.no> wrote in message news:4a5cb609-3c0d-42f4-9659-19bd4feed965@56g2000hsm.googlegroups.com...> On 12 Aug, 06:59, robert bristow-johnson <r...@audioimagination.com>> Circular convolution is seldom a desired result (I can't think of > a single example where it is), but rather a numerical effect one > wants to avoid.Then our definitions must be different. When I choose to multiply in frequency using DFT / IDFT then it is what I intend, want, etc. No avoidance involved whatsoever. Fred
Reply by ●August 14, 20082008-08-14
On 14 Aug, 09:45, "Fred Marshall" <fmarshallx@remove_the_x.acm.org> wrote:> "Rune Allnor" <all...@tele.ntnu.no> wrote in message> > Circular convolution is seldom a desired result (I can't think of > > a single example where it is), but rather a numerical effect one > > wants to avoid. > > Then our definitions must be different.�Nope. But I consider the wrap-around effects that occur in circular convolution the same way I consider aliasing in sampling: Undesriable, unavoidable (with the DFT method), their influence at the end result must at least be minimized and preferably eliminated alltogether. The usual stuff - know what you can get, know what you want, tweak what you can get in the direction of what you want. Standard Engineering Operations Procedure.> When I choose to multiply in > frequency using DFT / IDFT then it is what I intend, want, etc. �No > avoidance involved whatsoever.Usually one uses the DFT to compute convolution because one wants to save some computation time compared to naively computing the 'direct' or 'linear' (or whatever one wants to call it) convolution. Whenever I use the DFT method I make the effort to estimate the duration of end transients (trivial with FIR filters; a bit harder with IIR filters) and zero-pad the input data so that the wrap-around effects become 'sufficiently small'. I don't *want* those wrap-around effects to happen, but there is nothing I can do to prevent them from happening; they are side effects caused by using the DFT. The side effects can not be *avoided*, only accounted for and handled as best one can. Rune
Reply by ●August 14, 20082008-08-14
dbell wrote:> > On Aug 13, 5:49 pm, jim <"sjedgingN0sp"@m...@mwt.net> wrote: > > Rune Allnor wrote: > > > Circular convolution is seldom a desired result (I can't think of > > > a single example where it is), > > > > What if the OP has an image that is a 360� panorama that he needs to > > filter.> > Rune did say "seldom" :-)Yes I read that. I guess I failed to see why seldom or not makes any difference one way or the other. The OP asked for help with implementation. If the data one needed to convolve was like my example then one would need to do circular convolution and it seems unlikely to me that it would be as practical to do so by padding the filter kernel with a large number of zeroes and then DFT-multiply-IDFT as it would to just do it directly by making a slight modification to the linear convolution algorithm the OP said he already has. -jim ----== Posted via Pronews.Com - Unlimited-Unrestricted-Secure Usenet News==---- http://www.pronews.com The #1 Newsgroup Service in the World! >100,000 Newsgroups ---= - Total Privacy via Encryption =---
Reply by ●August 14, 20082008-08-14
On 14 Aug, 15:46, jim <".sjedgingN0sp"@m...@mwt.net> wrote:> dbell wrote: > > > On Aug 13, 5:49 pm, jim <"sjedgingN0sp"@m...@mwt.net> wrote: > > > Rune Allnor wrote: > > > > Circular convolution is seldom a desired result (I can't think of > > > > a single example where it is), > > > > What if the OP has an image that is a 360� panorama that he needs to > > > filter. > > > Rune did say "seldom" :-) > > Yes I read that. I guess I failed to see why seldom or not makes any difference > one way or the other.Well, because I have never seen an application where the wrap-around effects associated with circular convolution were desired, but left the possibilty open that there might be an application out there I don't know about.> The OP asked for help with implementation.So? Before helping with the implementation, why not demonstrate that my premise, that circular convolution is a prblem, is wrond by coming up with a couple of applications where the wrap-around is a desired and useful property? I'm not sure I would accept the 360 deg panorama, as matching the images would probably be be achievable by forward-backward filtering across each joint, and wrap-around effects from different joints of one image would probably be undesired. Rune
Reply by ●August 15, 20082008-08-15
wow. i just now got back to this thread and a lot was said in the meantime. On Aug 14, 4:07 am, Rune Allnor <all...@tele.ntnu.no> wrote:> On 14 Aug, 09:45, "Fred Marshall" <fmarshallx@remove_the_x.acm.org> > wrote: > > > "Rune Allnor" <all...@tele.ntnu.no> wrote in message > > > Circular convolution is seldom a desired result (I can't think of > > > a single example where it is), but rather a numerical effect one > > > wants to avoid.Rune, i, for the most part, agree with you but recognize the "seldom" cases like On Aug 13, 5:49 pm, jim <"sjedgingN0sp"@m...@mwt.net> wrote:> > What if the OP has an image that is a 360� panorama that he needs to > filter?it's possible that in music synthesis, there might be a periodic waveform (described by a single cycle) that one wants filtered. but, equivalently, what the user usually wants to do is adjust the amplitudes of the harmonics which is the same thing as the DFT/ multiply/iDFT thingie anyway.> > Then our definitions must be different.i thought the definition of circular convolution was clear. i still don't understand an essential definition of circular convolution that is not commutative and does not require both sequences to be the same length: x[n] -> {A B C D E F} h[n] -> {G H I J K L} if y[n] is the circular convolution of x[n] and h[n], then for y[n], you perform these dot-products: y[0] {A B C D E F} {G L K J I H} y[1] {A B C D E F} {H G L K J I} y[2] {A B C D E F} {I H G L K J} y[3] {A B C D E F} {J I H G L K} y[4] {A B C D E F} {K J I H G L} y[5] {A B C D E F} {L K J I H G} if i could draw it well with ASCII-art, i would draw the sequences circularly (with one ring inside the other) as is done in at least some textbooks. so imagine the F-tail appended to the A-head and similarly for L and G. now how to you do that for x[n] and h[n] having different lengths? i see no possible definition for it. whichever is shorter, some assumption has to be made for the missing values needed to bring the shorter sequence to the same length as the longer.> Nope. But I consider the wrap-around effects that occur in circular > convolution the same way I consider aliasing in sampling: > Undesriable, > unavoidable (with the DFT method), their influence at the end result > must at least be minimized and preferably eliminated alltogether.which is what that OLA and OLS methods of fast convolution are all about.> > > When I choose to multiply in > > frequency using DFT / IDFT then it is what I intend, want, etc. No > > avoidance involved whatsoever.okay, but then Fred, you have to accept that you are not performing linear convolution. you are performing circular convolution. as Rune says, well, maybe more aptly put by Jerry in his sig: "Engineering in making what you need out of the things you have", what we're doing with the FFT/multiply/iFFT (this doesn't make any advantageous sense if you don't use the fast DFT) and OLA or OLS is *adapting* something that only does circular convolution to the task of linear convolution. and we end up padding some zeros to make that happen.> Usually one uses the DFT to compute convolution because one wants to > save some computation time compared to naively computing the 'direct' > or 'linear' (or whatever one wants to call it) convolution. > > Whenever I use the DFT method I make the effort to estimate the > duration of end transients (trivial with FIR filters; a bit harder > with IIR filters) and zero-pad the input data so that the wrap-around > effects become 'sufficiently small'. > > I don't *want* those wrap-around effects to happen, but there is > nothing I can do to prevent them from happening; they are side > effects caused by using the DFT. The side effects can not be > *avoided*, only accounted for and handled as best one can.yeah, i think i agree with that. r b-j
Reply by ●August 15, 20082008-08-15
"robert bristow-johnson" <rbj@audioimagination.com> wrote in message news:52343262-125c-46fa-836a-9f4d89afff16@l64g2000hse.googlegroups.com... wow. i just now got back to this thread and a lot was said in the meantime. On Aug 14, 4:07 am, Rune Allnor <all...@tele.ntnu.no> wrote:> On 14 Aug, 09:45, "Fred Marshall" <fmarshallx@remove_the_x.acm.org> > wrote: > > > "Rune Allnor" <all...@tele.ntnu.no> wrote in message > > > Circular convolution is seldom a desired result (I can't think of > > > a single example where it is), but rather a numerical effect one > > > wants to avoid.Rune, i, for the most part, agree with you but recognize the "seldom" cases like On Aug 13, 5:49 pm, jim <"sjedgingN0sp"@m...@mwt.net> wrote:> > What if the OP has an image that is a 360� panorama that he needs to > filter?it's possible that in music synthesis, there might be a periodic waveform (described by a single cycle) that one wants filtered. but, equivalently, what the user usually wants to do is adjust the amplitudes of the harmonics which is the same thing as the DFT/ multiply/iDFT thingie anyway.> > Then our definitions must be different.i thought the definition of circular convolution was clear. i still don't understand an essential definition of circular convolution that is not commutative and does not require both sequences to be the same length: x[n] -> {A B C D E F} h[n] -> {G H I J K L} if y[n] is the circular convolution of x[n] and h[n], then for y[n], you perform these dot-products: y[0] {A B C D E F} {G L K J I H} y[1] {A B C D E F} {H G L K J I} y[2] {A B C D E F} {I H G L K J} y[3] {A B C D E F} {J I H G L K} y[4] {A B C D E F} {K J I H G L} y[5] {A B C D E F} {L K J I H G} if i could draw it well with ASCII-art, i would draw the sequences circularly (with one ring inside the other) as is done in at least some textbooks. so imagine the F-tail appended to the A-head and similarly for L and G. now how to you do that for x[n] and h[n] having different lengths? i see no possible definition for it. whichever is shorter, some assumption has to be made for the missing values needed to bring the shorter sequence to the same length as the longer.> Nope. But I consider the wrap-around effects that occur in circular > convolution the same way I consider aliasing in sampling: > Undesriable, > unavoidable (with the DFT method), their influence at the end result > must at least be minimized and preferably eliminated alltogether.which is what that OLA and OLS methods of fast convolution are all about.> > > When I choose to multiply in > > frequency using DFT / IDFT then it is what I intend, want, etc. No > > avoidance involved whatsoever.okay, but then Fred, you have to accept that you are not performing linear convolution. you are performing circular convolution. as Rune says, well, maybe more aptly put by Jerry in his sig: "Engineering in making what you need out of the things you have", what we're doing with the FFT/multiply/iFFT (this doesn't make any advantageous sense if you don't use the fast DFT) and OLA or OLS is *adapting* something that only does circular convolution to the task of linear convolution. and we end up padding some zeros to make that happen.> Usually one uses the DFT to compute convolution because one wants to > save some computation time compared to naively computing the 'direct' > or 'linear' (or whatever one wants to call it) convolution. > > Whenever I use the DFT method I make the effort to estimate the > duration of end transients (trivial with FIR filters; a bit harder > with IIR filters) and zero-pad the input data so that the wrap-around > effects become 'sufficiently small'. > > I don't *want* those wrap-around effects to happen, but there is > nothing I can do to prevent them from happening; they are side > effects caused by using the DFT. The side effects can not be > *avoided*, only accounted for and handled as best one can.yeah, i think i agree with that. r b-j ****** Geez guys, I don't know what the problem is here. All of the factoids aside I see no reason why circular convolution of finite-length sequences can't be equivalent to linear convolution (and should be for the most part I should think). To preface I should say that circular convolution makes no sense unless we're talking about DFT/*/IDFT implementation - so that has been my assumption here. To say that circular convolution is a problem when one has an IIR filter makes no sense to me in that using a DFT is going to force the unit sample response of your representation of that filter to be finite - thus, FIR. And, being FIR there is no problem except that now it's a "different" filter than the one we started with ... but how to avoid *that*? Now, if we somehow choose to allow overlap then it's our own doing and not a function of the method. I guess one could do this: Start with an IIR filter unit sample response of length L (as in Large). Have a signal of length N<<L. Now, we can either a) pad both sequences with zeros to length L + N -1 or greater OR b) we can pad the signal to length L. In (b) there will be overlap because we insisted on holding on to every last sample of the IIR unit sample response and decided to allow overlap. In (a) we would either shorten the IIR unit sample response a bit or zero pad it a bit - to guarantee no overlap. Now, one should be allowed to do whatever it takes. And, if the sequence length is getting too big and if the IIR response is getting too short and if the overlap isn't really a big deal then one might *choose* to allow it. But it's not built-in. Fred
Reply by ●August 15, 20082008-08-15
robert bristow-johnson wrote:> > wow. i just now got back to this thread and a lot was said in the > meantime. > > On Aug 14, 4:07 am, Rune Allnor <all...@tele.ntnu.no> wrote: > > On 14 Aug, 09:45, "Fred Marshall" <fmarshallx@remove_the_x.acm.org> > > wrote: > > > > > "Rune Allnor" <all...@tele.ntnu.no> wrote in message > > > > Circular convolution is seldom a desired result (I can't think of > > > > a single example where it is), but rather a numerical effect one > > > > wants to avoid. > > Rune, i, for the most part, agree with you but recognize the "seldom" > cases like > > On Aug 13, 5:49 pm, jim <"sjedgingN0sp"@m...@mwt.net> wrote: > > > > What if the OP has an image that is a 360� panorama that he needs to > > filter? > > it's possible that in music synthesis, there might be a periodic > waveform (described by a single cycle) that one wants filtered. but, > equivalently, what the user usually wants to do is adjust the > amplitudes of the harmonics which is the same thing as the DFT/ > multiply/iDFT thingie anyway. > > > > Then our definitions must be different. > > i thought the definition of circular convolution was clear. i still > don't understand an essential definition of circular convolution that > is not commutative and does not require both sequences to be the same > length: > > x[n] -> {A B C D E F} > > h[n] -> {G H I J K L} > > if y[n] is the circular convolution of x[n] and h[n], then for y[n], > you perform these dot-products: > > y[0] {A B C D E F} > {G L K J I H} > > y[1] {A B C D E F} > {H G L K J I} > > y[2] {A B C D E F} > {I H G L K J} > > y[3] {A B C D E F} > {J I H G L K} > > y[4] {A B C D E F} > {K J I H G L} > > y[5] {A B C D E F} > {L K J I H G} > > if i could draw it well with ASCII-art, i would draw the sequences > circularly (with one ring inside the other) as is done in at least > some textbooks. so imagine the F-tail appended to the A-head and > similarly for L and G. > > now how to you do that for x[n] and h[n] having different lengths? i > see no possible definition for it. whichever is shorter, some > assumption has to be made for the missing values needed to bring the > shorter sequence to the same length as the longer.Well x[n] is what is assumed to be cyclical by definition. A signal is considered to be either one period of a perfectly cyclical sequence or it isn't. If a person regards their x[n] as not part of an endlessly repeating pattern then yes for that person circular convolution is a problem, but if you know it is one cycle of a repeating pattern then you would want to do circular convolution. If you were doing DFT/IDFT convolution and you had a h[n] that was shorter then x[n] you would extend h[n] by adding zeroes. You can do the same thing as you did above without DFT by simply padding h[n] with zeroes. But neither of those methods will be very efficient if x[n] is long and h[n] is short. My understanding of the original question was that the OP asked : I have created code that does linear convolution - now how do I produce code that does circular convolution? IMO the easiest thing the OP could do would be to modify his existing code so that x[n] is extended by repetition (note h[n] doesn't get changed at all). If he extends x[n] correctly then the rest of his code should be good to go. Doing it that way will produce the same answer (the same y[n[]) as DFT/IDFT or the hand operations you showed above. -jim> > > Nope. But I consider the wrap-around effects that occur in circular > > convolution the same way I consider aliasing in sampling: > > Undesriable, > > unavoidable (with the DFT method), their influence at the end result > > must at least be minimized and preferably eliminated alltogether. > > which is what that OLA and OLS methods of fast convolution are all > about. > > > > > > When I choose to multiply in > > > frequency using DFT / IDFT then it is what I intend, want, etc. No > > > avoidance involved whatsoever. > > okay, but then Fred, you have to accept that you are not performing > linear convolution. you are performing circular convolution. as Rune > says, well, maybe more aptly put by Jerry in his sig: "Engineering in > making what you need out of the things you have", what we're doing > with the FFT/multiply/iFFT (this doesn't make any advantageous sense > if you don't use the fast DFT) and OLA or OLS is *adapting* something > that only does circular convolution to the task of linear > convolution. and we end up padding some zeros to make that happen. > > > Usually one uses the DFT to compute convolution because one wants to > > save some computation time compared to naively computing the 'direct' > > or 'linear' (or whatever one wants to call it) convolution. > > > > Whenever I use the DFT method I make the effort to estimate the > > duration of end transients (trivial with FIR filters; a bit harder > > with IIR filters) and zero-pad the input data so that the wrap-around > > effects become 'sufficiently small'. > > > > I don't *want* those wrap-around effects to happen, but there is > > nothing I can do to prevent them from happening; they are side > > effects caused by using the DFT. The side effects can not be > > *avoided*, only accounted for and handled as best one can. > > yeah, i think i agree with that. > > r b-j----== Posted via Pronews.Com - Unlimited-Unrestricted-Secure Usenet News==---- http://www.pronews.com The #1 Newsgroup Service in the World! >100,000 Newsgroups ---= - Total Privacy via Encryption =---