Hurtig Fourier-transformation

Hurtig Fourier-transformation ( FFT , FFT ) er en algoritme til accelereret beregning af den diskrete Fourier-transformation , der giver dig mulighed for at få resultatet på mindre end (kræves for direkte, formel-for-formel-beregning) tid. Nogle gange forstås den hurtige Fourier-transformation som en af algoritmerne, kaldet frekvens-tidsdecimeringsalgoritmen, som har kompleksitet . $O(N^2)$ $O(N\log(N))$

Algoritmen er anvendelig på alle kommutative associative ringe med en enhed, oftere anvendt på feltet med komplekse tal (c ) og på restringe (som især er en computerheltalstype ) . $\varepsilon=e^{2\pi i/n}$

Grundlæggende algoritme

Når man anvender den grundlæggende algoritme, kan den diskrete Fourier-transformation udføres i handlinger til især når handlinger er nødvendige . $O(N(p_1+\cdots+p_n))$ $N=p_1p_2\cdots p_n$ $N=2^n$ $O(N\log(N))$

Den diskrete Fourier-transformation omdanner et sæt tal til et sæt tal , således at hvor er den primitive rod af enhed , det vil sige for . Det vigtigste trin i algoritmen er at reducere problemet for tal til et problem med et mindre tal. For over feltet af komplekse tal introducerer vi: , , hvor er ethvert tal. Den diskrete Fourier-transformation kan repræsenteres som . (Disse udtryk kan let opnås, hvis den oprindelige sum opdeles i et mindre antal summer med et mindre antal led, og derefter bringes de resulterende summer til samme form ved at forskyde indeksene og deres efterfølgende omdøbning). $a_0, \dots, a_{n-1}$ $b_0, \dots, b_{n-1}$ $b_i=\sum_{j=0}^{n-1}a_j\varepsilon^{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}$

På denne måde:

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}\varepsilon _{N}^{ij}(\sum _{k=0}^{p-1}a_{kq +j}\varepsilon _{N}^{kiq})

Under hensyntagen til det og den endelige 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})

Yderligere beregnes hver , hvor , her er det stadig påkrævet at udføre handlinger, det vil sige, at operationer udføres på dette stadium . $b_{i}$ $i={\overline {0,p-1}}$ $PÅ)$ $p\cdot O(N)=O(Np)$

Yderligere overvejes hvor . Ved udskiftning i den sidste formel forblev udtrykkene i parentes uændrede, og da de allerede blev beregnet i det foregående trin, kræves der kun handlinger for at beregne hver af dem. Samlede tal. Derfor er operationerne på dette trin . Det sidste er sandt med god nøjagtighed for enhver . ${\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$

Det er logisk at bruge den hurtige Fourier-transformationsalgoritme til , fordi det med et lille antal samples giver en lille hastighedsforstærkning sammenlignet med den direkte beregning af den diskrete Fourier-transformation. Derfor er handlinger nødvendige for helt at flytte til et sæt tal . Derfor gør det ingen forskel, hvilke to tal der skal opdeles i - svaret ændrer sig ikke meget herfra. Antallet af operationer kan kun reduceres ved yderligere partitionering . $N\gg 1$ ${\displaystyle b_{0},\dots ,b_{N-1))$ $O(Np)+O(Nq)$ $N$ $N$

Algoritme hastighed : $(N=pq)$

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

Det vil sige, at antallet af operationer for enhver opdeling i to tal er , hvor . $N$ $O(Nc)$ $c=max(p,q)$

Invers Fourier Transform

Til den inverse Fourier-transformation kan du bruge den direkte Fourier-transformationsalgoritme - du skal bare bruge i stedet (eller anvende den komplekse konjugationsoperation først på inputdataene og derefter på resultatet opnået efter den direkte Fourier-transformation) og dividere endeligt resultat af . $\varepsilon^{-1}$ $\varepsilon$ $N$

Generel sag

Den generelle sag kan reduceres til den foregående. For laster: $4N>2^k\ge2N$

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

Betegnelse viser det sig: $\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}

hvis sat kl . $\bar{a}_i=0$ $i\ge N$

Dermed er problemet reduceret til at beregne foldningen , men dette kan gøres ved hjælp af tre Fourier-transformationer for elementerne: den direkte Fourier-transformation udføres for og , resultaterne ganges element for element, og den inverse Fourier-transformation udføres. $2^k$ $\{\bar{a}_i\}_{i=0}^{i=2^k-1}$ $\{c_i\}_{i=0}^{i=2^k-1}$

Beregning af alt og kræver handling, tre Fourier-transformationer kræver handling, multiplikation af resultaterne af Fourier-transformationer kræver handling, at beregne alt , når man kender værdierne af foldningen, kræver handling. I alt kræver den diskrete Fourier-transformation handlinger for enhver . $\bar{a}_i$ $c_{i}$ $PÅ)$ $O(N\log(N))$ $PÅ)$ $b_{i}$ $PÅ)$ $O(N\log(N))$ $N$

Denne Fast Fourier Transform algoritme kan kun fungere på en ring, når de primitive rødder af enhed er kendt i potenser og . $2N$ $2^k$

Konverteringsafledning fra diskret

Den mest almindelige hurtige Fourier-transformationsalgoritme er Cooley-Tukey-algoritmen , hvor den diskrete Fourier-transformation af udtrykkes som summen af diskrete Fourier-transformationer af lavere dimensioner og rekursivt for at opnå kompleksitet . Det elementære artikulationstrin for de mindre Fourier-transformationer i denne algoritme kaldes " sommerfuglen ". Inden for databehandling er den mest almindeligt anvendte rekursive halvering af transformationer base 2 (selvom enhver base kan bruges), og antallet af input samples er en potens af to. I tilfælde, hvor den diskrete transformation beregnes ud fra antallet af prøver, der er primtal, kan Bluestein- og Rader-algoritmerne bruges. $N=N_1 N_2$ $N_1$ $N_2$ $O(N\log(N))$

For eksempel for at beregne den hurtige Fourier-transformation ved hjælp af Cooley-Tukey-algoritmen med base 2 for en vektor bestående af elementer: $\vec x$ $N$

\vec X = \hat A \vec x

med elementer af formularen: $\hat A$

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

diskret transformation kan udtrykkes som summen af to dele: summen af lige indekser og summen af ulige indekser : $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}

Koefficienterne og kan omskrives som følger: $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 } \right) = a_{N/2}^{nm}

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

Som resultat:

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

Beregningen af dette udtryk kan forenkles ved at bruge:

periodicitetsegenskab for DFT: $a_{{N/2}}^{{(m+{\frac {N}{2}})n}}=a_{{N/2}}^{{nm}}$ ,
FFT-rotationsfaktoren opfylder følgende ligning: $\begin{matrix} 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{matrix}$

Som et resultat af forenklinger, der angiver den diskrete Fourier-transformation af lige indekser med og transformationen af ulige indekser med , for opnås: $x_{2m}$ $E_m$ $x_{2m + 1}$ $O_m$ $0\leqslant m<{\frac {N}{2))$

\begin{matrix} 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{matrix}

Denne post er basis for Cooley-Tukey-algoritmen med base 2 til beregning af den hurtige Fourier-transformation, det vil sige, at den diskrete transformation fra en vektor bestående af samples reduceres til en lineær sammensætning af to diskrete Fourier-transformationer fra samples, og hvis oprindelige opgave krævede operationer, derefter for den resulterende sammensætning - (på grund af genbrug af mellemresultater af beregninger og ). Hvis er en potens af to, så kan denne division fortsættes rekursivt, indtil den når en topunkts Fourier-transformation, som beregnes ved hjælp af følgende formler: $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}

Når man rekursivt dividerer den diskrete Fourier-transformation fra inputværdierne med summen af 2 diskrete transformationer fra inputværdierne, bliver kompleksiteten af algoritmen lig med . $N$ $N/2$ $O(N\log(N))$

Hurtig Fourier-transformation

Grundlæggende algoritme

Invers Fourier Transform

Generel sag

Konverteringsafledning fra diskret

Links