On 17 Aug, 18:14, "Fred Marshall" <fmarshallx@remove_the_x.acm.org> wrote:> Rune, > > I must be missing a few fundamentals: > > I don't understand why you compute: > > Y=X./fft(a',length(x)); > > instead of: > > Y=X.*fft(x);Because I want to compute the convolution y[n] = x[n] (*) h[n] where h[n] is computed from the IIR filter y[n] = x[n] - 0.9*x[n-1]. The above is a way to implement that filter by means of circular convolution.> Then, I'm not sure it's particularly meaningful to convolve with a unit > sample because there can't be any overlap anyway. M + 1 - 1 = M.I'm filtering the signal.> I object to the practice of doing DFT/*/IDFT process without appending > enough zeros to eliminate overlap.Interesting. This could be interpreted as a direct contradiction of your earlier statement that 'Circular convolution is a desired result.'> The Matlab "filter" function generates a > unit sample response of arbitrary length according to the length of the > input sequence.I don't know how that function is implemented; it is a built-in function in my edition of matlab so I can't read the source code. But it works as if it implements a linear convolution.> But, as long as that length is the length you decide to use > for the truncated unit sample response of your IIR, then that's fine of > course.In your first post you stated that 'When I choose to multiply in frequency using DFT / IDFT then it is what I intend, want, etc.' as if there were no problems whatsoever with this approach. Now you all of a sudden go to great lengths to avoid all those side effects I have been pointing at all along. Make up your mind: Do you agree or disagree with me when I way that the wrap-around effects associated with circular convolution are problems that are best avoided and need to be handled with care?> It seems to me that the proper implementation would go like this:No. The implementation I posted is proper wrt the purpose which was to demonstrate why wrap-around effects is a problem when you try to do filtering by naive use of the circular convolution. Rune

# Please help with Circular Convolution!

Started by ●August 11, 2008

Reply by ●August 17, 20082008-08-17

Reply by ●August 17, 20082008-08-17

"Rune Allnor" <allnor@tele.ntnu.no> wrote in message news:aca47588-317b-491f-8db5-729f03a3f26c@l42g2000hsc.googlegroups.com...> On 17 Aug, 18:14, "Fred Marshall" <fmarshallx@remove_the_x.acm.org> > wrote: >> Rune, >> >> I must be missing a few fundamentals: >> >> I don't understand why you compute: >> >> Y=X./fft(a',length(x)); >> >> instead of: >> >> Y=X.*fft(x); > > Because I want to compute the convolution > > y[n] = x[n] (*) h[n] > > where h[n] is computed from the IIR filter > > y[n] = x[n] - 0.9*x[n-1]. > > The above is a way to implement that filter by means of > circular convolution. > >> Then, I'm not sure it's particularly meaningful to convolve with a unit >> sample because there can't be any overlap anyway. M + 1 - 1 = M. > > I'm filtering the signal. > >> I object to the practice of doing DFT/*/IDFT process without appending >> enough zeros to eliminate overlap. > > Interesting. This could be interpreted as a direct contradiction > of your earlier statement that 'Circular convolution is a desired > result.' > >> The Matlab "filter" function generates a >> unit sample response of arbitrary length according to the length of the >> input sequence. > > I don't know how that function is implemented; it is a built-in > function in my edition of matlab so I can't read the source code. > But it works as if it implements a linear convolution. > >> But, as long as that length is the length you decide to use >> for the truncated unit sample response of your IIR, then that's fine of >> course. > > In your first post you stated that 'When I choose to multiply in > frequency using DFT / IDFT then it is what I intend, want, etc.' > as if there were no problems whatsoever with this approach. > > Now you all of a sudden go to great lengths to avoid all those > side effects I have been pointing at all along. > > Make up your mind: Do you agree or disagree with me when I > way that the wrap-around effects associated with circular > convolution are problems that are best avoided and need to > be handled with care? > >> It seems to me that the proper implementation would go like this: > > No. The implementation I posted is proper wrt the purpose > which was to demonstrate why wrap-around effects is a problem > when you try to do filtering by naive use of the circular > convolution. > > RuneRune, As usual, it seems that we're mostly in agreement. I thought you said that circular convolution when an IIR was involved caused wrap-around per se. I was trying to say that, properly implemented, it doesn't. The Matlab example you gave did demonstrate issues - so if that was the purpose then we agree. I rather felt that having the "filter" function in the midst of it all might be confounding - so I broke up the process into more fundamental steps is all. Beyond that, all I did was limit the length of sequences where appropriate. Regarding:>> I object to the practice of doing DFT/*/IDFT process without appending >> enough zeros to eliminate overlap. > > Interesting. This could be interpreted as a direct contradiction > of your earlier statement that 'Circular convolution is a desired > result.'I'm afraid that my "quoter" with carets ">" is sometimes broken and I can't find where I said "Circular convolution is a desired result" although I agree with that assertion of one is doing DFT/*/IDFT. I do find where you said "Circular convolution is seldom a desired result" and I didn't agree with that - so I'll accept it anyway. I asked if possibly we had a difference in definition. It appears to me that we probably do. I'll try: "Circular convolution is implemented by convolving periodic sequences (usually in time) - which can be done analytically and is rarely done numerically. This type of circular convolution can be implemented by taking a single period in time of each of two sequences (padding zeros if necessary to make the sequences of equal length), computing the DFT of each, multiplying the two DFTs and computing the IDFT." This definition neither allows nor disallows overlap. But, if I'm going to USE it then I'm going to prevent overlap - which is really easy to do. If you insist that circular convolution of finite sequences *causes* overlap then I think that's too strong a statement and I counter by saying: "then it wasn't done properly". And, I expand that assertion by saying if one wants to add an IIR filter into the picture then it's important to truncate the unit sample response of the IIR filter or be fully aware of the overlap one is causing by not doing so. Where do we disagree? Fred

Reply by ●August 18, 20082008-08-18

On 17 Aug, 18:58, Rune Allnor <all...@tele.ntnu.no> wrote:> Because I want to compute the convolution > > y[n] = x[n] (*) h[n] > > where h[n] is computed from the IIR filter > > y[n] = x[n] - 0.9*x[n-1].Typo: The filter should be y[n] = x[n] - 0.9*y[n-1] Rune

Reply by ●August 18, 20082008-08-18

On 18 Aug, 03:33, "Fred Marshall" <fmarshallx@remove_the_x.acm.org> wrote:> Rune, > > As usual, it seems that we're mostly in agreement. > > I thought you said that circular convolution when an IIR was involved caused > wrap-around per se.It does, although numerical round-off effects etc might be larger.> I was trying to say that, properly implemented, it doesn't.Actually, both examples filtered by the FFT / * / IFFT method would suffer from wrap-around. The difference is that with the long sequence (N=80) the impulse response of the IIR has diminished to the point where the effect is 'negligable.'> The Matlab example you gave did demonstrate issues - so if that was the > purpose then we agree. �I rather felt that having the "filter" function in > the midst of it all might be confounding - so I broke up the process into > more fundamental steps is all. �Beyond that, all I did was limit the length > of sequences where appropriate.OK.> Regarding: > > >> I object to the practice of doing DFT/*/IDFT process without appending > >> enough zeros to eliminate overlap. > > > Interesting. This could be interpreted as a direct contradiction > > of your earlier statement that 'Circular convolution is a desired > > result.' > > I'm afraid that my "quoter" with carets ">" is sometimes broken and I can't > find where I said "Circular convolution is a desired result" although I > agree with that assertion of one is doing DFT/*/IDFT. �I do find where you > said "Circular convolution is seldom a desired result" and I didn't agree > with that - so I'll accept it anyway.Just to be clear: The exact exchange I reacted to was this (distilled from your first post): Me: "Circular convolution is seldom a desired result" You: "Then our definitions must be different." Since 'convolution' (without qualifier) by default means 'linear convolution' I interpreted the above as you disagreeing with my statement that wrap-around effects associated with *circular* convolution are problems to be avoided.> I asked if possibly we had a difference in definition. �It appears to me > that we probably do. �I'll try: > > "Circular convolution is implemented by convolving periodic sequences > (usually in time) - which can be done analytically and is rarely done > numerically. �This type of circular convolution can be implemented by taking > a single period in time of each of two sequences (padding zeros if necessary > to make the sequences of equal length), computing the DFT of each, > multiplying the two DFTs and computing the IDFT."That's at odds with the definition I have seen: The circular convolution produces wrap-around as a property of the *algorithm*, not the input *data*.> This definition neither allows nor disallows overlap. > But, if I'm going to USE it then I'm going to prevent overlap - which is > really easy to do. > > If you insist that circular convolution of finite sequences *causes* overlap > then I think that's too strong a statement and I counter by saying: "then it > wasn't done properly".OK.> And, I expand that assertion by saying if one wants to add an IIR filter > into the picture then it's important to truncate the unit sample response of > the IIR filter or be fully aware of the overlap one is causing by not doing > so. > > Where do we disagree? > > FredAs of right now it seems that we disagree on the term 'circular convolution' is caused by the data or the algorithm. The DFT/*/IDFT method will cause wrap-around effects irrespective of the data and is therefore causing circular convolution no matter what the input data looked like or whether the sampled process is periodic or not. Having said that, being aware that the DFT/*/IDFT method in a certain sense is equivalent to convolving periodic data is probably the key to see when circular convolution will in fact useful in applications. Rune

Reply by ●August 18, 20082008-08-18

"Rune Allnor" <allnor@tele.ntnu.no> wrote in message news:69647ed0-0789-463a-b0a5-e25fa0345615@w7g2000hsa.googlegroups.com... On 18 Aug, 03:33, "Fred Marshall" <fmarshallx@remove_the_x.acm.org> wrote: As of right now it seems that we disagree on the term 'circular convolution' is caused by the data or the algorithm. The DFT/*/IDFT method will cause wrap-around effects irrespective of the data and is therefore causing circular convolution no matter what the input data looked like or whether the sampled process is periodic or not. Having said that, being aware that the DFT/*/IDFT method in a certain sense is equivalent to convolving periodic data is probably the key to see when circular convolution will in fact useful in applications. Rune ************************* Fred sez: Rune, Thanks for the thoughtful reply. Again my "quoter" is broken and no carets on your post show up above. Sorry about that. I get a couple of key comments here that seem worth mentioning. Here's what I understand the standard definitions to be: - The DFT/*/IDFT method *is* an implementation of circular convolution. - Circular convolution either causes overlap / wrap-around or not depending on the data: the nonzero extent of the input sequences. So, if M and N represent the number of nonzero samples in the input sequences, we must zero pad them to at least M + N -1 samples. So, when you say "causes circular convolution", I would say "causes overlap / wrap-around when using circular convolution". Circular convolution is a method and overlap / wrap-around is a *possible* affect caused by using that method. And, that's where we appear to disagree on terminology. Respectfully, all I can do is encourage you to consider the above. Regards, Fred

Reply by ●August 18, 20082008-08-18

On 18 Aug, 20:32, "Fred Marshall" <fmarshallx@remove_the_x.acm.org> wrote:> Here's what I understand the standard definitions to be: > > - The DFT/*/IDFT method *is* an implementation of circular convolution.Agreed.> - Circular convolution either causes overlap / wrap-around or not depending > on the data: the nonzero extent of the input sequences. �So, if M and N > represent the number of nonzero samples in the input sequences, we must zero > pad them to at least M + N -1 samples.Agreed. And conversely, if the nonzero extent of the linear convolution is longer than the buffer, wrap-around will occur.> So, when you say "causes circular convolution", I would say "causes overlap > / wrap-around when using circular convolution".I haven't looked up the exact phrasings I used, but the intention of the above phrases was to use them explicitly with the DFT / * / IDFT algorithm.> Circular convolution is a method and overlap / wrap-around is a *possible* > affect caused by using that method.Agreed.> And, that's where we appear to disagree on terminology. �Nah, we don't. Rune