Julia

Basic Formulas and Properties

by Martin D. Maas, Ph.D
Last updated:

Definitions and basic properties of the FFT

Definition of DFT and IDFT

Let’s begin by defining an N-point grid in [0,2π)[0,2\pi). That is, a grid which starts from zero and doesn’t contain the end-point.

{xj}0≤j≤N−1={2πjN:0≤j≤N−1}\begin{equation} \lbrace x_j \rbrace_{0 \le j \le N-1} = \left\lbrace \frac{2\pi j}{N} : \quad 0 \le j \le N-1 \right\rbrace \end{equation}

Given a vector v={vj}0≤j≤N−1v = \lbrace v_j \rbrace_{0 \le j \le N-1}, the DFT computes:

DFT(v)[k]=∑j=0N−1e−ikxjvj0≤k≤N−1\begin{equation} \mathrm{DFT}(v)[k] = \sum_{j=0}^{N-1} e^{-ik x_j}v_j \qquad 0 \le k \le N-1 \end{equation}

and the corresponding IFFT of a vector v yields

IDFT(v)[j]=1N∑k=0N−1eikxjvk0≤j≤N−1\begin{equation} \mathrm{IDFT}(v)[j] = \frac{1}{N} \sum_{k=0}^{N-1} e^{ik x_j}v_{k} \qquad 0 \le j \le N-1 \end{equation}

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

k=0,…,N−1\begin{equation} k = 0, \dots, N-1 \end{equation}

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:

eiNmxj=1m∈Z\begin{equation} e^{i N m x_j} = 1 \qquad m \in \mathbf{Z} \end{equation}

This implies, in particular, that Fourier modes with frequencies above N/2N/2 (also referred to as the ‘Nyquist frequency’) are equivalent, in our finite grid, to negative-frequency modes with k>−N/2k > -N/2.

In many cases, it becomes necessary to remove frequencies above Nyquist, and restate the IDFT in the more convenient form

1N∑k=−N/2N/2−1eikxjwkj=1,...,N.\begin{equation} \frac{1}{N} \sum_{k=-N/2}^{N/2-1} e^{ik x_j}w_k \quad j = 1,...,N. \end{equation}

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 vkv_k must be reordered into the wkw_k coefficients illustrated in the above formula. This reordering is handled with an fftshift function, which is a part of almost any FFT library.

Real FFT

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:

DFT(v)[j]=DFT(v)[n−j]∗,j=0,…,n\begin{equation} \mathrm{DFT}(v)[j] = \mathrm{DFT}(v)[n-j]^*, j=0,\dots,n \end{equation}

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 N/2+1N/2 + 1, where the division by two is rounded down, containing the first coefficients of the FFT.