Transformare rapidă Fourier

În matematică , transformata Fourier rapidă , adesea prescurtată ca FFT ( Fast Fourier Transform ), este un algoritm optimizat pentru a calcula transformata Fourier discretă (DFT) sau inversul acesteia.

FFT este utilizat într-o mare varietate de aplicații, de la procesarea digitală a semnalului la soluția ecuațiilor diferențiale parțiale la algoritmi pentru multiplicarea numerelor întregi mari datorită costului de calcul redus.

Definiție

Este $x_{0},\dots ,x_{N-1}$ ${\ displaystyle x_ {0}, \ dots, x_ {N-1}}$ $x_ {0}, \ dots, x _ {{N-1}}$ A $Nu.$ ${\ displaystyle N}$ $Nu.$ -plexul numerelor complexe . DFT este definit de formula:

X_{q}={\mathcal {F}}_{d}(x_{n})=\sum _{k=0}^{N-1}x_{k}e^{-i{\frac {2\pi }{N}}kq}\qquad q=0,1,\dots ,N-1

{\ displaystyle X_ {q} = {\ mathcal {F}} _ {d} (x_ {n}) = \ sum _ {k = 0} ^ {N-1} x_ {k} e ^ {- i { \ frac {2 \ pi} {N}} kq} \ qquad q = 0,1, \ dots, N-1}

X_ {q} = {\ mathcal {F}} _ {d} (x_ {n}) = \ sum _ {{k = 0}} ^ {{N-1}} x_ {k} e ^ {{- i {\ frac {2 \ pi} {N}} kq}} \ qquad q = 0,1, \ dots, N-1

Calculul acestei sume necesită în mod direct o serie de operații aritmetice $O(N^{2})$ ${\ displaystyle O (N ^ {2})}$ $O (N ^ {2})$ . Un algoritm FFT obține același rezultat cu o serie de operații $O(N\log(N))$ ${\ displaystyle O (N \ log (N))}$ $O (N \ log (N))$ . În general, acești algoritmi se bazează pe factorizarea $Nu.$ ${\ displaystyle N}$ $Nu.$ , dar există algoritmi FFT pentru aproape orice $Nu.$ ${\ displaystyle N}$ $Nu.$ , chiar și pentru numerele prime .

Deoarece antitransforma Fourier discretă este egală cu DFT, dar cu exponent al semnului opus e $1/N$ ${\ displaystyle 1 / N}$ $1 / N$ După factori, orice algoritm FFT poate fi inversat cu ușurință.

Algoritmul Cooley-Tukey

Cel mai popular algoritm FFT este algoritmul Cooley-Tukey. Acest algoritm se bazează pe principiul divizării și cuceririi și rupe recursiv un DFT de orice dimensiune $Nu.$ ${\ displaystyle N}$ $Nu.$ , cu $Nu.$ ${\ displaystyle N}$ $Nu.$ număr compus astfel încât $N=N_{1}N_{2}$ ${\ displaystyle N = N_ {1} N_ {2}}$ $N = N_ {1} N_ {2}$ în DFT-uri de dimensiuni mai mici $N_{1}$ ${\ displaystyle N_ {1}}$ $N_1$ Și $N_{2}$ ${\ displaystyle N_ {2}}$ $N_ {2}$ , cu $O(n)$ ${\ displaystyle O (n)}$ $Pe)$ multiplicări cu unitatea imaginară, numite factori twiddle .

Această metodă (și ideea unei transformate Fourier rapide în general) a fost popularizată de o publicație a lui James Cooley și John Wilder Tukey în 1965 , dar s-a descoperit mai târziu că cei doi autori au reinventat independent un algoritm cunoscut lui Carl Friedrich. Gauss în 1805 [1] (și mai târziu redescoperit în multe alte forme limitate).

Cea mai cunoscută utilizare a algoritmului Cooley - Tukey este divizarea și transformarea în două bucăți de $n/2$ ${\ displaystyle n / 2}$ $n / 2$ la fiecare pas și, prin urmare, este optimizat numai pentru dimensiunile care sunt puteri de două, dar, în general, poate fi utilizată orice factorizare (așa cum se știa atât de Gauss, cât și de Cooley și Tukey). Aceste cazuri se numesc rădăcină 2 și, respectiv, rădăcină mixtă (dar există și alte abordări cu nume specifice). În timp ce ideea de bază este recursivă, majoritatea implementărilor tradiționale rearanjează algoritmul pentru a evita recursivitatea explicită. De asemenea, deoarece algoritmul Cooley-Tukey descompune DFT în DFT-uri mai mici, acesta poate fi combinat în mod arbitrar cu orice alt algoritm DFT, precum cele descrise mai jos.

O implementare iterativă C ++ a FFT bazată pe algoritmul Cooley-Tukey este după cum urmează:

 #include <iostream>
#include <complex>
#define MAX 200

folosind spațiul de nume std ;

int log2 ( int N ) // funcție pentru a calcula logaritmul de bază 2 al unui întreg
{
  int k = N , i = 0 ;
  while ( k ) {
    k >> = 1 ;
    i ++ ;
  }
  retur i - 1 ;
}

int check ( int n ) // folosit pentru a verifica dacă numărul componentelor vectorului de intrare este o putere de 2
{
  returnează n > 0 && ( n & ( n - 1 )) == 0 ;
}

int invers ( int N , int n ) // calculați numărul invers al fiecărui număr întreg n față de numărul maxim N
{
  int j , p = 0 ;
  pentru ( j = 1 ; j <= log2 ( N ); j ++ ) {
    if ( n & ( 1 << ( log2 ( N ) - j )))
      p | = 1 << ( j - 1 );
  }
  retur p ;
}

soiuri nule (complex <double> * f1, int N) // aranjează elementele vectorului prin ordonarea acestora prin ordine inversă
{
  complex < dublu > f2 [ MAX ];
  pentru ( int i = 0 ; i < N ; i ++ )
    f2 [ i ] = f1 [ invers ( N , i )];
  pentru ( int j = 0 ; j < N ; j ++ )
    f1 [ j ] = f2 [ j ];
}

void transform ( complex < double > * f , int N ) // calculați vectorul transformat
{
  sorturi ( f , N ); // mai întâi comandați-o cu ordine inversă
  complex < dublu > W [ N / 2 ]; // vector de zerouri de unitate.
                            // În primul rând N / 2-1, dar aruncă o eroare cu următoarea buclă
                           // în timp ce încearcă să copieze într-o zonă nealocată „W [N / 2-1]”
  W [ 1 ] = polar ( 1. , -2. * M_PI / N );
  W [ 0 ] = 1 ;
  pentru ( int i = 2 ; i < N / 2 ; i ++ )
    W [ i ] = pow ( W [ 1 ], i );
  int n = 1 ;
  int a = N / 2 ;
  for ( int j = 0 ; j < log2 ( N ); j ++ ) {
    for ( int i = 0 ; i < N ; i ++ ) {
      if ( ! ( i & n )) {
        / * la fiecare pas de dublare a lui n, se utilizează indicii * /
        / * „i” luat alternativ în grupuri de n, o dată da și o dată nu. * /
        complex < dublu > temp = f [ i ];
        complex < dublu > Temp = W [( i * a ) % ( n * a )] * f [ i + n ];
        f [ i ] = temp + Temp ;
        f [ i + n ] = temp - Temp ;
      }
    }
    n * = 2 ;
    a = a / 2 ;
  }
}

void FFT ( complex < double > * f , int N , double d )
{
  transformare ( f , N );
  for ( int i = 0 ; i < N ; i ++ )
    f [ i ] * = d ; // înmulțiți vectorul cu pasul pentru a avea vectorul transformat efectiv
}

int main ()
{
  int n ;
  face {
    cout << "specifică dimensiunea vectorului, care este o putere de 2" << endl ;
    cin >> n ;
  } while ( ! verificați ( n ));
  dublu d ;
  cout << "introduceți dimensiunea pasului de eșantionare" << endl ;
  cin >> d ;
  cout << "sampling step =" << d << endl ;
  complex < double > vec [ MAX ];
  cout << "insert vector sample" << endl ;
  for ( int i = 0 ; i < n ; i ++ ) {
    cout << "insert component index" << i << endl ;
    cin >> vec [ i ];
    cout << "index" << i << "=" << vec [ i ] << endl ;
  }
  FFT ( vec , n , d );
  cout << "vector transformat" << endl ;
  pentru ( int j = 0 ; j < n ; j ++ )
    cout << vec [ j ] << endl ;
  retur 0 ;
}

Alți algoritmi pentru calcularea FFT

Există și alți algoritmi FFT în afară de Cooley-Tukey. Pentru N = N ₁ N ₂ cu numere coprimă N ₁ și N ₂ , se poate utiliza algoritmul Good-Thomas PFA ( P rime-factor F FT A lgorithm), pe baza teoremei restului chinezesc , care factorizează DFT într-un similar drum spre Cooley-Tukey. Algoritmul FFT Rader-Brenner este un sistem de factorizare asemănător Cooley-Tukey, dar cu factori imaginați puri, reducând numărul de înmulțiri cu prețul creșterii adunării și a instabilității numerice.

Algoritmii care rup recursiv DFT în operații mai mici, altele decât DFT, includ algoritmul Bruun și QFT. (Algoritmii Rader-Brenner și QFT au fost propuși pentru dimensiuni care sunt puteri de 2, dar este posibil ca acestea să poată fi adaptate pentru orice număr compus. Algoritmul Bruun poate fi aplicat oricăror dimensiuni și chiar compozite). În special, algoritmul FFT al lui Bruun se bazează pe interpretarea FFT ca factorizarea recursivă a polinomului z ⁿ -1 în polinoame cu coeficienți reali sub forma z ^m -1 și z ^2m + az ^m +1.

Un alt punct de vedere polinomial este exploatat de algoritmul FFT al lui Winograd, care factorizează z ⁿ -1 în polinoame ciclotomice , care au adesea coeficienți 1, 0 sau −1 și, prin urmare, necesită o multiplicare mică (dacă există), deci poate fi folosit pentru a obține FFT-uri cu un număr minim de înmulțiri și este adesea folosit pentru a găsi algoritmi eficienți pentru factori mici. Într-adevăr, Winograd a arătat că DFT poate fi calculat numai cu multiplicări O (n); din păcate, acest lucru se realizează cu un număr considerabil mai mare de adăugiri, un schimb nu mai favorabil pe procesoarele moderne echipate cu cipuri dedicate pentru multiplicarea în virgulă mobilă. În special, algoritmul Winograd folosește și algoritmii PFA și Rader pentru FFT-uri cu dimensiuni care sunt numere prime.

Un alt algoritm FFT număr prim se datorează LI Bluestein și este uneori numit ciripit -z algoritm: ea re-exprimă DFT ca convoluție, dimensiunea care poate fi adus la o putere de două și evaluate de Cooley-Tukey FFT .

Algoritmi FFT specializați pentru date reale și / sau simetrice

În multe aplicații datele de intrare pentru DFT sunt reale reale, caz în care rezultatul satisface simetria

f_{-j}=f_{j}^{*},

{\ displaystyle f _ {- j} = f_ {j} ^ {*},}

f _ {{- j}} = f_ {j} ^ {*},

și, în consecință, algoritmi FFT au fost dezvoltați pentru această situație ^[1] . O abordare este reutilizarea unui algoritm obișnuit și eliminarea părților de calcul redundante, economisind aproximativ un factor de doi în amprenta și timpul de memorie. Alternativ, este posibil să se exprime transforma Fourier discretă a unui n-pla cu un număr par al tuturor elementelor reale ca transformată discretă complexă a jumătății dimensiunii originale ale cărei părți reale și imaginare sunt elementele pare și impare ale elementelor originale, urmată de O (n) operațiuni de post-procesare.

S-a crezut cândva că n-plurile reale ale cărora se calculează DFT ar putea fi calculate mai eficient cu transformata Hartley discretă (numită DHT din acronimul D inscripționat H artley T ransform), dar s-a descoperit mai târziu că în Tipic specializat Se pot identifica algoritmi FFT care necesită mai puține operațiuni decât algoritmul DHT corespunzător. Algoritmul lui Bruun a fost, de asemenea, propus inițial pentru a profita de numerele reale ca intrare, dar nu a devenit niciodată popular.

Precizie și aproximări

Toți algoritmii FFT prezentați până acum calculează DFT exact (în sens aritmetic, adică neglijând erorile datorate calculelor în virgulă mobilă). Cu toate acestea, au fost propuși și algoritmi FFT care calculează DFT aproximativ , cu o eroare care poate fi făcută în mod arbitrar mică cu prețul unui efort de calcul mai mare. Acești algoritmi schimbă eroarea de aproximare în favoarea vitezei mai mari sau a altor caracteristici. Câteva exemple sunt algoritmul FFT al lui Edelman și colab. (1999), FFT bazat pe wavelet al lui Guo și Barrus (1996) sau cel al lui Shentov și colab. (1995).

Algoritmii FFT „exacți” au, de asemenea, erori atunci când se utilizează aritmetica în virgulă cu precizie finită, dar aceste erori sunt de obicei foarte mici; majoritatea algoritmilor FFT au proprietăți numerice excelente. Limita superioară a erorii relative pentru algoritmul Cooley-Tukey este O (ε log n), comparativ cu O (ε n ^3/2 ) pentru formula DFT originală (Gentleman și Sande, 1966). Cu toate acestea, aceste rezultate sunt foarte sensibile la acuratețea factorilor twiddle utilizați în FFT (care sunt valorile funcțiilor trigonometrice) și nu este neobișnuit ca implementările inexacte ale FFT să aibă o precizie mult mai proastă, pentru exemplu dacă folosesc tabele cu valori trigonometrice inexacte. Unii algoritmi FFT, cum ar fi Rader-Brenner, sunt inerent mai puțin stabili.

În aritmetica punctului fix, acuratețea erorilor acumulate de algoritmii FFT este mai slabă și crește ca O (√n) pentru algoritmul Cooley-Tukey ^[2] . În plus, realizarea acestei precizii necesită o atenție atentă și scalarea factorilor pentru a minimiza pierderea de precizie, iar algoritmii FFT cu punct fix necesită redimensionarea la fiecare etapă intermediară a descompunerilor ca în Cooley-Tukey.

Pentru a verifica corectitudinea unei implementări a unui algoritm FFT, se pot obține garanții stricte în timpul O (n log n) cu o procedură simplă care verifică liniaritatea, răspunsul la impuls și proprietățile de invarianță a timpului pentru datele de intrare aleatorii. ^[3] .

Notă

^ HV Sorensen, DL Jones, MT Heideman și CS Burrus. (1987, iunie). Algoritmi de transformare Fourier rapidă cu valoare reală. Tranzacții IEEE privind procesarea semnalului, 35 (6), 849-863.
^ Procesare digitală a semnalului, AV Oppenheim, RW Schafer, Prentice Hall, 1975
^ Funda Ergün, 1995, Testarea funcțiilor liniare multivariate: Depășirea blocajului generatorului, Proc. 27 Simpozion ACM despre teoria calculelor: 407-416.

Bibliografie

( EN ) Gilbert Strang, Wavelets , în American Scientist , vol. 82, nr. 3, mai-iunie 1994, p. 253. Accesat la 8 octombrie 2013 .
( EN ) DF Elliott și KR Rao, 1982, Transformări rapide: algoritmi, analize, aplicații . New York: Academic Press.
( EN ) Funda Ergün, 1995, Proc. 27 simpozion ACM pe teoria calculelor: 407–416.
( EN ) M. Frigo și SG Johnson, 2005, „ The Design and Implementation of FFTW3 ”, Proceedings of the IEEE 93 : 216–231.
( EN ) Carl Friedrich Gauss, 1866. „ Theoria Interpolationis Methodo Nova Tractata ”, banda Werke 3 , 265–327. Göttingen: Königliche Gesellschaft der Wissenschaften.
( EN ) WM Gentleman și G. Sande, 1966, „Fast Fourier transforms - for fun and profit,” Proc. AFIPS 29 : 563-578.
( EN ) H. Guo și CS Burrus, 1996, Proc. SPIE Intl. Soc. Opt. Eng. 2825 : 250-259.
( EN ) H. Guo, GA Sitton, CS Burrus, 1994, Proc. IEEE Conf. Acoust. Speech and Mr. Processing (ICASSP) 3 : 445–448.
( EN ) Steve Haynal și Heidi Haynal, „ Generating and Searching Families of FFT Algorithms ”, Journal on Satisfiability, Boolean Modeling and Computation vol. 7, pp. 145–187 (2011).
( EN ) SG Johnson și M. Frigo, 2007. " Un FFT split-radix modificat cu mai puține operațiuni aritmetice ", IEEE Trans. Procesarea semnalului 55 (1): 111-119.
( EN ) T. Lundy și J. Van Buskirk, 2007. "O nouă abordare matricială a FFT-urilor reale și a circumvoluțiilor de lungime 2 ^k ", Calcul 80 (1): 23-45.
(EN) Kent, Ray D. și Read, Charles (2002). Analiza acustică a vorbirii . ISBN 0-7693-0112-6 . Cită Strang, G. (1994) / mai - iunie). Wavelets. Om de știință american, 82, 250-255.
( EN ) James C. Schatzman, 1996, Acuratețea transformatei Fourier discrete și a transformatei Fourier rapide , SIAM J. Sci. Comput. 17 : 1150–1166.

Elemente conexe

linkuri externe

( EN ) Algoritmul Fourier rapid , pe cs.pitt.edu .
( EN ) Fast Fourier Transforms , Connexions carte online editată de C. Sidney Burrus, cu capitole de C. Sidney Burrus, Ivan Selesnick, Markus Pueschel, Matteo Frigo și Steven G. Johnson (2008).
( RO ) Link-uri către cod FFT și informații online. , pe fftw.org .
( EN ) National Taiwan University - FFT , la cmlab.csie.ntu.edu.tw . Adus la 12 ianuarie 2014 (arhivat din original la 30 aprilie 2010) .
( EN ) Programare FFT în algoritm C ++ - Cooley - Tukey. , la librow.com .
( RO ) Documentație online, linkuri, carte și cod. , la jjj.de.
( RO ) Utilizarea FFT pentru a construi distribuții de probabilitate agregate , pe vosesoftware.com .
( EN ) Sri Welaratna, „ Treizeci de ani de analizoare FFT ”, Sunet și vibrații (ianuarie 1997, ediția a 30-a aniversare). O revizuire istorică a dispozitivelor FFT hardware.
( RO ) FFT Noțiuni de bază și studiu de caz folosind Multi-Instrument ( PDF ), pe multi-instrument.com .
( EN ) Note de manual FFT, PPT-uri, videoclipuri la Holistic Numerical Methods Institute.
( EN ) ALGLIB FFT Code GPL Multilanguage licențiat (VBA, C ++, Pascal etc.), analiză numerică și bibliotecă de procesare a datelor.
( EN ) algoritmul și implementarea sFFT MIT MIT Sparse FFT.
( RO ) VB6 FFT VB6 optimizat implementarea bibliotecii cu cod sursă.
FFTW , bibliotecă de software cu limbaj C pentru FFT

Controlul autorității	GND ( DE ) 4136070-9

Portal IT

Portalul de matematică

[1] HV Sorensen, DL Jones, MT Heideman și CS Burrus. (1987, iunie). Algoritmi de transformare Fourier rapidă cu valoare reală. Tranzacții IEEE privind procesarea semnalului, 35 (6), 849-863.

[2] Procesare digitală a semnalului, AV Oppenheim, RW Schafer, Prentice Hall, 1975

[3] Funda Ergün, 1995, Testarea funcțiilor liniare multivariate: Depășirea blocajului generatorului, Proc. 27 Simpozion ACM despre teoria calculelor: 407-416.

[1]

[2]

[3]