Transformare rapidă Fourier

Transformarea Fourier rapidă ( FFT , FFT ) este un algoritm pentru calculul accelerat al transformării Fourier discrete care vă permite să obțineți rezultatul în mai puțin de timp (necesar pentru calculul direct, formulă cu formulă). Uneori, transformata Fourier rapidă este înțeleasă ca unul dintre algoritmi, numit algoritm de decimare frecvență-timp, care are complexitate . $O(N^2)$ $O(N\log(N))$

Algoritmul este aplicabil oricăror inele asociative comutative cu o unitate, mai des aplicat câmpului numerelor complexe ( c ) și inelelor reziduale (care, în special, este de tip întreg computerizat ). $\varepsilon=e^{2\pi i/n}$

Algoritm de bază

Când se aplică algoritmul de bază, transformarea Fourier discretă poate fi efectuată în acțiuni pentru , în special, atunci când sunt necesare acțiuni . $O(N(p_1+\cdots+p_n))$ $N=p_1p_2\cdots p_n$ $N=2^n$ $O(N\log(N))$

Transformarea Fourier discretă transformă o mulțime de numere într-o mulțime de numere , astfel încât , unde este rădăcina primitivă a unității , adică pentru . Pasul principal al algoritmului este de a reduce problema pentru numere la o problemă cu un număr mai mic. Pentru domeniul numerelor complexe, introducem: , , unde este orice număr. Transformata Fourier discretă poate fi reprezentată ca . (Aceste expresii pot fi obținute cu ușurință dacă suma inițială este împărțită într-un număr mai mic de sume cu un număr mai mic de termeni, iar apoi sumele rezultate sunt aduse la aceeași formă prin deplasarea indicilor și redenumirea ulterioară a acestora). $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}$

În acest fel:

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})

Ținând cont de faptul că și , înregistrarea finală: $\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})

În plus, fiecare este calculat , unde , aici este încă necesar să se efectueze acțiuni, adică operațiunile sunt efectuate în această etapă . $b_{i}$ $i={\overline {0,p-1}}$ $PE)$ $p\cdot O(N)=O(Np)$

Mai departe se consideră unde . La înlocuirea în ultima formulă, expresiile dintre paranteze au rămas neschimbate și, deoarece au fost deja calculate în pasul anterior, sunt necesare doar acțiuni pentru a calcula fiecare dintre ele. Numerele totale . Prin urmare, operațiile la acest pas sunt . Acesta din urmă este adevărat cu o precizie bună pentru orice . $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$

Este logic să folosiți algoritmul de transformare Fourier rapidă pentru , deoarece cu un număr mic de eșantioane oferă un câștig mic de viteză în comparație cu calculul direct al transformării Fourier discrete. Astfel, pentru a trece complet la un set de numere , sunt necesare acțiuni. Prin urmare, nu are nicio diferență în ce două numere să se împartă - răspunsul nu se va schimba prea mult. Numărul de operații poate fi redus doar prin partiționare ulterioară . $N\gg 1$ $b_{0},\dots,b_{N-1)$ $O(Np)+O(Nq)$ $N$ $N$

Viteza algoritmului : $(N=pq)$

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

Adică, numărul de operații pentru orice împărțire în două numere este , unde . $N$ $O(Nc)$ $c=max(p,q)$

Transformată Fourier inversă

Pentru transformarea Fourier inversă, puteți utiliza algoritmul de transformare Fourier directă - trebuie doar să utilizați în schimb (sau să aplicați operația de conjugare complexă mai întâi la datele de intrare și apoi la rezultatul obținut după transformarea Fourier directă) și să împărțiți rezultatul final de către . $\varepsilon^{-1}$ $\varepsilon$ $N$

Caz general

Cazul general poate fi redus la cel anterior. Pentru reținere: $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

Indicând aceasta rezultă: $\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}

dacă se pune la . $\bar{a}_i=0$ $i\ge N$

Astfel, problema se reduce la calcularea convoluției , dar aceasta se poate face folosind trei transformări Fourier pentru elemente: se realizează transformarea Fourier directă pentru și , rezultatele sunt înmulțite element cu element și se realizează transformarea Fourier inversă. $2^k$ $\{\bar{a}_i\}_{i=0}^{i=2^k-1}$ $\{c_i\}_{i=0}^{i=2^k-1}$

Calcularea tuturor și necesită acțiune, trei transformări Fourier necesită acțiune, înmulțirea rezultatelor transformării Fourier necesită acțiune, calcularea tuturor cunoașterea valorilor convoluției necesită acțiune. În total, transformata Fourier discretă necesită acțiuni pentru orice . $\bar{a}_i$ $c_{i}$ $PE)$ $O(N\log(N))$ $PE)$ $b_{i}$ $PE)$ $O(N\log(N))$ $N$

Acest algoritm de transformare Fourier rapidă poate funcționa numai pe un inel atunci când rădăcinile primitive ale unității sunt cunoscute în puterile lui și . $2N$ $2^k$

Derivarea conversiei din discret

Cel mai comun algoritm de transformare Fourier rapidă este algoritmul Cooley-Tukey , în care transformarea Fourier discretă a este exprimată ca sumă a transformărilor Fourier discrete de dimensiuni mai mici și recursiv pentru a atinge complexitatea . Etapa elementară de articulare a transformărilor Fourier mai mici din acest algoritm se numește „ fluture ”. În calcul, cea mai frecvent utilizată înjumătățire recursivă a transformărilor este baza 2 (deși poate fi utilizată orice bază), iar numărul de eșantioane de intrare este o putere de două. Pentru cazurile în care transformarea discretă este calculată din numărul de eșantioane care sunt numere prime, se pot utiliza algoritmii Bluestein și Rader. $N=N_1 N_2$ $N_1$ $N_2$ $O(N\log(N))$

De exemplu, pentru a calcula transformarea Fourier rapidă folosind algoritmul Cooley-Tukey cu bază 2 pentru un vector format din elemente: $\vec x$ $N$

\vec X = \hat A \vec x

cu elemente de forma: $\hat A$

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

transformarea discretă poate fi exprimată ca suma a două părți: suma indicilor pare și suma indicilor impari : $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}

Coeficienții și pot fi rescriși după cum urmează: $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}

Ca urmare:

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}

Calculul acestei expresii poate fi simplificat folosind:

Proprietatea de periodicitate a DFT: $a_{{N/2}}^{{(m+{\frac {N}{2}})n}}=a_{{N/2}}^{{nm}}$ ,
factorul de rotație FFT satisface următoarea ecuație: $\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{matrice}$

Ca rezultat al simplificărilor, notând transformata Fourier discretă a indicilor pare cu și transformarea indicilor impari cu , pentru se obține: $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{matrice}

Această intrare este baza algoritmului Cooley-Tukey cu baza 2 pentru calcularea transformării rapide Fourier, adică transformarea discretă dintr-un vector format din eșantioane este redusă la o compoziție liniară a două transformate Fourier discrete din probe, iar dacă sarcina originală a necesitat operații, apoi pentru compoziția rezultată - (datorită reutilizarii rezultatelor intermediare ale calculelor și ). Dacă este o putere de doi, atunci această împărțire poate fi continuată recursiv până când ajunge la o transformată Fourier în două puncte, care este calculată prin următoarele formule: $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}

Când se împarte recursiv transformata Fourier discretă din valorile de intrare la suma a 2 transformări discrete din valorile de intrare, complexitatea algoritmului devine egală cu . $N$ $N/2$ $O(N\log(N))$

Link -uri

Nussbaumer G. Algoritmi de transformare Fourier rapide și de convoluție. - M . : Radio și comunicare, 1985.