\input /home/pasky/school/fastex/lib.tex

\subchapter{Diskrétní Fourierova transformace}{

	$$ f(x) = c + \sum_{k=1}^{n/2-1} a_k \sin kx + \sum_{k=1}^{n/2-1} b_k \cos kx $$

	Jsme {\bf diskrétní}: $x_j = 2\pi/n \cdot j$,
	pak vezmeme $x_0,x_1,x_2,\ldots,x_{n-1}$.

	Psát $f(x)$ tak rozvláčně je otrava, takže přejdeme do $\cmplx$,
	i když nás vlastně zajímá $\real$:
	$$ e^{2x} = \cos x + i\sin x $$
	$$ \cos x = {e^{ix} + e^{-ix} \over 2} $$
	$$ \sin x = {e^{ix} - e^{-ix} \over 2i} $$

	Nyní můžeme použít zápis
	$$ f(x_j) = \sum_{k=0}^{n-1} \alpha_k e^{ikx_j} = \sum_{k=0}^{n-1} \alpha_k e^{i{2\pi kj \over n}} =: A_j $$
	a přitom stále platí periodicita, neboť
	$$ e^{ikx_j} = e^{i(k+n)x_j} = e^{ikx_j} \cdot \undernote{e^{inx_j}}{1} $$

	Diskrétní FT je teď vpodstatě zobrazení
	$(A_0,\ldots,A_{n-1}) \to (\alpha_0,\ldots,\alpha_{n-1})$.

	Zkusme něco alespoň zdánlivě jednoduššího:
	$(\alpha_0,\ldots,\alpha_{n-1}) \to (A_0,\ldots,A_{n-1})$.

	Zamysleme se nad $\omega = e^{2\pi i \over 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á
	$$\omega^0,\omega^1,\omega^2,\ldots,\omega^{n-1},\ \omega^n = \omega^0 = 1$$

	Můžeme tedy ještě zjednodušit zápis na
	$$ A_j = \sum_{k=0}^{n-1} \alpha_k \omega^{kj} $$

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

	$$ \matrix{A_0=&a_0\omega^{0\cdot0}&+&a_1\omega^{1\cdot0}&+&a_2\omega^{2\cdot0}&+&a_3\omega^{3\cdot0} \cr
	           A_1=&a_0\omega^{0\cdot1}&+&a_1\omega^{1\cdot1}&+&a_2\omega^{2\cdot1}&+&a_3\omega^{3\cdot1} \cr
	           A_2=&a_0\omega^{0\cdot2}&+&a_1\omega^{1\cdot2}&+&a_2\omega^{2\cdot2}&+&a_3\omega^{3\cdot2} \cr
	           A_3=&a_0\omega^{0\cdot3}&+&a_1\omega^{1\cdot3}&+&a_2\omega^{2\cdot3}&+&a_3\omega^{3\cdot3}} $$

	Rozdělím na liché a sudé sloupečky, dám je k sobě,
	v $A_k$ vytknu liché skupiny $\omega^k$.

	$$ \matrix{A_0=&a_0\omega^{0\cdot0}&+&a_2\omega^{2\cdot0}&+&\omega^0 & (a_1\omega^{0\cdot0}&+&a_3\omega^{2\cdot0}) \cr
	           A_1=&a_0\omega^{0\cdot1}&+&a_2\omega^{2\cdot1}&+&\omega^1 & (a_1\omega^{0\cdot1}&+&a_3\omega^{2\cdot1}) \cr
	           A_2=&a_0\omega^{0\cdot2}&+&a_2\omega^{2\cdot2}&+&\omega^2 & (a_1\omega^{0\cdot2}&+&a_3\omega^{2\cdot2}) \cr
	           A_3=&a_0\omega^{0\cdot3}&+&a_2\omega^{2\cdot3}&+&\omega^3 & (a_1\omega^{0\cdot3}&+&a_3\omega^{2\cdot3})} $$

	Teď si všimněme, že $\omega^4 = 1$.
	Díky násobení v exponentu o sudé číslo lze tedy v $A_2$ a $A_3$
	změnit $\omega^{2\cdot2}$ na $\omega^{2\cdot0}$ apod.

	$$ \matrix{A_0=&a_0\omega^{0\cdot0}&+&a_2\omega^{2\cdot0}&+&\omega^0 & (a_1\omega^{0\cdot0}&+&a_3\omega^{2\cdot0}) \cr
	           A_1=&a_0\omega^{0\cdot1}&+&a_2\omega^{2\cdot1}&+&\omega^1 & (a_1\omega^{0\cdot1}&+&a_3\omega^{2\cdot1}) \cr
	           A_2=&a_0\omega^{0\cdot0}&+&a_2\omega^{2\cdot0}&+&\omega^2 & (a_1\omega^{0\cdot0}&+&a_3\omega^{2\cdot0}) \cr
	           A_3=&a_0\omega^{0\cdot1}&+&a_2\omega^{2\cdot1}&+&\omega^3 & (a_1\omega^{0\cdot1}&+&a_3\omega^{2\cdot1})} $$

	Teď už je vidět, že tam máme půlku redundantní.
	{\it 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 $\log n$.
	Tomuhle postupu říkáme FFT, neboli Fast Fourier Transform.

\penalty-1000

	Dobře, ale co spektrální analýza, tedy
	$(A_0,\ldots,A_{n-1}) \to (\alpha_0,\ldots,\alpha_{n-1})$?

	Náš předchozí výpočet můžeme také popsat jako:
	$$ W_{p,q} = \omega^{p\cdot q} \qquad A = Wa $$
	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\cdot \omega^{-pq} $$
	To je vpodstatě stejná úloha jako předtím,
	jen místo $\omega$ vezmeme $\omega^{-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í\dots

	\proof{
		$$ (W)_{pq} = \omega^{pq} $$
		$$ (\overline{W})_{pq} = \omega^{-pq} $$

		$$ (W\cdot\overline{W})_{pq} = \sum_{s=0}^{n-1} W_{ps}\cdot\overline{W}_{sq}
			= \omega^{p0}\omega^{-0q} + \omega^{p1}\omega^{-1q} + \cdots + \omega^{ps}\omega^{-sq} + \cdots
			= \Gamma
			\opupon{?}{=} \cases{n & $p = q$ \cr 0 & $p \ne q$} $$

		Rozvoj přes $\omega$ můžeme také popsat jako
		$$ \Gamma = \omega^{0(p-q)} + \omega^{1(p-q)} + \omega^{2(p-q)} + \cdots $$
		$$ p \ne q,\ 0 \le p,q < n: Q = \omega^{p-q} \ne 1 $$
		$$ \Gamma = Q^0 + Q^1 + Q^2 + \cdots + 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
		$$ \Gamma = {Q^{(n-1)+1} - 1 \over Q-1}Q^0 $$
		a z definice $Q$:
		$$ \Gamma = 1 $$
	}

}

\bend