Gyors Fourier transzformáció

A gyors Fourier-transzformáció ( FFT , FFT ) a diszkrét Fourier-transzformáció gyorsított kiszámítására szolgáló algoritmus, amely lehetővé teszi, hogy az eredményt rövidebb idő alatt kapja meg, mint a (közvetlen, képletenkénti számításhoz szükséges) idő alatt. Néha a gyors Fourier-transzformációt az egyik algoritmusként értelmezik, amelyet frekvencia-idő decimációs algoritmusnak neveznek, és amelynek összetettsége . $O(N^2)$ $O(N\log(N))$

Az algoritmus minden egységgel rendelkező kommutatív asszociatív gyűrűre alkalmazható, gyakrabban a komplex számok mezőjére (c ) és a maradék gyűrűkre (amelyek különösen számítógépes egész típusúak ). $\varepsilon=e^{2\pi i/n}$

Alap algoritmus

Az alapalgoritmus alkalmazásakor a diszkrét Fourier-transzformáció végrehajtható a műveletekben , különösen, ha műveletekre van szükség . $O(N(p_1+\cdots+p_n))$ $N=p_1p_2\cdots p_n$ $N=2^n$ $O(N\log(N))$

A diszkrét Fourier-transzformáció a számok halmazát számhalmazzá alakítja át úgy, hogy hol van az egység primitív gyöke , azaz -re . Az algoritmus fő lépése, hogy a számok problémáját egy kisebb számmal rendelkező feladatra redukálja. A komplex számok mezőjére bevezetjük: , , ahol tetszőleges szám. A diszkrét Fourier-transzformációt . (Ezek a kifejezések könnyen megszerezhetők, ha az eredeti összeget kisebb számú, kisebb tagszámú összegre osztjuk, majd az így kapott összegeket az indexek eltolásával, majd átnevezésével azonos formára hozzuk). $a_0, \pontok, a_{n-1}$ $b_0, \pontok, b_{n-1}$ $b_i=\sum_{j=0}^{n-1}a_j\varepszilon^{ij}$ $\varepsilon$ $\varepsilon^n=1$ $\varepsilon^k\neq 1$ $0<k<n$ $N$ $N=pq,p>1,q>1$ $\varepsilon _{\nu }=e^{2\pi i/\nu }$ $\varepsilon _{\nu }^{\nu }=1$ $\nu$ $b_{i}=\sum _{k=0}^{p-1}\sum _{j=0}^{q-1}a_{kq+j}\varepsilon _{N}^{ (kq+j)i}$

Ilyen módon:

b_{i}=\sum _{k=0}^{p-1}\sum _{j=0}^{q-1}a_{kq+j}\varepsilon _{N}^{ (kq+j)i}=\sum _{j=0}^{q-1}\varepszilon _{N}^{ij}(\sum _{k=0}^{p-1}a_{kq +j}\varepsilon _{N}^{kiq})

Figyelembe véve, hogy és , a végső rekord: ${\displaystyle \varepsilon _{N}^{kiq}=\varepsilon _{N/q}^{ki))$ $N/q=p$

b_{i}=\sum _{j=0}^{q-1}\varepsilon _{N}^{ij}(\sum _{k=0}^{p-1}a_{kq +j}\varepsilon _{p}^{ki})

Továbbá mindegyik kiszámításra kerül , ahol , itt még műveleteket kell végrehajtani, vagyis a műveleteket ebben a szakaszban kell végrehajtani . $kettős}$ $i={\overline {0,p-1}}$ $TOVÁBB)$ $p\cdot O(N)=O(Np)$

Továbbá figyelembe veszik, hogy hol . Az utolsó képletben a csere során a zárójelben lévő kifejezések változatlanok maradtak, és mivel az előző lépésben már ki lettek számítva, mindegyik kiszámításához csak műveletek szükségesek. Összes számok. Ezért ebben a lépésben a műveletek a következők . Ez utóbbi jó pontossággal mindenre igaz . ${\displaystyle b_{i+mp))$ $i={\overline {0,p-1}},m={\overline {1,q-1}}$ $i\longmapsto i+mp$ $O(q)$ $p(q-1)=Np$ $(Np)\cdot O(q)=O((N-1)q)\cong O(Nq)$ $N$

Logikus a gyors Fourier-transzformációs algoritmus használata -re , mert kis számú minta esetén kis sebességnövekedést ad a diszkrét Fourier-transzformáció közvetlen számításához képest. Így ahhoz, hogy teljesen áttérjünk egy számkészletre , cselekvésekre van szükség. Ezért nem mindegy, hogy melyik két számra bontsuk fel – a válasz ettől nem sokat fog változni. A műveletek száma csak további particionálással csökkenthető . $N\gg 1$ ${\displaystyle b_{0},\dots ,b_{N-1))$ $O(Np)+O(Nq)$ $N$ $N$

Algoritmus sebessége : $(N=pq)$

$p\gg q\longrightarrow O(Np)$
$p\sim q\longrightarrow O(Nq)$
$p\ll q\longrightarrow O(Nq)$

Vagyis a két számra osztott műveletek száma , ahol . $N$ $O(Nc)$ $c=max(p,q)$

Inverz Fourier transzformáció

Az inverz Fourier-transzformációhoz használhatja a közvetlen Fourier-transzformációs algoritmust - csak helyette kell használnia ( vagy alkalmaznia kell a komplex konjugációs műveletet először a bemeneti adatokra, majd a közvetlen Fourier-transzformáció után kapott eredményre), és el kell osztania az végeredmény . $\varepsilon^{-1}$ $\varepsilon$ $N$

Általános eset

Az általános eset az előzőre redukálható. Tartásokhoz : $4N>2^k\ge2N$

b_i=\varepszilon^{-i^2/2}\sum_{j=0}^{N-1}\varepsilon^{(i+j)^2/2}\varepszilon^{-j^2/2 }a_j

A jelölésből kiderül: $\bar{a}_i=\varepsilon^{-i^2/2}a_i, \bar{b}_i=\varepsilon^{i^2/2}b_i, c_i=\varepsilon^{(2N-2- i)^2/2}$

\bar{b}_i=\sum_{j=0}^{2N-2-i}\bar{a}_jc_{2N-2-ij}

ha a . $\bar{a}_i=0$ $én N$

Így a probléma a konvolúció kiszámítására redukálódik , de ezt három Fourier-transzformációval is megtehetjük az elemekre: végrehajtjuk a közvetlen Fourier-transzformációt és -re , az eredményeket elemenként megszorozzuk, és végrehajtjuk az inverz Fourier-transzformációt. $2^k$ $\{\bar{a}_i\}_{i=0}^{i=2^k-1}$ $\{c_i\}_{i=0}^{i=2^k-1}$

Az összes kiszámítása és cselekvést igényel , három Fourier-transzformáció cselekvést igényel, a Fourier-transzformációk eredményének szorzása cselekvést igényel , a konvolúció értékeinek ismerete minden kiszámítása cselekvést igényel. Összességében a diszkrét Fourier-transzformáció műveleteket igényel bármely . $\bar{a}_i$ $c_{i}$ $TOVÁBB)$ $O(N\log(N))$ $TOVÁBB)$ $kettős}$ $TOVÁBB)$ $O(N\log(N))$ $N$

Ez a gyors Fourier-transzformációs algoritmus csak akkor tud működni egy gyűrűn, ha az egység primitív gyökerei ismertek és hatványaiban . $2N$ $2^k$

Konverziós származtatás diszkrétből

A legelterjedtebb gyors Fourier-transzformációs algoritmus a Cooley-Tukey-algoritmus , amelyben a diszkrét Fourier-transzformáció kisebb dimenziójú diszkrét Fourier-transzformációk összegeként és rekurzív módon fejeződik ki a komplexitás elérése érdekében . A kisebb Fourier-transzformációk elemi artikulációs lépését ebben az algoritmusban " pillangónak " nevezzük. A számítástechnikában a transzformációk leggyakrabban használt rekurzív felezése a 2. bázis (bár bármelyik bázis használható), a bemeneti minták száma pedig kettő hatványa. Azokban az esetekben, amikor a diszkrét transzformációt a prímszámú minták számából számítják ki, a Bluestein és Rader algoritmusok használhatók. $N=N_1 N_2$ $N_1$ $N_2$ $O(N\log(N))$

Például a gyors Fourier-transzformáció kiszámításához a Cooley-Tukey-algoritmus segítségével 2-es bázissal egy elemekből álló vektorhoz : $\vec x$ $N$

\vec X = \hat A \vec x

az űrlap elemeivel : $\kalap A$

a_{N}^{mn} = e^ { -\frac{2\pi i}{N} mn}

A diszkrét transzformáció két rész összegeként fejezhető ki: a páros indexek összege és a páratlan indexek összege : $m={2n}$ $m={2n+1}$

X_m=\sum_{n=0}^{N-1} x_n a_{N}^{mn} = \sum_{n=0}^{N/2-1}x_{2n} a_{N}^{ 2nm} + \sum_{n=0}^{N/2-1}x_{2n+1} a_{N}^{(2n+1)m}

Az és együtthatók a következőképpen írhatók át: $a_{N}^{2nm}$ $a_{N}^{(2n+1)m}$

a_{N}^{2nm} = e^\left( -2\pi i \frac{2mn}{N} \right) = e^ \left( -2\pi i \frac{mn}{N/2 } \jobbra) = a_{N/2}^{nm}

a_{N}^{(2n+1)m} = e^ \left( -2\pi i \frac{m}{N} \right) a_{N/2}^{nm}

Ennek eredményeként:

X_m=\sum_{n=0}^{N/2-1} x_{2n} a_{N/2}^{nm} + e^ { -\frac{2\pi i}{N} m} \ összeg_{n=0}^{N/2-1} x_{2n+1} a_{N/2}^{nm}

Ennek a kifejezésnek a kiszámítása egyszerűsíthető:

a DFT periodicitási tulajdonsága: $a_{{N/2}}^{{(m+{\frac {N}{2}})n}}=a_{{N/2}}^{{nm}}$ ,
az FFT elforgatási tényezője kielégíti a következő egyenletet: $\begin{mátrix} e^{\frac{-2\pi i}{N} (m + N/2)} & = & e^{\frac{-2\pi im}{N} - {\pi i}} \\ & = & e^{-\pi i} e^{\frac{-2\pi im}{N}} \\ & = & -e^{\frac{-2\pi im} {N}}\end{mátrix}$

Az egyszerűsítések eredményeként a páros indexek diszkrét Fourier-transzformációját -val jelölve, a páratlan indexek transzformációját pedig -vel jelölve kapjuk: $x_{2 m}$ $E_m$ $x_{2 m + 1}$ $O_m$ $0\leqslant m<{\frac {N}{2))$

\begin{mátrix} X_m & = & E_m + e^{-\frac{2\pi i}{N}m} O_m \\ X_{m+\frac{N}{2}} & = & E_m - e^ {-\frac{2\pi i}{N}m} O_m \end{mátrix}

Ez a bejegyzés a Cooley-Tukey algoritmus alapja 2-es bázissal a gyors Fourier-transzformáció kiszámításához, vagyis a mintákból álló vektorból származó diszkrét transzformációt két mintákból származó diszkrét Fourier-transzformáció lineáris összetételére redukáljuk , és ha a eredeti feladat műveleteket igényelt, majd a kapott összetételhez - (a számítások köztes eredményeinek újrafelhasználása miatt és ). Ha kettő hatványa, akkor ez az osztás rekurzív módon folytatható, amíg el nem éri a kétpontos Fourier-transzformációt, amelyet a következő képletekkel számítunk ki: $N$ $\frac N2$ $N^2$ $\frac{N^2}{2}$ $E_m$ $O_m$ $N$

\begin{cases} X_0=x_0+x_1\\ X_1=x_0-x_1 \end{cases}

Ha rekurzív módon elosztjuk a diszkrét Fourier-transzformációt a bemeneti értékekből 2 diszkrét transzformáció összegével a bemeneti értékekből, akkor az algoritmus összetettsége egyenlővé válik . $N$ $N/2$ $O(N\log(N))$

Linkek

Nussbaumer G. Gyors Fourier transzformáció és konvolúciós algoritmusok. - M . : Rádió és kommunikáció, 1985.