Re: Zero Padding in radix 2 FFT

Hmmmm.... long ago I suggested that we make it clear when we're talking
about theory or practice. I don't think the notion was very well received
and I think the idea was that we'd make it clear.

No such luck in this thread. We read about clear procedures / methods
("theoretical") and then somebody says: "yeah, but you can't reconstruct a
[real world] waveform with it" Hmmmmm....

I wonder if we can't just use a set of (theoretical) identities to make
things clear:

1)
continuous, infinite time <Fourier Transform> continuous, infinite frequency
and its inverse
2)
DISCRETE, infinite time <Fourier Transform> continuous, infinite frequency
and PERIODIC
(regular time intervals) and its inverse

3)
continuous, infinite time <Fourier Transform> DISCRETE, infinite frequency
and PERIODIC and its inverse

4)
DISCRETE, infinite time <Fourier Transform> DISCRETE, infinite frequency
and PERIODIC
and PERIODIC and its inverse

Now, all of these Fourier Transforms work just fine but we can make some
simplifying changes:
A) When a function is PERIODIC, then sums can be taken over a single period.
B) When a function is DISCRETE, then sums can be taken at discrete points.
C) When a function is DISCRETE PERIODIC, then sums can be taken over a
single period at discrete points.

[I will use AF, BF, CF to mean "forward" Fourier Transforms or
time-to-frequency and AI, BI, CI to mean "inverse" Fourier Transforms or
frequency-to-time in case the subtleties are important.....]

This leads to:
2) DISCRETE, infinite time <Fourier Transform> continuous, infinite
frequency and PERIODIC
(regular time intervals) and its inverse

2BF)When a function is DISCRETE, then sums can be taken at discrete points -
so in the "forward transform" we can have a Discrete Time Fourier Transform
(which is still an infinite sum)

2AI) When a function is PERIODIC, then the sums can be taken over a single
period - so in the "inverse transform" we can have a continous, finite
length, transform. This is in the same form as computation of a Fourier
Series but operating in the frequency domain.

It also leads to:
3)
continuous, infinite time <Fourier Transform> DISCRETE, infinite frequency
and PERIODIC and its inverse

3AF) When a function is PERIODIC, then sums can be taken over a single
period. I'm pretty sure that this is the classical Fourier Series
calculation....

3BI) When a function is DISCRETE, then sums can be taken at discrete points.
I'm pretty sure that this is the classical reconstruction from an infinite
set of Fourier Series coefficients.

Now, isn't that interesting? We have not yet said anything about Nyquist at
all and have avoided going into what happens if the infinite sums are
truncated as in Gibbs' phenomenon.
I think that's pretty cool.

Two things (and their duals) remain to talk about (theoretically):
- Discrete/Periodic
- Periodic/Discrete
- Finite time
- Finite frequency

Let's talk about the first dual pair first:
4)
DISCRETE, infinite time <Fourier Transform> DISCRETE, infinite frequency
and PERIODIC
and PERIODIC and its inverse

4BF) When a function is DISCRETE, then sums can be taken at discrete points.
4AF) When a function is PERIODIC, then sums can be taken over a single
period.
So, this leads to a finite sum.

4BI) When a function is DISCRETE, then sums can be taken at discrete points.
4AI) When a function is PERIODIC, then sums can be taken over a single
period.
This also leads to a finite sum.

So, the forward transform can be a Discrete and Finite Time, Fourier
Transform.
And, the inverse transform can be a Discrete and Finite Frequency, Inverse
Fourier Transform.
I think this is normally called the Discrete Fourier Transform (being
discrete in both domains and, correspondingly, periodic in both domains).

OK - still no Nyquist or Gibbs

Now the last dual pair:
- Finite time
- Finite frequency

The first one is the most comfortable to people I think because we just
*know* there isn't any infinite time for us to deal with.

Now we have:

1)
continuous, finite time <Fourier Transform> continuous, infinite frequency
and its inverse
2)
DISCRETE, finite time <Fourier Transform> continuous, infinite frequency
and PERIODIC
(regular time intervals) and its inverse

3) is a contraction in terms..... it can't be both periodic (infinite) and
finite (still theory)
continuous, finite time <Fourier Transform> DISCRETE, infinite frequency
and PERIODIC and its inverse

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

So, other than changing the time domain notation from "infinite" to
"finite", there is no other change in any of these cases. However, there is
a change in how the forward transforms can be dealt with:

1) can use a finite integral
2) can use a finite sum
3) is a contradiction
4) is a contradiction

So, then what's the catch with 3 and 4?
It's that they are contradictions for the functions they describe.
However, if we modify our perspective a little bit then they work. Like
this:

3*) continuous and PERIODIC <Fourier Transform> DISCRETE, infinite
frequency
and its inverse
We have already seen:
3AF) When a function is PERIODIC, then sums can be taken over a single
period. (Fourier Series integral calculation).
So, if the function is periodic then we can do the computation over a finite
time (an integral number of periods).

4*)DISCRETE and PERIODIC <Fourier Transform> DISCRETE, infinite frequency
and PERIODIC
and its inverse
We have already seen:
4AF) When a function is PERIODIC, then sums can be taken over a single
period.
So, if the function is periodic then we can do the sum over a finite time
(an integral number of periods).

Now, turn these observations around. If the sum or integral is over a
finite time AND IF the frequency domain is only calculated on a discrete set
of points, then how do we distinguish the result from one which was done
over a single period of a periodic (infinite) function?
I think the answer is: "you can't". Once the frequency domain is sampled
then the time domain *is* periodic.
[And, temporal aliasing results from only computing the frequency samples at
discrete points. Nyquist].

Finally, finite frequency (lowpass case):

1)
continuous, infinite time <Fourier Transform> continuous, finite frequency
and its inverse
2) is a contradiction
DISCRETE, infinite time <Fourier Transform> continuous, finite frequency
and PERIODIC
(regular time intervals) and its inverse

3)
continuous, infinite time <Fourier Transform> DISCRETE, finite frequency
and PERIODIC and its inverse

4) is a contradiction
DISCRETE, infinite time <Fourier Transform> DISCRETE, finite frequency and
PERIODIC
and PERIODIC and its inverse

Here, frequency was changed from "infinite" to "finite".
Now 2 and 4 are contradictions and the same kind of treatment as was used
for forward transforms in the time domain cases 3 and 4 can be applied to
the inverse transforms for cases 2 and 4.

Skipping the repetition of 2 and 4 with modifications we can make similar
observations about the inverse transforms.

Now, turn these observations around. If the sum or integral is over a
finite frequency AND IF the time domain is only calculated on a discrete set
of points, then how do we distinguish the result from one which was done
over a single spectral period of a periodic (infinite) function of
frequency?
The answer is: "you can't". Once the time domain is sampled then the
frequency domain *is* periodic.
[And, spectral aliasing results from only computing (or measuring) the time
samples at discrete points. Nyquist].

Here is the bottom line:

Until we sample otherwise continuous functions there is no problem in any of
these cases.
As soon as either temporal or spectral sampling (or both) is done, then
there can (or will?) be aliasing.

What we do in practice is to pretend that real world signals are both
bandlimited and time limited. Then we sample in time and frequency alike
and use the DFT. In theory the signals cannot be both bandlimited and time
limited at the same time - that is, the same signal cannot have both
properties.

It's always interested me that we are happy to worry the heck out of
spectral aliasing but don't think much about temporal aliasing. I think
there may be a practical reason for this but I've not articulated one. I do
know that some frequency domain interpolation methods can cause temporal
trillies far removed from abrupt changes (temporal aliasing).

Fred





.

Relevant Pages

  • 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
    ... > sinusoidals is periodic, i.e. ... > integral and sum over one *period* of the composite signal. ... does not have a well-defined Fourier transform. ... > The reason is that the infinite-extent signal has infinite energy, ...
    (comp.dsp)
  • 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: infinity
    ... One that /shows/ the completion of an infinite iterated (i.e., ... It follows from the problem statement that any change to the vase ... I would like to see a mathematical description of an infinite discrete ... proper continuum, free of the crippling need to move from point to ...
    (sci.math)
  • Re: does a mean vector exist?
    ... There is nothing finite or discrete about ... Therefore, an infinite continuum cannot be added or divided, esp. ... There might be a mean vector if we externalize and generalize the ... But what is external to the vector set might be finite ...
    (sci.math)