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

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

Is page par assume kiya gaya hai ki parent topic ki notation ke baare mein aapko kuch nahi pata. Hum har symbol ground up se banate hain, ek aise order mein jahan har ek cheez sirf pehle se defined cheezein use karti hai.

0. "Signal" aur "sample" actually hain kya

$n$ sirf ek index hai: yeh batata hai ki kaun si reading hai, $0$ se counting shuru karke. Toh $x_{0}$ pehli hai, $x_{1}$ doosri, aur aise aage.
$N$ readings ki total count hai.
Hum $0$ se count karte hain, isliye aakhri index $N - 1$ hai, $N$ nahi. Yeh "off by one" is subject mein ek zindagi bhar ki aadat hai — abhi se comfortable ho jao.

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

Topic ko iske kyon zaruurat hai: poora DFT ek list $x_{0} \dots x_{N - 1}$ khaata hai aur doosri list ugalta hai. Agar aap input ko timeline par dots ke roop mein nahi sochte, toh baad ki koi bhi cheez ka koi matlab nahi banega.

1. Complex numbers — ek plane mein arrows

Parent page $i$ , $e^{i θ}$ , aur letters par bars se bhari padi hai. Yeh sab ek picture mein rehta hai: ek flat plane mein ek point (ya arrow).

Horizontal axis real axis hai, vertical axis imaginary axis hai.
Figure mein red arrow dekho: uski length $r$ hai aur woh right-pointing axis se jo angle banata hai woh $θ$ hai.

Topic ko iske kyon zaruurat hai: parent ki line " $X_{N - k} = \overline{X_{k}}$ for real input" ek mirror-symmetry statement hai. Bar ki picture ke bina yeh bakwaas lagti hai; us picture ke saath, yeh sirf kehti hai ki do output arrows mirror images hain.

2. The exponential $e^{i θ}$ — unit circle par ek point

Yeh poori parent page ka sabse important symbol hai, toh hum ise carefully earn karte hain.

Figure ko dheere se padho:

Har $e^{i θ}$ radius 1 ke circle par hota hai ("unit circle"), kyunki $cos^{2} θ + sin^{2} θ = 1$ hamesha.
$θ$ ko thoda badhane par red dot thoda counter-clockwise rotate hota hai.
$θ$ radians mein measure hota hai: circle ka ek poora chakkar $2 π$ radians ka hota hai ( $360$ nahi). Toh $e^{2 π i} = e^{0} = 1$ — aap wapas wahi aate ho jahan se shuru kiya.

Topic ko iske kyon zaruurat hai: parent jis "pure rotating waves" ki baat karta hai woh literally $e^{i θ}$ hain jahan $θ$ aage badhta rehta hai. Har DFT frequency ek aisa spinning arrow hai.

Recall Why is

$e^{i θ}$ a rotation and not just growth? Ordinary $e^{x}$ (real $x$ ) grows. Multiplying the exponent by $i$ turns "grow outward" into "turn sideways", so the value circles instead of escaping. ::: The factor $i$ converts stretching into turning.

3. Roots of unity — circle par evenly spaced points

Ab parent formula ka star: $ω_{N}$ .

Aage badhne se pehle, un do letters se milte hain jo parent formula $ω_{N}$ ke exponents mein use karta hai:

Figure mein ( $N = 8$ ): red dot $ω_{8}$ hai, $1$ se ek kadam clockwise. Baaki black dots uski powers $ω_{8}^{2}, ω_{8}^{3}, \dots$ hain — aap har dot visit karte ho aur $N$ steps ke baad $1$ par wapas land karte ho, kyunki: $ω_{N}^{N} = (e^{- 2 π i / N})^{N} = e^{- 2 π i} = 1.$

Do facts jo parent rely karta hai, ab picture se obvious hain. Dono ko $N$ even chahiye taaki $N /2$ ek whole number ho (radix-2 FFT hamesha $N = 2^{m}$ use karta hai, jo even hai):

Pehla FFT split possible banata hai; doosra "butterfly" ko almost free banata hai. Dono ek circle par step karne ki pictures hain, kuch aur nahi.

Topic ko iske kyon zaruurat hai: $ω_{N}$ "frequency dial" hai. DFT sum mein weight $ω_{N}^{nk}$ kehta hai "sample $n$ ko $k$ notches spin karo" — poori geometry ke liye Roots of Unity dekho.

4. Sums — $\sum$ symbol

Topic ko iske kyon zaruurat hai: DFT $X_{k} = \sum_{n = 0}^{N - 1} x_{n} ω_{N}^{nk}$ (yahan $k$ Section 3 ka fixed frequency index hai, aur $n$ saare $N$ samples par run karta hai) ka matlab hai "ek output $k$ ke liye, har sample ko spin karo aur sab add karo". $\sum$ and add them all up wala part hai.

5. Geometric series — kyun orthogonality kaam karti hai

Parent ka proof ki basis waves independent hain, ek classic sum par tika hai.

DFT mein magic: ratio $r$ khud ek root of unity hai, toh $r^{N} = 1$ , jo top ko $r^{N} - 1 = 0$ bana deta hai. Poora sum zero ho jaata hai. Woh ek akeli line isiliye hai ki alag-alag frequencies ek doosre mein leak nahi hoti — Geometric Series aur Linear Algebra — Orthogonal Bases dekho.

Topic ko iske kyon zaruurat hai: "orthogonal basis" yeh kehne ka fancy tarika hai ki har frequency ko apne aap measure kiya ja sakta hai bina ek bada equation system solve kiye. Geometric series woh engine hai jo ise prove karta hai.

x_{n}

mein index

n

ka kya matlab hai, aur yeh kahan se start karta hai?

Yeh batata hai ki kaun si reading hai;

0

se start karta hai, toh aakhri index

N - 1

hai.

What single equation defines the imaginary unit

i

i^{2} = - 1

Draw/describe

z = a + b i

as a picture.

An arrow to the point

a

right,

b

up in the plane.

z = a + bi

ki length

r

kya hai, aur kyun?

r = a^{2} + b^{2}

a

aur

b

legs wale right triangle par Pythagoras se.

Conjugate

\overline{z}

geometrically kya karta hai?

Reflects the arrow across the real (horizontal) axis.

Plane par

e^{i θ}

kaun sa point hai?

The unit-circle point at angle

θ

(length 1), from Euler's formula

cos θ + i sin θ

Ek full turn kitne radians ka hota hai, aur

e^{2 π i}

kya hai?

2 π

radians;

e^{2 π i} = 1

In words, what is

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

One clockwise step to the next of

N

evenly spaced dots on the unit circle.

k

aur

X_{k}

ka kya matlab hai, aur

k

kaun si range leta hai?

k = 0, \dots, N - 1

batata hai kaun si frequency;

X_{k}

k

-va DFT output hai.

ω_{N}^{N} = 1

kyun?

N

steps of size

2 π / N

complete a full lap back to

1

State the two symmetries of

ω_{N}

(and the condition on

N

For even

N

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

and

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

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

aapko kya karne ka instruction deta hai?

Add

a_{0}

through

a_{N - 1}

Derive

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

for

r \neq = 1

Multiply-by-

r

trick:

S - r S = 1 - r^{N}

, so

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

Why is that sum

0

for a root of unity?

r^{N} = 1

makes the numerator

r^{N} - 1 = 0

⟨ a, b ⟩ = \sum_{n = 0}^{N - 1} a_{n} \overline{b_{n}} = 0

ka kya matlab hai?

The two length-

N

lists have zero overlap (orthogonal).

Recurrence

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

kiska solution hai?

O (N lo g N)

, via the Master Theorem.

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

0. "Signal" aur "sample" actually hain kya

1. Complex numbers — ek plane mein arrows

2. The exponential $e^{i θ}$ — unit circle par ek point

3. Roots of unity — circle par evenly spaced points

4. Sums — $\sum$ symbol

5. Geometric series — kyun orthogonality kaam karti hai

6. Orthogonal bases — ek ingredient ek baar measure karna

7. Big-O aur divide-and-conquer — speed measure karna

Prerequisite map

Equipment checklist