Please help with Circular Convolution!

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

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

On Aug 13, 5:49&#4294967295;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&#4294967295; 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

"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 

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

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

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

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

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

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

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