Trasformata di Fourier veloce

Inmatematica, latrasformata di Fourier veloce, spesso abbreviata conFFT(dall'ingleseFast Fourier Transform), è unalgoritmoottimizzato per calcolare latrasformata discreta di Fourier(DFT) o la sua inversa.
La FFT è utilizzata in una grande varietà di applicazioni, dall'elaborazione di segnali digitalialla soluzione diequazioni differenziali alle derivate parzialiaglialgoritmiper moltiplicarenumeri interidi grandi dimensioni grazie al basso costo computazionale.
Siax0,…,xN−1{\displaystyle x_{0},\dots ,x_{N-1}}unaN{\displaystyle N}-pla dinumeri complessi. La DFT è definita dalla formula:
Calcolare direttamente questa somma richiede una quantità di operazioni aritmeticheO(N2){\displaystyle O(N^{2})}. Un algoritmo FFT ottiene lo stesso risultato con un numero di operazioniO(Nlog⁡(N)){\displaystyle O(N\log(N))}. In generale questi algoritmi si basano sullafattorizzazionediN{\displaystyle N}, ma esistono algoritmi FFT per qualunqueN{\displaystyle N}, anche pernumeri primi.
Poiché l'antitrasformata discreta di Fourier è uguale alla DFT, ma con esponente di segno opposto e1/N{\displaystyle 1/N}a fattore, qualsiasi algoritmo FFT può essere facilmente invertito.
L'algoritmo FFT più diffuso è l'algoritmo di Cooley-Tukey. Questo algoritmo si basa sul principio didivide et impera, e spezza ricorsivamente una DFT di qualsiasi dimensioneN{\displaystyle N}, conN{\displaystyle N}numero compostotale cheN=N1N2{\displaystyle N=N_{1}N_{2}}in DFT più piccole di dimensioniN1{\displaystyle N_{1}}eN2{\displaystyle N_{2}}, insieme aO(n){\displaystyle O(n)}moltiplicazioni per l'unità immaginaria, dettifattori twiddle.
Questo metodo (e in generale l'idea di una trasformata di Fourier veloce) fu reso popolare da una pubblicazione diJames CooleyeJohn Wilder Tukeynel1965, ma in seguito si scoprì che i due autori avevano indipendentemente reinventato un algoritmo noto aCarl Friedrich Gaussnel1805(e successivamente riscoperto in molte altre forme limitate).
L'uso più conosciuto dell'algoritmo di Cooley-Tukey è di dividere e trasformare in due pezzi din/2{\displaystyle n/2}ad ogni passo, ed è quindi ottimizzato solo per dimensioni che siano potenze di due, ma in generale può essere utilizzata qualsiasi fattorizzazione (com'era noto sia a Gauss che a Cooley e Tukey). Questi casi sono chiamati rispettivamente casiradice 2eradice mista(ma esistono anche altri approcci con nomi specifici). Anche se l'idea di base è ricorsiva, la gran parte delle implementazioni tradizionali riorganizza l'algoritmo per evitare la ricorsione esplicita. Inoltre, poiché l'algoritmo di Cooley-Tukey spezza la DFT in DFT più piccole, può essere arbitrariamente combinato con qualsiasi altro algoritmo per la DFT, come quelli descritti qui sotto.
Un'implementazione iterativa inC++della FFT basata sull'algoritmo di Cooley-Tukey è la seguente:
Ci sono altri algoritmi per la FFT oltre al Cooley-Tukey. Per N=N1N2con N1e N2numericoprimipuò essere utilizzato l'algoritmo di Good-ThomasPFA(Prime-factorFFTAlgorithm), basato sulteorema cinese del resto, che fattorizza la DFT in un modo simile al Cooley-Tukey. L'algoritmo FFT di Rader-Brenner è un sistema di fattorizzazione simile al Cooley-Tukey ma con fattori twiddle immaginari puri, riducendo il numero delle moltiplicazioni al costo di un aumento delle addizioni e della instabilità numerica.
Gli algoritmi che suddividono ricorsivamente la DFT in operazioni più piccole diverse dalla DFT includono l'algoritmo di Bruun e il QFT. (Gli algoritmi di Rader-Brenner e il QFT sono stati proposti per dimensioni che siano potenze di 2, ma è possibile che vengano adattati per numeri composti qualunque. L'algoritmo di Bruun si può applicare su dimensioni qualunque anche composte). In particolare l'algoritmo per la FFT di Bruun è basato sull'interpretare la FFT come la fattorizzazione ricorsiva delpolinomioz-1 in polinomi a coefficienti reali nella forma z-1 e z+az+1.
Un altro punto di vista polinomiale è sfruttato dall'algoritmo FFT diSchmuel Winograd, che fattorizza z-1 inpolinomi ciclotomici, che spesso hanno coefficienti 1, 0 o −1, e quindi richiedono poche (se non nessuna) moltiplicazione, quindi può essere utilizzato per ottenere FFT con un numero minimo di moltiplicazioni ed è spesso usato per trovare algoritmi efficienti per piccoli fattori. In effetti Winograd dimostrò che la DFT può essere calcolata con solo O(n) moltiplicazioni; sfortunatamente questo si ottiene con un numero considerevolmente superiore di addizioni, uno scambio non più favorevole sui moderniprocessoridotati di chip dedicati per le moltiplicazioni in virgola mobile. In particolare, l'algoritmo di Winograd fa anche uso dell'algoritmo PFA e di quello di Rader per le FFT con dimensioni che siano numeri primi.
Un altro algoritmo FFT per numeri primi è dovuto a L. I. Bluestein ed è a volte chiamataalgoritmochirp-z: riesprime la DFT come unaconvoluzione, la cui dimensione può essere portata ad unapotenza di duee valutata dalla FFT di Cooley-Tukey.
In molte applicazioni i dati di input per la DFT sono reali puri, nel qual caso il risultato soddisfa la simmetria
e sono stati conseguentemente sviluppati algoritmi FFT per questa situazione. Un approccio consiste nel riutilizzare un algoritmo ordinario e rimuovere le parti di calcolo ridondanti, risparmiando approssimativamente un fattore due di occupazione di memoria e di tempo impiegato. In alternativa, è possibile esprimere latrasformata discreta di Fourierdi una n-pla con un numero pari di elementi tutti reali come la trasformata discreta complessa della metà della dimensione originaria le cui parti reali ed immaginarie sono gli elementi pari e dispari degli elementi originari, seguiti da O(n) operazioni di post-processo.
Si pensava una volta che le n-ple reali di cui calcolare la DFT potessero essere calcolate in modo più efficiente con la trasformata discreta di Hartley (dettaDHTdall'acronimo diDiscreteHartleyTransform), ma si scoprì in seguito che in genere possono essere individuati algoritmi FFT specializzati che richiedono meno operazioni del corrispondente algoritmo DHT. Anche l'algoritmo di Bruun fu inizialmente proposto per avvantaggiarsi dei numeri reali come input, ma non è mai diventato popolare.
Tutti gli algoritmi FFT presentati finora calcolano esattamente la DFT (in senso aritmetico, trascurando cioè gli errori dovuti ai calcoli in virgola mobile). Tuttavia sono stati anche proposti algoritmi FFT che calcolano la DFT approssimativamente, con un errore che può essere reso arbitrariamente piccolo al costo di un maggiore sforzo computazionale. Questi algoritmi scambiano l'errore di approssimazione a favore di una maggiore velocità od altre caratteristiche. Alcuni esempi sono l'algoritmo FFT di Edelman et al. (1999), la FFT di Guo e Barrus (1996) basata suiwaveleto quella di Shentov et al. (1995).
Anche gli algoritmi FFT "esatti" hanno degli errori quando viene utilizzata l'aritmetica a virgola mobile a precisione finita, ma questi errori sono in genere molto piccoli; la maggior parte degli algoritmi FFT hanno eccellenti proprietà numeriche. Il limite superiore dell'errore relativo per l'algoritmo di Cooley-Tukey èO(εlog⁡n),{\displaystyle O(\varepsilon \log n),}controO(εn3/2){\displaystyle O(\varepsilon n^{3/2})}per la formula originaria della DFT (Gentleman e Sande, 1966). Questi risultati, comunque, sono molto sensibili verso l'accuratezza deifattori twiddleusati nella FFT (che sono poi i valori dellefunzioni trigonometriche), e non è raro che implementazioni poco accurate della FFT abbiano precisione molto peggiori, ad esempio se utilizzano tabelle dei valori trigonometrici poco accurate. Alcuni algoritmi di FFT, come il Rader-Brenner, sono intrinsecamente meno stabili.
In aritmetica a virgola fissa, la precisione degli errori accumulati dagli algoritmi di FFT sono peggiori, e crescenti comeO(n){\displaystyle O({\sqrt {n}})}per l'algoritmo di Cooley-Tukey. Inoltre, raggiungere questa precisione richiede un'accurata attenzione e nello riscalare i fattori per minimizzare la perdita di precisione, e gli algoritmi di FFT in virgola fissa richiedono il riscalamento ad ogni stadio intermedio delle decomposizioni come nel Cooley-Tukey.
Per verificare la correttezza di un'implementazione di un algoritmo FFT, garanzie rigorose possono essere ottenute in tempoO(nlog⁡n){\displaystyle O(n\log n)}con una semplice procedura che controlla le proprietà di linearità, dellarisposta impulsivae della tempo-invarianza per dati in input casuali.