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

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

Scenario matrix

Har DFT/FFT problem jo tum miloge, in case classes mein se ek mein aayega. Columns batate hain ki case mein kya special hai; aakhri column us worked example ka naam deta hai jo ise cover karta hai.

Case class	Isme tricky kya hai	Covered by
DC / constant input	saare samples barabar → $k = 0$ par ek spike, baaki zeros	Ex 1
Single impulse (spike)	ek sample nonzero → flat spectrum, har $∣ X_{k} ∣$ barabar	Ex 2
Real cosine, on-grid	real input → do mirror spikes ( $k$ aur $N - k$ )	Ex 3
General real vector, hand DFT	poora computation, $ω_{N}$ ke saare quadrants use hote hain	Ex 4
Same vector via FFT butterflies	check karo algorithm = definition	Ex 5
Conjugate-symmetry shortcut	real input → aadha compute karo, baaki mirror karo	Ex 6
Degenerate: $N = 1$ aur $N = 2$	recursion ke base cases; "sabse chote DFTs"	Ex 7
Odd length $N = 3$	radix-2 fail hota hai — raw sum use karni padti hai	Ex 8
Word problem (real world)	ek tone ko sample karna, bins ko Hz mein padhna	Ex 9
Exam twist: cost counting	multiplies count karo, speedup number prove karo	Ex 10

Woh "signs / quadrants" jo parent note mein chinta ka vishay the (jaise $arctan$ mein), yahan unit circle par $ω_{N}^{nk}$ ki char jagahon ke roop mein dikhte hain: $+ 1$ (angle $0$ ), $- i$ (angle $- 90°$ ), $- 1$ (angle $180°$ ), $+ i$ (angle $+ 90°$ ). Neeche har example basically inhi char points par landing karna aur add karna hai.

Neeche wala figure haara master map hai. Horizontal axis real part hai, vertical axis imaginary part hai, aur white circle unit circle hai (radius $1$ ). Har colored arrow origin dot se shuru hota hai aur $ω_{4}$ ki ek power ki taraf point karta hai: yellow arrow $ω_{4}^{0} = 1$ ki taraf (right point karta hai, angle $0°$ ), blue arrow $ω_{4}^{1} = - i$ ki taraf (seedha neeche, angle $- 90°$ kyunki minus sign hai), pink arrow $ω_{4}^{2} = - 1$ ki taraf (left point karta hai, angle $180°$ ), aur doosra yellow arrow $ω_{4}^{3} = i$ ki taraf (seedha upar, angle $+ 90°$ ). Neeche har DFT sum bas inhi char spots par land karne wale arrows ko jodna hai.

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

Example 1 — DC / constant input

Worked example Flat signal

$N = 4$ lo aur $x = (5, 5, 5, 5)$ — ek signal jo kabhi nahi badalta. Saare char $X_{k}$ compute karo.

Forecast: abhi andaaza lagao. Agar ek signal mein bilkul bhi wiggle nahi hai, toh kitni frequencies light up honi chahiye? Kahaan?

Step 1. Sum likho $X_{k} = \sum_{n = 0}^{3} 5 \cdot ω_{4}^{nk} = 5 \sum_{n = 0}^{3} ω_{4}^{nk}$ . Yeh step kyun? $x_{n} = 5$ constant hai, isliye yeh sum se seedha factor ho jaata hai. Jo bacha hai woh roots of unity ka ek pure sum hai.

Step 2. $k = 0$ ke liye: har $ω_{4}^{0} = 1$ , isliye $X_{0} = 5 (1 + 1 + 1 + 1) = 20$ . Yeh step kyun? $k = 0$ ka matlab hai "yahaan kitna zero-frequency (average) hai?" — yeh hamesha bas $N \times$ mean hota hai.

Step 3. $k \neq = 0$ ke liye: $\sum_{n = 0}^{3} ω_{4}^{nk}$ circle ka ek poora chakkar hai — ek Geometric Series ratio $r = ω_{4}^{k} \neq = 1$ ke saath lekin $r^{4} = 1$ , isliye sum $\frac{r ^{4} - 1}{r - 1} = 0$ hai. Yeh step kyun? Yeh wohi orthogonality collapse hai parent note se: circle par equally spaced points cancel hokar zero ho jaate hain. Geometrically, agla figure $0°, 90°, 180°, 270°$ par char arrows dikhata hai jo tip-to-tail add hokar origin par wapas aate hain.

Result: $X = (20, 0, 0, 0)$ .

Verify: isko invert karo. $x_{n} = \frac{1}{4} \sum_{k} X_{k} ω_{4}^{- nk} = \frac{1}{4} (20) = 5$ har $n$ ke liye — flat signal wapas aata hai. ✓ Sanity: sirf ek nonzero bin, bilkul waisa hi jaisa forecast kiya gaya tha zero wiggle wale signal ke liye.

Neeche ke char unit arrows (har ek $k \neq = 0$ sum ke ek term ke liye) head-to-tail chain banaate hain aur starting dot par wapas land karte hain — isliye sum exactly zero hota hai.

Example 2 — single impulse (Ex 1 ka dual)

Worked example Ek sample mein saari energy

$N = 4$ , $x = (1, 0, 0, 0)$ — ek akela "click". Spectrum compute karo.

Forecast: Ex 1 time mein flat tha aur frequency mein spike tha. Yeh time mein spike hai. Guess karo spectrum kaisa dikhega.

Step 1. $X_{k} = \sum_{n = 0}^{3} x_{n} ω_{4}^{nk} = x_{0} ω_{4}^{0 \cdot k} = 1$ . Yeh step kyun? Sirf $x_{0}$ nonzero hai, aur uska weight $ω_{4}^{0} = 1$ hai har $k$ ke liye. Baaki saare terms vanish ho jaate hain kyunki unka sample $0$ hai.

Step 2. Isliye $X_{k} = 1$ saare $k$ ke liye. Yeh step kyun? Time mein ek sharp click sabhi frequencies equally contain karta hai — constant signal ka exact mirror. Yeh "delta function ka flat spectrum hota hai" ka discrete cousin hai.

Result: $X = (1, 1, 1, 1)$ .

Verify: saare char bins ke liye $∣ X_{k} ∣ = 1$ (flat magnitude). Invert karo: $x_{n} = \frac{1}{4} \sum_{k} 1 \cdot ω_{4}^{- nk}$ . $n = 0$ ke liye yeh $\frac{1}{4} (4) = 1$ hai; $n \neq = 0$ ke liye roots sum to $0$ ho jaate hain (Ex 1 argument). Toh $x = (1, 0, 0, 0)$ wapas aata hai. ✓

Example 3 — real cosine exactly grid par sampled

Worked example Bin 3 par ek pure tone

$N = 8$ , $x_{n} = cos (\frac{2 π \cdot 3 \cdot n}{8})$ , $n = 0, \dots, 7$ . Pata karo kaun se bins light up hote hain.

Forecast: ek real cosine — kitne spikes, aur kaun se $k$ par?

Step 1. Euler use karo: $cos θ = \frac{1}{2} (e^{i θ} + e^{- i θ})$ , isliye $x_{n} = \frac{1}{2} (e^{2 π i 3 n /8} + e^{- 2 π i 3 n /8})$ . Yeh step kyun? DFT basis complex exponentials se bana hai, isliye cosine ko do exponentials ki tarah rewrite karna isko basis ke saath directly match karne deta hai — koi summing required nahi.

Step 2. Inverse DFT $x_{n} = \frac{1}{N} \sum_{k} X_{k} e^{+ 2 π i k n / N}$ se compare karo. Wahaan har term ek positive-exponent exponential $e^{+ 2 π i k n /8}$ hai amplitude $\frac{1}{N} X_{k} = \frac{1}{8} X_{k}$ ke saath. Yeh step kyun? IDFT hame exactly batata hai ki har bin kya shape contribute karta hai: bin $k$ contribute karta hai $\frac{1}{8} X_{k} e^{+ 2 π i k n /8}$ . Isliye $X_{k}$ padhne ke liye hum bas apne do exponentials ko is template se term by term match karte hain.

Step 3. $x_{n}$ ke do pieces ko IDFT terms se match karo.

$\frac{1}{2} e^{+ 2 π i 3 n /8}$ $k = 3$ template hai jahan $\frac{1}{8} X_{3} = \frac{1}{2} \Rightarrow X_{3} = 4$ .
$\frac{1}{2} e^{- 2 π i 3 n /8} = \frac{1}{2} e^{+ 2 π i (8 - 3) n /8} = \frac{1}{2} e^{+ 2 π i 5 n /8}$ $k = 5$ template hai jahan $\frac{1}{8} X_{5} = \frac{1}{2} \Rightarrow X_{5} = 4$ . Yeh step kyun? Negative frequency $- 3$ ka $8$ -point grid par apna koi bin label nahi; yeh wrap hokar $8 - 3 = 5$ ho jaata hai. Isliye doosra exponential bin $5$ mein land karta hai, mirror spike deta hai. Baaki saare bins ka amplitude $0$ hai kyunki $x_{n}$ mein koi aur exponential nahi hai.

Result: $X_{3} = X_{5} = 4$ , baaki sab $0$ . Do mirror spikes.

Verify: neeche ka bar chart $∣ X_{k} ∣$ plot karta hai: $k = 3$ (yellow) aur $k = 5$ (pink) par do barabar spikes, dashed line Nyquist $N /2 = 4$ mark karta hai. Numerically raw sum deta hai $X_{3} = 4$ aur $X_{5} = \overline{X_{3}} = 4$ . ✓ Bin $5 = N - 3$ folded negative frequency hai.

Example 4 — general real vector, full hand DFT (saare char quadrants)

Worked example

$N = 4$ , $x = (1, 2, 3, 4)$ Raw definition se har $X_{k}$ compute karo, $ω_{4}$ ki char positions mein se har ek use karke.

Forecast: kaun se $X_{k}$ real honge, aur kaun sa pair complex conjugates hoga?

Step 1. Powers list karo: $ω_{4} = - i$ , isliye $ω_{4}^{0} = 1$ (angle $0$ ), $ω_{4}^{1} = - i$ (angle $- 90°$ ), $ω_{4}^{2} = - 1$ (angle $180°$ ), $ω_{4}^{3} = i$ (angle $+ 90°$ ). Yeh step kyun? Neeche har product inhi char spots mein se ek par land karta hai; pehle unhe naam dena sign errors rokta hai — yeh haara "quadrant check karo" wala version hai.

Step 2. $X_{0} = 1 + 2 + 3 + 4 = 10$ . Kyun? $k = 0$ weights saare $1$ hain: running total (mean $\times N$ ).

Step 3. $X_{1} = 1 + 2 (- i) + 3 (- 1) + 4 (i) = (1 - 3) + (- 2 + 4) i = - 2 + 2 i$ . Kyun? $k = 1$ $1, - i, - 1, i$ se guzarta hai — ek poora clockwise loop.

Step 4. $X_{2} = 1 + 2 (- 1) + 3 (1) + 4 (- 1) = 1 - 2 + 3 - 4 = - 2$ . Kyun? $k = 2$ deta hai $(- 1)^{n}$ : ek pure alternating sum, hamesha real.

Step 5. $X_{3} = 1 + 2 (i) + 3 (- 1) + 4 (- i) = (1 - 3) + (2 - 4) i = - 2 - 2 i$ . Kyun? $k = 3$ steps $1, i, - 1, - i$ — $k = 1$ ka counter-clockwise mirror, isliye hum $\overline{X_{1}}$ expect karte hain.

Result: $X = (10, - 2 + 2 i, - 2, - 2 - 2 i)$ .

Verify: $X_{0}$ aur $X_{2}$ real hain (jaise forecast kiya gaya: $k = 0$ aur $k = N /2$ real input ke liye hamesha real hote hain); $X_{3} = \overline{X_{1}}$ . Energy check (Parseval): $\sum ∣ x_{n} ∣^{2} = 1 + 4 + 9 + 16 = 30$ ; $\frac{1}{N} \sum ∣ X_{k} ∣^{2} = \frac{1}{4} (100 + 8 + 4 + 8) = \frac{120}{4} = 30$ . ✓

Example 5 — same vector via FFT butterflies

Worked example Cooley–Tukey

$x = (1, 2, 3, 4)$ par Ex 4 ko even/odd split use karke reproduce karo, aur operations count karo.

Forecast: FFT ko identical answer $(10, - 2 + 2 i, - 2, - 2 - 2 i)$ dena chahiye — lekin kam multiplies ke saath. Kitne kam?

Step 1. Split karo: even-indexed $x_{0, 2} = (1, 3)$ , odd-indexed $x_{1, 3} = (2, 4)$ . Yeh step kyun? Yeh core Cooley–Tukey move hai (Divide and Conquer Algorithms) — ek size-4 DFT ko do size-2 DFTs mein convert karo.

Step 2. Length-2 DFTs (yahaan $ω_{2} = - 1$ , isliye $(a, b)$ ka DFT $(a + b, a - b)$ hai): $E_{0} = 1 + 3 = 4, E_{1} = 1 - 3 = - 2$ ; $O_{0} = 2 + 4 = 6, O_{1} = 2 - 4 = - 2$ . Yeh step kyun? Size-2 base case hai — bas ek sum aur ek difference, bilkul bhi multiplies nahi.

Step 3. Twiddles $ω_{4}^{0} = 1, ω_{4}^{1} = - i$ . Butterflies: $X_{0} = E_{0} + ω_{4}^{0} O_{0} = 4 + 6 = 10$ ; $X_{1} = E_{1} + ω_{4}^{1} O_{1} = - 2 + (- i) (- 2) = - 2 + 2 i$ ; $X_{2} = E_{0} - ω_{4}^{0} O_{0} = 4 - 6 = - 2$ ; $X_{3} = E_{1} - ω_{4}^{1} O_{1} = - 2 - 2 i$ . Yeh step kyun? Har pair $(X_{k}, X_{k + 2})$ product $ω_{4}^{k} O_{k}$ share karta hai — ek baar compute hota hai, phir add aur subtract kiya jaata hai (free second half).

Result: $X = (10, - 2 + 2 i, - 2, - 2 - 2 i)$ — Ex 4 se identical. ✓

Verify: Ex 4 se exactly match karta hai. Ab honest op-count, multiplies aur additions:

Naïve DFT: $N^{2} = 16$ complex multiplies aur $N (N - 1) = 12$ complex additions.
Yeh FFT: do size-2 DFTs $0$ multiplies use karte hain (sirf $4$ add/subtracts total); combine stage mein $N /2 = 2$ twiddle multiplies hain (aur ek $ω_{4}^{0} = 1$ se hai, isliye really $1$ nontrivial) plus $N = 4$ add/subtracts char butterfly outputs ke liye. Toh multiplies $16$ se $2$ par aate hain aur additions $12$ se $8$ par. Chote se $N = 4$ par bhi dono counts girte hain; multiply saving woh hai jo $N$ badhne par compound hoti hai (Ex 10 dekho).

Neeche butterfly figure mein do blue inputs $(E_{0}, O_{0})$ aur $(E_{1}, O_{1})$ left par hain, yellow outputs $X_{0} \dots X_{3}$ right par hain, aur pink edges woh hain jo twiddle multiply $ω_{4}^{k}$ carry karte hain.

Example 6 — conjugate-symmetry shortcut

Worked example Sirf aadha compute karo, baaki mirror karo

$N = 8$ , real input $x = (0, 1, 0, - 1, 0, 1, 0, - 1)$ . $X_{N - k} = \overline{X_{k}}$ use karke aadha kaam bachao.

Forecast: real input ke liye, 8 mein se actually kitne independent complex bins hain?

Step 1. Signal ko closed form mein recognize karo. $x_{n} = sin (\frac{2 π \cdot 2 n}{8})$ test karo: $n = 1$ par, $sin (π /2) = 1$ ✓; $n = 2$ par, $sin (π) = 0$ ✓; $n = 3$ par, $sin (3 π /2) = - 1$ ✓. Toh $x_{n} = sin (2 π \cdot 2 n /8)$ , frequency $2$ ki pure sine hai. Yeh step kyun? Closed form naam dena spikes predict karne deta hai ( $k = 2$ aur uska mirror) compute karne se pehle, aur sum ko Ex 3 jaisa Euler match bana deta hai.

Step 2. $sin θ = \frac{1}{2 i} (e^{i θ} - e^{- i θ})$ likho aur IDFT template $\frac{1}{8} X_{k} e^{+ 2 π i k n /8}$ se match karo (bilkul Ex 3 ki tarah). $+ 2$ exponential deta hai $\frac{1}{8} X_{2} = \frac{1}{2 i} \Rightarrow X_{2} = \frac{8}{2 i} = - 4 i$ ; $- 2$ exponential bin $6$ par wrap hota hai $\frac{1}{8} X_{6} = - \frac{1}{2 i} \Rightarrow X_{6} = + 4 i$ ke saath. Baaki saare bins $0$ . Yeh step kyun? Ex 3 wahi trick, lekin sine ka $\frac{1}{2 i}$ coefficients ko imaginary aur sign mein opposite banata hai (sine ek odd function hai).

Step 3. Independent bins: $X_{0}, \dots, X_{4}$ (yeh $\frac{N}{2} + 1 = 5$ hain); baaki $X_{8 - k} = \overline{X_{k}}$ se free mein aate hain. Yeh step kyun? Real input mein conjugate symmetry hoti hai, isliye hum bins $0$ se $N /2$ tak compute karte hain aur baaki ko bina aur kaam ke reflect karte hain.

Result: $X = (0, 0, - 4 i, 0, 0, 0, 4 i, 0)$ .

Verify: $X_{6} = \overline{X_{2}} = \overline{- 4 i} = 4 i$ ✓. Parseval: $\sum ∣ x_{n} ∣^{2} = 4 \cdot 1 = 4$ ; $\frac{1}{8} \sum ∣ X_{k} ∣^{2} = \frac{1}{8} (16 + 16) = 4$ ✓. Forecast confirm hua: sirf 5 independent bins.

Example 7 — degenerate base cases $N = 1$ aur $N = 2$

Example 8 — odd length $N = 3$ (radix-2 forbidden)

Worked example Jab Cooley–Tukey evenly split nahi kar sakta

$N = 3$ , $x = (1, 1, 1)$ aur phir $x = (1, 2, 3)$ . Raw sum se compute karo — tum odd length ko halve nahi kar sakte.

Forecast: $N = 3$ hone par even/odd trick ka kya hoga?

Step 1. $ω_{3} = e^{- 2 π i /3}$ . Iske powers hain $ω_{3}^{0} = 1$ , $ω_{3}^{1} = - \frac{1}{2} - \frac{3}{2} i$ , $ω_{3}^{2} = - \frac{1}{2} + \frac{3}{2} i$ . Yeh step kyun? $3$ prime hai — radix-2 ko $N = 2^{m}$ chahiye, isliye hum definition par wapas jaate hain (ya Bluestein / mixed-radix use karte hain, parent ke mistakes section mein mention hai). Hum pehle teen circle positions list karte hain, $120°$ apart.

Step 2, case $(1, 1, 1)$ . $X_{0} = 1 + 1 + 1 = 3$ ; $X_{1} = 1 + ω_{3} + ω_{3}^{2} = 0$ ; $X_{2} = 1 + ω_{3}^{2} + ω_{3}^{4} = 1 + ω_{3}^{2} + ω_{3} = 0$ (kyunki $ω_{3}^{4} = ω_{3}^{3} \cdot ω_{3} = ω_{3}$ ). Yeh step kyun? Constant signal → single DC spike, bilkul Ex 1 ki logic $N = 3$ par: teen equally spaced arrows sum to zero. Note karo $ω_{3}^{4} = ω_{3}$ kyunki $ω_{3}^{3} = 1$ .

Step 3, case $(1, 2, 3)$ . Pehle $X_{0} = 1 + 2 + 3 = 6$ (sum, kyunki saare weights $1$ hain). Phir $X_{1} = 1 \cdot ω_{3}^{0} + 2 \cdot ω_{3}^{1} + 3 \cdot ω_{3}^{2} = 1 + 2 (- \frac{1}{2} - \frac{3}{2} i) + 3 (- \frac{1}{2} + \frac{3}{2} i) .$ Real part: $1 - 1 - \frac{3}{2} = - \frac{3}{2}$ . Imaginary part: $- 3 i + \frac{3 3}{2} i = \frac{3}{2} i$ . Toh $X_{1} = - \frac{3}{2} + \frac{3}{2} i$ . Aakhir mein $X_{2} = \overline{X_{1}} = - \frac{3}{2} - \frac{3}{2} i$ . Yeh step kyun? Hum har sample ko uski circle position mein plug karte hain aur real aur imaginary parts alag-alag add karte hain. $X_{0}$ hamesha plain sum hota hai. $X_{2} = \overline{X_{1}}$ kyunki input real hai, isliye conjugate symmetry $X_{N - k} = \overline{X_{k}}$ last bin free mein deti hai — wohi shortcut jaisa Ex 6 mein, ab $N = 3$ par.

Result: $(1, 1, 1) \to (3, 0, 0)$ ; $(1, 2, 3) \to (6, - \frac{3}{2} + \frac{3}{2} i, - \frac{3}{2} - \frac{3}{2} i)$ .

Verify $(1, 2, 3)$ : $∣ X_{1} ∣^{2} = \frac{9}{4} + \frac{3}{4} = 3$ . Parseval: $\sum ∣ x_{n} ∣^{2} = 1 + 4 + 9 = 14$ ; $\frac{1}{3} (36 + 3 + 3) = \frac{42}{3} = 14$ ✓.

Example 9 — real-world word problem

Worked example Ek bin ko hertz mein padhna

Tum ek audio signal $f_{s} = 8000$ Hz par sample karte ho aur $N = 1024$ samples lete ho. FFT bin $k = 128$ par ek bada spike dikhata hai. Tone ki frequency (Hz mein) kya hai?

Forecast: andaaza lagao — bin 128 mein spike 1024 mein se low, middle, ya high note hai?

Step 1. Bin spacing $Δ f = \frac{f _{s}}{N} = \frac{8000}{1024} = 7.8125$ Hz. Yeh step kyun? DFT frequency axis $[0, f_{s})$ ko $N$ barabar bins mein baant ta hai; bin $k$ $k \cdot Δ f$ par baitha hai. (Yeh Sampling & Aliasing (Nyquist) arithmetic hai.)

Step 2. Frequency $= k \cdot Δ f = 128 \times 7.8125 = 1000$ Hz. Yeh step kyun? Bin index ko spacing se multiply karo. Kyunki $128 < N /2 = 512$ , yeh ek genuine positive frequency hai, alias nahi.

Step 3. Range par sanity check: sabse high representable frequency Nyquist $f_{s} /2 = 4000$ Hz hai bin $512$ par. $1000$ Hz isse kaafi neeche hai. Yeh step kyun? Confirm karta hai ki hum ek real tone padh rahe hain, koi fold-back alias nahi.

Result: tone $1000$ Hz hai — ek middle-register note, kyunki bin $128$ Nyquist tak sirf ek quarter raasta hai.

Verify: $128 \times \frac{8000}{1024} = \frac{1024000}{1024} = 1000$ Hz ✓. Units: (bins) $\times$ (Hz/bin) = Hz ✓.

Example 10 — exam twist: speedup number prove karo

Worked example Multiplies count karo

$N = 1024 = 2^{10}$ ke liye, naïve DFT ko kitne complex multiplies chahiye vs radix-2 FFT ko, aur speedup kya hai?

Forecast: parent ne speedup $N / lo g_{2} N$ quote kiya. $N = 1024$ ke liye, roughly kaisa factor — tens, hundreds, thousands?

Step 1. Naïve: $N^{2} = 102 4^{2} = 1, 048, 576$ complex multiplies. Yeh step kyun? $N$ outputs mein se har ek $N$ products ka sum hai — parent note se $O (N^{2})$ cost.

Step 2. FFT: $\frac{N}{2} lo g_{2} N$ nontrivial twiddle multiplies $= \frac{1024}{2} \times 10 = 5120$ . Yeh step kyun? $lo g_{2} N = 10$ stages hain (Master Theorem on $T (N) = 2 T (N /2) + c N$ ), har ek mein $N /2 = 512$ butterflies hain, har ek mein ek twiddle multiply.

Step 3. Speedup $\frac{N ^{2}}{\frac{N}{2} lo g _{2} N} = \frac{2 N}{lo g _{2} N} = \frac{2 \times 1024}{10} = 204.8$ ; parent ka looser estimate $N / lo g_{2} N = 102.4$ . Yeh step kyun? Is baat par depend karta hai ki tum $N^{2}$ ko $N lo g N$ se compare karo ya tighter $\frac{N}{2} lo g N$ se, factor roughly $100$ – $200 \times$ hoga.

Result: naïve $\approx 1.05 \times 1 0^{6}$ , FFT $\approx 5120$ , speedup $\approx 200 \times$ .

Verify: $102 4^{2} /5120 = 204.8$ ✓. Isliye real-time audio kaam karta hai: $8$ kHz par $5120$ multiplies kisi bhi chip ke liye trivial hain; ek million nahi.

Recall

Recall Scenario check

Constant signal $(c, \dots, c)$ , $N$ points — spectrum? ::: $X_{0} = N c$ , baaki saare $X_{k} = 0$ . Single impulse $(1, 0, \dots, 0)$ — spectrum? ::: Flat: saare $k$ ke liye $X_{k} = 1$ . Real cosine integer freq $f$ par, length $N$ — kaun se bins? ::: $k = f$ aur $k = N - f$ , har ek amplitude $N /2$ . Real sine freq $f$ par — bin values? ::: $X_{f} = - i N /2$ , $X_{N - f} = + i N /2$ (imaginary, opposite signs). Radix-2 FFT $N = 3$ handle kyun nahi kar sakta? ::: $3$ power of $2$ nahi hai; equal even/odd halves mein split nahi ho sakta. $N$ -point FFT ka bin $k$ , $f_{s}$ par sampled, kaun si frequency par hai? ::: $k \cdot f_{s} / N$ Hz ( $k < N /2$ ke liye). Real length- $N$ input ke liye kitne independent complex bins hain? ::: $N /2 + 1$ (bins $0$ se $N /2$ tak); baaki conjugates hain. Radix-2 FFT ka multiply count? ::: Roughly $\frac{N}{2} lo g_{2} N$ twiddle multiplies.

Is saari speed ka payoff dekhne ke liye Convolution Theorem dekho: polynomials aur integers ki fast multiplication.