From 21240fc26aaae68c670adcaf250a09cfd7a69fc0 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Sun, 29 Nov 2009 11:52:52 +0100 Subject: [PATCH] Paralelni a nerekurzivni FFT + dodatek o konecnych telesech. --- 9-fft/9-fft.tex | 90 ++++++++++++++++++++++++++++++++----------------- lecnotes.tex | 6 ++++ 2 files changed, 65 insertions(+), 31 deletions(-) diff --git a/9-fft/9-fft.tex b/9-fft/9-fft.tex index b2e0639..c2249ce 100644 --- a/9-fft/9-fft.tex +++ b/9-fft/9-fft.tex @@ -211,7 +211,7 @@ Polynomy stupn $\Theta(n \log n)$ pro vyhodnocení, $\Theta(n)$ pro vynásobení a~$\Theta(n \log n)$ pro pøevedení zpìt. -\s{Pou¾ití:} +\s{Pou¾ití FFT:} \itemize\ibull @@ -221,44 +221,72 @@ $\Rightarrow$ spektr \:Násobení dlouhých èísel v~èase $\Theta(n \log n)$. \endlist -\s{Hardwarová implementace FFT} +\s{Paralelní implementace FFT} \figure{img.eps}{Pøíklad prùbìhu algoritmu na~vstupu velikosti 8}{3in} +Zkusme si prùbìh algoritmu FFT znázornit graficky (podobnì, jako jsme kreslili +hradlové sítì). Na~levé stranì obrázku se nachází vstupní vektor $x_0,\ldots,x_{n-1}$ +(v~nìjakém poøadí), na~pravé stranì pak výstupní vektor $y_0,\ldots,y_{n-1}$. +Sledujme chod algoritmu pozpátku: Výstup spoèítáme z~výsledkù \uv{polovièních} +transformací vektorù $x_0,x_2,\ldots,x_{n-2}$ a $x_1,x_3,\ldots,x_{n-1}$. +Èerné krou¾ky pøitom odpovídají výpoètu lineární kombinace $a+\omega^kb$, +kde $a,b$ jsou vstupy krou¾ku a $k$~nìjaké pøirozené èíslo závislé na poloze +krou¾ku. Ka¾dá z~polovièních transformací se poèítá analogicky z~výsledkù +transformace velikosti $n/4$ atd. Celkovì výpoèet probíhá v~$\log_2 n$ vrstvách +po~$\Theta(n)$ operacích. -\>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. +Jeliko¾ operace na~ka¾dé vrstvì probíhají na sobì nezávisle, mù¾eme je poèítat +paralelnì. Ná¹ diagram tedy popisuje hradlovou sí» pro paralelní výpoèet FFT +v~èase $\Theta(\log n\cdot T)$ a prostoru $\O(n\cdot S)$, kde $T$ a~$S$ znaèí +èasovou a prostorovou slo¾itost výpoètu lineární kombinace dvou komplexních èísel. -\>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, ¾e 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{Cvièení:} Doka¾te, ¾e permutace vektoru $x_0,\ldots,x_{n-1}$ odpovídá bitovému +zrcadlení, tedy ¾e na pozici~$b$ shora se vyskytuje prvek $x_d$, kde~$d$ je +èíslo~$b$ zapsané ve~dvojkové soustavì pozpátku. -\s{Z~toho:} +\s{Nerekurzivní FFT} -\itemize\ibull -\:Kombinaèní obvod pro DFT -s~$\Theta(\log n)$ hladinami -a $\Theta(n)$ hradly na~hladinì. -\:Nerekurzivní algoritmus (postupujeme zleva) v~èase $\Theta(n \log n)$. +Obvod z~pøedchozího obrázku také mù¾eme vyhodnocovat po~hladinách zleva doprava, +èím¾ získáme elegantní nerekurzivní algoritmus pro výpoèet FFT v~èase $\Theta(n\log n)$ +a prostoru $\Theta(n)$: -\endlist -\bigskip +\algo +\algin $x_0,\ldots,x_{n-1}$ +\:Pro $j=0,\ldots,n-1$ polo¾íme $y_k\= x_{r(k)}$, kde $r$ je funkce bitového zrcadlení. +\:Pøedpoèítáme tabulku $\omega^0,\omega^1,\ldots,\omega^{n-1}$. +\:$b\= 1$ \cmt{velikost bloku} +\:Dokud $bNakonec dodejme, ¾e poèítat lze nejen nad tìlesem komplexních èísel, ale -v podstatì nad ka¾dým komutativním tìlesem s~$n$-tou primitivní odmocninou -(pøíkladem jsou tìlesa øádu $p = 2^k + 1$, $p$ prvoèíslo) èi dokonce -komutativním okruhem s~multiplikativními inversemi pro øád vektoru -a~primitivní odmocninu. +\s{FFT v~koneèných tìlesech} + +Nakonec dodejme, ¾e Fourierovu transformaci lze zavést nejen nad tìlesem +komplexních èísel, ale i v~nìkterých koneèných tìlesech, pokud zaruèíme +existenci primitivní $n$-té odmocniny z~jednièky. Napøíklad v~tìlese ${\bb +Z}_p$ pro prvoèíslo $p=2^k+1$ platí $2^k=-1$, tak¾e $2^{2k}=1$ +a $2^0,2^1,\ldots,2^{2k-1}$ jsou navzájem rùzná, tak¾e èíslo~2 je~primitivní +$2k$-tá odmocnina z~jedné. To se nám ov¹em nehodí pro algoritmus FFT, jeliko¾ +$2k$ bude málokdy mocnina dvojky. + +Zachrání nás ov¹em algebraická vìta, která øíká, ¾e multiplikativní grupa +libovolného koneèného tìlesa je cyklická, tedy ¾e v¹echny nenulové prvky tìlesa lze +zapsat jako mocniny nìjakého èísla~$g$ (generátoru). Napøíklad pro $p=2^{16}+1=65\,537$ +je jedním takovým generátorem èíslo~$3$. Jeliko¾ mezi èísly $g^1,g^2,\ldots,g^{p-1}$ +se musí ka¾dý nenulový prvek tìlesa vyskytnout právì jednou, je~$g$ primitivní +$2^k$-tou odmocninou z~jednièky, tak¾e mù¾eme poèítat FFT pro libovolný vektor, +jeho¾ velikost je mocnina dvojky men¹í nebo rovná $2^k$.\foot{Bli¾¹í prùzkum +na¹ich úvah o~FFT dokonce odhalí, ¾e není ani potøeba tìleso. Postaèí libovolný +komutativní okruh, ve~kterém existuje pøíslu¹ná primitivní odmocnina +z~jednièky, její multiplikativní inverze (ta ov¹em existuje v¾dy, proto¾e +$\omega^{-1} = \omega^{n-1}$) a multiplikativní inverze èísla~$n$. To nám +poskytuje je¹tì daleko více volnosti ne¾ tìlesa, ale není snadné takové okruhy +hledat.} \bye diff --git a/lecnotes.tex b/lecnotes.tex index f6e5a54..a11e5da 100644 --- a/lecnotes.tex +++ b/lecnotes.tex @@ -86,6 +86,12 @@ \def\algin{\:{\I Vstup:} } \def\algout{\:{\I Výstup:} } +% Priraditko +\def\={\leftarrow} + +% Komentar +\def\cmt#1{~~{\sl (#1)}} + % Nekolikapismenkova promenna (mozno pouzit v textovem i math modu) \def\<#1>{\leavevmode\hbox{\it #1\/}} -- 2.39.2