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

Raymond Toy wrote:
> dlakelan wrote:
>> I am not actually advocating changing what the FFT DOES, only how we
>> describe what it does, so that people know where the frequencies are.
>> The current formula in the documentation is true because frequencies
>> higher than the Nyquist frequency (pi radians per sample) alias
>> appropriately onto negative frequencies...
...

> Ok.  So which formula do you want changed?  The formula for the
> definition of the FFT?

Yes, and the inverse transform i guess.

For the forward transform, I think we can describe it equivalently as:

y[k] = (1/n) sum (x[j] exp (- 2 %pi %i j k / n )), j, 0, n-1) for k <= n/2
y[k] = (1/n) sum (x[j] exp (- 2 %pi %i j (k-n) / n)), j, 0, n-1) for k > n/2

also, I forget, does maxima array indexing start at 0 or at 1? (this 
assumes 0 start)

This is a definition that treats y[k] as positive frequencies from 0 to 
pi radians/sample when k <= n/2 and as negative frequencies from 
-pi(1-1/n) to -pi/n. (unless I slipped up somewhere)

I think this should be equivalent but it makes it more clear to the user 
what frequencies are where. Some text should help as well.

Am I missing something? Does this formula define a different transform? 
I certainly haven't had time to prove the equivalence, but the concept 
is that a point on the unit circle in the complex plane can be described 
by an angle from 0 to 2pi or from -pi to pi and either one describes the 
same point.