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

4.10.26 · D2 · Maths › Advanced Topics (Elite Level) › Fourier analysis — DFT, FFT algorithm (Cooley-Tukey)

Step 0 — Ek word jo pehle define karna zaroori hai: $ω_{N}$

KYA HAI. Hum baar baar ek hi object par depend karenge, toh chaliye pehle usse bana lete hain. Origin par centre karke radius $1$ ka ek circle lo. Uspe $N$ equally spaced dots mark karo, point $(1, 0)$ se shuru karke clockwise jaao. Start ke baad ka pehla dot $ω_{N}$ kehlayega (padho "omega-sub-N").

CLOCKWISE KYUN? Kyunki DFT $e^{- 2 π i / N}$ use karta hai — minus sign ek clockwise turn hai. Yeh minus kahaan se aata hai yeh hum baad mein dekhenge; abhi bas maan lo ki dots clockwise jaate hain.

PICTURE. Figure mein amber dot $ω_{N}$ hai. $k$ dots walk karne par aap $ω_{N}^{k}$ par pahunch jaate ho (multiply karna by $ω_{N}$ matlab "ek aur step turn karo"). $N$ dots baad aap wapas aa jaate ho: $ω_{N}^{N} = 1$ . Yeh hain $N$-th roots of unity.

$ω_{N} = one clockwise step of 36 0^{\circ} / N e^{- 2 π i / N}, dot number k ω_{N}^{k}, back to start ω_{N}^{N} = 1$

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

Definition Ek complex point ko kaise padhen (aur angle direction ke baare mein ek note)

Is circle par ek point $cos θ + i sin θ$ likha jaata hai: horizontal coordinate $cos θ$ hai, vertical $sin θ$ hai, aur $i$ bas ek label hai jiska matlab hai "yeh part vertical axis ka hai". Angle $θ$ positive horizontal axis se measure hota hai. Ek convention warning: normal textbook picture $θ$ ko counterclockwise measure karta hai, toh $e^{i θ} = cos θ + i sin θ$ counterclockwise turn karta hai jaise $θ$ badhta hai. Hamaara $ω_{N} = e^{- 2 π i / N}$ exponent mein minus carry karta hai, yaani angle $- 2 π / N$ — woh negative angle hi hai jo dots ko clockwise march karaata hai. Toh standard formula $cos θ + i sin θ$ bilkul wahi raha; hum bas usme ek negative $θ$ daal rahe hain. Cosine/sine picture mein kuch bhi ulta nahi hua — sirf angle ka sign badla jo hum plug in kar rahe hain.

Step 1 — $N$ points par ek "pure wave" ek dot hai jo fixed steps se spin karta hai

KYA HAI. Ek frequency $k$ fix karo (ek whole number). $N$ points ki ek list banao: dot $ω_{N}^{0} = 1$ se shuru karo aur har naye sample $n$ par $k$ dots clockwise jump karo. Sample $n$ dot $ω_{N}^{nk}$ par baithta hai. Woh $N$ points ek object mein collect karo aur usse $e^{(k)}$ bolao.

$e_{n}^{(k)} = ω_{N}^{nk}, which sample n, which frequency k, total dots jumped nk$

KYUN. Yeh list $cos$ aur $sin$ ka discrete cousin hai: iska horizontal shadow ek cosine trace karta hai, vertical shadow ek sine. Frequency $k$ = "ek sample mein kitne dots jump karte hain" = wave kitni tezi se wiggle karti hai. Yeh lists hamare building blocks hain — parent note ke basis vectors.

PICTURE. $N = 8$ ke liye, $k = 1$ ek sample per ek dot step karta hai (slow spin, slow wiggle); $k = 2$ ek sample per do dots step karta hai (faster). Same circle, alag stride. Figure mein cyan curve ( $k = 1$ ) follow karo — ek gentle hump — versus amber curve ( $k = 2$ ) — same $8$ samples mein double wiggles.

Step 2 — DFT poochta hai "mere data mein har wave kitni hai?"

KYA HAI. Data $x_{0}, \dots, x_{N - 1}$ diya gaya hai, DFT coefficient $X_{k}$ measure karta hai ki wave $k$ data mein kitni strongly appear karti hai. Hum isse compute karte hain har sample ko wave $k$ ke against line karke aur add karke:

$X_{k} = \sum_{n = 0}^{N - 1} data sample x_{n} \cdot wave k at sample n ω_{N}^{nk}$

Definition Inner product aur conjugate kyun aata hai

Do complex numbers ki lists $a$ aur $b$ ko "match" karne ke liye hum inner product $⟨ a, b ⟩ = \sum_{n} a_{n} \overline{b_{n}}$ use karte hain, jahan $\overline{b_{n}}$ complex conjugate hai (imaginary part ka sign flip karo, yaani dot ko horizontal axis ke across reflect karo). Conjugate zaroori hai: yeh $⟨ a, a ⟩ = \sum_{n} ∣ a_{n} ∣^{2}$ ko ek real, non-negative "length-squared" banata hai. Data ko wave $k$ par project karne ka matlab hai $⟨ x, e^{(k)} ⟩ = \sum_{n} x_{n} \overline{e_{n}^{(k)}} = \sum_{n} x_{n} \overline{ω_{N}^{nk}} = \sum_{n} x_{n} ω_{N}^{nk}$ compute karna — aur kyunki $\overline{ω_{N}^{nk}} = ω_{N}^{- nk}$ ... ruko: $ω_{N} = e^{- 2 π i / N}$ , toh $\overline{ω_{N}^{nk}} = e^{+ 2 π ink / N}$ . Forward DFT ko un-conjugated weight $ω_{N}^{nk} = e^{- 2 π ink / N}$ ke saath likhna exactly conjugated basis par projection hai. Wohi conjugation hai jahan $ω_{N}$ mein minus sign aata hai.

MULTIPLY-AND-ADD KYUN? Yeh ek orthogonal basis par projection hai. Kyunki waves orthogonal hain (parent Step 2, ek Geometric Series argument: $⟨ e^{(k)}, e^{(j)} ⟩ = N δ_{k j}$ ), data ko wave $k$ ke against match karna exactly wave $k$ ka share pick out karta hai aur har doosri wave ko zero cancel kar deta hai. Equations solve nahi karna — bas ek weighted sum.

PICTURE. Socho $N$ tuning forks hain, ek per frequency; $X_{k}$ batata hai fork $k$ kitna loud ring karta hai. Figure $N \times N$ grid of weights $ω_{N}^{nk}$ stack karta hai — colour = har weight ka angle. Aise padho: top row ( $k = 0$ ) ek flat colour hai — har weight $1$ hai, toh $X_{0}$ bas plain sum hai. Ek row neeche jaao ( $k$ badhta hai) aur colours row ke across tezi se cycle karte hain: row $k$ poore $k$ colour-cycles sweep karta hai jab $n$ $0$ se $N - 1$ tak jaata hai. Poore grid mein $N \times N$ coloured cells hain — yeh literally woh $N^{2}$ multiplies hain jo FFT avoid karega.

Step 3 — Sum split karo: even samples, odd samples

KYA HAI. Maano $N$ even hai. Samples ko index parity se sort karo: even-indexed wale $x_{0}, x_{2}, x_{4}, \dots$ aur odd-indexed wale $x_{1}, x_{3}, x_{5}, \dots$ . Ek bade sum ko do mein split karo:

$X_{k} = even samples m = 0 \sum N /2 - 1 x_{2 m} ω_{N}^{2 mk} + odd samples m = 0 \sum N /2 - 1 x_{2 m + 1} ω_{N}^{(2 m + 1) k}$

PARITY SE KYUN SPLIT KARO? Kyunki — aur yahi saara magic hai — even part ek smaller DFT niklegaa, aur odd part bhi. Yeh ek divide-and-conquer move hai: same problem ke do half-size copies solve karo.

PICTURE. Figure data ko do choti rows mein comb karta hai: cyan bars "even comb" hain ( $x_{0}, x_{2}, x_{4}, x_{6}$ ), amber bars "odd comb" ( $x_{1}, x_{3}, x_{5}, x_{7}$ ). Notice karo ki har comb mein exactly $N /2$ teeth hain — do half-size problems.

Step 4 — Odd part se ek twiddle factor bahar nikalo

KYA HAI. Odd sum mein, exponent hai $(2 m + 1) k = 2 mk + k$ . Kyunki $ω_{N}^{2 mk + k} = ω_{N}^{k} \cdot ω_{N}^{2 mk}$ , factor $ω_{N}^{k}$ $m$ par depend nahi karta, toh woh sum ke bahar slide ho jaata hai:

$X_{k} = \sum_{m} x_{2 m} ω_{N}^{2 mk} + woh "twiddle", bahar nikala ω_{N}^{k} \sum_{m} x_{2 m + 1} ω_{N}^{2 mk}$

BAHAR KYUN NIKALO? Kyunki ek baar woh chala jaata hai, dono remaining inner sums ka weight $ω_{N}^{2 mk}$ identical hota hai. Identical structure = dono ke liye ek hi sub-routine reuse kar sakte hain. Aakela bachaa hua $ω_{N}^{k}$ twiddle factor kehlata hai — ek single rotation jo per output apply hoti hai.

PICTURE. Figure mein do cyan boxes even aur odd sums hain; ab woh same weight $ω_{N}^{2 mk}$ carry karte hain. Unke beech amber dot twiddle $ω_{N}^{k}$ hai — woh ek rotation bahar nikali hui, odd box ke saamne baithee hai.

Step 5 — Key identity: $ω_{N}^{2} = ω_{N /2}$

KYA HAI. Shared weight $ω_{N}^{2 mk}$ dekho. Square group karo: $ω_{N}^{2 mk} = (ω_{N}^{2})^{mk}$ . Ab $ω_{N}^{2}$ compute karo:

$ω_{N}^{2} = (e^{- 2 π i / N})^{2} = e^{- 2 π i / (N /2)} = ω_{N /2}$

YEH REDUCTION KYUN FINISH KARTA HAI? $ω_{N /2}$ ek half-size grid ka twiddle hai. Toh har inner sum, $\sum_{m} x_{2 m} ω_{N /2}^{mk} = E_{k} aur \sum_{m} x_{2 m + 1} ω_{N /2}^{mk} = O_{k},$ literally ek $N /2$ -point DFT hai — $E_{k}$ even samples ka, $O_{k}$ odd samples ka. Humne ek size- $N$ problem ko do size- $N /2$ problems mein badal diya.

PICTURE. Figure mein faint white dots bade $N = 8$ circle hain; amber dots half-size $N /2 = 4$ circle hain. Bade circle ke around double stride se step karna (squaring) exactly amber dots par land karta hai — squaring = har doosra dot skip karna = ek chhote circle par drop karna.

$X_{k} = DFT_{N /2} of evens E_{k} + twiddle ω_{N}^{k} DFT_{N /2} of odds O_{k}$

Step 6 — Free second half: ek sign flip se do outputs milte hain

KYA HAI. Hamare paas $k = 0, \dots, \frac{N}{2} - 1$ ke liye $X_{k} = E_{k} + ω_{N}^{k} O_{k}$ hai. Lekin $E_{k}$ aur $O_{k}$ half-size DFTs hain, toh woh naturally sirf $N /2$ values produce karte hain — outputs $X_{N /2}, \dots, X_{N - 1}$ kaise milenge? Poochho ki $k + \frac{N}{2}$ par kya hota hai. Do facts:

$E_{k}$ aur $O_{k}$ period $N /2$ ke saath repeat karte hain (length $N /2$ ka DFT wrap around ho jaata hai): $E_{k + N /2} = E_{k}$ , same $O$ ke liye.
Twiddle sign flip karta hai: $ω_{N}^{k + N /2} = ω_{N}^{N /2} ω_{N}^{k} = (- 1) ω_{N}^{k}$ , kyunki $ω_{N}^{N /2}$ exactly half lap around ka dot hai $= - 1$ .

YEH PAYOFF KYUN HAI. Yeh dono milao:

$X_{k} = E_{k} + ω_{N}^{k} O_{k} X_{k + N /2} = E_{k} - ω_{N}^{k} O_{k}$

Dono outputs ek same multiply $ω_{N}^{k} O_{k}$ share karte hain — ek mein $+$ lagti hai, doosre mein $-$ . Do results, ek multiplication. Yeh hai butterfly.

PICTURE. Figure mein, do cyan inputs $E_{k}, O_{k}$ left side se enter karte hain; beech mein amber node single multiply $ω_{N}^{k} O_{k}$ hai; crossing lines usse upar le jaati hain (add → top output $X_{k}$ ) aur neeche (subtract → bottom output $X_{k + N /2}$ ). Woh crossing wings isliye butterfly kehlate hain.

Step 7 — Edge & degenerate cases (reader ko kabhi stranded mat chhoddo)

KYA / KYUN / PICTURE, chaar corners jinhe aap zaroor hit karoge:

$N = 1$ (base case). Ek single sample mein combine karne ko kuch nahi: $X_{0} = x_{0}$ . Recursion yahan ruk jaati hai — yeh "size-1 circle" hai, ek akela dot. Har FFT in par bottom out karta hai.
$N$ odd / power of 2 nahi. Even-odd split ko $N$ even chahiye; radix-2 ko $N = 2^{m}$ chahiye. Doosre $N$ ke liye ya toh zero pad karo agle power of two tak, ya mixed-radix / Bluestein use karo. Picture: aap ek odd row ko do equal combs mein nahi kaat sakte.
$k = 0$ (DC term). Har twiddle $ω_{N}^{0} = 1$ hai: $X_{0} = \sum_{n} x_{n}$ , bas plain sum (average $\times N$ ). Frequency $0$ ki "wave" flat line hai — bilkul koi wiggle nahi.
$k = N /2$ (Nyquist). Fastest resolvable wave: yeh $+ 1, - 1, + 1, - 1$ alternate karti hai. Yahan $ω_{N}^{N /2} = - 1$ , toh $X_{N /2} = \sum_{n} (- 1)^{n} x_{n}$ . $k = N /2$ se aage, indices negative frequencies par alias ho jaate hain (parent ka last mistake). Dekho Sampling & Aliasing (Nyquist).

PICTURE. Figure do extreme waves overlay karta hai: cyan flat line DC wave hai ( $k = 0$ , koi wiggle nahi); amber zig-zag Nyquist wave hai ( $k = N /2$ , fastest possible alternation). Har real frequency in dono ke beech rehti hai.

Ek-picture summary

Upar sab kuch $N = 4$ ke liye ek single diagram mein collapse ho jaata hai: do length-2 DFTs (har ek ek single butterfly) twiddles ki ek layer se feed hokar do output butterflies mein jaate hain. $x = (1, 2, 3, 4)$ ko iske through trace karo aur aapko milega $X = (10, - 2 + 2 i, - 2, - 2 - 2 i)$ — brute-force $N^{2}$ sum ka same answer, fraction of the cost mein. Left se right padho: chaar inputs left pe enter karte hain; crossings ki pehli pair (cyan/amber) beech mein half-DFT values $E_{0}, E_{1}, O_{0}, O_{1}$ produce karti hai; crossings ki doosri pair twiddles apply karti hai aur add/subtract se right pe chaar outputs $X_{0}, \dots, X_{3}$ deti hai.

Recall Feynman retelling (plain words, no symbols)

Socho ek wheel hai jisme $N$ equally spaced pegs hain. Ek "wave" ek marker hai jo har tick ek fixed number of pegs hop karta hai — fast wave ke liye zyada hop, slow wave ke liye thoda. DFT poochta hai, har possible hop-size ke liye, "kya yeh wave mera data mein chhup rahi hai?" — data ko us wave ke against rakhke aur add karke.

Har wave ke against har sample ke liye yeh karna ek giant $N \times N$ grid of little multiplies hai — slow. FFT ka trick: apna data even-numbered aur odd-numbered samples mein split karo. Ek clean fact ki wajah se — bade wheel pe double-fast hop karna same hai jaise half the pegs wale wheel pe normally hop karna — har half same kind of problem ban jaata hai, but half the size. Woh do chhote problems solve karo, phir stitch karo: har pair ke liye odd answer ek baar spin karo (woh "twiddle"), phir add karo ek output ke liye aur subtract karo doosre ke liye. Do answers, ek spin. Woh paired add/subtract butterfly hai.

Halving karte raho — even/odd, even/odd — jab tak har piece ek single number na ho jo khud hi answer ho. Lagbhag $lo g_{2} N$ layers of halving, har layer saare $N$ numbers ko ek baar touch karti hai. Isliye $N^{2}$ $N lo g N$ ban jaata hai, aur isliye aapka phone ek photo par Fourier transform kar sakta hai aapke blink khatam karne se pehle.

Recall Quick self-check

Woh single identity kaunsi hai jo har half-sum ko ek smaller DFT mein badal deti hai? ::: $ω_{N}^{2} = ω_{N /2}$ — twiddle ko square karna aapko half-size circle par drop kar deta hai. $X_{k + N /2}$ almost free kyun hai? ::: $ω_{N}^{k + N /2} = - ω_{N}^{k}$ , toh shared product ka sirf sign flip hota hai. Ek butterfly ke do outputs kya hain? ::: $E_{k} + ω_{N}^{k} O_{k}$ aur $E_{k} - ω_{N}^{k} O_{k}$ . Recursion kahaan rukti hai? ::: $N = 1$ par, jahan $X_{0} = x_{0}$ .