Re: Zero Padding in radix 2 FFT

Fred Marshall wrote:
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:

I never liked these so called identites. If I take two periodic functions and their periods are related by an irrational constant the sum is no longer periodic. Their resulting Fourier transform is continuous and consists of delta functions, but not at rationally related frequencies.

I find it easier to thing of everything being continuous, and use delta functions where appropriate. This makes everything linear with respect to addition of waveforms.



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