A famous simple question on FFT

Suppose we have a function f(t) defined on the finite interval [a,b]. 

We first equally divide the interval [a,b] in to N-1 segments with N
points, namely t_1, t_2,...,t_k,...,t_N. 

Apparently, we have t_1=a,...,t_k=a+(k-1)(b-a)/(N-1),...,t_N=b. 

Now, we have a data set of N points, i.e. f(t_1),f(t_2),...,f(t_N). 

Next, let us apply the FFT on this data set, and denote the output data as
F(v_1),F(v_2),...,F(v_N). 

The question is:
v_1=?, v_2=?,...v_k=?,...,v_N=?


Could anyone get me a simple answer?

Many thanks!

(Remarks: FFT has been introduced in many text books including the famous
online book numerical recipe. However, for some curious reason, none of
these clearly state the above improtant question, although many have been
done on explaining how it works.)

OK, let's give it a shot:

"FFT gives the amplitudes and phases for a bunch of sine waves that, when
added together, will cross through the sample points."
This statement is not 100 % accurate, but I hope it gives the "big
picture".

There are at least two questions, where I would start investigating:
- Sampling the function, no matter whether the samples are FFTed later on,
can be good for a couple of surprises.

- FFT is one particular case of Discrete Fourier Transform (DFT). There
are plenty of references on the web.

-mn

On Sep 23, 8:30 am, "mnentwig" <mnent...@elisanet.fi> wrote:
> OK, let's give it a shot:
>
> "FFT gives the amplitudes and phases for a bunch of sine waves that, when
> added together, will cross through the sample points."
> This statement is not 100 % accurate, but I hope it gives the "big
> picture".

with a little post-processing (to convert real and imaginary parts to
amplitudes and phases), it *is* 100% correct.

> There are at least two questions, where I would start investigating:
> - Sampling the function, no matter whether the samples are FFTed later on,
> can be good for a couple of surprises.

yeah, but it doesn't change the fact that with that little post-
processing, the "FFT gives the amplitudes and phases for a bunch of
sine waves that, when added together, will cross through the sample
points."  that's a completely accurate statement and needs no further
qualification, does it?

> - FFT is one particular case of Discrete Fourier Transform (DFT). There
> are plenty of references on the web.

the FFT *is* the DFT.  an (efficient) implementation of it.

r b-j

Thanks all, anyway!

But, the question remains not being answered...

Could anyone give me the answers?

Thanks again!

-lucklman

>> with a little post-processing (to convert real and imaginary parts to
amplitudes and phases), it *is* 100% correct.

Yes... the little bit of postprocessing is what I had in mind, for
standard complex-valued DFT.

Well, my lawyer recommended the wording "... that may comprise a bunch of
sine waves...". But I think he's too cautious :)

But what I thought I should point out: 
- Sampling is good for some surprises
- FFT is good for more surprises. 
They can be understood one by one, and figuring out both at the same time
may be more difficult than it needs to be. 
From the OP I got the impression that somebody is right now getting it
"figured out". But I might be mistaken...

Cheers

Markus

lucklman wrote:
> Suppose we have a function f(t) defined on the finite interval [a,b]. 
> 
> We first equally divide the interval [a,b] in to N-1 segments with N
> points, namely t_1, t_2,...,t_k,...,t_N. 
> 
> Apparently, we have t_1=a,...,t_k=a+(k-1)(b-a)/(N-1),...,t_N=b. 
> 
> Now, we have a data set of N points, i.e. f(t_1),f(t_2),...,f(t_N). 
> 
> Next, let us apply the FFT on this data set, and denote the output data as
> F(v_1),F(v_2),...,F(v_N). 
> 
> The question is:
> v_1=?, v_2=?,...v_k=?,...,v_N=?
> 
> 
> Could anyone get me a simple answer?
> 
> Many thanks!
> 
> (Remarks: FFT has been introduced in many text books including the famous
> online book numerical recipe. However, for some curious reason, none of
> these clearly state the above improtant question, although many have been
> done on explaining how it works.)
> 

The FFT is a discrete operation so you would have something like this:

f[n] <--> F[k]

If you want to look at a sequence you would have something like

f[n=0] f[n=1] ... f[n=N-1] <-->  F[k=0] F[k=1] ... F[k=N-1]

So in your case you know the first sample (n=0) corresponds to time "a" 
and the last sample (n=N-1) corresponds to time "b".  (Side note, I'm 
using the notation "0 to N-1" rather than "1 to N" as you did since that 
is more common in electrical engineering.)

The corresponding output samples correspond to frequencies contained 
within the sample window [a,b].  The k=0 sample would correspond to DC 
(i.e. 0 frequency), the k=1 sample would correspond to 1/fs, the k=2 
sample would correspond to 2/fs, etc.  By "fs" I am referring to the 
sampling rate.  In your case fs would be (b-a)/N.

>lucklman wrote:
>> Suppose we have a function f(t) defined on the finite interval [a,b]. 
>> 
>> We first equally divide the interval [a,b] in to N-1 segments with N
>> points, namely t_1, t_2,...,t_k,...,t_N. 
>> 
>> Apparently, we have t_1=a,...,t_k=a+(k-1)(b-a)/(N-1),...,t_N=b. 
>> 
>> Now, we have a data set of N points, i.e. f(t_1),f(t_2),...,f(t_N). 
>> 
>> Next, let us apply the FFT on this data set, and denote the output data
as
>> F(v_1),F(v_2),...,F(v_N). 
>> 
>> The question is:
>> v_1=?, v_2=?,...v_k=?,...,v_N=?
>> 
>> 
>> Could anyone get me a simple answer?
>> 
>> Many thanks!
>> 
>> (Remarks: FFT has been introduced in many text books including the
famous
>> online book numerical recipe. However, for some curious reason, none
of
>> these clearly state the above improtant question, although many have
been
>> done on explaining how it works.)
>> 
>
>The FFT is a discrete operation so you would have something like this:
>
>f[n] <--> F[k]
>
>If you want to look at a sequence you would have something like
>
>f[n=0] f[n=1] ... f[n=N-1] <-->  F[k=0] F[k=1] ... F[k=N-1]
>
>So in your case you know the first sample (n=0) corresponds to time "a" 
>and the last sample (n=N-1) corresponds to time "b".  (Side note, I'm 
>using the notation "0 to N-1" rather than "1 to N" as you did since that

>is more common in electrical engineering.)
>
>The corresponding output samples correspond to frequencies contained 
>within the sample window [a,b].  The k=0 sample would correspond to DC 
>(i.e. 0 frequency), the k=1 sample would correspond to 1/fs, the k=2 
>sample would correspond to 2/fs, etc.  By "fs" I am referring to the 
>sampling rate.  In your case fs would be (b-a)/N.
>


Thank you very much for your considerate answer!

>lucklman wrote:
>> Suppose we have a function f(t) defined on the finite interval [a,b]. 
>> 
>> We first equally divide the interval [a,b] in to N-1 segments with N
>> points, namely t_1, t_2,...,t_k,...,t_N. 
>> 
>> Apparently, we have t_1=a,...,t_k=a+(k-1)(b-a)/(N-1),...,t_N=b. 
>> 
>> Now, we have a data set of N points, i.e. f(t_1),f(t_2),...,f(t_N). 
>> 
>> Next, let us apply the FFT on this data set, and denote the output data
as
>> F(v_1),F(v_2),...,F(v_N). 
>> 
>> The question is:
>> v_1=?, v_2=?,...v_k=?,...,v_N=?
>> 
>> 
>> Could anyone get me a simple answer?
>> 
>> Many thanks!
>> 
>> (Remarks: FFT has been introduced in many text books including the
famous
>> online book numerical recipe. However, for some curious reason, none
of
>> these clearly state the above improtant question, although many have
been
>> done on explaining how it works.)
>> 
>
>The FFT is a discrete operation so you would have something like this:
>
>f[n] <--> F[k]
>
>If you want to look at a sequence you would have something like
>
>f[n=0] f[n=1] ... f[n=N-1] <-->  F[k=0] F[k=1] ... F[k=N-1]
>
>So in your case you know the first sample (n=0) corresponds to time "a" 
>and the last sample (n=N-1) corresponds to time "b".  (Side note, I'm 
>using the notation "0 to N-1" rather than "1 to N" as you did since that

>is more common in electrical engineering.)
>
>The corresponding output samples correspond to frequencies contained 
>within the sample window [a,b].  The k=0 sample would correspond to DC 
>(i.e. 0 frequency), the k=1 sample would correspond to 1/fs, the k=2 
>sample would correspond to 2/fs, etc.  By "fs" I am referring to the 
>sampling rate.  In your case fs would be (b-a)/N.
>

I think you meant fs*1/N, fs*2/N,... and fs = N/(b-a) :)

On Sep 23, 4:43 am, "lucklman" <doctorle...@hotmail.com> wrote:
> Suppose we have a function f(t) defined on the finite interval [a,b].
>
> We first equally divide the interval [a,b] in to N-1 segments with N
> points, namely t_1, t_2,...,t_k,...,t_N.
>
> Apparently, we have t_1=a,...,t_k=a+(k-1)(b-a)/(N-1),...,t_N=b.
>
> Now, we have a data set of N points, i.e. f(t_1),f(t_2),...,f(t_N).
>
> Next, let us apply the FFT on this data set, and denote the output data as
> F(v_1),F(v_2),...,F(v_N).
>
> The question is:
> v_1=?, v_2=?,...v_k=?,...,v_N=?
>
> Could anyone get me a simple answer?

Why do you assume that there exists a simple answer?
What happens if you get 3 contradictory answers to your
3 repeated questions?

You could start with the definition of a DFT:
F(k) = sum (from n=0 to N-1) of f(i)*e^(2*pi*i*k*n/N)

Why is this interesting?

Each sum is the correlation of the input samples against
a bunch of orthogonal sine functions (in the complex
domain).  If your signal is composed of sine functions,
then the DFT/FFT will break it apart into its components.

Fourier proved that many arbitrary functions (there are
certain conditions) can be broken into a composition of
orthogonal sinusoids (plus DC, which can be considered
a sinusoid of frequency zero).

For real functions, you only get DC + N/2 sinusoids because
the frequencies above bin N/2 alias or overlap with those
below bin N/2.  However because the resulting DFT bins are
complex (degree of freedom 2, either real and imaginary,
or magnitude and phase), you end up with the same amount
of information (degrees of freedom) as in the original
signal.

An FFT is just a method or algorithm for calculating
a DFT, but with different efficiency and numerical
accuracy properties.


IMHO. YMMV.
--
rhn A.T nicholson d.0.t C-o-M

fatnbafan wrote:

> I think you meant fs*1/N, fs*2/N,... and fs = N/(b-a) :)

Yes, that's right.  Thanks for the polite correction.  The bin spacing 
is dependent upon the FFT size so there should definitely be an "N" in 
there!