The recursive radix-two fast Fourier transform

Let $m\in \mathbb{N}$ and $N=2^m$. The radix-two fast Fourier transform ${\mathrm{FFT}}_m:{\mathbb{C}}^{\mathbb{Z}\mathrm{/}N}\to {\mathbb{C}}^{\mathbb{Z}\mathrm{/}N}$ is defined by recursion on $m$ as follows. At $m=0$ the group is $\mathbb{Z}\mathrm{/}1\mathbb{Z}$ and ${\mathrm{FFT}}_0:={\mathrm{i}\mathrm{d}}_{{\mathbb{C}}^{\mathbb{Z}\mathrm{/}1}}$. For $m\ge 1$, given $f\in {\mathbb{C}}^{\mathbb{Z}\mathrm{/}{2}^m}$ with even and odd parts $e,o\in {\mathbb{C}}^{\mathbb{Z}\mathrm{/}{2}^{m-1}}$ (The radix-two even/odd factorisation of the DFT), and given $E:={\mathrm{FFT}}_{m-1}(e)$ and $O:={\mathrm{FFT}}_{m-1}(o)$, extend $E$ and $O$ from $\mathbb{Z}\mathrm{/}{2}^{m-1}\mathbb{Z}$ to $\mathbb{Z}$ by $2^{m-1}$-periodicity and set

${\mathrm{FFT}}_m(f)(k):=E(k)+e^{-2\pi ik\mathrm{/}{2}^m}O(k),k\in \mathbb{Z}\mathrm{.}$

Then ${\mathrm{FFT}}_m(f)(k+2^m)={\mathrm{FFT}}_m(f)(k)$ for every $k\in \mathbb{Z}$, because $E$ and $O$ are $2^{m-1}$-periodic and $e^{-2\pi i(k+2^m)\mathrm{/}{2}^m}=e^{-2\pi ik\mathrm{/}{2}^m}{e}^{-2\pi i}=e^{-2\pi ik\mathrm{/}{2}^m}$ ($\exp (z+w)=\exp z\exp w$, and the complex exponential extends the real exponential, $\ker (\exp )=2\pi i\mathbb{Z}$, and $\exp z=\exp w$ exactly when $z-w\in 2\pi i\mathbb{Z}$); hence ${\mathrm{FFT}}_m(f)$ factors through $\mathbb{Z}\to \mathbb{Z}\mathrm{/}{2}^m\mathbb{Z}$ and ${\mathrm{FFT}}_m$ is a well-defined map ${\mathbb{C}}^{\mathbb{Z}\mathrm{/}{2}^m}\to {\mathbb{C}}^{\mathbb{Z}\mathrm{/}{2}^m}$.

The recursion is legitimate. Put ${\mathcal{F}}_m:={\mathbb{C}}^{\mathbb{Z}\mathrm{/}{2}^m}$ for each $m\in \mathbb{N}$, and use the tagged state set $A:=\{(m,g):m\in \mathbb{N},g:{\mathcal{F}}_m\to {\mathcal{F}}_m\}$. For a state $(m,g)\in A$ and $f\in {\mathcal{F}}_{m+1}$, let $e,o\in {\mathcal{F}}_m$ be the even and odd parts supplied by The radix-two even/odd factorisation of the DFT, and define $g^{+}(f)\in {\mathcal{F}}_{m+1}$ by $g^{+}(f)([k{]}_{2^{m+1}}):=g(e)([k{]}_{2^m})+e^{-2\pi ik\mathrm{/}{2}^{m+1}}g(o)([k{]}_{2^m})$ for $k\in \mathbb{Z}$. This is well defined on $[k{]}_{2^{m+1}}$: replacing $k$ by $k+2^{m+1}$ leaves the recursive values unchanged modulo $2^m$ and multiplies the twiddle by $e^{-2\pi i}=1$ ($\exp (z+w)=\exp z\exp w$, and the complex exponential extends the real exponential, $\ker (\exp )=2\pi i\mathbb{Z}$, and $\exp z=\exp w$ exactly when $z-w\in 2\pi i\mathbb{Z}$). Thus $g^{+}$ is a total map ${\mathcal{F}}_{m+1}\to {\mathcal{F}}_{m+1}$, and $T:A\to A$ defined by $T(m,g):=(m+1,g^{+})$ is a total step function. Starting from $a:=(0,{\mathrm{i}\mathrm{d}}_{{\mathcal{F}}_0})$, the recursion theorem The recursion theorem gives a unique $H:\mathbb{N}\to A$ with $H(0)=a$ and $H(m+1)=T(H(m))$. By induction (The principle of mathematical induction, The natural numbers $\mathbb{N}$ (von Neumann)) the first coordinate of $H(m)$ is $m$; writing $H(m)=(m,{\mathrm{FFT}}_m)$ gives ${\mathrm{FFT}}_m:{\mathcal{F}}_m\to {\mathcal{F}}_m$ and exactly the base and combine clauses above. Termination is immediate from recursion on $m$: each recursive call uses level $m-1$, and the base case $m=0$ returns the input. The exponent arithmetic uses $2^{m+1}=2\cdot 2^m$ and, for the rescaling below, $2^{-m\mathrm{/}2}=(2^m{)}^{-1\mathrm{/}2}$ (Laws of integer exponents, Rational powers $a^r$ of a positive base, Laws of rational exponents).

What the algorithm computes. Correctness is proved separately later on this page: ${\mathrm{FFT}}_m(f)(k)=X_k(f)$ for every input, where $X$ is the unnormalised transform of The unnormalised engineering DFT and its conversion to the unitary transform; the unitary transform of this page is recovered from the output by the single rescaling $2^{-m\mathrm{/}2}$ at length $N=2^m$. The operation count is likewise the subject of a later item. At level $m$ the recursion forms the even and odd parts of a length-$2^m$ list and performs one combine per output value, reading $E$ and $O$ at their classes and multiplying by the twiddle factors $e^{-2\pi ik\mathrm{/}{2}^m}$.

• The base case is a genuine case, not a convention. $\mathbb{N}$ contains $0$ (The natural numbers $\mathbb{N}$ (von Neumann)), so ${\mathrm{FFT}}_0$ is defined by the same recursion that defines all the other levels, and the length-one transform is the identity. Nothing in the definition excludes $N=1$, and the recursion is total on $\mathbb{N}$.

• The two conventions, once more. The recursion outputs the unnormalised transform: the definition of ${\mathrm{FFT}}_m$ contains no factor $N^{-1\mathrm{/}2}$, and the combine uses the twiddle factors $e^{-2\pi ik\mathrm{/}{2}^m}$ with the same sign as $X$ of The unnormalised engineering DFT and its conversion to the unitary transform. Dividing the output by $2^{m\mathrm{/}2}$ yields the unitary transform, and no other rescaling is needed.