— — Diskrétní Fourierova transformace

Diskrétní Fourierova transformace

f(x) = c + ∑_{k=1}^{n/2−1} a_{k} sinkx + ∑_{k=1}^{n/2−1} b_{k} coskx

Jsme diskrétní: x_{j} = 2π/n · j, pak vezmeme x_{0}, x_{1}, x_{2}, …, x_{n−1}. Psát f(x) tak rozvláčně je otrava, takže přejdeme do ℂ, i když nás vlastně zajímá ℝ:

e^{2x} = cosx + i sinx

cosx = \frac{e^{ix} + e^{−ix}}{2}

sinx = \frac{e^{ix} − e^{−ix}}{2i}

Nyní můžeme použít zápis

f(x_{j}) = ∑_{k=0}^{n−1} α_{k}e^{ikx_{j}} = ∑_{k=0}^{n−1} α_{k}e^{i \frac{2πkj}{n}} =: A_{j}

a přitom stále platí periodicita, neboť

e^{ikx_{j}} = e^{i(k+n)x_{j}} = e^{ikx_{j}} · \underbrace{e^{inx_{j}}}_{1}

Diskrétní FT je teď vpodstatě zobrazení (A_{0}, …, A_{n−1}) → (α_{0}, …, α_{n−1}). Zkusme něco alespoň zdánlivě jednoduššího: (α_{0}, …, α_{n−1}) → (A_{0}, …, A_{n−1}). Zamysleme se nad ω = e^{\frac{2πi}{n}} . Pro různá n je vždy vzdálenost od nuly 1, jde tedy o různé body na

jednotkové kružnici. Máme navzájem téměř různá

ω^{0}, ω^{1}, ω^{2}, …, ω^{n−1}, ω^{n} = ω^{0} = 1

Můžeme tedy ještě zjednodušit zápis na

A_{j} = ∑_{k=0}^{n−1} α_{k}ω^{kj}

Ale kdybychom tohle počítali, bude to O(n^{2}). My to však umíme rychleji, v O(n logn).

\begin{matrix}A_{0} = & a_{0}ω^{0·0} & + & a_{1}ω^{1·0} & + & a_{2}ω^{2·0} & + & a_{3}ω^{3·0} \\ A_{1} = & a_{0}ω^{0·1} & + & a_{1}ω^{1·1} & + & a_{2}ω^{2·1} & + & a_{3}ω^{3·1} \\ A_{2} = & a_{0}ω^{0·2} & + & a_{1}ω^{1·2} & + & a_{2}ω^{2·2} & + & a_{3}ω^{3·2} \\ A_{3} = & a_{0}ω^{0·3} & + & a_{1}ω^{1·3} & + & a_{2}ω^{2·3} & + & a_{3}ω^{3·3} \end{matrix}

Rozdělím na liché a sudé sloupečky, dám je k sobě, v A_{k} vytknu liché skupiny ω^{k}.

\begin{matrix}A_{0} = & a_{0}ω^{0·0} & + & a_{2}ω^{2·0} & + & ω^{0} & (a_{1}ω^{0·0} & + & a_{3}ω^{2·0}) \\ A_{1} = & a_{0}ω^{0·1} & + & a_{2}ω^{2·1} & + & ω^{1} & (a_{1}ω^{0·1} & + & a_{3}ω^{2·1}) \\ A_{2} = & a_{0}ω^{0·2} & + & a_{2}ω^{2·2} & + & ω^{2} & (a_{1}ω^{0·2} & + & a_{3}ω^{2·2}) \\ A_{3} = & a_{0}ω^{0·3} & + & a_{2}ω^{2·3} & + & ω^{3} & (a_{1}ω^{0·3} & + & a_{3}ω^{2·3}) \end{matrix}

Teď si všimněme, že ω^{4} = 1. Díky násobení v exponentu o sudé číslo lze tedy v A_{2} a A_{3} změnit ω^{2·2} na ω^{2·0} apod.

\begin{matrix}A_{0} = & a_{0}ω^{0·0} & + & a_{2}ω^{2·0} & + & ω^{0} & (a_{1}ω^{0·0} & + & a_{3}ω^{2·0}) \\ A_{1} = & a_{0}ω^{0·1} & + & a_{2}ω^{2·1} & + & ω^{1} & (a_{1}ω^{0·1} & + & a_{3}ω^{2·1}) \\ A_{2} = & a_{0}ω^{0·0} & + & a_{2}ω^{2·0} & + & ω^{2} & (a_{1}ω^{0·0} & + & a_{3}ω^{2·0}) \\ A_{3} = & a_{0}ω^{0·1} & + & a_{2}ω^{2·1} & + & ω^{3} & (a_{1}ω^{0·1} & + & a_{3}ω^{2·1}) \end{matrix}

Teď už je vidět, že tam máme půlku redundantní. Navíc tohle ale můžeme dělat rekurzivně s každou čtvrtinou! (Resp. s každou polovinou, protože dvě čtvrtiny jsou redundantní.) Blíže viz hezký algovisionový applet.

Hop a máme logn. Tomuhle postupu říkáme FFT, neboli Fast Fourier Transform.

Dobře, ale co spektrální analýza, tedy (A_{0}, …, A_{n−1}) → (α_{0}, …, α_{n−1})?

Náš předchozí výpočet můžeme také popsat jako:

W_{p,q} = ω^{p·q} A = W a

Nás tudíž zajímá W^{−1} (protože a = W^{−1}A), a za okamžik si dokážeme:

(W^{−1})_{pq} = 1/n · ω^{−pq}

To je vpodstatě stejná úloha jako předtím, jen místo ω vezmeme ω^{−1} (a nakonci musíme vše vydělit n). Periodicita i vše ostatní je zachováno, sluníčko svítí, ptáčci zpívají…

DŮKAZ:

(W)_{pq} = ω^{pq}
(\overline{W})_{pq} = ω^{−pq}

(W · \overline{W})_{pq} = ∑_{s=0}^{n−1} W_{ps} · \overline{W}_{sq} = ω^{p0}ω^{−0q} + ω^{p1}ω^{−1q} + ⋯ + ω^{ps}ω^{−sq} + ⋯ = Γ=^{?} \{ \begin{matrix}n & p = q \\ 0 & p ≠ q \end{matrix}

Rozvoj přes ω můžeme také popsat jako

Γ = ω^{0(p−q)} + ω^{1(p−q)} + ω^{2(p−q)} + ⋯
p ≠ q, 0 ≤ p, q < n : Q = ω^{p−q} ≠ 1
Γ = Q^{0} + Q^{1} + Q^{2} + ⋯ + Q^{n−1}

a to si můžeme představit jako body rovnoměrně rozložené po jednotkové kružnici, tedy se nám vyruší. Formálně si to ale dokážeme přes součet geometrické řady

Γ = \frac{Q^{(n−1)+1} − 1}{Q − 1}Q^{0}

a z definice Q:

Γ = 1