>
>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

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.
�����������������������������������������������������������������������

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.

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.

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?

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.

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.

> This boils down to - for me - whose more accurate.  In fact, I stumbled
> across fftw and one of the key benchmarks from the numbers shown is
> 'accuracy'.   I haven't downloaded the code from site yet but I'm
> curious to get a better feel for how one measures the _accuracy_ of
> FFTs/IFFTs.

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

Cordially,
Steven G. Johnson

See the introduction of http://fftw.org/newsplit.pdf for references
regarding bounds on the number of arithmetic operations required by the
DFT.  (In particular, for the multiplicative bounds see refs. [16-17].)

forums_mp@hotmail.com wrote:
> For starters, pardon my simplicity.  That said,  given - an array of
> sample data such that: data [ 8 ] = { 0., 0., 1., 0., 2., 0., 3., 0. };

Is this a sawtooth wave?  Whose periodic form is used
as an example for DFT and FT spectrums in a few, perhaps
many, standard textbooks?

All you'd need to guess might be the scale factor
(applying Parseval theorem in ones head?)


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

<forums_mp@hotmail.com> wrote in message 
news:1144932114.957314.185830@z34g2000cwc.googlegroups.com...
>
> For starters, pardon my simplicity.  That said,  given - an array of
> sample data such that: data [ 8 ] = { 0., 0., 1., 0., 2., 0., 3., 0. };
>
> If I ran an FFT on that via matlab  - so now:
>  a = [0+0i 1+0i 2+0i, 3+0i]
>  b= fft( a );
>
> The result:
>  6.000
> -2.000 - 2.000i
> -2.000
> -2.000 + 2.00i
...
> 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
or putting in your values of a=0,b=1,c=2,d=3
6,0
-2,-2
-2,0
-2,2


Cheers,
bob

[..]

> Ask yourself if you would see the difference between graphs of (12,0)
> and (12,-4.66966e-016) if each unit square were a kilometer on a side.

Makes sense, but as mentioned in a response to Rick.  I think I might
have gotten side tracked with 'accuracy'.  This after perusing a few
texts/the web, in addition to observing fftw's benchmarks highlighting
the importance (my take on it) of accuracy.   In the end you're
correct.  Will I _see the difference_?    No.  Does that mean one
result is more accurate that the other.. ?   Being a newbie.  Not sure
to make of that :)

Rick Lyons wrote:

> >So I run an FFT on the results i.e  6, 0, -2, -2, -2, 0, -2 , 2 and the
> >result from program 1
> >
> >Program 1
> >(0,0)
> >(12,-4.66966e-016)
> >(8,0)
> >(4,4.66966e-016)
> >
> >Program 2
> >0
> >0
> >12
> >0
> >8
> >0
> >4
> >0
> >
> >The results from Matlab match that of Program 2.
> >
> >I begin to ask myself.  How could the imaginaries be zero given the
> >data set - 6, 0, -2, -2, -2, 0, -2 , 2.  Doesn't make sense to me..
> >I'll need to delve into the math because in my mind program 2 and
> >matlab ( i didn't say that too load ) have accuracy issues.
>
> Wait wait.
> Now you have two issues to deal with here.
>
> (1) Are your FFT results "scrambled" in order?
>     (That's the "bit reversal" property of
>      radix-2 FFTs.)  Make sure you account for that.
Scrambled?  For a data set of

   R    I
   -6   0
   -2  -2
   -2   0
   -2   2
Matlab tells me I should get.   Matlab of course 'ignores' the 0
imaginaries.
0
0
12
0
8
0
4
0


>
> (2) It looks like you performed a forward
>     FFT, and then performed another forward
>     FFT instead of an inverse FFT. (Although
>     I'm not exactly sure what you're trying to
>     accomplish.)
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.

> In any case, if a sequence has symmetric real
> parts and antisymmetric imaginary parts, then
> the FFT (or inverse FFT) will result in a
> sequence that will have zero-valued imaginary parts.
>
> (Do a Google search "hermitian symmetry")
Will do.

>
> Values like 4.66966e-016 are interpretted
> as zero because that super small value is a
> result of computational errors.

This boils down to - for me - whose more accurate.  In fact, I stumbled
across fftw and one of the key benchmarks from the numbers shown is
'accuracy'.   I haven't downloaded the code from site yet but I'm
curious to get a better feel for how one measures the _accuracy_ of
FFTs/IFFTs.