La trasformata di Fourier ricorre spesso in fisica e in matematica, il che significa che ha anche molti usi quotidiani.
In breve, la trasformata di Fourier prende un segnale in input, spesso nel dominio del tempo o dello spazio, e lo trasforma nel dominio delle frequenze.
Più concretamente, se il segnale in input è un insieme disordinato (cioè una sovrapposizione) di frequenze diverse, la trasformata separa le singole frequenze e ne mostra le rispettive intensità.
Questo rende la trasformata uno strumento principale nell'elaborazione dei segnali (per esempio filtraggio, compressione, ecc.) e in molte applicazioni di data science.
Perciò è forse più usata di quanto si immagini a prima vista, e questo la rende anche un esempio perfetto di come i numeri immaginari si rivelino indispensabili, visto che l'output della trasformata di Fourier è in generale un numero complesso.
Sebbene la trasformata di Fourier abbia una formulazione integrale, noi siamo digitali, quindi ci interessa la versione discreta.
La derivazione della trasformata va oltre lo scopo di questo esercizio, ma la trasformata discreta diretta, verso il dominio delle frequenze, assume la forma seguente:
Xₖ = Σ xₙ * ℯ^(-2iπk * n/N)
Qui la somma è su n, e N è il numero di campioni, k è la frequenza, i l'unità immaginaria e xₙ un singolo campione.
Per quanto estremamente utile, la trasformata di Fourier, se implementata in modo ingenuo, è un po' lenta (O(n²)).
La trasformata di Fourier veloce (FFT) è un algoritmo che la rende molto più rapida.
Di solito si usa una strategia di divide et impera che sfrutta alcune simmetrie della formulazione e porta a una complessità asintotica O(Nlog(N)).
Questa accelerazione migliora molto la praticità della trasformata e la gamma di applicazioni per cui è adatta.
