is FFT always approximate?

Ron N. wrote:
> robert bristow-johnson wrote:
> > the DFT *always*, always, always, always, always periodically extends
> > the data that is passed to it, and if you don't keep that in mind, you
> > can get burned.
>
> Funny.  Last DFT I calculated fit in finite memory.

non-sequitur.  but if we do change the subject to that, earlier i said:
"the DFT inherently periodically extends whatever data you give it
(i.e. it assumes the N samples passed to it are representative of
exactly one period)."  it fits in finite memory because you only need
one cycle (N samples) to fully describe a periodic function.

>  Neither did it change the incoming audio sample stream.

windowing off the N samples (buy yanking it out of the audio stream) is
the first thing that changed something (before the DFT even gets it)
and then passing those N samples to the DFT is what periodically
extends them in both directions.  when you windowed off the N samples,
x[n] is undefined outside of [0 .. N) but when those N samples are
passed to the DFT, at that point x[n+N] = x[n] for all n.

>
> > that interpretation (periodic or circular extension) is the only one
> > that makes sense in general.  there are times when you may not need it,
> > but i can't think of any where it doesn't have some effect.  even the
> > wrapping of those sinc-like tales in the spectrum do to windowing in
> > the time domain.
>
> There can be no sinc-like tails if the function is periodic in the
> aperature, since under that assumption, only bin frequencies can
> exist.  Sinc-like tails can only wrap around if you postulate the
> existance of non-bin frequencies, which is inconsistant with the
> assumption that the results must be interpreted as if the data
> were periodically extended.

my point was that either way you look at it, you "virtually" always
have to consider the circular nature of the DFT.

say you have a sinusoid that completes precisely 8.5 cycles in the time
of the N sample aperture.

if you look at it as a sinusoid as a sinusoid of frequency of 8.5/N
cycles/sample (which is an interpretation and what i meant by if you
had informal or ad hoc information), then you see a big peak at bins 8
and 9 (and bins N-9 and N-8) with sinc-like tails coming off of it and
wrapping around at the boundary between x[N-1] and x[0].  circular
extension.

or you can look at it another way and say that you have a periodic
sequence in which in one period it makes 8.5 cycles of a sinusoid, does
a 180 phase jump and continues with another 8.5 sin waves in the next
period.  then bins x[1] and x[N-1] have the fundamental in it, x[2]
x[N-2] has the 2nd harmonic, etc.

the data is exactly the same and the DFT output will be exactly the
same, but it's interpreted differently.  now, given a priori
information, you might be able to look at the data and surmise (or
interpret) that it is not likely the latter case, but the former.
that's a human interpretation.  there is no numerical reason to say it
is the first vs. the second situation.

two different human interpretations.  doesn't matter to the DFT.
multiply the DFT output, X[k], by exp(-j*2*pi*m*k/N) and IDFT, and
you'll get x[(n-m)mod_N] if you don't periodically extend it (but that
mod operator essentially did the periodic extension for you) or the
more simple and natural x[n-m] if you do periodically extend it.

still, in any case, it's periodically extended.

> In normal use, the data or function outside any finite DFT can
> be either periodic or not.

sure, outside of the DFT the data can be anything, but once you window
some of it off (which has the windowing effects in the spectrum) and
pass it to the DFT, it treats it as periodic with period N.  if it does
it "sometimes" it does it always, because the DFT doesn't know the
difference.

>  Thus the results, interpreted as some
> sort of spectrum, are often underconstrained

that's the first interpretation above.  doesn't matter.  it still was
periodically extended and that will show when you apply shifting.

r b-j

robert bristow-johnson wrote:

> say you have a sinusoid that completes precisely 8.5 cycles in the time
> of the N sample aperture.
>
> if you look at it as a sinusoid as a sinusoid of frequency of 8.5/N
> cycles/sample (which is an interpretation and what i meant by if you
> had informal or ad hoc information), then you see a big peak at bins 8
> and 9 (and bins N-9 and N-8) with sinc-like tails coming off of it and
> wrapping around at the boundary between x[N-1] and x[0].  circular
> extension.
>
> or you can look at it another way and say that you have a periodic
> sequence in which in one period it makes 8.5 cycles of a sinusoid, does
> a 180 deg phase jump and continues with another 8.5 sin waves in the
> next period.  then bins x[1] and x[N-1] have the fundamental in it, x[2]
> x[N-2] has the 2nd harmonic, etc.

made a mistake.  meant to say "then bins X[1] and X[N-1] have the
fundamental in it, X[2] and X[N-2] have the 2nd harmonic, etc."

> the data is exactly the same and the DFT output will be exactly the
> same, but it's interpreted differently.  now, given a priori
> information, you might be able to look at the data and surmise (or
> interpret) that it is not likely the latter case, but the former.
> that's a human interpretation.  there is no numerical reason to say it
> is the first vs. the second situation.
>
> two different human interpretations.  doesn't matter to the DFT.
> multiply the DFT output, X[k], by exp(-j*2*pi*m*k/N) and IDFT, and
> you'll get x[(n-m)mod_N] if you don't periodically extend it (but that
> mod operator essentially did the periodic extension for you) or the
> more simple and natural x[n-m] if you do periodically extend it.
>
> still, in any case, it's periodically extended.

that's still the point i stand on, typo nonwithstanding.

r b-j

Ron N. wrote:

   ...

> It's actually the other way around.  The probability that an aperature
> on a random arbitrary function just happens to be an integer period
> window on a periodic or circular function looks close to zero.  So the
> periodic interpretation might be the exceptional one which requires
> information.

But the DFT doesn't "know" that. Given a set of samples, its output will 
be precisely the same whatever the periodicity of the samples data. 
Since the basis functions into which the sample set is decomposed are 
periodic and related by integers, their sum is periodic as well.

We may use our engineering smarts to apply the results only where they 
make sense, but periodicity is the beginning, and pruning comes later. 
You might call it fudging the result in order to make it consonant with 
reality.

   ...

> If I use a hammer to stir pasta, it's cleanliness and coefficient
> of drag in viscous fluids are probably more relevant than it's swing
> weight and impact resonance.

:-)

You also need to worry that strands of spaghetti don't get wedged in the 
claw. Or had you a ball-peen hammer in mind?

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

Ghostie wrote:
> "robert bristow-johnson" <rbj@audioimagination.com> wrote in
> news:1154406448.806363.135510@b28g2000cwb.googlegroups.com:
>
> snip....snip
>
> > Rune, the DFT doesn't know or care what the "true" data is.  it
>
> ship....snip
>
>
> It's data are, not data is.  Data is plural.  Datum is singular.  I would
> have thought that someone as anal retentive as yourself would have known
> that.

One difference between American and Imperial English is the treatment
of collective nouns. We know the "data" is plural, however the use of
the word is almost always as a collective noun and in American English
(spoken where RBJ lives), collective nouns are singular. Most of us
native English speakers understand this and accept this difference
without the need to try to correct someone on this usage.

Clay

Rune Allnor wrote:

(snip)

>>Rune, the DFT doesn't know or care what the "true" data is.  it
>>crunches the numbers the same in any case.  it does not know if the N
>>samples you pass it were N samples of some aperiodic sequence or if
>>those happened to be N samples defining exactly one period of a
>>periodic sequence.  it deals with it the same in either case and (this
>>is what is inexplicably controversial here sometimes) assumes it is the
>>latter.

The question was when is it an approximation.  It is an approximation
if the "true" data isn't periodic with the appropriate period.
I might even say that it isn't an approximation in that case, it
might not even be close.


(snip)

> I disagree with this as being a fundamental property of the DFT.
> I agree that this is a side effect when using the DFT to process
> finite samples of infinite sequences.

In comparing DFT, DST, and DCT the periodic boundary conditions
are fundamental to DFT.  DCT has the boundary condition that the
derivative goes to zero at the end.  DST has the function value
go to zero at the end.  As usual for standing waves, for the DST
and DCT the result has a period twice as long as the transform.

(snip)

> I find it ridiculous to claim that any finite sub sequence of
> an infinite series happens to represent exactly one period
 > of the infinite series.

If the infinite series gets small enough after a while, it
shouldn't be too bad.  In the discussion on bandwidth I was
remembering that an FM signal spectrum has infinite width,
but that doesn't stop placing FM radio stations 200kHz apart.

Most infinite signals aren't very interesting over a
finite amount of time.

-- glen

Clay wrote:

(snip)

>>It's data are, not data is.  Data is plural.  Datum is singular.  I would
>>have thought that someone as anal retentive as yourself would have known
>>that.

> One difference between American and Imperial English is the treatment
> of collective nouns. We know the "data" is plural, however the use of
> the word is almost always as a collective noun and in American English
> (spoken where RBJ lives), collective nouns are singular. Most of us
> native English speakers understand this and accept this difference
> without the need to try to correct someone on this usage.

I thought this was officially changed.  Consider, though, that in
bit terms data is plural, unless you only have one bit.

A glass of water contains many individual water molecules, so
shouldn't water be plural?

-- glen

glen herrmannsfeldt wrote:

   ...

> A glass of water contains many individual water molecules, so
> shouldn't water be plural?

In many languages, it is. I know little Hebrew, but water in Hebrew is 
"mayim"; the plural form of some word I suspect most Israelis have never 
uttered.

One goes to a one-spring spa to "take the waters". You can probably find 
other vestigial English usages of the plural.

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������