Fourier Transforms

$\newcommand\inv{^{-1}}\newcommand\invt{^{-t}} \newcommand\bbP{\mathbb{P}} \newcommand\bbR{\mathbb{R}} \newcommand\defined{ \mathrel{\lower 5pt \hbox{{\equiv\atop\mathrm{D}}}}} \newcommand\macro{\langle#1\rangle}$ Back to Table of Contents
Let $y(t)$ be a function defined on $(-\infty,\infty)$. If this function is built up out of sine and cosine functions $y(t) = \sum_{k=-\infty}^\infty \alpha_k \sin 2\pi kt + \beta_k \cos 2\pi kt$ then we can recover the $\alpha_k,\beta_k$ coefficients from taking the inner product with sine and cosine functions: $(\sin 2\pi nt,\sin 2\pi mt)=0 \quad \hbox{if n\not=m}$ where the inner product is defined as $(f,g) = \int_{\-infty}^\infty f(t)g(t)dt$ This inspires us to make a transform function $Y(\omega)$ that describes the frequency content in the function $y(t)$: $Y(\omega) = \frac 1{\sqrt{2\pi}} \int_{-\infty}^\infty e^{-i\omega T} y(t) dt$ If we limit $y(t)$ to a measurement interval $(0,T)$ (or we assume that the function is periodic on this interval) and we use a discrete interval $h=1/N$, giving measurement point $t_k=kh$ and frequencies $\omega_n = 2\pi n/Nh$, we can approximate $\begin{array} {r@{=}l} Y(\omega) & \frac 1{\sqrt{2\pi}} \int_{-\infty}^\infty e^{-i\omega t} y(t) dt\\ & \frac 1{\sqrt{2\pi}} \int_0^T e^{-i\omega t} y(t) dt\\ & \frac 1{\sqrt{2\pi}} \sum_{k=1}^N e^{-i\omega_nt_k} y(t_k) h\\ & \frac 1{\sqrt{2\pi}} \sum_{k=1}^N e^{-2\pi ikn/N} y(t_k) h\\ \end{array}$ Dividing out $h$ we define $Y_n = Y(\omega_n)/h = \frac1{\sqrt{2\pi}} \sum_{k=1}^N y_k e^{-2\pi ikn/N}$ and the inverse transform $y(t) = \frac1{\sqrt{2\pi}} \int_{-\infty}^\infty e^{i\omega t} \approx \sum_{n=1}^N \frac{2\pi}{Nh} \frac{e^{i\omega_n t}}{\sqrt{2\pi}} Y(\omega_n).$ With a complex variable $Z=e^{-2\pi i/N}$ this becomes $y_k = \frac{\sqrt{2\pi}}N \sum_{n=1}^N Z^{-nk} Y_n, \quad Y_n = \frac1{\sqrt{2\pi}} \sum_{k=1}^N Z^{nk} y_k.$
To motivate the FFT algorithm let us consider a concrete example with $N=8$. With $Z_n=e^{-2\pi n/8}$ we have that $Z_n=Z_{n+8k}$ and $Z_{n+4}=-Z_n$, so we only have to compute 4 $Z_n$ values. The computation $\begin{array} {l} Y_0 = Z_0y_0+Z_0y_1+\cdots\\ Y_1 = Z_0y_0+Z_1y_1+Z_2y_2+\cdots\\ Y_2 = Z_0y_0+Z_2y_1+Z_4y_2+Z_6y_3+\cdots\\ Y_3 = Z_0y_0+Z_3y_1+Z_6y_3+\cdots\\ \cdots\\ y_7 = Z_0y_1+Z_7y_1+Z_{14}y_2+\cdots \end{array}$ reduces to $\begin{array} {l} Y_0=Z_0y_0+Z_0y_1+Z_0y_2+Z_0y_3+Z_0y_4+Z_0y_5+Z_0y_6+Z_0y_7 \\ Y_1=Z_0y_0+Z_1y_1+Z_2y_2+Z_3y_3-Z_0y_4-Z_1y_5-Z_2y_6-Z_3y_7 \\ Y_2=Z_0y_0+Z_2y_2-Z_0Y-2-Z_2y_3+Z_0y_4+Z_2y_5-Z_0y_6-Z_0y_7 \\ Y_3=Z_0y_0+Z_3y_1-Z_2y_2+Z_1y_3-Z_0y_4-Z_3y_5+Z_2y_6-Z_1y_7 \\ Y_4=Z_0y_0-Z_0y_1+Z_0y_2-Z_0y_3+Z_0y_4-Z_0y_5+Z_0y_6-Z_0y_7 \\ Y_5=Z_0y_0-Z_1y_1+Z_2y_2-Z_3y_3-Z_0y_4+Z_1y_5-Z_2y_6+Z_3y_7 \\ Y_6=Z_0y_0-Z_2y_2-Z_0Y_2+Z_2y_3+Z_0y_4-Z_2y_5-Z_0y_6+Z_0y_7 \\ Y_7=Z_0y_0-Z_3y_1-Z_2y_2-Z_1y_3-Z_0y_4+Z_3y_5+Z_2y_6+Z_1y_7 \\ \end{array}$ There is a large number of common subexpressions and almost subexpressions'. For instance, note that $Y_0,Y_1$ contain $Z_0y_0\pm Z_0y_4$. Next, $Y_0,Y_2$ and $Y_4,Y_6$ contain $(Z_0y_0\pm Z_2y_2) \pm (Z_0y_4\pm Z_2y_6)$. Et cetera. Thus, the FFT algorithm can be built out of an elementary butterfly' $\left. \begin{array} {r}x\\y \end{array} \right\} \Rightarrow \left\{ \begin{array} {r}x+y\\x-y \end{array} \right.$
Let $\omega_n$ be the $n$-th root of unity: $\omega_n=e^{-2\pi i/n}$ which has the property that $\omega_{n/2}=\omega_n^2$.
The Fourier sum $Y_k=\sum_{j=0}^{n-1} \omega_n^{jk} y_j$ If $n$ is even and $k\leq n/2-1$: $\begin{array} {r@{{}={}}l} Y_k &\sum_{\mathrm{even}\,j} \omega_n^{jk} y_j + \sum_{\mathrm{odd}\,j} \omega_n^{jk} y_j \\ &\sum_{j=0}^{n/2-1} \omega_n^{2jk} y_{2j} + \omega_n \sum_{j=0}^{n/2-1} \omega_n^{2jk} y_{2j+1} \\ &\sum_{j=0}^{n/2-1} \omega_{n/2}^{jk} y_{2j} + \omega_n \sum_{j=0}^{n/2-1} \omega_{n/2}^{jk} y_{2j+1} \end{array}$ so the length-$n$ Fourier transform consists of two length-$n/2$ transforms and a single multiplication by $\omega_n$.