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

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

Poore note mein yahi do symbols baar baar aate hain. Shuru karne se pehle inhe plain words mein samajh lo:

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

Level 1 — Recognition

Problem 1.1

$ω_{8}^{0}$ , $ω_{8}^{4}$ , aur $ω_{8}^{8}$ ki values batao — koi exponential calculate mat karo, sirf "clockwise rotation kahan land karta hai" ka use karo.

Recall Solution 1.1

Upar figure mein $8$ tick marks wali clock imagine karo. Har step ek-aathvaan turn hota hai.

$ω_{8}^{0}$ : zero steps liye, abhi bhi shuruat mein hi hain $\Rightarrow 1$ .
$ω_{8}^{4}$ : chaar steps = aadha full turn = $1$ ke bilkul opposite wala point $\Rightarrow - 1$ .
$ω_{8}^{8}$ : aath steps = ek poora turn, waapis ghar $\Rightarrow 1$ . Humne kya use kiya: $ω_{N}^{N} = 1$ aur "aadha turn $- 1$ hota hai." Koi calculator nahi, sirf circle ki geometry.

Problem 1.2

DFT formula $X_{k} = \sum_{n = 0}^{N - 1} x_{n} ω_{N}^{nk}$ mein, kaun sa index input position hai aur kaun sa output frequency? $X_{0}$ words mein hamesha kya hota hai?

Recall Solution 1.2

$n$ = input position (kaunsa sample), yeh woh cheez hai jis par sum liya ja raha hai.
$k$ = output frequency (kaun sa coefficient tum bana rahe ho).
$X_{0} = \sum_{n} x_{n} ω_{N}^{0} = \sum_{n} x_{n} \cdot 1 = \sum_{n} x_{n}$ : sabhi samples ka seedha sum (yeh "DC term" hai, $N \times$ average ke barabar). Frequency zero par wave kabhi rotate nahi karti, isliye har sample weight $1$ ke saath count hota hai.

Level 2 — Application

Problem 2.1

$x = (1, 0, 0, 0)$ (position $0$ par ek spike), $N = 4$ ka DFT compute karo.

Recall Solution 2.1

Sirf $x_{0} = 1$ nonzero hai, isliye har sum apne $n = 0$ term par collapse ho jaata hai: $X_{k} = \sum_{n = 0}^{3} x_{n} ω_{4}^{nk} = x_{0} ω_{4}^{0} = 1 for every k .$ Result: $X = (1, 1, 1, 1)$ . Matlab: time mein ek bilkul sharp spike frequency mein bilkul flat hoti hai — yeh har frequency ko equally contain karti hai. Yeh "ek delta mein saari frequencies hoti hain" ka discrete cousin hai.

Problem 2.2

Constant signal $x = (1, 1, 1, 1)$ , $N = 4$ ka DFT compute karo.

Recall Solution 2.2

$X_{k} = \sum_{n = 0}^{3} 1 \cdot ω_{4}^{nk} = 1 + ω_{4}^{k} + ω_{4}^{2 k} + ω_{4}^{3 k} .$ Yeh ratio $r = ω_{4}^{k}$ ke saath ek Geometric Series hai.

$k = 0$ : ratio $= 1$ , chaaron terms $1$ hain, sum $= 4$ .
$k = 1, 2, 3$ : $r \neq = 1$ lekin $r^{4} = ω_{4}^{4 k} = 1$ , isliye $\frac{r ^{4} - 1}{r - 1} = \frac{0}{r - 1} = 0$ .

Result: $X = (4, 0, 0, 0)$ . Matlab: ek constant sirf frequency $0$ hai — Problem 2.1 ka bilkul mirror image. Time mein flat $\Rightarrow$ frequency mein single spike.

Problem 2.3

$x = (2, 0, - 2, 0)$ ka poora $N = 4$ DFT directly compute karo.

Recall Solution 2.3

Yaad karo $ω_{4}^{0} = 1, ω_{4}^{1} = - i, ω_{4}^{2} = - 1, ω_{4}^{3} = i$ . Sirf $x_{0} = 2, x_{2} = - 2$ bachte hain. $X_{k} = 2 ω_{4}^{0} + (- 2) ω_{4}^{2 k} = 2 - 2 ω_{4}^{2 k} = 2 - 2 (- 1)^{k} .$

$k = 0$ : $2 - 2 (1) = 0$ .
$k = 1$ : $2 - 2 (- 1) = 4$ .
$k = 2$ : $2 - 2 (1) = 0$ .
$k = 3$ : $2 - 2 (- 1) = 4$ .

Result: $X = (0, 4, 0, 4)$ . $k = 1$ aur $k = 3 = N - 1$ par do nonzero spikes ek discrete cosine-jaisi wave ka frequency $\pm 1$ pair hain.

Level 3 — Analysis

Problem 3.1

Prove karo ki real input $x_{n}$ ke liye, DFT satisfy karta hai $X_{N - k} = \overline{X_{k}}$ (bar matlab complex conjugate). Phir batao ki kyun yeh ek real signal ka spectrum store karne ka kaam aadha kar deta hai.

Recall Solution 3.1

Definition se shuru karo frequency $N - k$ par: $X_{N - k} = \sum_{n = 0}^{N - 1} x_{n} ω_{N}^{n (N - k)} = \sum_{n} x_{n} ω_{N}^{n N} ω_{N}^{- nk} .$ $ω_{N}^{n N} = (ω_{N}^{N})^{n} = 1^{n} = 1$ use karo (full turns kuch nahi karte): $X_{N - k} = \sum_{n} x_{n} ω_{N}^{- nk} .$ Ab conjugate. Kyunki $x_{n}$ real hai, $\overline{x_{n}} = x_{n}$ , aur $\overline{ω_{N}^{nk}} = ω_{N}^{- nk}$ (conjugate karna rotation direction flip kar deta hai). Isliye $\overline{X_{k}} = \overline{\sum_{n} x_{n} ω_{N}^{nk}} = \sum_{n} x_{n} ω_{N}^{- nk} = X_{N - k} . ■$ Kyun kaam bachta hai: spectrum ka upper half sirf lower half ka conjugate mirror hai. $k = 0, \dots, N /2$ store karo aur baaki free mein pata hai — real audio spectra isi tarah rakhe jaate hain.

Problem 3.2

Parent note ke orthogonality claim ko numerically verify karo $N = 4$ ke liye: dikhao ki $⟨ e^{(1)}, e^{(3)} ⟩ = 0$ , jahan $e_{n}^{(k)} = e^{2 π ik n / N}$ . Explain karo ki argument ki kaun si line ise zero banati hai.

Recall Solution 3.2

$⟨ e^{(1)}, e^{(3)} ⟩ = \sum_{n = 0}^{3} e^{2 π i (1) n /4} \overline{e^{2 π i (3) n /4}} = \sum_{n = 0}^{3} e^{2 π i (1 - 3) n /4} = \sum_{n = 0}^{3} (e^{- π i})^{n} = \sum_{n = 0}^{3} (- 1)^{n} .$ Yeh $1 - 1 + 1 - 1 = 0$ hai. Vanishing line: ratio $r = e^{- π i} = - 1$ $1$ nahi hai, phir bhi $r^{4} = 1$ , isliye Geometric Series sum $\frac{r ^{4} - 1}{r - 1} = \frac{0}{- 2} = 0$ . Orthogonality aur kuch nahi sirf yeh geometric-series cancellation hai — wave poore turns complete karti hai aur average zero ho jaata hai.

Level 4 — Synthesis

Problem 4.1

$x = (0, 1, 0, 1, 0, 1, 0, 1)$ ka $N = 8$ FFT ek Cooley–Tukey split (even/odd) use karke compute karo, aur result interpret karo. Twiddles jo tumhe chahiye ho sakti hain: $ω_{8}^{k} = e^{- iπ k /4}$ .

Recall Solution 4.1

Even aur odd positions mein split karo.

Even part $x_{0, 2, 4, 6} = (0, 0, 0, 0)$ .
Odd part $x_{1, 3, 5, 7} = (1, 1, 1, 1)$ .

Even part ka length-4 DFT sabhi zeros hai: $E_{k} = 0$ for all $k$ . Odd part $(1, 1, 1, 1)$ ka length-4 DFT hai (Problem 2.2 logic se, ab $N = 4$ ): $O = (4, 0, 0, 0)$ , yani $O_{0} = 4, O_{1} = O_{2} = O_{3} = 0$ .

Butterfly recombine $X_{k} = E_{k} + ω_{8}^{k} O_{k}$ aur $X_{k + 4} = E_{k} - ω_{8}^{k} O_{k}$ for $k = 0, 1, 2, 3$ :

$k = 0$ : $X_{0} = 0 + ω_{8}^{0} \cdot 4 = 4$ ; $X_{4} = 0 - 4 = - 4$ .
$k = 1, 2, 3$ : $O_{k} = 0$ , isliye $X_{k} = 0$ aur $X_{k + 4} = 0$ .

Result: $X = (4, 0, 0, 0, - 4, 0, 0, 0)$ . Interpretation: signal $(0, 1, 0, 1, \dots)$ "constant $\frac{1}{2}$ " plus "sabse fast wave $(+ \frac{1}{2}, - \frac{1}{2}, \dots)$ " hai. Yeh $k = 0$ par DC spike (value $4$ ) aur $k = N /2 = 4$ par Nyquist spike (value $- 4$ ) ke roop mein dikhte hain — dekho Nyquist. Har doosri frequency bilkul absent hai.

Problem 4.2

Recurrence $T (N) = 2 T (N /2) + c N$ use karke, radix-2 FFT $N = 8$ ke liye kitne exact complex multiplications (twiddle multiplies) karta hai yeh count karo, aur naïve DFT ke $N^{2}$ se compare karo.

Recall Solution 4.2

Har level par count karo. $lo g_{2} 8 = 3$ levels mein se har ek par $N /2 = 4$ butterflies hain, aur har butterfly mein ek twiddle multiply $ω_{N}^{k} O_{k}$ hoti hai. Isliye FFT multiply count hai $\frac{N}{2} lo g_{2} N = \frac{8}{2} \cdot 3 = 12 complex multiplies.$ (Inme se kuch $ω^{0} = 1$ se trivial multiplies hain; inhe bhi count karke hum $12$ paate hain.) Naïve DFT: $N^{2} = 64$ complex multiplies. Ratio: $64/12 \approx 5.3 \times$ kam, pehle se hi itne chote size $N = 8$ par. $N = 2^{20}$ par wahi formula parent note ka $\approx 5 \times 1 0^{4}$ speedup deta hai.

Level 5 — Mastery

Problem 5.1

Do length-4 sequences $a = (1, 2, 0, 0)$ aur $b = (1, 1, 0, 0)$ ko polynomials ke coefficients maana jaata hai, aur tum unka circular convolution $c = a ⊛ b$ (length 4) chahte ho. Convolution Theorem use karo: transform karo, pointwise multiply karo, inverse-transform karo. Phir direct convolution se verify karo.

Recall Solution 5.1

Circular convolution definition: $c_{m} = \sum_{n = 0}^{3} a_{n} b_{(m - n) mod 4}$ .

DFT ke through route (theorem: time mein convolution = frequency mein pointwise product). Pehle $A = DFT (a)$ with $ω_{4}^{k} \in {1, - i, - 1, i}$ : $A_{k} = 1 + 2 ω_{4}^{k} \Rightarrow A = (3, 1 - 2 i, - 1, 1 + 2 i) .$ Phir $B = DFT (b) = 1 + ω_{4}^{k}$ : $B = (2, 1 - i, 0, 1 + i) .$ Pointwise product $C_{k} = A_{k} B_{k}$ :

$C_{0} = 3 \cdot 2 = 6$ .
$C_{1} = (1 - 2 i) (1 - i) = 1 - i - 2 i + 2 i^{2} = - 1 - 3 i$ .
$C_{2} = (- 1) (0) = 0$ .
$C_{3} = \overline{C_{1}} = - 1 + 3 i$ (real inputs $\Rightarrow$ conjugate symmetry, Problem 3.1).

Inverse DFT $c_{m} = \frac{1}{4} \sum_{k} C_{k} ω_{4}^{- mk}$ , with $ω_{4}^{- 1} = i$ :

$c_{0} = \frac{1}{4} (6 + (- 1 - 3 i) + 0 + (- 1 + 3 i)) = \frac{1}{4} (4) = 1$ .
$c_{1} = \frac{1}{4} (6 + (- 1 - 3 i) i + 0 + (- 1 + 3 i) (- i)) = \frac{1}{4} (6 + (- i + 3) + (i + 3)) = \frac{1}{4} (12) = 3$ .
$c_{2} = \frac{1}{4} (6 + (- 1 - 3 i) (- 1) + 0 + (- 1 + 3 i) (- 1)) = \frac{1}{4} (6 + 1 + 3 i + 1 - 3 i) = \frac{1}{4} (8) = 2.$
$c_{3} = \frac{1}{4} (6 + (- 1 - 3 i) (- i) + 0 + (- 1 + 3 i) (i)) = \frac{1}{4} (6 + (i - 3) + (- i - 3)) = \frac{1}{4} (0) = 0.$

Toh $c = (1, 3, 2, 0)$ . Direct check (polynomial multiply phir mod 4 wrap): $(1 + 2 x) (1 + x) = 1 + 3 x + 2 x^{2}$ , coefficients $(1, 3, 2, 0)$ — kuch wrap nahi hota, toh match karta hai. ✓ Humne kya prove kiya: frequency domain mein multiply karna time mein convolve karne jaisa hi hai. Yahi reason hai ki FFT polynomial aur integer multiplication ko fast banata hai.

Problem 5.2

Ek DFT convention question with a numeric consequence. Physicist Alice forward DFT mein $1/ N$ factor aage laati hai aur inverse par koi factor nahi; parent note iska ulta use karta hai. $x = (1, 2, 3, 4)$ ke liye, Alice ka $X_{0}^{Alice}$ compute karo aur confirm karo ki yeh parent ke $X_{0}$ ka $\frac{1}{N}$ times hai.

Recall Solution 5.2

Parent ka $X_{0} = \sum_{n} x_{n} = 1 + 2 + 3 + 4 = 10$ . Alice ke forward transform mein $\frac{1}{N} = \frac{1}{4}$ hai: $X_{0}^{Alice} = \frac{1}{4} \cdot 10 = 2.5$ . Indeed $2.5 = \frac{1}{4} \cdot 10$ . ✓ Kyun matter karta hai: factor $N = ⟨ e^{(k)}, e^{(k)} ⟩$ (ek basis vector ka squared norm, Linear Algebra — Orthogonal Bases se) ko kahin na kahin rehna hi hai. Chahe yeh forward map par ho, inverse par, ya $1/ N$ ke roop mein dono par split ho — yeh sirf convention hai — lekin tumhe pata hona chahiye ki tumhari library kaun sa use karti hai warna tumhare amplitudes $N$ ke factor se galat ho jaate hain.

Recap

Recall Self-test checklist

Kaun sa time-domain signal totally flat spectrum deta hai? ::: Ek single spike $(1, 0, \dots, 0)$ — uska DFT sabhi $1$ s hota hai. Constant signal se kaun sa spectrum aata hai? ::: $k = 0$ par ek single spike: $(N, 0, \dots, 0)$ . Spectrum ki real-input symmetry? ::: $X_{N - k} = \overline{X_{k}}$ . Radix-2 FFT ke multiplies ka butterfly count? ::: $\frac{N}{2} lo g_{2} N$ . Convolution ko fast arithmetic mein kaise badlate ho? ::: Dono ko transform karo, pointwise multiply karo, inverse-transform karo (Convolution Theorem). DFT se linear (circular nahi) convolution pane ke liye kya karna chahiye? ::: Zero-pad karo length $\geq de g a + de g b + 1$ tak taaki koi wraparound na ho.