Rychlá Fourierova transformace

Rychlá Fourierova transformace ( FFT , FFT ) je algoritmus pro zrychlený výpočet diskrétní Fourierovy transformace , který umožňuje získat výsledek za kratší čas (požadovaný pro přímý výpočet podle vzorce). Někdy je rychlá Fourierova transformace chápána jako jeden z algoritmů, nazývaný frekvenčně-časový decimační algoritmus, který má složitost . $O(N^2)$ $O(N\log(N))$

Algoritmus je použitelný pro všechny komutativní asociativní kruhy s jednotkou, častěji se používá v oboru komplexních čísel (c ) a na zbytkové kruhy (což je zejména počítačový celočíselný typ ). $\varepsilon=e^{2\pi i/n}$

Základní algoritmus

Při aplikaci základního algoritmu lze diskrétní Fourierovu transformaci provádět v akcích pro , zejména když jsou akce potřebné . $O(N(p_1+\cdots+p_n))$ $N=p_1p_2\cdots p_n$ $N=2^n$ $O(N\log(N))$

Diskrétní Fourierova transformace transformuje množinu čísel na množinu čísel , taková , kde je primitivní kořen jednoty , tedy pro . Hlavním krokem algoritmu je zredukovat problém čísel na problém s menším číslem. Pro přes obor komplexních čísel zavedeme: , , kde je libovolné číslo. Diskrétní Fourierova transformace může být reprezentována jako . (Tyto výrazy lze snadno získat, pokud se původní součet rozdělí na menší počet součtů s menším počtem členů a výsledné součty se pak posunem indexů a jejich následným přejmenováním dostanou do stejné podoby). $a_0, \tečky, a_{n-1}$ $b_0, \tečky, 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}=\součet _{k=0}^{p-1}\součet _{j=0}^{q-1}a_{kq+j}\varepsilon _{N}^{ (kq+j)i}$

Takto:

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

S ohledem na to a konečný záznam: ${\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})

Dále se vypočítá každý , kde , zde je stále nutné provádět akce, to znamená, že operace se provádějí v této fázi . $bi}$ $i={\overline {0,p-1}}$ $NA)$ $p\cdot O(N)=O(Np)$

Dále se uvažuje kde . Při nahrazení v posledním vzorci zůstaly výrazy v závorkách nezměněny, a protože byly vypočteny již v předchozím kroku, je k výpočtu každého z nich zapotřebí pouze akce. Celková čísla. Operace v tomto kroku jsou tedy . To druhé platí s dobrou přesností pro všechny . ${\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$

Je logické použít algoritmus rychlé Fourierovy transformace pro , protože s malým počtem vzorků poskytuje malý nárůst rychlosti ve srovnání s přímým výpočtem diskrétní Fourierovy transformace. K úplnému přechodu na sadu čísel jsou tedy nutné akce. Nezáleží tedy na tom, na která dvě čísla se má rozdělit - odpověď se tím příliš nezmění. Počet operací lze snížit pouze dalším rozdělením . $N\gg 1$ ${\displaystyle b_{0},\tečky ,b_{N-1))$ $O(Np)+O(Nq)$ $N$ $N$

Rychlost algoritmu : $(N=pq)$

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

To znamená, že počet operací pro jakékoli rozdělení na dvě čísla je , kde . $N$ $O(Nc)$ $c=max(p,q)$

Inverzní Fourierova transformace

Pro inverzní Fourierovu transformaci můžete použít přímý algoritmus Fourierovy transformace - stačí použít místo něj (nebo použít operaci komplexní konjugace nejprve na vstupní data a poté na výsledek získaný po přímé Fourierově transformaci) a rozdělit konečný výsledek podle . $\varepsilon^{-1}$ $\varepsilon$ $N$

Obecný případ

Obecný případ lze zredukovat na předchozí. Pro držení: $4N>2^k\ge2N$

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

Označení to dopadá: $\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}

pokud je uvedeno na . $\bar{a}_i=0$ $i\ge N$

Problém se tedy redukuje na výpočet konvoluce , ale to lze provést pomocí tří Fourierových transformací pro prvky: přímá Fourierova transformace se provede pro a , výsledky se vynásobí prvek po prvku a provede se inverzní Fourierova transformace. $2^k$ $\{\bar{a}_i\}_{i=0}^{i=2^k-1}$ $\{c_i\}_{i=0}^{i=2^k-1}$

Výpočet všeho a vyžaduje akci, tři Fourierovy transformace vyžadují akci, násobení výsledků Fourierových transformací vyžaduje akci, výpočet všeho, znalost hodnot konvoluce vyžaduje akci. Celkem diskrétní Fourierova transformace vyžaduje akce pro libovolné . $\bar{a}_i$ $c_{i}$ $NA)$ $O(N\log(N))$ $NA)$ $bi}$ $NA)$ $O(N\log(N))$ $N$

Tento algoritmus rychlé Fourierovy transformace může fungovat na prstenci pouze tehdy, když jsou primitivní kořeny jednoty známy v mocninách a . $2N$ $2^k$

Odvození převodu z diskrétního

Nejběžnějším rychlým algoritmem Fourierovy transformace je Cooley-Tukeyův algoritmus , ve kterém je diskrétní Fourierova transformace vyjádřena jako součet diskrétních Fourierových transformací nižších dimenzí a rekurzivně, aby bylo dosaženo složitosti . Elementární artikulační krok menších Fourierových transformací v tomto algoritmu se nazývá " motýl ". Ve výpočetní technice se nejčastěji používá rekurzivní půlení transformací základ 2 (ačkoli lze použít jakýkoli základ) a počet vstupních vzorků je mocninou dvou. Pro případy, kdy se diskrétní transformace vypočítává z počtu vzorků, které jsou prvočísly, lze použít algoritmy Bluestein a Rader. $N=N_1 N_2$ $N_1$ $N_2$ $O(N\log(N))$

Například pro výpočet rychlé Fourierovy transformace pomocí Cooley-Tukeyho algoritmu se základem 2 pro vektor sestávající z prvků: $\vec x$ $N$

\vec X = \hat A \vec x

s prvky formuláře: $\ klobouk A$

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

diskrétní transformaci lze vyjádřit jako součet dvou částí: součet sudých indexů a součet lichých indexů : $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}

Koeficienty a lze přepsat takto: $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}

Jako výsledek:

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

Výpočet tohoto výrazu lze zjednodušit pomocí:

vlastnost periodicity DFT: $a_{{N/2}}^{{(m+{\frac {N}{2}})n}}=a_{{N/2}}^{{nm}}$ ,
FFT rotační faktor splňuje následující rovnici: $\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}$

V důsledku zjednodušení označíme diskrétní Fourierovu transformaci sudých indexů pomocí a transformaci lichých indexů pomocí , for dostaneme: $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}

Tato položka je základem Cooley-Tukeyho algoritmu se základem 2 pro výpočet rychlé Fourierovy transformace, to znamená, že diskrétní transformace z vektoru sestávajícího ze vzorků je redukována na lineární složení dvou diskrétních Fourierových transformací ze vzorků, a pokud původní úkol vyžadoval operace, pak pro výslednou skladbu - (kvůli opětovnému použití mezivýsledků výpočtů a ). Pokud je mocnina dvou, pak toto dělení může pokračovat rekurzivně, dokud nedosáhne dvoubodové Fourierovy transformace, která se vypočítá podle následujících vzorců: $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}

Při rekurzivním dělení diskrétní Fourierovy transformace ze vstupních hodnot součtem 2 diskrétních transformací ze vstupních hodnot se složitost algoritmu rovná . $N$ $N/2$ $O(N\log(N))$

Odkazy

Nussbaumer G. Rychlá Fourierova transformace a konvoluční algoritmy. - M .: Rádio a komunikace, 1985.