How can I compute the inverse FFT "manually"? How are the FFT wavenumbers ordered?

Hi all. In my efforts to try to understand the FFT, I am trying to understand the following example:

Let Z = [z1, ..., zn] (n is even, for simplicity) be an array of complex numbers, and let

    F = fft(Z);

Because MATLAB uses the complex exponential FFT, the coefficients stored in F are ordered by

    [0:1:N/2 , -N/2+1:1:-1]

right? If we use the fftshift() function, however, we can get the order to be

    [-N/2+1:1:N/2]

MY QUESTION

From this, how would I compute the inverse FFT? I think it would be:

    F = fftshift(fft(Z));
    k = -N/2+1:1:N/2;
    and then we would have
    Z(n) == (1/N)*sum(F.*exp(1i*2*pi*(n)*(k)/N)) ????

My only uncertainty comes from the fact that the documentation says the following:

    For length N input vector x, the DFT is a length N vector X,
    with elements
                     N
       X(k) =       sum  x(n)*exp(-j*2*pi*(k-1)*(n-1)/N), 1 <= k <= N.
                    n=1
    The inverse DFT (computed by IFFT) is given by
                     N
       x(n) = (1/N) sum  X(k)*exp( j*2*pi*(k-1)*(n-1)/N), 1 <= n <= N.
                    k=1

Why are we summing k from 1:N here? Why is it not -N/2+1 : N/2 ???

Please let me know if anything is unclear and I'll try to clarify :)

Answer 1

[David Goodmanson]

Hi Alex,

On input and output the fft and ifft have an array whose corresponding frequencies are in the order 0:N-1 as implied by the documentation. Zero frequency or zero time corresponds to the first element. It's only after you use fftshift or ifftshift that the corresponding zero of frequency (or time) is shifted to the middle of the array. So for even N, if you defined a time array by

t = (-N/2:N/2-1)*delta_t
g = g(t)   % some function of t

then to get the fft you would use

h = fft(ifftshift(g))

which gives a function whose corresponding frequency grid has a first element at f = 0. If you wanted to have zero frequency in the center then

h = fftshift(h)
%  and the corresponding frequency grid is 
(-N/2:N/2-1)*delta_f

where in all cases

delta_f * delta_t = 1/N
or if you prefer
delta_t  = 1/Fs;  delta_f = Fs/N;