# Trasformata di Fourier veloce

In matematica, la trasformata di Fourier veloce, spesso abbreviata con FFT (dall'inglese Fast Fourier Transform), è un algoritmo ottimizzato per calcolare la trasformata discreta di Fourier (DFT) o la sua inversa.
La FFT è utilizzata in una grande varietà di applicazioni, dall'elaborazione di segnali digitali alla soluzione di equazioni differenziali alle derivate parziali agli algoritmi per moltiplicare numeri interi di grandi dimensioni grazie al basso costo computazionale.

## Definizione

Sia $x_{0},\dots ,x_{N-1}$ una $N$-pla di numeri complessi. La DFT è definita dalla 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.$
Calcolare direttamente questa somma richiede una quantità di operazioni aritmetiche $O(N^{2})$. Un algoritmo FFT ottiene lo stesso risultato con un numero di operazioni $O(N\log(N))$. In generale questi algoritmi si basano sulla fattorizzazione di $N$, ma esistono algoritmi FFT per qualunque $N$, anche per numeri primi.
Poiché l'antitrasformata discreta di Fourier è uguale alla DFT, ma con esponente di segno opposto e $1/N$ a fattore, qualsiasi algoritmo FFT può essere facilmente invertito.

## Algoritmo di Cooley-Tukey

L'algoritmo FFT più diffuso è l'algoritmo di Cooley-Tukey. Questo algoritmo si basa sul principio di divide et impera, e spezza ricorsivamente una DFT di qualsiasi dimensione $N$, con $N$ numero composto tale che $N=N_{1}N_{2}$ in DFT più piccole di dimensioni $N_{1}$ e $N_{2}$, insieme a $O(n)$ moltiplicazioni per l'unità immaginaria, detti fattori twiddle.
Questo metodo (e in generale l'idea di una trasformata di Fourier veloce) fu reso popolare da una pubblicazione di James Cooley e John Wilder Tukey nel 1965, ma in seguito si scoprì che i due autori avevano indipendentemente reinventato un algoritmo noto a Carl Friedrich Gauss nel 1805 (e successivamente riscoperto in molte altre forme limitate).
L'uso più conosciuto dell'algoritmo di Cooley-Tukey è di dividere e trasformare in due pezzi di $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 casi radice 2 e radice 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 in C++ della FFT basata sull'algoritmo di Cooley-Tukey è la seguente:

## Altri algoritmi per calcolare la FFT

Ci sono altri algoritmi per la FFT oltre al Cooley-Tukey. Per N=N$_1$N$_2$ con N$_1$ e N$_2$ numeri coprimi può essere utilizzato l'algoritmo di Good-Thomas PFA (Prime-factor FFT Algorithm), basato sul teorema 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 del polinomio z$^n$-1 in polinomi a coefficienti reali nella forma z$^m$-1 e z$^{2m}$+az$^m$+1.
Un altro punto di vista polinomiale è sfruttato dall'algoritmo FFT di Schmuel Winograd, che fattorizza z$^n$-1 in polinomi 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 moderni processori dotati 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 chiamata algoritmo chirp-z: riesprime la DFT come una convoluzione, la cui dimensione può essere portata ad una potenza di due e valutata dalla FFT di Cooley-Tukey.

## Algoritmi FFT specializzati per dati reali e/o simmetrici

In molte applicazioni i dati di input per la DFT sono reali puri, nel qual caso il risultato soddisfa la simmetria
    $f_{-j}=f_{j}^{*},$
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 la trasformata discreta di Fourier di 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 (detta DHT dall'acronimo di Discrete Hartley Transform), 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.

## Accuratezza e approssimazioni

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 sui wavelet o 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(\varepsilon \log n),$ contro $O(\varepsilon n^{3/2})$ per la formula originaria della DFT (Gentleman e Sande, 1966). Questi risultati, comunque, sono molto sensibili verso l'accuratezza dei fattori twiddle usati nella FFT (che sono poi i valori delle funzioni 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 come $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 tempo $O(n\log n)$ con una semplice procedura che controlla le proprietà di linearità, della risposta impulsiva e della tempo-invarianza per dati in input casuali.