Reply by Rune Allnor 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. &#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
Reply by Fred Marshall 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 Rune Allnor 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. &#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
Reply by Rune Allnor 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 Fred Marshall 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. > > 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
Reply by Rune Allnor August 17, 20082008-08-17
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
Reply by Fred Marshall August 17, 20082008-08-17
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);

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 object to the practice of doing DFT/*/IDFT process without appending 
enough zeros to eliminate overlap.  The Matlab "filter" function generates a 
unit sample response of arbitrary length according to the length of the 
input sequence.  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.

It seems to me that the proper implementation would go like this:

%Define IIR filter coefficients:
a=[1,-0.9];
%
%Define unit sample inputs
%
uL(1)=1;
uL(2:159)=0;
uS(1)=1;
uS(2:39)=0;
%
%Case I - Linear convolution, long filter.**********
%
%Input length is 80 samples (really 10 nonzero samples);
%Define long input with 10-sample gate
x(1:10)=1;
%
%M + N -1 will be 80 + 80 - 1 = 159
x(11:159)=0;
%
%
%Filter unit sample response length is 80 samples
%
%Define long filter unit sample response
h1 = filter(1,a,uL);
%Choose to limit filter unit sample response to 80 samples
%Whatever the choice (even if it's 159), it's now a FIR
h1(81:159)=0;
%
%Define long filter output
%
y1=conv(x,h1);
%
%Case II - Linear convolution, short filter.**********
%
%Input length is 20 samples (really 10 nonzero samples);
%Define short input with 10-sample gate
%M + N - 1 will be 20 + 20 -1 = 39
%
xx=x(1:39);
%
%Define short filter unit sample response
%
h2=h1(1:20);
h2(21:39)=0;
%
%Define short filter output
y2=conv(xx,h2);
%
clf
subplot(3,1,1)

plot(y1(1:159),'b'),axis [0 160 0 8]
%axis manual [0 160 0 8]
hold on
plot(y2,'r'),axis [0 160 0 8]
title('Linear convolution')
legend('N = 80','N = 20')

%Case III - Circular convolution, long filter.**********
%
%Compute long circular convolution with DFT/*/IDFT
%Sequences are length 159
%
%FFT of long input
X=fft(x);
%FFT of filter
H1=fft(h1);
%FFT of long output
Y=X.*H1;
y3=real(ifft(Y));

%Case IV - Circular convolution, short filter.**********
%Sequences are length 39
%
%FFT of short input
Xx=fft(xx);
%FFT of filter
H2=fft(h2);
%FFT of short output
Yy=Xx.*H2;
y4=real(ifft(Yy));

subplot(3,1,2)
axis equal
plot(y3,'b')
hold on
plot(y4,'r')
title('Circular convolution')
legend('N = 80','N = 20')

%Case V - Circular convolution, too-short sequences.**********
%Sequences are length 20
%
%FFT of short input
Zz=fft(xx(1:20));
%FFT of filter
H3=fft(h2(1:20));
%FFT of short output
Qq=Zz.*H3;
y5=real(ifft(Qq));

subplot(3,1,3)
axis equal
plot(y3,'b')
hold on
plot(y5,'g')
title('Overlapped Circular convolution')
legend('N = 80 not overlapped','N = 20 overlapped')

Fred



Reply by jim August 16, 20082008-08-16

m26k9 wrote:
> > If you want to know about CP in OFDM, I have a simple graphical > representation done here: > just-tech-stuff.hobby-site.com/PFDM_CP.html
Thanks for posting that Maduranga. There is an error in your link it should be: http://just-tech-stuff.hobby-site.com/OFDM_CP.html ----== 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 jim August 16, 20082008-08-16

robert bristow-johnson wrote:
> > On Aug 16, 9:40 am, jim <"sjedgingN0sp"@m...@mwt.net> wrote: > ... > > > > Yes one would hope so since your interpretation of the question was > > How do I use circular convolution to achieve the same result. > > Myself, I didn't think that was the question. > > my only interpretation of the question was this: > > > > On Aug 11, 10:28 pm, "Mani007" <thugulys...@hotmail.com> wrote: > > > ... > > > > I would just like to ask how can I compute the circular convolution of the > > > > two sequences: {x(n)} = {4,3,2,1} and {h(n)} = {5,6,7} > > that question cannot be answered until one resolves the problem of the > two sequences not being the same length. > > > If by some wild chance he really wanted to know how to do circular > > convolution when he said "I know how to compute the linear > > convolution, but I am stuck as to how to do the circular convolution." > > And if he would like to achieve a result without using DFT then he > > doesn't need to be concerned that x[] and h[] are not the same length. > > i have no idea how to do circular convolution (which is commutative) > without x[n] and h[n] being the same length. either in the frequency > domain (with the DFT) or directly in the time domain. i just cannot > find nor infer a definition of such an operation.
Yes I see. But why would it matter to the OP if RBJ can or cannot find or infer a definition as long as he has a working implementation? -jim
> > 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 =---
Reply by robert bristow-johnson August 16, 20082008-08-16
On Aug 16, 9:40 am, jim <"sjedgingN0sp"@m...@mwt.net> wrote:
...
> > Yes one would hope so since your interpretation of the question was > How do I use circular convolution to achieve the same result. > Myself, I didn't think that was the question.
my only interpretation of the question was this:
> > On Aug 11, 10:28 pm, "Mani007" <thugulys...@hotmail.com> wrote: > > ... > > > I would just like to ask how can I compute the circular convolution of the > > > two sequences: {x(n)} = {4,3,2,1} and {h(n)} = {5,6,7}
that question cannot be answered until one resolves the problem of the two sequences not being the same length.
> If by some wild chance he really wanted to know how to do circular > convolution when he said "I know how to compute the linear > convolution, but I am stuck as to how to do the circular convolution." > And if he would like to achieve a result without using DFT then he > doesn't need to be concerned that x[] and h[] are not the same length.
i have no idea how to do circular convolution (which is commutative) without x[n] and h[n] being the same length. either in the frequency domain (with the DFT) or directly in the time domain. i just cannot find nor infer a definition of such an operation. r b-j