Snad jiz finalni verze kapitoly o FFT.

[ads2.git] / 8-fft / 8-fft.tex

diff --git a/8-fft/8-fft.tex b/8-fft/8-fft.tex
index cd67ba8c113d686b5b6baa94bfdd8ad59054ae60..b8929802b5489d80eed6a1619354d8b36e9cab40 100644 (file)
--- a/8-fft/8-fft.tex
+++ b/8-fft/8-fft.tex
@@ -87,10 +87,8 @@ Pot
 
 
 \s{Definice:}
-\>{\I Diskretní Fourierova transformace (DFT)}
-je funkce $f: { {\bb C} ^n} \rightarrow { {\bb C} ^n}$ pøiøazující ka¾dému vektoru~$x\in {\bb C}^n$
-vektor~$y\in{\bb C}^n$ takový, ¾e pro ka¾dé~$j$ platí:
-$$y_{j} = \sum \limits ^{n-1}_{k=0} x_{k} \cdot \omega ^{jk}.$$
+\>{\I Diskretní Fourierova transformace} $(DFT)$
+je funkce $f: { {\bb C} ^n} \rightarrow { {\bb C} ^n}$, kde $y=f(x) \equiv \forall j \ y_{j} = \sum \limits ^{n-1}_{k=0} x_{k} \cdot \omega ^{k}$.
 
 
 \s{Jak najít inverzní matici?} Víme, ¾e $\Omega =\Omega ^{T}$ proto¾e $\omega ^{jk} = \omega ^{kj}$.
@@ -165,19 +163,10 @@ $\O(n \log n)$ pro vyhodnocen
 \figure{img.eps}{Pøíklad prùbìhu algoritmu na vstupu velikosti 8}{3in}
 
 
-\>Obrázek ukazuje zapojení kombinaèního obvodu pro DFT pro vstup velikosti 8. Èíslo $\log n$ znaèí poèet hladin, tj. u nás $\log 8 = 3$ hladiny.
+\>Obrázek ukazuje zapojení kombinaèního obvodu pro DFT pro vstup velikosti~8. Hladin bude v¾dy $\log_2 n$, tj. v~na¹em pøípadì $\log_2 8 = 3$ hladiny.
 
-\>Základem je kombinaèní obvod tzv. motýlek. (Na obrázku znázornìn dvìma èarami, pøekøí¾enými v jejich støedech). Co motýlek dìlá? Podívejme se na následující obrázek.
-
-\figure{img2.eps}{Kombinaèní obvod tzv. motýlek}{1in}
-
-\>Vstup jsou komplexní èísla $x_1$ a $x_2$ a výstup komplexní èísla $y_1$ a $y_2$, taková ¾e
-\>$y_1 = x_1 + \omega^j \cdot x_2$
-\>$y_2 = x_1 - \omega^j \cdot x_2$
-
-\>kde index $j$ znaèí
-
-\>V¹imìme si poøadí vstupních hodnot (koeficientù). Èísla jsou v binarním tvaru 0-7 pøeètená pozpátku.
+\>Podívejme se na pravou èást obrázku, tedy výstup celého obvodu. Èerná koleèka pøedstavují podobvody, rovnice vedle nich operaci, kterou provádìjí. Hodnoty $y_j$ znaèí hodnotu polynomu $P$ v bodì $\omega^j$ kde $\omega^j$ je $j-tá$ mocnina primitivní $n$-té odmocniny z jednièky. K jejímu spoètení ale potøebujeme znát hodnoty $s_k$ a $l_k$ kde $k$ je z intervalu $[0, {n/2} -1]$ a $s_k$ a $l_k$ jsou hodnoty polynomu stupnì ${n/2}$ v bodì $\omega^{2k}$. V polynomu $s$ jsou sudé koeficienty a v polynomu $l$ liché koeficienty polynomu $P$. Vidíme ze se jedná pøesnì o ná¹ rekurzivní algoritmus pro poèítání FFT a tímto zpùsobem postavíme celou sí».
+\>Tímto obvodem jsme tedy získali nerekurzivní algoritmus pro poèítání FFT. V¹imìme si poøadí vstupních hodnot (koeficientù). Èísla jsou v binárním tvaru 0--7 pøeètená pozpátku. Pro pøedstavu jaké koeficienty polynomu $P$ se objevují v rùzných hladinách, na obrázku jsou naznaèena jejich èísla spolu s pøíslu¹nými mocninami primitivní $n$-té odmocniny z jednièky. 
 
 \s{Z toho:}
 
@@ -189,5 +178,4 @@ a $\O(n)$ hradly na hladin
 
 \endlist
 
-
 \bye