FFT computation

R.G. Stockwell wrote:
> <forums_mp@hotmail.com> wrote in message
[..]

> > The question.  For the simple data set ( and perhaps more compilcated )
> > shown can I literally look at the data and obtain the results ( knowing
> > the formula of course ) withouth much pen and paper?
>
> You're adoing a 4 point fft of a real valued time series, with your array
> "a" above.
> So yes, it is really easy. Just write out on a piece of paper
> the transformation matrix for a N=4 DFT.  Assume the time series
> is [A,B,C,D]
>
> First of all, the (zeroth point) DC value is just the total of the points
> (as you point out).
>
> The first point is the first harmonic, which is  [A - C, B-D]
>
> Second point is the nyquist point (since N is even, you know it
> has a zero imaginary part). The real part is A -B +C -D
>
> The third and final point is the symmetric reflection (i.e. with phase flip)
> of the first point.  (A-C, -B + D).
>
> So you have the result in the form (real,imag)
> A+B+C+D, 0
> A-C, B-D
> A-B+C-D, 0
> A-C, D-B
Incredible.. Thanks.

stev...@alum.mit.edu wrote:

> If your FFT is unnormalized, then you will probably see Inf because
> each unnormalized FFT of length N increases the L2 norm (the rms
> magnitude) of the data by sqrt(N)...and sqrt(8)^1000 overflows double
> precision.   Most FFT routines, including Matlab's, use an unnormalized
> forward transform.
I see...
>
> If you normalize the FFT by 1/sqrt(N), then it is a unitary
> (norm-preserving) operation, and repeatedly FFTing the array will
> simply oscillate between the input, its DFT, the input in reverse
> order, and the DFT in reverse order (with small deviations due to the
> finite precision).  e.g. in Matlab if you do fft(fft(x))/length(x) you
> get x in reverse order (except for the first element).  This can be
> proved easily from the DFT definition.
I'll try that in a few .. will have more questions I'm sure.

[...]

> In general, you compare it to an FFT computed in greater precision.
> What input data you use and how you do the comparison (e.g. what norm)
> depends somewhat on the application.  The method used for the FFTW
> accuracy graphs is described at:
>       http://www.fftw.org/accuracy/method.html
> and some references can be found at
> http://www.fftw.org/accuracy/comments.html
Indeed.  I've got print -outs here I'm perusing, trying to get my head
around the approach and the various numbers.

forums_mp@hotmail.com wrote:

   ...

> Indeed.  I did a forward, then another forward.  I was just trying to
> understand the _accuracy_ if you will.  I asked myself.  If I did a
> 
>>1000 forwards FFTs on 8 samples at what point do I see a QNAN or IND or ..  ?  The next question then was why?
> 
> I dont think I can answer the why yet but .. just learning the _hard_
> way right now.  Beyond the theory in the texts, playing with software
> and matlab helps me envision things alot better.

   ...

> This boils down to - for me - whose more accurate.  ...


You aren't seeing the accuracy. You're seeing how many significant 
figures the print routine was set to show. A number like -4.66966e-016, 
displayed to 12 significant figures, will print as '0'.

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

>
>krishna_sun82 wrote:
>
>>
>> Do you know the FFT algorithm?
>Workign through some basics in a course here once again :) - will get
>there soon.
>
>> If so, for the sequence given by you, you
>> can calculate a 4 point FFT in mind. Add everything for the first
term.
>> Add odd terms and subtract even terms to get the third one. The other
two
>> involves complex number calculations. It all depends on how fast you
can
>> add and subtract numbers.
>
>Lets see something here:
>I add the real and imaginaries for the first set of values:
>  Real:  0 + 1 + 2 + 3 = 6;
>  Imag: 0 +  0 + 0 + 0 = 0i;
>
>The second set of values... From the sound of it ( based on your reply
>), I could do:
>  Real : 1 + 3 ( odd ) - 2  = ( 4 - 2 ) = 2 ( I suspect I need to do
>this backwards to get the minus 2 )
>  Imaginary : ?

The thing you did is the calculation for the third term. I did not talk
about second and fourth. And when I said that you have add odd and
subtract even, I meant zero based indexing in time domain. Sorry for that
confusion.

>
>The third set of value:
>  ?
>Fourth set
>  ?
>
>>

For a 4pt FFT, just given terms, treating them as row matrix and multiply
with the following 4 x 4

1  1  1  1
1 -j -1  j
1 -1  1 -1
1  j -1 -j

You will get the result as a column matrix.

- Krishna