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

4.10.26 · Maths › Advanced Topics (Elite Level)

1. The Discrete Fourier Transform (DFT)

YEH formula kyun? (First principles se derivation)

HUM kya chahte hain: $x_{n}$ ko $N$ points par sabse simple periodic functions ka combination likhna — complex exponentials $e^{2 π ik n / N}$ , har integer frequency $k$ ke liye ek.

Step 1 — Basis propose karo. Vectors $e^{(k)}$ define karo jinka components $e_{n}^{(k)} = e^{2 π ik n / N}$ ho.

Yeh step kyun? $N$ points ke discrete grid par sirf $N$ distinct frequencies exist karti hain (frequency $k$ aur $k + N$ same samples dete hain kyunki $e^{2 π i (k + N) n / N} = e^{2 π ik n / N}$ ). Toh humein exactly $N$ basis vectors chahiye.

Step 2 — Dikhao ki yeh orthogonal hain. Inner product compute karo (conjugate ke saath): $⟨ e^{(k)}, e^{(j)} ⟩ = \sum_{n = 0}^{N - 1} e^{2 π ik n / N} e^{- 2 π ij n / N} = \sum_{n = 0}^{N - 1} (e^{2 π i (k - j) / N})^{n} .$ Yeh ek geometric series hai jiska ratio $r = e^{2 π i (k - j) / N}$ hai.

Yeh step kyun? Orthogonality ka matlab hai ki hum har coefficient ko independently extract kar sakte hain — koi linear system solve karne ki zaroorat nahi.

Agar $k = j$ ho: har term $1$ hai, sum $= N$ .
Agar $k \neq = j$ ho: $r \neq = 1$ lekin $r^{N} = e^{2 π i (k - j)} = 1$ , toh $\sum_{n} r^{n} = \frac{r ^{N} - 1}{r - 1} = 0$ .

Is tarah $⟨ e^{(k)}, e^{(j)} ⟩ = N δ_{k j}$ .

Step 3 — Project karo. $x_{n} = \frac{1}{N} \sum_{k} X_{k} e^{2 π ik n / N}$ likho (inverse). $e^{(k)}$ ke saath inner product lete hain aur orthogonality use karte hain toh sirf ek term bachta hai, jisse milta hai: $X_{k} = \sum_{n = 0}^{N - 1} x_{n} e^{- 2 π ik n / N} = \sum_{n} x_{n} ω_{N}^{nk} .$ Yahi DFT hai. Minus sign isliye aata hai kyunki project karte waqt conjugate lete hain.

2. Naive DFT ki cost

Har $X_{k}$ mein $N$ products ka sum hai; $N$ outputs hain $\Rightarrow$ $N^{2}$ complex multiplications. $N = 1 0^{6}$ ke liye yeh $1 0^{12}$ ops hain — bahut slow. FFT isse fix karta hai.

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

Maan lo $N$ even hai (radix-2 ko $N = 2^{m}$ chahiye). Split karo: $X_{k} = \sum_{n even} x_{n} ω_{N}^{nk} + \sum_{n odd} x_{n} ω_{N}^{nk} .$ $n = 2 m$ (even) aur $n = 2 m + 1$ (odd) lo, $m = 0, \dots, N /2 - 1$ : $X_{k} = \sum_{m} x_{2 m} ω_{N}^{2 mk} + ω_{N}^{k} \sum_{m} x_{2 m + 1} ω_{N}^{2 mk} .$

Key identity: $ω_{N}^{2} = e^{- 4 π i / N} = e^{- 2 π i / (N /2)} = ω_{N /2}$ .

Yeh kyun matter karta hai: $ω_{N}^{2 mk} = ω_{N /2}^{mk}$ , toh har inner sum exactly length $N /2$ ka DFT hai: $X_{k} = E_{k} + ω_{N}^{k} O_{k}$ jahaan $E_{k} = DFT_{N /2} (even part)$ , $O_{k} = DFT_{N /2} (odd part)$ .

Free second half (woh symmetry jo speedup deti hai): $E_{k}$ aur $O_{k}$ period $N /2$ ke saath periodic hain, aur $ω_{N}^{k + N /2} = ω_{N}^{N /2} ω_{N}^{k} = - ω_{N}^{k}$ . Isliye: $X_{k} = E_{k} + ω_{N}^{k} O_{k}, X_{k + N /2} = E_{k} - ω_{N}^{k} O_{k}, k = 0, \dots, \frac{N}{2} - 1.$

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

Complexity (derive karo)

$T (N)$ = $N$ -point FFT karne ka kaam. Hum do half-size FFTs karte hain plus $N /2$ butterflies ( $O (N)$ combine): $T (N) = 2 T (N /2) + c N .$ Master Theorem se (ya $lo g_{2} N$ levels unroll karke, har level ka cost $c N$ ): $T (N) = O (N lo g_{2} N) .$ $lo g N$ levels kyun? $N$ ko baar baar halve karte hue size 1 tak pahunchne mein $lo g_{2} N$ steps lagte hain; har full level mein saare $N$ values ek baar touch hote hain.

4. Worked examples

5. Common mistakes (Steel-manned)

6. Active recall

Recall Flashcards

#flashcards/maths $X_{k}$ ke liye DFT formula kya hai? ::: $X_{k} = \sum_{n = 0}^{N - 1} x_{n} ω_{N}^{nk}$ with $ω_{N} = e^{- 2 π i / N}$ . DFT basis vectors independently usable kyun hain? ::: Yeh orthogonal hain: $⟨ e^{(k)}, e^{(j)} ⟩ = N δ_{k j}$ (geometric-series argument). $k \neq = j$ inner product zero kyun hota hai? ::: Geometric series jiska ratio $r \neq = 1$ lekin $r^{N} = 1$ hai, toh $(r^{N} - 1) / (r - 1) = 0$ . Cooley–Tukey split — kaun se do sub-DFTs aate hain? ::: Even-indexed aur odd-indexed samples ke length- $N /2$ DFTs, $E_{k}$ aur $O_{k}$ . Key identity jo sub-sums ko half-size DFTs banati hai? ::: $ω_{N}^{2} = ω_{N /2}$ . Butterfly equations kya hain? ::: $X_{k} = E_{k} + ω_{N}^{k} O_{k}$ aur $X_{k + N /2} = E_{k} - ω_{N}^{k} O_{k}$ . $X_{k + N /2}$ almost free kyun aata hai? ::: $ω_{N}^{k + N /2} = - ω_{N}^{k}$ , toh sirf sign flip hota hai. FFT recurrence aur uska solution? ::: $T (N) = 2 T (N /2) + c N \Rightarrow O (N lo g_{2} N)$ . Naive DFT se speedup factor kya hai? ::: $N / lo g_{2} N$ . Real input ke liye, $X_{k}$ aur $X_{N - k}$ mein kya relation hai? ::: $X_{N - k} = \overline{X_{k}}$ (conjugate symmetry). IDFT mein $1/ N$ kyun hai? ::: Basis vectors ka squared norm $N$ hai; normalization usse undo karta hai.

Recall Feynman: 12-saal ke bacche ko explain karo

Socho tumne piano par ek chord record kiya ek wiggly line ki tarah. DFT ek aisi machine hai jo sunte hain aur batati hai "itna C, itna E, itna G." Slow tarike se karna aisa hai jaise har note ko recording ke har moment ke against check karo — bahut saara checking. FFT ek smart shortcut hai: recording ko "even moments" aur "odd moments" mein split karta hai, har chote piece ko figure out karta hai, phir ek quick twist se glue karta hai. Baar baar split karne se bahut kam kaam hota hai — aur isi wajah se tumhara phone music bars ko real time mein naachte hua dikhata hai.

7. Connections

Roots of Unity — $ω_{N}$ aur cyclic structure jo DFT ko power karta hai.
Geometric Series — basis orthogonality prove karta hai.
Linear Algebra — Orthogonal Bases — DFT ek unitary (Fourier) matrix se change of basis hai.
Divide and Conquer Algorithms — merge sort jaisi hi recurrence.
Master Theorem — $T (N) = 2 T (N /2) + c N$ solve karta hai.
Convolution Theorem — FFT polynomial/integer multiplication ko $O (N lo g N)$ banata hai.
Continuous Fourier Transform — DFT ka integral limit.
Sampling & Aliasing (Nyquist) — kyun $k$ negative frequencies par wrap karta hai.