The Discrete Fourier Transform and the FFT: A Worked Example

This post explains the idea behind the fast Fourier transform (FFT) for a one-dimensional sequence, and then checks it against a direct calculation on a small example.

The radix-2 decimation-in-time FFT

For a sequence \(x_0, x_1, \ldots, x_{N-1}\), the discrete Fourier transform (DFT) is

\[X_k=\sum_{m=0}^{N-1} x_m\, e^{-\frac{2 \pi i}{N} m k}, \qquad k = 0, 1, \ldots, N-1 .\]

Suppose \(N\) is even. Split the sum into even-indexed and odd-indexed terms:

\[X_k=\sum_{m=0}^{N / 2-1} x_{2 m}\, e^{-\frac{2 \pi i }{N}(2 m) k}+\sum_{m=0}^{N / 2-1} x_{2 m+1}\, e^{-\frac{2 \pi i}{N}(2 m+1) k}.\]

Factoring \(e^{-2\pi i k/N}\) out of the second sum,

\[X_k=\underbrace{\sum_{m=0}^{N / 2-1} x_{2 m}\, e^{-\frac{2 \pi i }{N / 2} m k}}_{E_k}+e^{-\frac{2 \pi i}{N} k} \underbrace{\sum_{m=0}^{N / 2-1} x_{2 m+1}\, e^{-\frac{2 \pi i}{N / 2} m k}}_{O_k}=E_k+e^{-\frac{2 \pi i}{N} k}\, O_k ,\]

where \(E_k\) and \(O_k\) are the DFTs of the even- and odd-indexed subsequences, each of length \(N/2\).

Both \(E_k\) and \(O_k\) are periodic in \(k\) with period \(N/2\), and \(e^{-\frac{2\pi i}{N}\left(k + \frac N2\right)} = -e^{-\frac{2\pi i}{N}k}\). So for \(k = 0, \ldots, \frac N2 - 1\),

\[\begin{aligned} X_k & =E_k+e^{-\frac{2 \pi i}{N} k}\, O_k, \\ X_{k+\frac{N}{2}} & =E_k-e^{-\frac{2 \pi i}{N} k}\, O_k . \end{aligned}\]

A DFT of length \(N\) thus reduces to two DFTs of length \(N/2\) plus \(N/2\) multiplications by the “twiddle factors” \(e^{-2\pi i k/N}\). Applying the idea recursively when \(N\) is a power of \(2\) gives the FFT, with \(O(N\log N)\) operations instead of the \(O(N^2)\) of the direct sum.

Example: the DFT of \([1, 2, 3, 4]\)

Direct calculation

With \(N = 4\),

\[X_k = \sum_{n=0}^{3} x_n\, e^{-2\pi i \frac{kn}{4}}, \qquad k = 0, 1, 2, 3 .\]

For \(X_0\), every exponential is \(1\):

\[X_0 = 1 + 2 + 3 + 4 = 10.\]

For \(X_1\):

\[\begin{aligned} X_1 &= 1 + 2 e^{-i \frac{\pi}{2}} + 3 e^{-i \pi} + 4 e^{-i \frac{3\pi}{2}} \\ &= 1 + 2(-i) + 3(-1) + 4(i) \\ &= -2 + 2i. \end{aligned}\]

For \(X_2\):

\[\begin{aligned} X_2 &= 1 + 2 e^{-i \pi} + 3 e^{-2\pi i} + 4 e^{-3\pi i} \\ &= 1 - 2 + 3 - 4 \\ &= -2. \end{aligned}\]

For \(X_3\):

\[\begin{aligned} X_3 &= 1 + 2 e^{-i \frac{3\pi}{2}} + 3 e^{-3\pi i} + 4 e^{-i \frac{9\pi}{2}} \\ &= 1 + 2(i) + 3(-1) + 4(-i) \\ &= -2 - 2i. \end{aligned}\]

So the DFT is

\[[10,\ -2+2i,\ -2,\ -2-2i].\]

Using the FFT

Split into even- and odd-indexed elements, \([x_0, x_2] = [1, 3]\) and \([x_1, x_3] = [2, 4]\), and take their length-2 DFTs:

\[\begin{aligned} E_0 &= 1 + 3 = 4, & E_1 &= 1 + 3e^{-i\pi} = -2, \\ O_0 &= 2 + 4 = 6, & O_1 &= 2 + 4e^{-i\pi} = -2 . \end{aligned}\]

Write \(W_N = e^{-2 \pi i/ N}\), so that

\[X_k = E_k + W_N^k\, O_k, \qquad X_{k+N/2} = E_k - W_N^k\, O_k .\]

For \(N = 4\),

\[W_4 = e^{-2\pi i / 4} = e^{-i\pi/2} = -i .\]

Therefore

\[\begin{aligned} X_0 &= E_0 + W_4^0\, O_0 = 4 + 6 = 10, \\ X_1 &= E_1 + W_4^1\, O_1 = -2 + (-i)(-2) = -2 + 2i, \\ X_2 &= E_0 - W_4^0\, O_0 = 4 - 6 = -2, \\ X_3 &= E_1 - W_4^1\, O_1 = -2 - (-i)(-2) = -2 - 2i, \end{aligned}\]

which agrees with the direct calculation:

\[[10,\ -2+2i,\ -2,\ -2-2i].\]

The saving is invisible for four points, but it grows quickly: the direct DFT of \(N = 2^{20}\) points needs about \(10^{12}\) complex multiplications, while the FFT needs about \(10^{7}\). This is what makes Fourier methods practical in applications such as image processing, where an image is convolved with a filter to blur it or detect edges.

Credits

The derivation follows the Wikipedia article on the Cooley–Tukey FFT algorithm.

Changes on 25 October 2026

What was wrong.

• The twiddle factor for \(N = 4\) was taken as \(i\) instead of \(-i\). The FFT result then disagreed with the direct calculation, while the text said they agreed.
• The DFT sums started at \(m = 1\) instead of \(m = 0\), which drops the first term.
• A typo turned \(2\pi i\) into \(2Ni\) in the final formula.

What changed. All are fixed, and the FFT is worked through on the same example so that the two results can be compared. Previously titled “An example of Discrete Fourier Transform using FFT Algorithm”.