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 | |||
| $f_n$ | $F_q$ | |||
$n$ | $q$ | |||
$\text{Re}[f_n]$ $\text{Im}[f_n]$ | $\text{Re}[F_q]$ $\text{Im}[F_q]$ | |||