On Apr 26, 10:04�pm, dvsarwate <dvsarw...@yahoo.com> wrote:
> On Apr 26, 10:19�am, Clay <c...@claysturner.com> wrote:
>
> > Your version "c" at 1st blush seems like it would be good, but a
> > little deeper exploration indicates that if the lengths are relatively
> > prime and the sequences are periodically extended, then your resulting
> > sequence is a sequence of constant value!
>
> Yes indeed. �More generally, the result is periodic
> with period equal to the greatest common divisor
> of the lengths, which gcd is, of course, 1 for the
> relatively prime case that you considered and a
> sequence of period 1 has constant value. �Oh well,
> back to the drawing board.....
>
> --Dilip Sarwate
It is a fun exercise!
Clay
Reply by dvsarwate●April 26, 20112011-04-26
On Apr 26, 10:19�am, Clay <c...@claysturner.com> wrote:
> Your version "c" at 1st blush seems like it would be good, but a
> little deeper exploration indicates that if the lengths are relatively
> prime and the sequences are periodically extended, then your resulting
> sequence is a sequence of constant value!
Yes indeed. More generally, the result is periodic
with period equal to the greatest common divisor
of the lengths, which gcd is, of course, 1 for the
relatively prime case that you considered and a
sequence of period 1 has constant value. Oh well,
back to the drawing board.....
--Dilip Sarwate
Reply by Fred Marshall●April 26, 20112011-04-26
On 4/26/2011 9:11 AM, robert bristow-johnson wrote:
> On Apr 25, 5:38 pm, Fred Marshall<fmarshallxremove_th...@acm.org>
> wrote:
>> On 4/25/2011 1:49 PM, dvsarwate wrote:
>>
>>
>>
>>> On Apr 25, 9:10 am, Jerry Avins<j...@ieee.org> wrote:
>>
>>>> To do that, arsalan would need to understand what circular convolution
>>>> is. That might be too much like actually *doing* the homework.
>>
>>> Not to do Arsalan's homework for him (her?), but
>>> how do comp.dsp-ers define the circular convolution
>>> of two sequences of different lengths (which is
>>> what Arsalan has in his question: lengths 4 and 3)?
>>
>>> (a) zero-pad the shorter sequence to have the
>>> same length as the longer one?
>
> it's the result of playing the waveform defined by the longer one into
> a LTI filter with h[n] defined by the shorter one.
>
>>
>>> (b) zero-pad both to length equal to the sum of
>>> the lengths (or the sum minus one for nitpickers)?
>
> a repetition of the linear convulotion of both zero padded.
>
>>> (c) periodically extend both to length equal to
>>> the least common multiple of the lengths?
>
> well it's another periodic waveform with filter (and both are missing
> harmonics).
>
>>> (d)?
>>
>
> from a POV of normal, everyday communication with the DSP discipline,
> i would suggest it's about equal-lengthed sequences and is the result
> of the inverse DFT of the product of the DFTs of the two given
> sequences.
>
>>> Another question that springs to mind is
>>> "If linear convolution is desired, why should
>>> circular convolution be used at all unless the
>>> intent is to use the FFT algorithm to speed
>>> up the calculations?" Absent the use of the
>>> FFT algorithm, using DFTs to compute a
>>> circular convolution in order to get a linear
>>> convolution result seems to be similar to
>>> scratching your left ear with your right hand
>>> after wrapping your arm twice around your
>>> head.
>
> other than testing the whole thing. if it doesn't work, you might
> wanna know if it's the FFT or your connection to it.
>
>>> Heck of a way to get rid of an itch!
>>
>> Indeed a heck of a way!
>>
>> But "compute a circular convolution in order to get a linear convolution
>> result [of finite sequences]" is, or should almost always be, the
>> objective. That is, I don't imagine circular convolution results that
>> are different than the linear convolution results - unless one of the
>> sequences is rather arbitrarily truncated in order to be treated as
>> finite. Even in that case, multiple results can be combined to yield
>> the "continuous" result.
>>
>> So we agree that it *must* be to get speedup to be sensible and, by the
>> way, it's possible to get even greater speedup by performing some tricks
>> in frequency (as used in interpolation).
>>
>
> it can't be just people who think about waveform generation for audio/
> musical application. aren't there other people who have to generate
> periodic waveforms for speech or image or communications or
> something? you have to barf out a waveform into some channel, and you
> have some theoretical idea what the channel is gonna do to your
> waveform (some filter). so you time-alias the impulse response of
> that filter, DFT it, apply the complex reciprocal to it and multiply
> by the DFT of the desired waveform at the other end of the channel?
>
> i'll admit, that for me i think of a note waveform and the other end
> of the channel is one's eardrum or something like that. but this kind
> of application has to be a lot broader than musical note synthesis.
>
> r b-j
>
>
I wasn't thinking beyond the sequence-sequence convolution operation really.
If one wants to generate a periodic waveform using something similar
then sure.... But then I'd be thinking about a repetitive operation
that goes beyond circular. Or I might be thinking that "circular"
includes periodic sequences inside it. Or ....
Fred
Fred
Reply by Fred Marshall●April 26, 20112011-04-26
On 4/26/2011 4:49 AM, dvsarwate wrote:
> On Apr 26, 12:46 am, dbd<d...@ieee.org> wrote:
>
>> My thought provoking approach is to ask, "What size circle?"
>
> I suggested three alternatives (a), (b), and (c) earlier
> as well as a "free response" but nobody was willing
> to commit to any of them. I guess people are still
> thinking about it, Dale, or more likely, will just ignore
> the question.
>
> Dilip Sarwate
>
Just for reference and....
Really I wasn't trying to *do* the homework.
(a) zero-pad the shorter sequence to have the
same length as the longer one?
No. This won't do.
(b) zero-pad both to length equal to the sum of
the lengths (or the sum minus one for nitpickers)?
This is the minimum length needed - so it can be greater.
(c) periodically extend both to length equal to
the least common multiple of the lengths?
perhaps if one has a reason to do so ... periodically??
Fred
(d)?
Reply by robert bristow-johnson●April 26, 20112011-04-26
On Apr 25, 5:38�pm, Fred Marshall <fmarshallxremove_th...@acm.org>
wrote:
> On 4/25/2011 1:49 PM, dvsarwate wrote:
>
>
>
> > On Apr 25, 9:10 am, Jerry Avins<j...@ieee.org> �wrote:
>
> >> To do that, arsalan would need to understand what circular convolution
> >> is. That might be too much like actually *doing* the homework.
>
> > Not to do Arsalan's homework for him (her?), but
> > how do comp.dsp-ers define the circular convolution
> > of two sequences of different lengths (which is
> > what Arsalan has in his question: lengths 4 and 3)?
>
> > (a) zero-pad the shorter sequence to have the
> > same length as the longer one?
it's the result of playing the waveform defined by the longer one into
a LTI filter with h[n] defined by the shorter one.
>
> > (b) zero-pad both to length equal to the sum of
> > the lengths (or the sum minus one for nitpickers)?
a repetition of the linear convulotion of both zero padded.
> > (c) periodically extend both to length equal to
> > the least common multiple of the lengths?
well it's another periodic waveform with filter (and both are missing
harmonics).
> > (d)?
>
from a POV of normal, everyday communication with the DSP discipline,
i would suggest it's about equal-lengthed sequences and is the result
of the inverse DFT of the product of the DFTs of the two given
sequences.
> > Another question that springs to mind is
> > "If linear convolution is desired, why should
> > circular convolution be used at all unless the
> > intent is to use �the FFT algorithm to speed
> > up the calculations?" �Absent the use of the
> > FFT algorithm, using DFTs to compute a
> > circular convolution in order to get a linear
> > convolution result seems to be similar to
> > scratching your left ear with your right hand
> > after wrapping your arm twice around your
> > head.
other than testing the whole thing. if it doesn't work, you might
wanna know if it's the FFT or your connection to it.
> > �Heck of a way to get rid of an itch!
>
> Indeed a heck of a way!
>
> But "compute a circular convolution in order to get a linear convolution
> result [of finite sequences]" is, or should almost always be, the
> objective. �That is, I don't imagine circular convolution results that
> are different than the linear convolution results - unless one of the
> sequences is rather arbitrarily truncated in order to be treated as
> finite. �Even in that case, multiple results can be combined to yield
> the "continuous" result.
>
> So we agree that it *must* be to get speedup to be sensible and, by the
> way, it's possible to get even greater speedup by performing some tricks
> in frequency (as used in interpolation).
>
it can't be just people who think about waveform generation for audio/
musical application. aren't there other people who have to generate
periodic waveforms for speech or image or communications or
something? you have to barf out a waveform into some channel, and you
have some theoretical idea what the channel is gonna do to your
waveform (some filter). so you time-alias the impulse response of
that filter, DFT it, apply the complex reciprocal to it and multiply
by the DFT of the desired waveform at the other end of the channel?
i'll admit, that for me i think of a note waveform and the other end
of the channel is one's eardrum or something like that. but this kind
of application has to be a lot broader than musical note synthesis.
r b-j
Reply by Clay●April 26, 20112011-04-26
On Apr 26, 7:49�am, dvsarwate <dvsarw...@yahoo.com> wrote:
> On Apr 26, 12:46�am, dbd <d...@ieee.org> wrote:
>
> > My thought provoking approach is to ask, "What size circle?"
>
> I suggested three alternatives (a), (b), and (c) earlier
> as well as a "free response" but nobody was willing
> to commit to any of them. �I guess people are still
> thinking about it, Dale, or more likely, will just ignore
> the question.
>
> Dilip Sarwate
Certainly unequal lengths in something that is "supposed" to have
similar lengths throws a wrench into the process.
Your version "c" at 1st blush seems like it would be good, but a
little deeper exploration indicates that if the lengths are relatively
prime and the sequences are periodically extended, then your resulting
sequence is a sequence of constant value!
I'll give some more thought to variants "a" and "b"
Clay
Reply by Dave●April 26, 20112011-04-26
On Apr 25, 9:31�pm, Rune Allnor <all...@tele.ntnu.no> wrote:
> On Apr 25, 10:49�pm, dvsarwate <dvsarw...@yahoo.com> wrote:
>
> > On Apr 25, 9:10�am, Jerry Avins <j...@ieee.org> wrote:
>
> > > To do that, arsalan would need to understand what circular convolution
> > > is. That might be too much like actually *doing* the homework.
>
> > Not to do Arsalan's homework for him (her?), but
> > how do comp.dsp-ers define the circular convolution
> > of two sequences of different lengths (which is
> > what Arsalan has in his question: lengths 4 and 3)?
>
> As always, I choose the more controversial approach:
>
> As far as I am concerned, circular convolution is an
> unwanted side effect that appears if / when one implements
> the 'usual' convolution by the DFT / FFT. I am not aware
> of any applications where the circular convolution is desired.
>
> Rune
Take a look at Papoulis' description of Chirp Scaling - For a digital
implementation of the same thing - it explicitly requires a circular
convolution.
The main idea is how to get f(at) from f(t) where a is a scalar.
Papoulis showed that by using a combination of blocks consisting of
mixers with chirp signals and filters with chirp impulse responses you
can generate f(at). This technique forms the basis of Chirp Scaling
algorithms in Synthetic Aperture Radar.
An alternative application allows you to generate the Fourier
Transform of the signal purely in the time domain. So starting with
f(t) you can come up with F(t), where t in F(t) actually represents
the frequency domain.
Cheers,
David
Reply by dvsarwate●April 26, 20112011-04-26
On Apr 26, 12:46�am, dbd <d...@ieee.org> wrote:
> My thought provoking approach is to ask, "What size circle?"
I suggested three alternatives (a), (b), and (c) earlier
as well as a "free response" but nobody was willing
to commit to any of them. I guess people are still
thinking about it, Dale, or more likely, will just ignore
the question.
Dilip Sarwate
Reply by Fred Marshall●April 26, 20112011-04-26
On 4/25/2011 4:05 PM, Jerry Avins wrote:
>
> I don't agree. Occam's razor suggests that circular convolution is
> merely the way the problem was assigned.
>
> Jerry
> --
spoilsport! :-)
Reply by Fred Marshall●April 26, 20112011-04-26
On 4/25/2011 6:31 PM, Rune Allnor wrote:
> On Apr 25, 10:49 pm, dvsarwate<dvsarw...@yahoo.com> wrote:
>> On Apr 25, 9:10 am, Jerry Avins<j...@ieee.org> wrote:
>>
>>
>>
>>> To do that, arsalan would need to understand what circular convolution
>>> is. That might be too much like actually *doing* the homework.
>>
>> Not to do Arsalan's homework for him (her?), but
>> how do comp.dsp-ers define the circular convolution
>> of two sequences of different lengths (which is
>> what Arsalan has in his question: lengths 4 and 3)?
>
> As always, I choose the more controversial approach:
>
> As far as I am concerned, circular convolution is an
> unwanted side effect that appears if / when one implements
> the 'usual' convolution by the DFT / FFT. I am not aware
> of any applications where the circular convolution is desired.
>
> Rune