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

---

1. The Discrete Fourier Transform (DFT)

WHY this formula? (Derivation from first principles)

WHAT we want: write $x_n$ as a combination of the simplest periodic functions on $N$ points — the complex exponentials $e^{2\pi i k n /N}$, one per integer frequency $k$.

Step 1 — Propose the basis. Define vectors $\mathbf{e}^{(k)}$ with components $e^{(k)}_n = e^{2\pi i kn/N}$.

Why this step? On a discrete grid of $N$ points, only $N$ distinct frequencies exist (frequency $k$ and $k+N$ give the same samples since $e^{2\pi i (k+N)n/N}=e^{2\pi i kn/N}$). So we need exactly $N$ basis vectors.

Step 2 — Show they are orthogonal. Compute the inner product (with conjugate): $\langle \mathbf{e}^{(k)},\mathbf{e}^{(j)}\rangle = \sum_{n=0}^{N-1} e^{2\pi i kn/N}\,e^{-2\pi i jn/N}=\sum_{n=0}^{N-1} \big(e^{2\pi i(k-j)/N}\big)^n.$ This is a geometric series with ratio $r=e^{2\pi i(k-j)/N}$.

Why this step? Orthogonality means we can extract each coefficient independently — no solving a linear system.

• If $k=j$: every term is $1$, sum $=N$.
• If $k\ne j$: $r\ne 1$ but $r^N = e^{2\pi i(k-j)}=1$, so $\sum_{n} r^n = \dfrac{r^N-1}{r-1}=0$.

Thus $\langle \mathbf{e}^{(k)},\mathbf{e}^{(j)}\rangle = N\,\delta_{kj}$.

Step 3 — Project. Write $x_n=\frac1N\sum_k X_k\, e^{2\pi i kn/N}$ (inverse). Taking the inner product with $\mathbf e^{(k)}$ and using orthogonality kills all but one term, giving $X_k=\sum_{n=0}^{N-1} x_n\, e^{-2\pi i kn/N}=\sum_n x_n\,\omega_N^{nk}.$ That is the DFT. The minus sign appears because we conjugate when projecting.

---

2. Cost of the naïve DFT

Each $X_k$ is a sum of $N$ products; there are $N$ outputs $\Rightarrow$ $N^2$ complex multiplications. For $N=10^6$ that's $10^{12}$ ops — too slow. The FFT fixes this.

---

3. The FFT — Cooley–Tukey (radix-2)

Assume $N$ is even (radix-2 needs $N=2^m$). Split: $X_k=\sum_{n\text{ even}} x_n\omega_N^{nk}+\sum_{n\text{ odd}} x_n\omega_N^{nk}.$ Let $n=2m$ (even) and $n=2m+1$ (odd), $m=0,\dots,N/2-1$: $X_k=\sum_{m} x_{2m}\,\omega_N^{2mk}+\omega_N^{k}\sum_m x_{2m+1}\,\omega_N^{2mk}.$

Key identity: $\omega_N^{2}=e^{-4\pi i/N}=e^{-2\pi i/(N/2)}=\omega_{N/2}$.

Why this matters: $\omega_N^{2mk}=\omega_{N/2}^{mk}$, so each inner sum is exactly a DFT of length $N/2$: $\boxed{\;X_k = E_k + \omega_N^{k}\,O_k\;}$ where $E_k=\text{DFT}_{N/2}(\text{even part})$, $O_k=\text{DFT}_{N/2}(\text{odd part})$.

The free second half (the symmetry that gives the speedup): $E_k$ and $O_k$ are periodic with period $N/2$, and $\omega_N^{k+N/2}=\omega_N^{N/2}\omega_N^k=-\omega_N^k$. Therefore: $X_{k} = E_k + \omega_N^k O_k,\qquad X_{k+N/2}=E_k - \omega_N^k O_k,\quad k=0,\dots,\tfrac N2-1.$

Complexity (derive it)

Let $T(N)$ = work to do an $N$-point FFT. We do two half-size FFTs plus $N/2$ butterflies ($O(N)$ combine): $T(N)=2\,T(N/2)+cN.$ By the Master Theorem (or unrolling $\log_2 N$ levels, each costing $cN$): $T(N)=O(N\log_2 N).$ Why $\log N$ levels? Halving $N$ repeatedly until size 1 takes $\log_2 N$ steps; each full level touches all $N$ values once.

---

4. Worked examples

---

5. Common mistakes (Steel-manned)

---

6. Active recall

Recall Flashcards

#flashcards/maths DFT formula for $X_k$? ::: $X_k=\sum_{n=0}^{N-1}x_n\,\omega_N^{nk}$ with $\omega_N=e^{-2\pi i/N}$. Why are the DFT basis vectors usable independently? ::: They are orthogonal: $\langle e^{(k)},e^{(j)}\rangle=N\delta_{kj}$ (geometric-series argument). Why does the $k\ne j$ inner product vanish? ::: Geometric series with ratio $r\ne1$ but $r^N=1$, so $(r^N-1)/(r-1)=0$. Cooley–Tukey split — what two sub-DFTs appear? ::: Length-$N/2$ DFTs of the even-indexed and odd-indexed samples, $E_k$ and $O_k$. Key identity that makes sub-sums into half-size DFTs? ::: $\omega_N^2=\omega_{N/2}$. The butterfly equations? ::: $X_k=E_k+\omega_N^kO_k$ and $X_{k+N/2}=E_k-\omega_N^kO_k$. Why does $X_{k+N/2}$ come almost free? ::: $\omega_N^{k+N/2}=-\omega_N^k$, so only a sign flips. FFT recurrence and its solution? ::: $T(N)=2T(N/2)+cN\Rightarrow O(N\log_2 N)$. Speedup factor over naïve DFT? ::: $N/\log_2 N$. For real input, relation between $X_k$ and $X_{N-k}$? ::: $X_{N-k}=\overline{X_k}$ (conjugate symmetry). Why the $1/N$ in the IDFT? ::: Basis vectors have squared norm $N$; normalization undoes it.

Recall Feynman: explain to a 12-year-old

Imagine you record a chord on a piano as a wiggly line. The DFT is a machine that listens and tells you "this much C, this much E, this much G." Doing it the slow way is like checking every note against every moment of the recording — tons of checking. The FFT is a smart shortcut: it splits the recording into "even moments" and "odd moments," figures out each smaller piece, then glues them back with one quick twist each. Splitting again and again means way less work — and that's how your phone shows music bars dancing in real time.

---

7. Connections

• Roots of Unity — $\omega_N$ and the cyclic structure powering the DFT.
• Geometric Series — proves basis orthogonality.
• Linear Algebra — Orthogonal Bases — DFT is a change of basis by a unitary (Fourier) matrix.
• Divide and Conquer Algorithms — same recurrence as merge sort.
• Master Theorem — solves $T(N)=2T(N/2)+cN$.
• Convolution Theorem — FFT makes polynomial/integer multiplication $O(N\log N)$.
• Continuous Fourier Transform — the integral limit of the DFT.
• Sampling & Aliasing (Nyquist) — why $k$ wraps to negative frequencies.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, DFT ka matlab simple hai: tumhare paas $N$ samples hain (jaise sound ya signal), aur tum jaanna chahte ho ki usme kaun kaun si frequencies kitni hain. Iske liye hum signal ko pure rotating waves ($e^{-2\pi i kn/N}$) ke combination me todte hain. Har wave alag frequency $k$ ki hoti hai, aur formula $X_k=\sum_n x_n\,\omega_N^{nk}$ bas yeh "kitna" measure karta hai. Yeh waves orthogonal hoti hain (geometric series se prove hota hai), isiliye har coefficient alag se nikal aata hai — koi bada equation solve nahi karna padta.

Ab problem yeh hai ki naive tareeke se yeh $N^2$ operations leta hai, jo bade $N$ ke liye bahut slow hai. Yahin pe FFT (Cooley–Tukey) ka jaadu aata hai. Idea: samples ko even index aur odd index me baant do. Dono halves khud apne aap me chhoti DFT ($N/2$ size) ban jaate hain — kyunki ek mast identity hai, $\omega_N^2=\omega_{N/2}$. Phir dono ko jodne ke liye butterfly use karte hain: $X_k=E_k+\omega_N^k O_k$ aur $X_{k+N/2}=E_k-\omega_N^k O_k$. Dhyaan do — neeche wala output bas sign flip se mil gaya, free me! Ek multiply me do output.

Yeh splitting baar baar karte raho, toh $\log_2 N$ levels banti hain, har level $N$ work, total $O(N\log N)$. $N=2^{20}$ pe yeh lagbhag 50,000 guna fast hai naive se. Isiliye MP3, JPEG, MRI, mobile audio bars — sab FFT pe chalte hain.

Ek common galti: log sochte hain FFT aur DFT alag-alag answer dete hain. Nahi! FFT bas DFT ka fast algorithm hai, answer bilkul same. Aur radix-2 FFT ke liye $N$ ka power-of-2 hona zaroori hai, warna mixed-radix ya Bluestein lagta hai. Inverse karte waqt $1/N$ lagana mat bhoolna, warna scale bigad jaata hai.