Foundations — Fourier analysis — DFT, FFT algorithm (Cooley-Tukey)

This page assumes you know nothing about the notation on the parent topic. We build every symbol from the ground up, in an order where each one only uses things already defined.

0. What a "signal" and a "sample" even are

• $n$ is just an index: it names which reading, counting from $0$. So $x_0$ is the first, $x_1$ the second, and so on.
• $N$ is the total count of readings.
• We start counting at $0$, so the last index is $N-1$, not $N$. This "off by one" is a lifelong habit in this subject — get comfortable now.

Why the topic needs it: the whole DFT eats a list $x_0\dots x_{N-1}$ and spits out another list. If you don't picture the input as dots on a timeline, nothing later has a home.

1. Complex numbers — arrows in a plane

The parent page is full of $i$, $e^{i\theta }$, and bars over letters. All of it lives in one picture: a point (or arrow) in a flat plane.

• The horizontal axis is the real axis, the vertical axis is the imaginary axis.
• Look at the red arrow in the figure: its length is $r$ and the angle it makes with the right-pointing axis is $\theta$.

Why the topic needs it: the parent's line "$X_{N-k}=\overline{X_k}$ for real input" is a mirror-symmetry statement. Without the bar picture it's gibberish; with it, it just says two output arrows are mirror images.

2. The exponential $e^{i\theta }$ — a point on the unit circle

This is the single most important symbol on the whole parent page, so we earn it carefully.

Read the figure slowly:

• Every $e^{i\theta }$ sits on the circle of radius 1 (the "unit circle"), because ${\cos }^2\theta +{\sin }^2\theta =1$ always.
• Increasing $\theta$ by a little rotates the red dot a little counter-clockwise.
• $\theta$ is measured in radians: a full trip around the circle is $2\pi$ radians (not $360$). So $e^{2\pi i}=e^0=1$ — you're back where you started.

Why the topic needs it: the "pure rotating waves" the parent talks about are literally $e^{i\theta }$ with $\theta$ marching forward. Each DFT frequency is one such spinning arrow.

3. Roots of unity — evenly spaced points on the circle

Now the star of the parent formula: ${\omega }_N$.

Before we go further, meet the two letters the parent formula uses as exponents on ${\omega }_N$:

In the figure ($N=8$): the red dot is ${\omega }_8$, one step clockwise from $1$. The other black dots are its powers ${\omega }_8^2,{\omega }_8^3,\dots$ — you visit every dot and land back on $1$ after $N$ steps, because: ${\omega }_N^N=(e^{-2\pi i/N}{)}^N=e^{-2\pi i}=1.$

Two facts the parent leans on, now obvious from the picture. Both need $N$ to be even so that $N/2$ is a whole number (radix-2 FFT always uses $N=2^m$, which is even):

The first makes the FFT split possible; the second makes the "butterfly" nearly free. Both are pictures of stepping around a circle, nothing more.

Why the topic needs it: ${\omega }_N$ is the "frequency dial". The weight ${\omega }_N^{nk}$ in the DFT sum says "spin sample $n$ by $k$ notches" — see Roots of Unity for the full geometry.

4. Sums — the $\sum$ symbol

Why the topic needs it: the DFT $X_k={\sum }_{n=0}^{N-1}{x}_n{\omega }_N^{nk}$ (here $k$ is the fixed frequency index from Section 3, and $n$ runs over all $N$ samples) is "for one output $k$, spin every sample and add them all up". The $\sum$ is the and add them all up part.

5. Geometric series — why orthogonality works

The parent's proof that the basis waves are independent rests on one classic sum.

The magic in the DFT: the ratio $r$ is itself a root of unity, so $r^N=1$, which makes the top $r^N-1=0$. The whole sum collapses to zero. That single line is why different frequencies don't leak into each other — see Geometric Series and Linear Algebra — Orthogonal Bases.

Why the topic needs it: "orthogonal basis" is a fancy way of saying each frequency can be measured on its own without solving a big equation system. The geometric series is the engine that proves it.

6. Orthogonal bases — measuring one ingredient at a time

Why the topic needs it: the whole derivation of the DFT is "project onto orthogonal waves". Full background: Linear Algebra — Orthogonal Bases.

7. Big-O and divide-and-conquer — measuring speed

The FFT half of the parent page is about cost, not values.

Why the topic needs it: this is literally why the FFT is famous — not new math, just a faster route to the same DFT numbers.

Prerequisite map

Downstream, these feed Convolution Theorem, Continuous Fourier Transform, and Sampling & Aliasing (Nyquist) — but you don't need those to read the parent.

Equipment checklist

Test yourself — cover the right side. If any answer surprises you, re-read that section before the parent.