Re: Zero Padding in radix 2 FFT


"Rune Allnor" <allnor@xxxxxxxxxxxx> wrote in message
news:1136633990.170197.267160@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
>
> Fred Marshall wrote:
>> "Stan Pawlukiewicz" <spam@xxxxxxxxxxxxxx> wrote in message
>> news:dplqnc$m0k$1@xxxxxxxxxxxxxxxxxxxxxx
>> >
>>
>>
>> >
>> > My essential point is that you have a characteristic called "periodic"
>> > that is not necessarily preserved under the operations of addition and
>> > time shift.
>> >
>>
>> Interesting.... so this is a troll, eh Stan?
>
> I don't know if Stan a troll, but he is right.
>
>> I assume you mean two periodic functions cannot necessarily be shifted
>> and
>> added unless there is a rational relationship between their frequencies?
>>
>> a + b = c where a and b are periodic and not related by a rational number
>> in
>> period.
>>
>> Summation is a linear operation. So that's OK.
>> But the property of periodicity is destroyed because its not joint.
>
> Exactly. In time domain this is sort of "obvious". Consider two
> continuous
> sinusoidals of infinite extent and with frequencies f1=f and f2
> =sqrt(2)*f.
> There exists no period T and integer n such that the sum of these
> sinusoidals is periodic, i.e.
>
> sin(2*pi*f1*t)+sin(2*pi*f2*t)=sin(2*pi*f1*t+nT)+sin(2*pi*f2*t+nT)
>
> does not hold for any n and T.
>
>> All that means is that more specific methods that would take advantage of
>> periodicity cannot be used. That may be a big deal in some limited
>> context
>> but sure not a big deal in the overall scheme of things. I might say:
>> "Oh
>> damn! I can't use a finite sum.... what a bummer!"
>
> Formally, yes. And the problem is even worse, as I will show below.
> Both the Fourier series and the DFT work under the constraint that the
> integral and sum over one *period* of the composite signal. While the
> sinusoidals are periodic in their own right, sums of sinusoidals with
> non-rational ratios of frequencies are not periodic, and the Fourier
> series/DFT can not be computed. Formally speaking.
>
> Even worse, the signal comprising two sinusoidals of non-rational
> frequency ratio, does not have a well-defined Fourier transform.
> The reason is that the infinite-extent signal has infinite energy,
>
> E = integral |sin(2*pi*f1*t)+sin(2*pi*f2*t)|^2dt = infinite
>
> when the integral limits are -infinite and +infinite.
>
> So basically, the Fourier transform is not defined for a signal
>
> x(t)=sin(2*pi*f1*t)+sin(2*pi*f2*t), -inf < t < inf
>
> where the ratio f1/f2 is non-rational.
>
>> and then remember that
>> I have a boss and I'm going to have to go ahead and do an integral
>> instead
>> in order to finish my work.
>
> Now the philosophical aspects of a limited-length observation
> of a data set becomes important, as John Monro and I discussed
> in a different subthread. Since you never have an infinitely long
> data sequence to work with, one uses the DFT and handles
> the inherent and "weird" assumption about the signal being
> periodic, as best one can.
>
>> Surely you don't mean to say that when more specific / simpler methods
>> can
>> be used .. that they should not? That would deny the Fourier Series -
>> which
>> is just a particular form of the Fourier Transform.......
>
> Formally, there are no Fourier transforms that can be used to analyze
> the infinitely long sum of two sines of non-rational frequency ratio.
> In practice, one never have to worry since one always have finite
> data records to work with.
>
>> The "periodicians" are in pretty good company I'd say. And for good
>> reason.
>>
>> Fred
>
> Rune

Rune,

Well, OK, now *that's* interesting - that the FT is not defined for such a
superposition of sinusoids. Not something that I would have thought of or
imagined.

I would have thought along these lines:

The FT is a linear transform so superposition applies.
Compute the FT of one sinusoid,
Compute the FT of the other sinusoid
Add the sinusoids together.
Compute the FT of the sum <<< which I guess you say is not defined
Add the two FTs from above together << I have to wonder why one cannot do
this?
Why does the IFFT of this latter sum not exist? It seems a pretty simple
function....

However interesting this may be, I assert that it is off topic or at least
ignoring the context provided. Everything I said was labeled to be
*theoretical*. So, infinite time is normal in that context.

This particular function is limited to:

1)
continuous, infinite time <Fourier Transform> continuous, infinite frequency
and its inverse

except the Fourier Transform isn't defined for this particular function.....

and, when arbitrarily time-limited is described by:

1)
continuous, finite time <Fourier Transform> continuous, infinite frequency
and its inverse

and, I believe this applies if you decide to use a time-limited version of
that same superposition of sinusoids. And this one exists.

However:
> Since you never have an infinitely long
> data sequence to work with, one uses the DFT and handles
> the inherent and "weird" assumption about the signal being
> periodic, as best one can.

This statement mixes two things - so I'll object a bit. From above, the
Fourier Transforms are continuous and not the Discrete variety. So far I've
only admitted to the finite time continuous version. If you want to
introduce "discrete" then there are other problems which I avoided in the
pairs but which you may need to deal with. I said:

4) is also a contradiction in terms for the same reason (still theory)
DISCRETE, finite time <Fourier Transform> DISCRETE, infinite frequency,
PERIODIC
and PERIODIC and its inverse

I probably should have mentioned that the "cases" 1 through 4 were intended
to be a *sequence* of cases going from the most general to the more
specific.

Fred


.

Relevant Pages

  • Re: Zero Padding in radix 2 FFT
    ... >> sinusoidals is periodic, i.e. ... does not have a well-defined Fourier transform. ... infinite time is normal in that context. ... > only admitted to the finite time continuous version. ...
    (comp.dsp)
  • Re: Zero Padding in radix 2 FFT
    ... Their resulting Fourier transform is continuous and consists of delta functions, but not at rationally related frequencies. ... continuous, infinite time continuous, infinite frequency ... DISCRETE, infinite time continuous, infinite frequency and PERIODIC ... When a function is PERIODIC, then sums can be taken over a single period. ...
    (comp.dsp)
  • Re: Zero Padding in radix 2 FFT
    ... continuous, infinite time continuous, infinite frequency ... DISCRETE, infinite time <Fourier Transform> continuous, infinite frequency ... When a function is PERIODIC, then sums can be taken over a single period. ...
    (comp.dsp)