Please help with Circular Convolution!

On 15 Aug, 17:35, "Fred Marshall" <fmarshallx@remove_the_x.acm.org>
wrote:
> "robert bristow-johnson" <r...@audioimagination.com> wrote in message
>
> news:52343262-125c-46fa-836a-9f4d89afff16@l64g2000hse.googlegroups.com...
...
> > 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. &#4294967295;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).

Circular and linear convolution *can* be (almost) equivalent,
but it requires a conciencius effort to get there.

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

Agreed.

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

Wrong. The wrap-around effects are there. The matlab script below
demonstrates the difference between linear and circular convolution
with an IIR filter y[n] = x[n]-0.9x[n-1].

The impulse response fades away in about 80 samples (x[70]=2.4e-4).
When you use linear convolution you see no difference between
the impulse response computed with a N=20 buffere length and the
impulse response computed with N=80 buffer length.

In the case of circular convolution the difference is large.
This difference is the result of wrap-around effects caused
by the circular convolution.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
a=[1,-0.9];
x=zeros(80,1);
x(1)=1;
y1 = filter(1,a,x);
xx=x(1:20);
y2=filter(1,a,xx);

clf
subplot(2,1,1)
plot(y1,'b')
hold on
plot(y2,'r')
title('Linear convolution')
legend('N = 80','N = 20')

X=fft(x);
Y=X./fft(a',length(x));
y3=real(ifft(Y));
Xx=fft(xx);
Yy=Xx./fft(a',length(xx));
y4=real(ifft(Yy));

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

> 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*?

An IIR is an IIR even if the data buffer is of finite length.

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

There is the third option: Decide at what length L the IIR
impulse response has become 'practically 0' and zero-pad
the signal to N+L-1, irrespective of how L relates to N.

Rune

On Aug 15, 12:07 pm, jim <"sjedgingN0sp"@m...@mwt.net> wrote:
>
>         Well x[n] is what is assumed to be cyclical by definition.

i didn't pick that up from the OP.  but maybe it's true

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

which is what i was saying (or meant to say) from the beginning.

>  But neither of those methods will be very efficient if
> x[n] is long and h[n] is short.

true, but if you break it up (which is what happens in fast
convolution), the result is theoretically the same as if h[n] was zerp-
padded and you did it in one big convolution.  i still see no
theoretical definition of circular convolution where the two sequences
are inherently different lengths.  one way or another, you end up
extending the shorter one to be as long as the longer.

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

and the way he put it, with one sequence longer than the other, made
his question impossible to answer directly until one settles this
issue of sequence lengths.

i still think that circular convolution is a commutative operation.
if that is the case, *either* x[n] or h[n] can be periodically
extended and the other finite length sequence be interpreted as the
FIR taps operating on this periodic sequence.  for the two sequences
to be commutative and the result to end up the same, the two sequences
*must* have definition of equal length.  *something* must be assumed
to extend the shorter one (and i do not mean any periodic extension of
it).

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

but then the shorter h[n] was assumed to be zero extended.

r b-j

robert bristow-johnson wrote:
> 
> On Aug 15, 12:07 pm, jim <"sjedgingN0sp"@m...@mwt.net> wrote:
> >
> >         Well x[n] is what is assumed to be cyclical by definition.
> 
> i didn't pick that up from the OP.  but maybe it's true

How can it be anything but true? I.E. It makes a lot less sense if you
assume anything else.

> 
> >  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.
> 
> which is what i was saying (or meant to say) from the beginning.
> 
> >  But neither of those methods will be very efficient if
> > x[n] is long and h[n] is short.
> 
> true, but if you break it up (which is what happens in fast
> convolution), the result is theoretically the same as if h[n] was zerp-
> padded and you did it in one big convolution. 

	That is still not very efficient. I mean in the example I gave if the
panorama image that needed to be filtered was 4000 pixels wide and the
filter was 5 pixels wide why would anyone consider using a DFT?
Whether you did the DFT piece wise or all at once it would still be
not very efficient way to approach the problem.
	


> i still see no
> theoretical definition of circular convolution where the two sequences
> are inherently different lengths.  one way or another, you end up
> extending the shorter one to be as long as the longer.

No actually not. If you assume the x[] is to be the periodic signal
(by convention) then if for some reason you want to convolve with h[n]
which is too long it will still need to be made the length of x[] to
do it by DFT/IDFT. That means h[] would need to be wrapped around to
be made shorter. If you were committed to using DFT to do this you
could use circular convolution to do that. But if you just forget
about DFT then there is no problem as long as you are able extend x[n]
as far as you need to.
	Here is what it boils down to: x[n] can be extended periodically in
either direction as far as you want (altho to extend beyond what your
program will actually access is wasteful). h[n] can be any length -
even much longer than the period of the lowest frequency in the signal
fed to it (that is all h[] being longer than x[] means). 
	


> 
> >         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?
> 
> and the way he put it, with one sequence longer than the other, made
> his question impossible to answer directly until one settles this
> issue of sequence lengths.

> 
> i still think that circular convolution is a commutative operation.
> if that is the case, *either* x[n] or h[n] can be periodically
> extended and the other finite length sequence be interpreted as the
> FIR taps operating on this periodic sequence.  


Yes that would be true, if we assume that the OP put all the letters
of the alphabet in a hat and blindly pulled the letters "x" and "h"
out of the hat to make his example. If you believe that there is no
special significance to his choice of using x and h in his example
then yes you are correct there is no way to know whether he means
circular with a period of 4 or circular with a period of 3. However,
if that is your assumption, it seems a lot wilder than mine which is
that he meant that x[n] was one cycle of a periodic signal. 

	If your point to the OP is that if you aren't careful to dot every i
and cross every t someone is likely to come along and quibble you to
death then you made your point nicely.

-jim


>for the two sequences
> to be commutative and the result to end up the same, the two sequences
> *must* have definition of equal length.  *something* must be assumed
> to extend the shorter one (and i do not mean any periodic extension of
> it).
> 
> >         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.
> 
> but then the shorter h[n] was assumed to be zero extended.
> 
> 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 =---

On Aug 15, 3:38 pm, jim <"sjedgingN0sp"@m...@mwt.net> wrote:
> robert bristow-johnson wrote:
>
> > On Aug 15, 12:07 pm, jim <"sjedgingN0sp"@m...@mwt.net> wrote:
>
> > > Well x[n] is what is assumed to be cyclical by definition.
>
> > i didn't pick that up from the OP.  but maybe it's true
>
> How can it be anything but true?

well, uh, maybe the application is good ol' fashioned fast
convolution.  where the intended final product is *linear* convolution
and (as Rune alluded to) we're using some tool (with an FFT inside it)
that doesn't inherently do linear convolution, but instead does
circular convolution very efficiently.

then is x[n] assumed to be circular?  not in my mind.  i would be
assuming that x[n] was N samples yanked out of a much longer stream of
samples and x[N-1] likely does *not* append very nicely to x[0].  but
because i have this nifty cicular convolver that's so damn efficient,
i'm gonna see what i can do to press it into service as a decent
linear convolver.  to do that, the only techniques i know of to make
my efficient circular convolver accomplish the task of linear
convolution are "OverLap Add" and "OverLap Save".

> I.E. It makes a lot less sense if you
> assume anything else.

when you do circular convolution, you assume, well at least *I* assume
that both x[n] and h[n] are *made* to be cyclical even if they weren't
defined to be such to start with.

>
> > >  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.
>
> > which is what i was saying (or meant to say) from the beginning.
>
> > >  But neither of those methods will be very efficient if
> > > x[n] is long and h[n] is short.
>
> > true, but if you break it up (which is what happens in fast
> > convolution), the result is theoretically the same as if h[n] was zero-
> > padded and you did it in one big convolution.
>
> That is still not very efficient.

the latter (one big convolution) is not.  but the point i was trying
to make is that if x[n] is long and h[n] is short, the result of
convolving them should be the same no matter what the technique.

> I mean in the example I gave if the
> panorama image that needed to be filtered was 4000 pixels wide and the
> filter was 5 pixels wide why would anyone consider using a DFT?

not for h[n] being 5 samples long, but what if we add a couple of
zeros to both and it was 400000 and 500?  you can see (i hope) that
treating the longer sequence as if it were indefinitely long (like a
real-time signal) and busting it up into segments (the optimal length
of the segments would be a function of the 500 and other cost
parameters if the FFT) and doing OLA or OLS *will* be the most
efficient.

> Whether you did the DFT piece wise or all at once it would still be
> not very efficient way to approach the problem.
>
> > i still see no
> > theoretical definition of circular convolution where the two sequences
> > are inherently different lengths.  one way or another, you end up
> > extending the shorter one to be as long as the longer.
>
> No actually not. If you assume the x[] is to be the periodic signal
> (by convention)

what convention?  none that i know of.

> then if for some reason you want to convolve with h[n]
> which is too long it will still need to be made the length of x[] to
> do it by DFT/IDFT. That means h[] would need to be wrapped around to
> be made shorter. If you were committed to using DFT to do this you
> could use circular convolution to do that. But if you just forget
> about DFT then there is no problem as long as you are able extend x[n]
> as far as you need to.
> Here is what it boils down to: x[n] can be extended periodically in
> either direction as far as you want (altho to extend beyond what your
> program will actually access is wasteful). h[n] can be any length -
> even much longer than the period of the lowest frequency in the signal
> fed to it (that is all h[] being longer than x[] means).
>
> > > 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?
>
> > and the way he put it, with one sequence longer than the other, made
> > his question impossible to answer directly until one settles this
> > issue of sequence lengths.
>
> > i still think that circular convolution is a commutative operation.
> > if that is the case, *either* x[n] or h[n] can be periodically
> > extended and the other finite length sequence be interpreted as the
> > FIR taps operating on this periodic sequence.
>
> Yes that would be true, if we assume that the OP put all the letters
> of the alphabet in a hat and blindly pulled the letters "x" and "h"
> out of the hat to make his example. If you believe that there is no
> special significance to his choice of using x and h in his example
> then yes you are correct there is no way to know whether he means
> circular with a period of 4 or circular with a period of 3. However,
> if that is your assumption, it seems a lot wilder than mine which is
> that he meant that x[n] was one cycle of a periodic signal.

i think your assumption is more of an assumption than one that
convolution (whether is circular or linear) is a commutative
operation.  i do recognize that we usually say that x[n] is the input,
y[n] is the output, and h[n] is the system characteristic that gets us
from the input to the output.  but theoretically it shouldn't matter
whether it's x[n] that comes first and h[n] comes second or the other
way around.  x and h should be interchangable in the convolution
operation.  in this context, i am not thinking at all about wasteful
coding (but i have that comment above, just FYI).

> If your point to the OP is that if you aren't careful to dot every i
> and cross every t someone is likely to come along and quibble you to
> death then you made your point nicely.

i wonder who is quibbling whom to death.  all's i said was that this
from the OP...:

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}

... was problematic in the very statement of the problem.  i do not
know, without extending h[n] by 1 sample or by shortening x[n] by 1
sample, how to show the OP how to do circular convolution.  i just
don't know how to do it because it doesn't make sense.  at least not
to me.

r b-j

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

Cheers.

robert bristow-johnson wrote:
> 
> On Aug 15, 3:38 pm, jim <"sjedgingN0sp"@m...@mwt.net> wrote:
> > robert bristow-johnson wrote:
> >
> > > On Aug 15, 12:07 pm, jim <"sjedgingN0sp"@m...@mwt.net> wrote:
> >
> > > > Well x[n] is what is assumed to be cyclical by definition.
> >
> > > i didn't pick that up from the OP.  but maybe it's true
> >
> > How can it be anything but true?
> 
> well, uh, maybe the application is good ol' fashioned fast
> convolution.  where the intended final product is *linear* convolution
> and (as Rune alluded to) we're using some tool (with an FFT inside it)
> that doesn't inherently do linear convolution, but instead does
> circular convolution very efficiently.

Yes I get it (I got it before when you explained it). You are saying
he was not literally asking how to implement circular convolution.
Instead he asking how to do linear convolution using
DFT/multiply/IDFT. Your interpretation is what he really should have
said was -> How can I avoid the effects of CC?

	I already said several posts back in response to someone else who
suggested I had misinterpreted what the OP wants that if that is what
he was asking then my suggestion was not what he wants.




> 
> then is x[n] assumed to be circular?  not in my mind.  i would be
> assuming that x[n] was N samples yanked out of a much longer stream of
> samples and x[N-1] likely does *not* append very nicely to x[0].  but
> because i have this nifty cicular convolver that's so damn efficient,
> i'm gonna see what i can do to press it into service as a decent
> linear convolver.  to do that, the only techniques i know of to make
> my efficient circular convolver accomplish the task of linear
> convolution are "OverLap Add" and "OverLap Save".
> 
> > I.E. It makes a lot less sense if you
> > assume anything else.
> 
> when you do circular convolution, you assume, well at least *I* assume
> that both x[n] and h[n] are *made* to be cyclical even if they weren't
> defined to be such to start with.

So if his question was I know how to do these two sequences via linear
convolution How do I arrive at the same answer with DFT/IDFT? Why not
just answer the question?  For example someone might respond to just
pad both sequences with zeroes to length 8 and do FFT/multiply/IFFT
and the result will be a sequence that doesn't wrap around. Not the
most efficient or elegant way but that should be enough to let him see
how it works.


> >
> > > >  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.
> >
> > > which is what i was saying (or meant to say) from the beginning.
> >
> > > >  But neither of those methods will be very efficient if
> > > > x[n] is long and h[n] is short.
> >
> > > true, but if you break it up (which is what happens in fast
> > > convolution), the result is theoretically the same as if h[n] was zero-
> > > padded and you did it in one big convolution.
> >
> > That is still not very efficient.
> 
> the latter (one big convolution) is not.  but the point i was trying
> to make is that if x[n] is long and h[n] is short, the result of
> convolving them should be the same no matter what the technique.

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.

	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.


-jim


> 
> > I mean in the example I gave if the
> > panorama image that needed to be filtered was 4000 pixels wide and the
> > filter was 5 pixels wide why would anyone consider using a DFT?
> 
> not for h[n] being 5 samples long, but what if we add a couple of
> zeros to both and it was 400000 and 500?  you can see (i hope) that
> treating the longer sequence as if it were indefinitely long (like a
> real-time signal) and busting it up into segments (the optimal length
> of the segments would be a function of the 500 and other cost
> parameters if the FFT) and doing OLA or OLS *will* be the most
> efficient.
> 





> > Whether you did the DFT piece wise or all at once it would still be
> > not very efficient way to approach the problem.
> >
> > > i still see no
> > > theoretical definition of circular convolution where the two sequences
> > > are inherently different lengths.  one way or another, you end up
> > > extending the shorter one to be as long as the longer.
> >
> > No actually not. If you assume the x[] is to be the periodic signal
> > (by convention)
> 
> what convention?  none that i know of.
> 
> > then if for some reason you want to convolve with h[n]
> > which is too long it will still need to be made the length of x[] to
> > do it by DFT/IDFT. That means h[] would need to be wrapped around to
> > be made shorter. If you were committed to using DFT to do this you
> > could use circular convolution to do that. But if you just forget
> > about DFT then there is no problem as long as you are able extend x[n]
> > as far as you need to.
> > Here is what it boils down to: x[n] can be extended periodically in
> > either direction as far as you want (altho to extend beyond what your
> > program will actually access is wasteful). h[n] can be any length -
> > even much longer than the period of the lowest frequency in the signal
> > fed to it (that is all h[] being longer than x[] means).
> >
> > > > 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?
> >
> > > and the way he put it, with one sequence longer than the other, made
> > > his question impossible to answer directly until one settles this
> > > issue of sequence lengths.
> >
> > > i still think that circular convolution is a commutative operation.
> > > if that is the case, *either* x[n] or h[n] can be periodically
> > > extended and the other finite length sequence be interpreted as the
> > > FIR taps operating on this periodic sequence.
> >
> > Yes that would be true, if we assume that the OP put all the letters
> > of the alphabet in a hat and blindly pulled the letters "x" and "h"
> > out of the hat to make his example. If you believe that there is no
> > special significance to his choice of using x and h in his example
> > then yes you are correct there is no way to know whether he means
> > circular with a period of 4 or circular with a period of 3. However,
> > if that is your assumption, it seems a lot wilder than mine which is
> > that he meant that x[n] was one cycle of a periodic signal.
> 
> i think your assumption is more of an assumption than one that
> convolution (whether is circular or linear) is a commutative
> operation.  i do recognize that we usually say that x[n] is the input,
> y[n] is the output, and h[n] is the system characteristic that gets us
> from the input to the output.  but theoretically it shouldn't matter
> whether it's x[n] that comes first and h[n] comes second or the other
> way around.  x and h should be interchangable in the convolution
> operation.  in this context, i am not thinking at all about wasteful
> coding (but i have that comment above, just FYI).
> 
> > If your point to the OP is that if you aren't careful to dot every i
> > and cross every t someone is likely to come along and quibble you to
> > death then you made your point nicely.
> 
> i wonder who is quibbling whom to death.  all's i said was that this
> from the OP...:
> 
> 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}
> 
> ... was problematic in the very statement of the problem.  i do not
> know, without extending h[n] by 1 sample or by shortening x[n] by 1
> sample, how to show the OP how to do circular convolution.  i just
> don't know how to do it because it doesn't make sense.  at least not
> to me.
> 
> 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 =---

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

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

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

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