for your info: ch. 11 mbe: fast fourier transforms

Robert Dodier wrote:
> On 5/3/09, dlakelan <dlakelan at street-artists.org> wrote:
> 
>> Hi Robert, did you see my suggestions for the documentation of the fft
>> routine about a month ago? The documentation made it seems like the
>> frequencies involved were 0 to 2%pi radians per sample, but in fact they
>> are 0 to %pi followed by -%pi up to -%pi/n [...]
> 
> Yes, I saw that. After trying some examples, I guess I don't understand
> what you're getting at. The results seem to match the definition of the
> transform stated in the documentation:
> 
>   y[k]: (1/n) sum (x[j] exp (-2 %i %pi j k / n), j, 0, n-1)
> 
> i.e. the k'th element is associated with frequency k*2*%pi/n.

If this were true, then when you multiply all coefficients by 
%i*k*2*%pi/n and take the inverse you should get the derivative. In fact 
you need to multiply by a different function that looks like a sawtooth. 
It ramps up to a maximum, then goes to zero, then goes negative maximum 
and linear ramps up towards zero again, as follows.
 
derivcoefs:float(append(makelist(pi*k,k,0,n/2-1),[0],makelist(pi*k,k,1,n/2-1)-pi*n/2)), 
/* tricky the way the frequencies correspond to k */

Another way to see what is going on is to fill your real array with a 
gaussian that has its peak in the center, and take the fft then plot the 
absolute value of the frequencies. you will see a split gaussian with 
peaks near the beginning and end of the array. If you take the fourier 
transform of the gaussian symmetric around zero, you get amplitudes that 
are a gaussian symmetric around zero frequency, but this symmetry in the 
vector output is slightly folded around.

These situations are common in dealing with FFT data if I remember 
correctly (I did a lot of FFT stuff about 10 years ago), but somewhat 
difficult to explain. Let me know if this helps or if you want more 
examples.

When dealing with the FFT of real data, often the results are 
represented only as frequencies from 0 to pi, since the frequencies from 
0 to -pi are the complex conjugate (I think). In that case you never see 
these issues, basically the proper symmetry is taken care of behind the 
scenes.