Basic Formulas and Properties
Definitions and basic properties of the FFT
Definition of DFT and IDFT
Let’s begin by defining an N-point grid in . That is, a grid which starts from zero and doesn’t contain the end-point.
Given a vector , the DFT computes:
and the corresponding IFFT of a vector v yields
Aliasing and Negative Frequencies
I want to highlight this property early on, because it is usually leads to the most confusing errors when we intend to use FFTs in our codes.
In view of the definition we just introduced, the original FFT frequencies appear to be
But there is a tricky thing going on behind the scenes. It turns out that, for an N-point grid such as ours, we have the following identity:
This implies, in particular, that Fourier modes with frequencies above (also referred to as the ‘Nyquist frequency’) are equivalent, in our finite grid, to negative-frequency modes with .
In many cases, it becomes necessary to remove frequencies above Nyquist, and restate the IDFT in the more convenient form
This simple fact is the source of much of the confusion which usually strikes someone willing to use the FFT algorithm in various applications.
In order to use this last expression, the original FFT coefficients must be reordered into the coefficients illustrated in the above formula. This reordering is handled with an
fftshift function, which is a part of almost any FFT library.
The real fft computes the same transform as defined above, but employs certain symmetry relations for increased performance.
In particular, in the case the input signal is real, it’s transform will have hermitian symmetry:
where we have extended the definition of the DFT to the negative indices by periodicity.
Computationally, this property is used by FFT libraries to obtain a function, usually referred as RFFT, which avoids computing the duplicate data and obtains a 2X improvement in computing time and storage.
The rfft returns a vector of size , where the division by two is rounded down, containing the first coefficients of the FFT.