Trasformata discreta di Fourier

In matematica, in particolare nell'analisi di Fourier, la trasformata discreta di Fourier, anche detta DFT (acronimo del termine inglese Discrete Fourier Transform), è un particolare tipo di trasformata di Fourier. Si tratta anche di un caso particolare della trasformata zeta.

Si tratta di una trasformata che converte una collezione finita di campioni equispaziati di una funzione in una collezione di coefficienti di una combinazione lineare di sinusoidi complesse, ordinate al crescere della frequenza. Analogamente alla trasformata di Fourier, si tratta di un modo per rappresentare una funzione (la cui variabile è spesso il tempo) nel dominio delle frequenze. Le frequenze delle sinusoidi della combinazione lineare (periodica) prodotta dalla trasformata sono multipli interi di una frequenza fondamentale, il cui periodo è la lunghezza dell'intero intervallo di campionamento, la durata del segnale.

Si differenzia dalla trasformata di Fourier a tempo discreto per il fatto che la funzione in ingresso e la funzione prodotta sono successioni finite, e può essere quindi considerata come una trasformata per l'analisi di Fourier di funzioni su un dominio limitato e discreto.

Diversamente dalla trasformata continua di Fourier, pertanto, la DFT richiede in ingresso una funzione discreta i cui valori sono in generale complessi e non nulli, e hanno una durata limitata. Questo rende la DFT ideale per l'elaborazione di informazioni su un elaboratore elettronico. In particolare la trasformata discreta di Fourier è ampiamente utilizzata nel campo dell'elaborazione numerica dei segnali e nei campi correlati per analizzare le frequenze contenute in un segnale, per risolvere equazioni differenziali alle derivate parziali e per compiere altre operazioni, come la convoluzione o la moltiplicazione di numeri interi molto grandi. Alla base di questi utilizzi c'è la possibilità di calcolare in modo efficiente la DFT usando gli algoritmi per trasformata di Fourier veloce.

La successione di numeri complessi è trasformata nella successione di numeri complessi dalla trasformata discreta di Fourier secondo la formula:[1]

dove è l'unità immaginaria e è una radice dell'unità primitiva N-esima. La trasformata è spesso rappresentata dal simbolo , usato come o o .

La trasformata discreta di Fourier descrive completamente la trasformata di Fourier a tempo discreto (DTFT) di una successione periodica con periodo N, che possiede uno spettro di frequenze discreto. Inoltre, fornisce campioni equidistanti di lunghezza finita della DTFT. Si tratta della correlazione incrociata della successione in ingresso e la sinusoide complessa di frequenza .

Si tratta inoltre dell'analogo discreto della formula per i coefficienti della serie di Fourier, che è inversa della trasformata di Fourier discreta (abbreviata talvolta in IDFT, da Inverse Discrete Fourier Transform):

Una descrizione semplice di queste equazioni è che i numeri complessi rappresentano l'ampiezza e la fase di diverse componenti sinusoidali del segnale in ingresso . La DFT calcola gli dati gli , mentre la IDFT calcola gli come somma delle componenti sinusoidali di frequenza cicli per campione. Scrivendo le equazioni in questa forma, si utilizza la formula di Eulero per esprimere le sinusoidi in termini di esponenziali complessi, che sono più semplici da manipolare. Esprimendo gli in forma polare, si può così ottenere l'ampiezza delle sinusoidi e la fase da modulo e argomento di , rispettivamente:

Si noti che i fattori di normalizzazione che moltiplicano DFT e IDFT (qui e ) e i segni degli esponenti sono delle convenzioni e possono essere differenti in alcuni testi. Gli unici requisiti di queste convenzioni sono che DFT e IDFT devono avere esponenti di segno opposto e che il prodotto dei fattori deve essere . Un fattore di normalizzazione sia per DFT che per IDFT rende le trasformate unitarie, il che ha alcuni vantaggi nella trattazione teorica, tuttavia è spesso più pratico nelle operazioni numeriche effettuare le normalizzazioni un'unica volta come nelle espressioni qui esposte.

È da notare che la trasformata discreta di Fourier è direttamente implementabile su un calcolatore, in quanto richiede un numero finito di operazioni, al contrario della serie o della trasformata di Fourier che richiedono il calcolo di integrali o di somme di serie. Tuttavia, il calcolo della DFT non viene comunque mai implementato secondo la definizione qui data, ma si preferisce utilizzare algoritmi ottimizzati che richiedono uno sforzo computazionale minore. Il tempo di calcolo necessario per la DFT con la definizione qui data è direttamente proporzionale ad , per gli algoritmi ottimizzati (denominati trasformata di Fourier veloce, o in inglese FFT (da Fast Fourier Transform) è proporzionale a , e quindi il vantaggio nell'utilizzarli è tanto maggiore quanto più grande è .

La DFT può anche essere espressa in forma matriciale attraverso la cosiddetta matrice di Fourier. Inoltre, può essere generalizzata consentendo traslazioni nel tempo di un fattore e/o in frequenza di un fattore . In tal caso viene detta DFT generalizzata o GDFT (generalized DFT), e condivide le stesse proprietà della DFT tradizionale:

Spesso si usa traslare di un fattore , ottenendo ad esempio per un segnale che è antiperiodico nel dominio della frequenza, cioè .

Trasformata in più dimensioni

[modifica | modifica wikitesto]

La trasformata discreta di Fourier di un vettore funzione di variabili discrete , con , è definita come:

dove . In modo più compatto, definendo e come vettori -dimensionali con indice che va da 0 a , dove:

si ha:

dove la divisione è .

La trasformata inversa è, analogamente al caso unidimensionale:

La trasformata discreta di Fourier in più dimensioni esprime l'ingresso come una combinazione lineare di onde piane, o sinusoidi multidimensionali, la cui direzione di oscillazione nello spazio è e l'ampiezza .

La trasformata discreta di Fourier è una trasformazione lineare invertibile che gode delle proprietà esposte nel seguito.

Ortogonalità

[modifica | modifica wikitesto]

I vettori formano una base ortogonale sull'insieme dei vettori complessi di dimensione :

dove è il delta di Kronecker. Tale condizione consente di ricavare la formula per la IDFT dalla definizione di DFT.

Teoremi di Plancherel e Parseval

[modifica | modifica wikitesto]
Lo stesso argomento in dettaglio: Teorema di Plancherel e Teorema di Parseval.

Se e sono le trasformate discrete di Fourier di e il teorema di Plancherel afferma che:

dove l'asterisco denota la coniugazione complessa. Il teorema di Parseval è un caso particolare del teorema di Plancherel:

Se si valuta la definizione di DFT per tutti gli interi invece che per la successione infinita che ne risulta è un'estensione periodica con periodo della DFT. La periodicità può essere mostrata come segue:

In modo analogo si estende periodicamente la trasformata discreta inversa.

Moltiplicando la successione per una fase lineare , con intero, si ottiene la traslazione circolare della trasformata . Analogamente, la traslazione circolare di corrisponde alla moltiplicazione di per una fase lineare. Esplicitamente, se

allora:

Convoluzione circolare e correlazione incrociata

[modifica | modifica wikitesto]
Lo stesso argomento in dettaglio: Convoluzione e Correlazione incrociata.

Il teorema di convoluzione per la trasformata di Fourier a tempo discreto mostra come la convoluzione di due successioni infinite possa essere vista come la trasformazione inversa del prodotto delle singole trasformate. Se le successioni hanno lunghezza finita si ha:

Si tratta della convoluzione della successione con una successione estesa tramite sommazione periodica:

In modo analogo, la correlazione incrociata di e è data da:

La valutazione diretta di entrambe le somme richiede operazioni per una sequenza in uscita lunga

Inoltre, si mostra che:

Si tratta della convoluzione circolare di e .

Inoltre, anche il viceversa è vero:[2] una trasformata che cambia convoluzione in prodotto ordinario è la trasformata di Fourier (con permutazione dei coefficienti).

La DFT può essere espressa come una matrice di Vandermonde:

dove:

La trasformata inversa è data dalla matrice inversa:

La DFT diventa una trasformazione unitaria utilizzando coefficienti di normalizzazione uguale a . La DFT unitaria è così definita dalla matrice unitaria:

Il determinante è il prodotto degli autovalori, che sono sempre e .

L'ortogonalità della DFT, menzionata in precedenza, può essere quindi anche espressa attraverso la condizione di ortonormalità:

Se inoltre è definita come la DFT unitaria di allora:

ed il teorema di Plancherel può essere quindi anche espresso come:

Se si visualizza la DFT come una trasformazione di coordinate che si limita a determinare le componenti di un vettore in un nuovo sistema di coordinate, la precedente relazione mostra come il prodotto scalare di due vettori si conserva sotto una DFT unitaria. Nel caso in cui ciò implica che la lunghezza di un vettore non cambia, in accordo con il teorema di Parseval:

Autovettori e autovalori

[modifica | modifica wikitesto]
Lo stesso argomento in dettaglio: Autovettore e autovalore.

Si consideri la trasformazione unitaria definita in precedenza per la DFT di lunghezza :

La matrice associata soddisfa l'equazione:

che può essere mostrata considerando che facendo agire quattro volte si ottiene il dato iniziale. Da questo segue che gli autovalori soddisfano l'equazione:

Quindi, gli autovalori di sono le radici quarte dell'unità: è +1, −1, , o Dal momento che vi sono quattro autovalori distinti per una matrice , essi possiedono una certa molteplicità algebrica. Nella seguente tabella si mostra la molteplicità degli autovalori della matrice che rappresenta la DFT unitaria in funzione della lunghezza della trasformata:

dimensione N λ = +1 λ = −1 λ = -i λ = +i
4m m + 1 m m m − 1
4m + 1 m + 1 m m m
4m + 2 m + 1 m + 1 m m
4m + 3 m + 1 m + 1 m + 1 m

In modo equivalente, il polinomio caratteristico di è:

Non si conosce nessuna formula analitica semplice per calcolare gli autovettori, che non sono univoci in quanto ogni combinazione lineare di autovettori associati allo stesso autovalore è un autovettore solo per tale autovalore.

Relazione con la trasformata continua

[modifica | modifica wikitesto]
Lo stesso argomento in dettaglio: Trasformata di Fourier.
In alto: funzione e sua ripetizione periodica. In basso: trasformata di e sua ripetizione periodica nel dominio delle frequenze. Si nota l'assenza di aliasing in entrambi i casi.

Per mostrare la relazione con la versione continua della trasformata di Fourier si considera una funzione dotata di trasformata di Fourier , e si costruiscono le ripetizioni periodiche:

con periodi e legati dalla relazione . Indicando inoltre:

che soddisfano la relazione , si definiscono le due -ple di numeri:

Valgono allora le seguenti uguaglianze:

Se non vi è sovrapposizione né nel dominio dei tempi né in quello delle frequenze, è possibile ricavare la trasformata continua da quella discreta.

  1. ^ Eric Weisstein, MathWorld - Discrete Fourier Transform, su mathworld.wolfram.com, 2012.
  2. ^ Emmanuel Amiot, Music through Fourier Space, Zürich, Springer, 2016, p. 8, ISBN 978-3-319-45581-5.

Voci correlate

[modifica | modifica wikitesto]

Altri progetti

[modifica | modifica wikitesto]

Collegamenti esterni

[modifica | modifica wikitesto]
  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica