FFT computation

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

I'm going through a matlab couse and the individual who's teaching the
course happens to be fairly acclimated with image/signal processing.
At issue.  Prior to executing the test via matlab - he was able to give
the answer in advance.  Obviously I suspect he's done this a million
times utilizing I suspect this same example.  I was intrigued though
that and asked myself is that possible?  i.e Give the data points
above, could I obtain the result - in my head - if you will.

I realized quickly I could get - the first line -
  6.000 + 0i   by simply summing the real and imaginary components.

The second third and fourth lines I'm not seeing withouth diving into
the formula ( though I haven't done this yet ).
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?

Of course I could ask the individual but it's more of a curiosity
question for someone who's just staring to dive into this DSP business
heavily.

>
>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
>
>I'm going through a matlab couse and the individual who's teaching the
>course happens to be fairly acclimated with image/signal processing.
>At issue.  Prior to executing the test via matlab - he was able to give
>the answer in advance.  Obviously I suspect he's done this a million
>times utilizing I suspect this same example.  I was intrigued though
>that and asked myself is that possible?  i.e Give the data points
>above, could I obtain the result - in my head - if you will.
>
>I realized quickly I could get - the first line -
>  6.000 + 0i   by simply summing the real and imaginary components.
>
>The second third and fourth lines I'm not seeing withouth diving into
>the formula ( though I haven't done this yet ).
>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?
>
>Of course I could ask the individual but it's more of a curiosity
>question for someone who's just staring to dive into this DSP business
>heavily.
>

Do you know the FFT algorithm? 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.

Actually, I never tried computing FFT in mind. You need not have to
compute FFT in mind to be a DSP enthusiast.

- Krishna

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 third set of value:
  ?
Fourth set
  ?

>
> Actually, I never tried computing FFT in mind. You need not have to
> compute FFT in mind to be a DSP enthusiast.
Understood.. I was just trying to do this just to get a feel for it if
you will

My mental arithmetic is notoriously bad, and I don't use MATLAB, but
your data just tells you that you have a sum of three sine waves (OK,
complex exponentials..) of amplitudes 1, 2 and 3 respectively at
frequencies 1, 2 and 3. So you only need to know trigonometry, and the
angles involved come out easily at multiples of pi/2 so the sine values
are readily known.

The FT coefficients in your data set are just telling you the amplitude
and phase of sine wave components. Granted, these are expressed as
complex numbers but still each is just:

   cos(2.pi.k.p/N) + j.sin(2.pi.k.p/N)

where k is the coefficient's index, p is the index of the transformed
rsult, and N is the number of coefficients.

For a 4-point FT this is:

  cos(pi.k/2) + j.sin(pi.k/2)

Since your imaginary parts are all zero, the phase of each sine wave is
the same.

So to calculate the FT you just need to add four of these together
based on the given values. You need to calculate the sum of these sine
waves at times 0, 1, 2, 3 and you are done. It helps that (pi.0/2) = 0,
(pi.1/2) = pi/2, (pi.3/2) = 3.pi/2 so the sine values are known.

I probably mae some mistaked in there somewhere, but when I last did
this (25 years ago) it seemed easy.

Chris
=================
Chris Bore
www.bores.com

Chris Bore wrote:
> My mental arithmetic is notoriously bad, and I don't use MATLAB, but
> your data just tells you that you have a sum of three sine waves (OK,
> complex exponentials..) ...

Chris,

To you mean that because of the (nearly) formal identity of the direct 
and inverse transforms, one can construe the time samples as frequencies 
and obtain correct results? I think that's clever enough to have been 
made explicit.

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

You state it much more succinctly than I did.

Chris

On 13 Apr 2006 05:41:54 -0700, 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. };
>
>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
>
>I'm going through a matlab couse and the individual who's teaching the
>course happens to be fairly acclimated with image/signal processing.
>At issue.  Prior to executing the test via matlab - he was able to give
>the answer in advance.  Obviously I suspect he's done this a million
>times utilizing I suspect this same example.  I was intrigued though
>that and asked myself is that possible?  i.e Give the data points
>above, could I obtain the result - in my head - if you will.
>
>I realized quickly I could get - the first line -
>  6.000 + 0i   by simply summing the real and imaginary components.
>
>The second third and fourth lines I'm not seeing withouth diving into
>the formula ( though I haven't done this yet ).
>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?
>
>Of course I could ask the individual but it's more of a curiosity
>question for someone who's just staring to dive into this DSP business
>heavily.

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

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.

[-Rick-]

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.

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

Cordially,
Steven G. Johnson