fft definition in matlab doc puzzling

Hi all,

I'm a bit puzzled with the definition of fft in the documentation :

https://fr.mathworks.com/help/matlab/ref/fft.html

The definition at the very end in "more about" states the fft as a projection on positive frequency (from 0 to Fs/N) while the examples suggest a "two sided" spectrum ie. with positive frequencies and negative ones (-Fs/2 to Fs/2).

To make my question more precise :

the definition in the doc is :

Given that the fft results in both positive and negative frequencies, I woumld have guess a defintion like :

Am I missing something ?

thanks in advance for your help,

Francois.

[Walter Roberson]

?? I do not see the word "projection" at all in that documentation ??

[françois anquez]

Dear Walter,

the word projection is not written. However suming on all is a projection on harmonic k.

all the best,

Francois.

Answer 1

[Matt J]

Given that the fft results in both positive and negative frequencies, I woumld have guess a defintion like :

Perhaps a better way to clear up the confusion is to point out that for any given sinuoid at some "positive" frequency , the corresponding negative frequency sinusoid is indentical, due to n-periodicity, to , or equivalently to , where .

Bust since and both lie in the interval 2...n, we can see that summing from k=1...n in the FFT is sufficient to capture all the same pairs of positive and negative frequencies as summing from -n/2 to +n/2.

[françois anquez]

thanks Matt this was the argument I was seeking for.

all the best,

francois.

Answer 2

[Matt J]

Your second definition only makes sense if you define the indexing in Y(k) to be modulo-n. Otherwise, it is not clear what it means for a vector Y to be indexed at negative k.

If you are defining Y(k) to be modulo n, then the two IFFT definitions are equivalent because Y(k) and W_n(j-1)(k-1) are then both n-periodic with respect to k. Therefore any sum over n successive indices k gives the same result.

[françois anquez]

Dear Matt,

thanks for your answer. However I not sure it is only a matter of indexing.

The two definition do not lead to the same transform. I quickly checked the two sums (for 1:n and for -n/2:n/2) lead to a different number in the general cas for a given k.

Still I'm wondering what am I missing.

Moreover the two definitions lead to decompostion of functions that have different frequency components. For example, the definition on the documentation page :

lead to harmonic component that do not verify shannon theorem (k>n/2) while the other does not.. Still I'm puzzled.

all the Best,

Francois.

[Matt J]

I would need to see the code you used to do your comparison(s).

[françois anquez]

function [coef1,coef2]=essaiFFT(X,k)

[N,~]=size(X);
N=N-1;
WN=exp(-i*2*pi/N);

coef1=0;
for jj=1:(N+1)
  coef1=coef1+X(jj,1)*power(WN,(jj-1)*(k-1));
end % for jj

coef2=0;
for jj=(-(N/2)):(N/2)
  coef2=coef2+X(jj+N/2+1,1)*power(WN,(jj-1)*(k-1));
end % for jj

end % function

[Matt J]

The test code should be as below. The main problem with your implementation is that in the first version of the coefficient calculation, you are putting the time origin at X(1) whereas in the second version, you are putting the time origin at X(N/2). Thus, the second version is really the transform of a phase-shifted version of X.

function [coef1,coef2]=essaiFFT_Matt(X,k)

    N=numel(X);
    WN=exp(-1i*2*pi/N);
    
    coef1=0;
    for j=1:N
      coef1=coef1+X(j)*power(WN,(j-1)*(k-1));
    end
    
    
    coef2=0;  
    for j=(1:N) - floor(N/2)   %floor() handles odd N
      
      index=mod(j-1,N)+1;  %modulo N transform for 1-based indexing
      
      coef2=coef2 + X(index)*power(WN,(j-1)*(k-1));
      
    end % for jj
    
    
end % function