How can I compute the inverse FFT "manually"? How are the FFT wavenumbers ordered?
3 views (last 30 days)
Show older comments
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 :)
0 Comments
Answers (1)
David Goodmanson
on 13 Aug 2017
Edited: David Goodmanson
on 13 Aug 2017
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;
0 Comments
See Also
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!