Please help with Circular Convolution!

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

"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.
>
> Rune

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

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

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. &#4294967295;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. &#4294967295;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. &#4294967295;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. &#4294967295;It appears to me
> that we probably do. &#4294967295;I'll try:
>
> "Circular convolution is implemented by convolving periodic sequences
> (usually in time) - which can be done analytically and is rarely done
> numerically. &#4294967295;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?
>
> Fred

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

"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

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. &#4294967295;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. &#4294967295;

Nah, we don't.

Rune