FFT computation

On 13 Apr 2006 12:43:04 -0700, forums_mp@hotmail.com wrote:

>
>Rick Lyons wrote:
>> Hi,
>>   If I remember correctly, a four-point DFT
>> requires no multiplications.
>> So if you memorize the simple 4-pt DFT
>> algorithm, you could compute a 4-pt
>> DFT in your head.
>>
>> I also have this vague recollection that you can
>> compute the magnitudes-squared for an 8-pt
>> DFT with no multiplications.
>>
>> Don't take my word for any of this.
>> As Ronny Reagan would say, "Trust, but verify."
>>
>> [-Rick-]
>
>Yes, I'm in the process of trying to get a good grasp on all this.  I
>think part of the problem surrounds the fact that I'm running FFT using
>two sets of programs and comparing the results to Matlab.   So I run an
>FFT on the data set
>   data [ 8 ] = { 0., 0., 1., 0., 2., 0., 3., 0. };
>
>Program 1.
>
>(6,0)
>(-2,-2)
>(-2,0)
>(-2,2)
>
>Program 2
>6
>0
>-2
>-2
>-2
>0
>-2
>2
>
>Matlab states the same.
>So all three match.
>
>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.

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

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

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

[-Rick-]

On Thu, 13 Apr 2006 19:22:45 GMT, R.Lyons@_BOGUS_ieee.org (Rick Lyons)
wrote:

>On 13 Apr 2006 05:41:54 -0700, forums_mp@hotmail.com wrote:
>
>
>Hi,
>  I think I screwed up in my last post.
>
>I think you can compute DFT magnitudes 
>(not magnitudes-squared) for an 8-pt 
>DFT using no multiplications.
>
>Again, check this for yourself.
>

Excuse me while I struggle to remove two 
separate feet from my mouth.

I no longer believe that you can compute 
DFT magnitudes for an 8-pt 
DFT using no multiplications.

[-Rick-]

forums_mp@hotmail.com wrote:
> Rick Lyons wrote:
> 
>>Hi,
>>  If I remember correctly, a four-point DFT
>>requires no multiplications.
>>So if you memorize the simple 4-pt DFT
>>algorithm, you could compute a 4-pt
>>DFT in your head.
>>
>>I also have this vague recollection that you can
>>compute the magnitudes-squared for an 8-pt
>>DFT with no multiplications.
>>
>>Don't take my word for any of this.
>>As Ronny Reagan would say, "Trust, but verify."
>>
>>[-Rick-]
> 
> 
> Yes, I'm in the process of trying to get a good grasp on all this.  I
> think part of the problem surrounds the fact that I'm running FFT using
> two sets of programs and comparing the results to Matlab.   So I run an
> FFT on the data set
>    data [ 8 ] = { 0., 0., 1., 0., 2., 0., 3., 0. };
> 
> Program 1.
> 
> (6,0)
> (-2,-2)
> (-2,0)
> (-2,2)
> 
> Program 2
> 6
> 0
> -2
> -2
> -2
> 0
> -2
> 2
> 
> Matlab states the same.
> So all three match.
> 
> 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.

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.

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

stevenj@alum.mit.edu wrote:
> Nope.  An unscaled 8-point DFT requires at least 4 real
> multiplications.
>
> In general, the absolute minimum number of irrational real
> multiplications for a complex-input DFT of size N = 2^m has been proved
> to be 4*N - 2*m^2 - 2*m - 4.  (The algorithms that achieve this minimum
> are, unfortunately, impractical for large N because the number of
> additions explodes.)

So 20 irrational real multiplications for an m of 4.  A factor of five
difference.  Wow!!  Where is this proof so I can read up on some of
this stuff?

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.

[..]

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

<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

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

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