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

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

Is page ke prerequisites: Roots of Unity, Geometric Series, Linear Algebra — Orthogonal Bases, Divide and Conquer Algorithms, Master Theorem, Convolution Theorem, Continuous Fourier Transform, Sampling & Aliasing (Nyquist).

Definition Is page par use hone wali Notation aur conventions

Ye symbols neeche baar baar aate hain; inhe abhi pakad lo taaki koi bhi trap hidden notation ki wajah se na nikle.

DFT $N$ samples $x_{0}, x_{1}, \dots, x_{N - 1}$ leta hai aur $N$ coefficients $X_{0}, X_{1}, \dots, X_{N - 1}$ output karta hai, formula $X_{k} = \sum_{n = 0}^{N - 1} x_{n} ω_{N}^{nk}$ se, har $k = 0, 1, \dots, N - 1$ ke liye. Dono indices $n$ (sample position) aur $k$ (frequency) ek hi range $0$ se $N - 1$ par chalte hain.
$ω_{N} = e^{- 2 π i / N}$ twiddle factor hai: unity ka ek primitive $N$ -th root, yaani unit circle ke around ek full turn ka $1/ N$ hissa, minus sign ki wajah se clockwise liya gaya. Ye satisfy karta hai $ω_{N}^{N} = 1$ .
$E_{k}$ aur $O_{k}$ butterfly ke andar use hone wale half-size DFTs hain: $E_{k}$ , even-indexed samples $x_{0}, x_{2}, x_{4}, \dots$ ka length- $N /2$ DFT hai, aur $O_{k}$ , odd-indexed samples $x_{1}, x_{3}, x_{5}, \dots$ ka length- $N /2$ DFT hai. Dono $k = 0, \dots, N /2 - 1$ se indexed hain lekin period $N /2$ ke saath periodic hain, isliye $E_{k + N /2} = E_{k}$ aur $O_{k + N /2} = O_{k}$ .
Discrete negative frequency: index $k > N /2$ frequency $k - N$ ko represent karta hai, jo negative hai. Ye isliye hai kyunki $ω_{N}^{nk} = ω_{N}^{n (k - N)}$ (kyunki $ω_{N}^{n N} = 1$ ), isliye index $k$ aur index $k - N$ samples par identically act karte hain. Frequencies isliye circle ${\dots, - 2, - 1, 0, 1, 2, \dots}$ modulo $N$ par rehti hain; index $k$ ki "true" frequency woh hai jo $k$ ya $k - N$ mein magnitude mein chhoti ho.
$lo g_{2} N$ ka matlab base-2 (binary) logarithm hai — " $N$ ko 1 tak pahunchne se pehle kitni baar halve kar sakte ho?" $N = 2^{m}$ ke liye, $lo g_{2} N = m$ . Is page par har $lo g$ base 2 ka hai.
Sign convention: forward DFT negative exponent use karta hai, $X_{k} = \sum_{n = 0}^{N - 1} x_{n} ω_{N}^{nk}$ ; inverse positive exponent $1/ N$ ke saath use karta hai. Neeche saare "minus-sign in the exponent" answers yahi choice assume karte hain.

Sach ya jhooth — justify karein

FFT ek alag, approximate version of the DFT compute karta hai

Jhooth. FFT usi DFT ke liye ek exact algorithm hai; ye sirf arithmetic ko reorganize karta hai. Practice mein farq sirf floating-point rounding ka hota hai, jo bahut chhota hota hai aur algorithm ki logic se related nahi hai.

N

ko double karne se DFT-vs-FFT speed advantage roughly double ho jaata hai

Jhooth. Advantage

N / lo g_{2} N

hai, jo sublinearly badhta hai: kyunki

lo g_{2} N

denominator bhi badhta hai,

N

double karne se double se kam speedup milti hai (ye

N / lo g_{2} N

2 N / (lo g_{2} N + 1)

tak jaati hai).

Real input signal ke liye, DFT outputs ka exactly aadha, doosre aadhe ki redundant copies hoti hain

Sach. Conjugate symmetry

X_{N - k} = \overline{X_{k}}

upper half ko lower half ka mirror bana deti hai, isliye

N - 1

nonzero-frequency outputs pair up ho jaate hain aur sirf

X_{1}, \dots, X_{N /2 - 1}

(plus real

X_{0}

aur, even

N

ke liye, real

X_{N /2}

) independent hain.

DFT basis vectors ek orthonormal basis form karte hain

Jhooth. Ye orthogonal hain lekin normal nahi: har ek ka squared norm

N

hai,

1

nahi. Yahi

N

ka factor exactly woh wajah hai kyunki inverse DFT ko

1/ N

chahiye.

Radix-2 Cooley–Tukey kisi bhi positive integer

N

ke liye kaam karta hai

Jhooth. Radix-2 ko

N = 2^{m}

chahiye. Arbitrary

N

ke liye mixed-radix splitting ya Bluestein's algorithm chahiye; libraries padding ya methods switch karke yeh chhupaati hain.

Frequency index

k = N - 1

signal mein highest frequency represent karta hai

Jhooth.

k = N /2

se aage ke indices negative frequencies represent karte hain (

k

ka matlab

k - N

hai), isliye

k = N - 1

corresponds karta hai

- 1

se — lowest-magnitude negative frequency, essentially sabse slow wiggle.

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

aur

ω_{N} = e^{+ 2 π i / N}

same DFT define karte hain

Jhooth — ye forward aur inverse conventions define karte hain (ek sign flip). Dono valid choices hain, lekin aapko consistent rehna hoga: inhe mix karne se result scramble ho jaata hai.

Butterfly step do outputs compute karta hai lekin sirf ek nontrivial multiplication chahiye

Sach.

X_{k} = E_{k} + ω_{N}^{k} O_{k}

aur

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

(jahan

E_{k}, O_{k}

even/odd half-DFTs hain) single product

ω_{N}^{k} O_{k}

reuse karte hain; levels ke across is reuse ka compounding hi puri speedup ka source hai.

Real signal ke DFT ki har entry real hoti hai

Jhooth.

X_{0}

aur (even

N

ke liye)

X_{N /2}

real hain, lekin baaki generally complex hain — ye amplitude aur phase dono encode karte hain.

Error dhundho

"Kyunki

E_{k}

ek length-

N /2

DFT hai, ye sirf

k = 0, \dots, N /2 - 1

ke liye defined hai; isliye

X_{k + N /2}

undefined hai." — flaw dhundho

Flaw ye hai ki

E_{k}

ko apni range ke bahar undefined maana ja raha hai.

E_{k}

(even-sample half-DFT) period

N /2

ke saath periodic hai, isliye

E_{k + N /2} = E_{k}

; butterfly yahi periodicity use karta hai, koi domain violate nahi karta.

"Do distinct basis vectors ka inner product zero hai kyunki har term zero hoti hai." — kya galat hai

Individual terms zero nahi hain; ye magnitude 1 ke complex numbers hain. Sum zero isliye hota hai kyunki ye ek geometric series hai ratio

r \neq = 1

ke saath jo

r^{N} = 1

satisfy karta hai, jisse

(r^{N} - 1) / (r - 1) = 0

aata hai.

"Frequency 3 par ek pure cosine sirf

k = 3

par ek single spike deta hai." — isko correct karo

Real cosine

\frac{1}{2} (e^{i θ} + e^{- i θ})

hota hai, isliye ye

+ 3

aur

- 3

dono carry karta hai. Negative frequency

- 3

index

k = N - 3

par baithta hai (kyunki index

k

ka matlab frequency

k - N

hai), jo do spikes produce karta hai, ek nahi.

"Recurrence

T (N) = 2 T (N /2) + c N

O (N)

deta hai kyunki har baar work halve hoti hai." — reasoning fix karo

Hum size halve karte hain lekin do subproblems hain, aur

c N

combine cost har level par recur karti hai,

lo g_{2} N

levels mein se har ek par.

lo g_{2} N

levels par

c N

sum karne se

O (N lo g_{2} N)

aata hai,

O (N)

nahi.

"Inverse par

1/ N

bhoolna sirf rescale karta hai, isliye ye harmless hai." — ye kyun dangerous hai

Ye aapki reconstructed signal ko

N

se multiply karta hai, jo

N = 2^{20}

ke liye ek million ka factor hai. Kisi bhi chained pipeline mein (transform, process, invert) ye numbers destroy karta hai aur original se koi bhi comparison khatam kar deta hai.

"Kyunki

ω_{N}^{N} = 1

hai,

ω_{N}^{nk} = 1

jab bhi

nk

N

ka multiple ho, isliye woh terms

X_{k}

se drop out ho jaate hain." — subtle mistake pakdo

Ye "drop out" nahi hote —

ω_{N}^{nk} = 1

ka matlab hai ki woh term sum mein

x_{n} \cdot 1 = x_{n}

contribute karta hai, ye poora count hota hai, remove nahi. Weight of 1, weight of 0 nahi hai.

Why questions

N

sample points par exactly

N

distinct frequencies kyun honi chahiye, isse zyada nahi?

Discrete grid par, frequency

k

aur

k + N

identical samples produce karte hain kyunki

e^{2 π i (k + N) n / N} = e^{2 π ik n / N}

. Isliye frequencies modulo

N

wrap ho jaati hain, exactly

N

distinguishable chodke.

DFT ke liye basis ki orthogonality itni important kyun hai?

Ye har coefficient

X_{k}

ko ek single independent projection se padh lene deta hai, isliye koi simultaneous linear system solve nahi karna padta. Extraction har coefficient ke liye ek weighted sum ban jaata hai.

Identity

ω_{N}^{2} = ω_{N /2}

FFT ko kyun unlock karti hai?

Ye har even/odd sub-sum

\sum x_{2 m} ω_{N}^{2 mk}

\sum x_{2 m} ω_{N /2}^{mk}

mein turn karti hai — literally ek half-size DFT. Sub-DFT ko recognize karna hi woh cheez hai jo recursion possible banati hai.

X_{k + N /2}

"almost free" kyun aata hai?

Kyunki

ω_{N}^{k + N /2} = ω_{N}^{N /2} ω_{N}^{k} = - ω_{N}^{k}

(

ω_{N}^{N /2} = - 1

use karke): sirf ek sign flip hota hai. Expensive product

ω_{N}^{k} O_{k}

ek baar compute hota hai aur minus ke saath reuse hota hai.

Speedup ratio exactly

N / lo g_{2} N

kyun hai?

Naïve DFT

\sim N^{2}

operations leta hai (

N

outputs mein se har ek

N

products ka sum hai), jabki FFT

\sim N lo g_{2} N

leta hai. Unka ratio

N^{2} / (N lo g_{2} N) = N / lo g_{2} N

hai — run-time mein

N

ka ek factor cancel ho jaata hai, log denominator mein bachta hai.

Forward DFT exponent mein minus sign kyun hai?

Basis vector par project karne ke liye conjugate inner product use hota hai, aur

e^{2 π ik n / N}

ko conjugate karne se

e^{- 2 π ik n / N} = ω_{N}^{nk}

milta hai. Inverse, jo project nahi karta balki reconstruct karta hai, plus sign carry karta hai.

Real input conjugate symmetry

X_{N - k} = \overline{X_{k}}

kyun force karta hai?

k

N - k

se replace karne par exponent ka sign flip ho jaata hai, aur real

x_{n}

ke liye ye poore sum ka exactly complex conjugation hai. Data ki reality spectrum mein ek mirror symmetry ban jaati hai.

FFT speedup ko "compounding factors of 2" kyun kaha jaata hai?

Recursion ka har level, har multiply par do outputs compute karke factor-of-2 saving deta hai, aur

lo g_{2} N

levels hain. Savings levels ke across add nahi balki multiply hoti hain.

Edge cases

Ek single sample (

N = 1

) ka DFT kya return karta hai?

Sirf sample khud:

X_{0} = x_{0}

. Ye recursion ka base case hai — length-1 "DFT" identity hai, jahan FFT recursion bottom out karti hai.

X_{0}

kisi bhi input ke liye hamesha kiske barabar hota hai?

Plain sum

\sum_{n = 0}^{N - 1} x_{n}

, kyunki har term ke liye

ω_{N}^{0} = 1

. Ye DC component hai — signal ke average ka

N

guna.

Even

N

ke liye, middle index

k = N /2

mein kya special hai?

ω_{N}^{N /2} = e^{- iπ} = - 1

, isliye

X_{N /2} = \sum_{n} x_{n} (- 1)^{n}

— ek purely alternating sum. Real input ke liye ye coefficient real hai; ye Nyquist frequency hai (dekho Sampling & Aliasing (Nyquist)).

Agar

N

odd ho (power of two nahi), to FFT recursion ka kya hota hai?

Radix-2 splitting ruk jaati hai — aap cleanly halve nahi kar sakte. Aapko mixed-radix switch karna hoga, next power of two tak pad karna hoga, ya Bluestein use karna hoga, warna even/odd trick apply nahi hoti.

Agar saare samples equal hon (

x_{n} = c

sab

n

ke liye), to spectrum kya hoga?

Sirf

X_{0} = N c

nonzero hai; baaki har

X_{k} = 0

hai kyunki

\sum_{n} ω_{N}^{nk} = 0

for

k \neq = 0

(wahi vanishing geometric series phir). Ek constant signal pure DC hai.

Ek single impulse

x_{0} = 1

, baaki sab

0

, ka DFT kya hai?

Har

X_{k} = 1

: weighted sum sirf

n = 0

term pick karta hai, jiska weight

ω_{N}^{0} = 1

sab

k

ke liye hai. Time mein ek spike flat, all-frequencies spectrum hai — discrete uncertainty principle miniature mein.