FFT

sigla dell'inglese Fast Fourier Transform (trasformata veloce di Fourier). Classe di algoritmi di largo impiego specialmente con gli elaboratori, che rende possibile il calcolo della trasformata discreta di Fourier (Discrete Fourier Transform, DFT) per una gamma di situazioni molto ampia. Dato che il ruolo della DFT in rapporto all'elaborazione dei segnali digitali è speculare a quello della trasformata ordinaria di Fourier dei segnali analogici, la FFT ha contribuito in modo essenziale alla progressiva affermazione dell'elaborazione dei segnali digitali in tempo reale. Algoritmi capaci di ridurre la complessità del calcolo della DFT, complessità che cresce con il quadrato dei termini (N) della sequenza che costituisce il segnale digitale (o digitalizzato), erano noti fin dall'inizio del Novecento; con queste tecniche il livello di complessità fu abbassato da N² a NlnN. Con la pubblicazione, nel 1965, di un metodo per il calcolo della DFT che, quando la lunghezza della sequenza N è un numero composto, cioè il prodotto di due o più interi, la riduce al calcolo delle due trasformate separate di ordine inferiore, si sono aperte nuove prospettive. A partire da tale risultato ci fu un fiorire di applicazioni della DFT all'elaborazione automatica dei segnali e lo sviluppo di numerosi algoritmi di calcolo che per la loro caratteristica di abbattere i tempi impegnati dell'elaboratore divennero noti come algoritmi per la trasformata veloce di Fourier, o semplicemente FFT. Le due forme più note di FFT sono: a) a decimazione nel tempo. Nello scomporre il calcolo della DFT si agisce sulla frequenza del segnale digitale, ossia si opera sulla sua rappresentazione nel tempo; b) a decimazione in frequenza. La scomposizione della sequenza in sottosequenze sempre più corte è fatta agendo sui coefficienti della DFT, ossia sulla rappresentazione del segnale in frequenza. La FFT trova applicazione naturale nell'analisi dei segnali, ma il suo impiego si è ormai esteso ad altri campi, nei sistemi lineari, in ottica, nella teoria della probabilità, nella fisica quantistica.