Advanced Solid State Physics



Magnetic effects and
Fermi surfaces


Linear response


Crystal Physics



Structural phase

Landau theory
of second order
phase transitions




Exam questions




Course notes

TUG students


Discrete Fourier Transforms

Fourier analysis is a form of interpolation that uses periodic functions to interpolate between discrete data points. Consider a set of $N$ data points $(x_n,f_n)$ where the points are equally spaced in $x$: $x_n = n\Delta x$. We seek a periodic function $f(x)$ with a period $N\Delta x$ that passes through all of the points. This function can be expressed as a Fourier series which can either be written in terms of sines and cosines,

\[ \begin{equation} f(x) = \sum\limits_{q=0}^{\infty}\left[a_q\cos\left(\frac{2\pi qx}{N\Delta x}\right)+b_q\sin\left(\frac{2\pi qx}{N\Delta x}\right)\right], \end{equation} \]

or in terms of complex exponentials,

\[ \begin{equation} f(x) = \sum\limits_{q=-\infty}^{\infty}F_q\exp \left(\frac{i2\pi qx}{N\Delta x}\right). \end{equation} \]

The equivalence of these two expressions can be shown using Euler's formula: $e^{ix}=\cos x+i\sin x$. The coefficients can be complex and are related by,

\[ \begin{equation} a_q = F_{q}+F_{-q} \qquad \text{and}\qquad b_q = F_{q}-F_{-q}. \end{equation} \]

If $f(x)$ is a real function, then $a_q$ and $b_q$ are real and $F_q = F_{-q}^*$ so that $a_q = 2\mathcal{Re}(F_{q})$ and $b_q = 2\mathcal{Im}(F_{q})$.

Although it is possible to construct many periodic functions that go through all the data points $f_n$ with wavelengths smaller than $\Delta x$, it makes sense to restrict the sum over $q$ to the fewest necessary to go through all the points. There are two common choices: $q$ can be restricted to the range $q=0,1,2,\cdots,N-1$ or $q=-N/2,\cdots,-2,-1,0,1,2,\cdots,N/2$. The first choice appears more often in the literature but the second choice produces the smoothest function $f(x)$. To keep the discussion general, we restrict the sum over $q$ to the range $q=j,j+1,j+2,\cdots,j+N-1$ and the starting value $j$ can be specified later.

The points $(x_n,f_n)$ are substituted into expression for the Fourier series,

\[ \begin{equation} \label{eq:iDFT} f_n = \sum\limits_{q=j}^{j+N-1}F_q\exp \left(\frac{i2\pi qx_n}{N\Delta x}\right)=\sum\limits_{q=j}^{j+N-1}F_qe^{i2\pi qn/N}. \end{equation} \]

To determine the Fourier coefficients $F_q$, multiply by $e^{-i2\pi q'n/N}$ and sum over $n$.

\[ \begin{equation} \sum\limits_{n=0}^{N-1}f_ne^{-i2\pi q'n/N} = \sum\limits_{n=0}^{N-1}\sum\limits_{q=j}^{j+N-1}F_qe^{i2\pi (q-q')n/N}. \end{equation} \]

In the double sum on the right side, consider a specific value of $q$ and sum over $n$. Each term $e^{i2\pi (q-q')n/N}$ can be represented as a vector that originates at the origin and ends on the unit circle in the complex plane. These vectors are uniformly distributed around the unit circle and add to zero unless $q=q'$. When $q=q'$, the double sum evaluates to $NF_q$. This yields an expression for the Fourier coefficients,

\[ \begin{equation} \label{eq:DFT} F_q = \frac{1}{N} \sum\limits_{n=0}^{N-1}f_ne^{-i2\pi qn/N}. \end{equation} \]

Equation (\ref{eq:DFT}) is called the Discrete Fourier Transform (DFT) of the data series $f_n$ and Eq. (\ref{eq:iDFT}) is known as the inverse discrete Fourier transform.

The form below accepts a sequence of complex numbers $f_n$ and calculates the discrete Fourier transform. It is also possible to input the values of $F_q$ on the right and calculate the inverse discrete Fourier transform. The smoothest fit is obtained for $j^*=\text{Int}(-N/2+1)$ where $\text{Int} (x)$ rounds down to the nearest integer. The $j^*$ buttons use this value.

Real space

Reciprocal space





$\text{Re}[f_n]$  $\text{Im}[f_n]$ 

$\text{Re}[F_q]$  $\text{Im}[F_q]$ 

  1. R. N. Bracewell, The Fourier Transform and Its Applications, McGraw-Hill (1978).