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.

Definizione

La successione di $N$ numeri complessi $x_0,x_1,\dots ,x_{N-1}$ è trasformata nella successione di $N$ numeri complessi $X_0,X_1,\dots ,X_{N-1}$ dalla trasformata discreta di Fourier secondo la formula:

$X_k=\sum _{n=0}^{N-1}{x}_n{e}^{-\frac{2\pi i}{N}kn},k=0,\dots ,N-1,$

dove $i$ è l'unità immaginaria e $e^{\frac{2\pi i}{N}}$ è una radice dell'unità primitiva N-esima. La trasformata è spesso rappresentata dal simbolo $ℱ$, usato come $𝐗=ℱ\left\{𝐱\right\}$ o $ℱ\left(𝐱\right)$ 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 $k/N$.

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):

$x_n=\frac{1}{N}\sum _{k=0}^{N-1}{X}_k{e}^{\frac{2\pi i}{N}kn},n=0,\dots ,N-1.$

Una descrizione semplice di queste equazioni è che i numeri complessi $X_k$ rappresentano l'ampiezza e la fase di diverse componenti sinusoidali del segnale in ingresso $x_n$. La DFT calcola gli $X_k$ dati gli $x_n$, mentre la IDFT calcola gli $x_n$ come somma delle componenti sinusoidali $(1/N)X_k{e}^{\frac{2\pi i}{N}kn}$ di frequenza $k/N$ 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 $X_k$ in forma polare, si può così ottenere l'ampiezza delle sinusoidi $A_k$ e la fase ${\varphi }_k$ da modulo e argomento di $X_k$, rispettivamente:

$A_k=|X_k|=\sqrt{\mathrm{Re}(X_k{)}^2+\mathrm{Im}(X_k{)}^2},{\phi }_k=\arg (X_k)=\mathrm{atan2}(\mathrm{Im}(X_k),\mathrm{Re}(X_k)).$

Si noti che i fattori di normalizzazione che moltiplicano DFT e IDFT (qui $1$ e $1/N$) 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 $1/N$. Un fattore di normalizzazione $1/\sqrt{N}$ 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 $N^2$, per gli algoritmi ottimizzati (denominati trasformata di Fourier veloce, o in inglese FFT (da Fast Fourier Transform) è proporzionale a $N{\log }_2(N)$, e quindi il vantaggio nell'utilizzarli è tanto maggiore quanto più grande è $N$.

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 $a$ e/o in frequenza di un fattore $b$. In tal caso viene detta DFT generalizzata o GDFT (generalized DFT), e condivide le stesse proprietà della DFT tradizionale:

$X_k=\sum _{n=0}^{N-1}{x}_n{e}^{-\frac{2\pi i}{N}(k+b)(n+a)},k=0,\dots ,N-1.$

Spesso si usa traslare di un fattore $1/2$, ottenendo ad esempio per $a=1/2$ un segnale che è antiperiodico nel dominio della frequenza, cioè $X_{k+N}=-X_k$.

Trasformata in più dimensioni

La trasformata discreta di Fourier di un vettore $x_{n_1,n_2,\dots ,n_d}$ funzione di $d$ variabili discrete $n_{\ell }=0,1,\dots ,N_{\ell }-1$, con $\ell \in \{1,2,\dots ,d\}$, è definita come:

$X_{k_1,k_2,\dots ,k_d}=\sum _{n_1=0}^{N_1-1}\left({\omega }_{N_1}^{k_1{n}_1}\sum _{n_2=0}^{N_2-1}({\omega }_{N_2}^{k_2{n}_2}\cdots \sum _{n_d=0}^{N_d-1}{\omega }_{N_d}^{k_d{n}_d}\cdot x_{n_1,n_2,\dots ,n_d})\right)$

dove ${\omega }_{N_{\ell }}=\exp (-2\pi i/N_{\ell })$. In modo più compatto, definendo $𝐧=(n_1,n_2,\dots ,n_d)$ e $𝐤=(k_1,k_2,\dots ,k_d)$ come vettori $d$-dimensionali con indice che va da 0 a $𝐍-1$, dove:

$𝐍-1=(N_1-1,N_2-1,\dots ,N_d-1)$

si ha:

$X_{𝐤}=\sum _{𝐧=0}^{𝐍-1}{e}^{-2\pi i𝐤\cdot (𝐧/𝐍)}{x}_{𝐧},$

dove la divisione $𝐧/𝐍$ è $𝐧/𝐍=(n_1/N_1,\dots ,n_d/N_d)$.

La trasformata inversa è, analogamente al caso unidimensionale:

$x_{𝐧}=\frac{1}{\prod _{\ell =1}^d{N}_{\ell }}\sum _{𝐤=0}^{𝐍-1}{e}^{2\pi i𝐧\cdot (𝐤/𝐍)}{X}_{𝐤}.$

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 $X_{𝐤}$.

Proprietà

La trasformata discreta di Fourier è una trasformazione lineare invertibile $ℱ:{ℂ}^N\to {ℂ}^N$ che gode delle proprietà esposte nel seguito.

Ortogonalità

I vettori $u_k={[e^{\frac{2\pi i}{N}kn}|n=0,1,\dots ,N-1]}^T$ formano una base ortogonale sull'insieme dei vettori complessi di dimensione $N$:

$u_k^T{u}_{k^{\prime }}^{*}=\sum _{n=0}^{N-1}\left(e^{\frac{2\pi i}{N}kn}\right)\left(e^{\frac{2\pi i}{N}(-k^{\prime })n}\right)=\sum _{n=0}^{N-1}{e}^{\frac{2\pi i}{N}(k-k^{\prime })n}=N{\delta }_{k{k}^{\prime }},$

dove ${\delta }_{k{k}^{\prime }}$ è il delta di Kronecker. Tale condizione consente di ricavare la formula per la IDFT dalla definizione di DFT.

Teoremi di Plancherel e Parseval

Template:Vedi anche Se $X_k$ e $Y_k$ sono le trasformate discrete di Fourier di $x_n$ e $y_n$ il teorema di Plancherel afferma che:

$\sum _{n=0}^{N-1}{x}_n{y}_n^{*}=\frac{1}{N}\sum _{k=0}^{N-1}{X}_k{Y}_k^{*},$

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

$\sum _{n=0}^{N-1}|x_n{|}^2=\frac{1}{N}\sum _{k=0}^{N-1}|X_k{|}^2.$

Periodicità

Se si valuta la definizione di DFT per tutti gli interi $k$ invece che per $k=0,\dots ,N-1$ la successione infinita che ne risulta è un'estensione periodica con periodo $N$ della DFT. La periodicità può essere mostrata come segue:

$X_{k+N}\stackrel{\mathrm{d}\mathrm{e}\mathrm{f}}{=}\sum _{n=0}^{N-1}{x}_n{e}^{-\frac{2\pi i}{N}(k+N)n}=\sum _{n=0}^{N-1}{x}_n{e}^{-\frac{2\pi i}{N}kn}\underset{1}{\underbrace{e^{-2\pi in}}}=\sum _{n=0}^{N-1}{x}_n{e}^{-\frac{2\pi i}{N}kn}=X_k.$

In modo analogo si estende periodicamente la trasformata discreta inversa.

Traslazione

Moltiplicando la successione $x_n$ per una fase lineare $e^{\frac{2\pi i}{N}nm}$, con $m$ intero, si ottiene la traslazione circolare della trasformata $X_k$. Analogamente, la traslazione circolare di $x_n$ corrisponde alla moltiplicazione di $X_k$ per una fase lineare. Esplicitamente, se

$ℱ(\{x_n\}{)}_k=X_k,$

allora:

$ℱ(\{x_n\cdot e^{\frac{2\pi i}{N}nm}\}{)}_k=X_{k-m},ℱ(\{x_{n-m}\}{)}_k=X_k\cdot e^{-\frac{2\pi i}{N}km}.$

Convoluzione circolare e correlazione incrociata

Template:Vedi anche 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 $N$ si ha:

${ℱ}^{-1}{\left\{𝐗\mathbf{\cdot }𝐘\right\}}_n=\sum _{l=0}^{N-1}{x}_l\cdot (y_N{)}_{n-l}\stackrel{\mathrm{d}\mathrm{e}\mathrm{f}}{=}(𝐱\mathbf{*}{𝐲}_{𝐍}{)}_n.$

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

$({𝐲}_{𝐍}{)}_n\stackrel{\mathrm{d}\mathrm{e}\mathrm{f}}{=}\sum _{p=-\mathrm{\infty }}^{\mathrm{\infty }}{y}_{(n-pN)}=y_{n(\mathrm{mod}N)}.$

In modo analogo, la correlazione incrociata di $𝐱$ e ${𝐲}_{𝐍}$ è data da:

${ℱ}^{-1}{\left\{{𝐗}^{\mathbf{*}}\mathbf{\cdot }𝐘\right\}}_n=\sum _{l=0}^{N-1}{x}_l^{*}\cdot (y_N{)}_{n+l}\stackrel{\mathrm{d}\mathrm{e}\mathrm{f}}{=}(𝐱\mathbf{\star }{𝐲}_{𝐍}{)}_n.$

La valutazione diretta di entrambe le somme richiede $O(N^2)$ operazioni per una sequenza in uscita lunga $N.$

Inoltre, si mostra che:

$ℱ{\left\{𝐱\mathbf{\cdot }𝐲\right\}}_k\stackrel{\mathrm{d}\mathrm{e}\mathrm{f}}{=}\sum _{n=0}^{N-1}{x}_n\cdot y_n\cdot e^{-\frac{2\pi i}{N}kn}=\frac{1}{N}(𝐗\mathbf{*}{𝐘}_{𝐍}{)}_k.$

Si tratta della convoluzione circolare di $𝐗$ e $𝐘$.

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

DFT unitaria

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

$𝐅=\left[\begin{array}{cccc}{\omega }_N^{0\cdot 0}& {\omega }_N^{0\cdot 1}& \dots & {\omega }_N^{0\cdot (N-1)}\\ {\omega }_N^{1\cdot 0}& {\omega }_N^{1\cdot 1}& \dots & {\omega }_N^{1\cdot (N-1)}\\ ⋮& ⋮& \ddots & ⋮\\ {\omega }_N^{(N-1)\cdot 0}& {\omega }_N^{(N-1)\cdot 1}& \dots & {\omega }_N^{(N-1)\cdot (N-1)}\end{array}\right]$

dove:

${\omega }_N=e^{-2\pi i/N}.$

La trasformata inversa è data dalla matrice inversa:

${𝐅}^{-1}=\frac{1}{N}{𝐅}^{*}.$

La DFT diventa una trasformazione unitaria utilizzando coefficienti di normalizzazione uguale a $1/\sqrt{N}$. La DFT unitaria è così definita dalla matrice unitaria:

$𝐔=𝐅/\sqrt{N},{𝐔}^{-1}={𝐔}^{*},|\det (𝐔)|=1.$

Il determinante è il prodotto degli autovalori, che sono sempre $\pm 1$ e $\pm i$.

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

$\sum _{m=0}^{N-1}{U}_{km}{U}_{mn}^{*}={\delta }_{kn}.$

Se inoltre $𝐗$ è definita come la DFT unitaria di $𝐱$ allora:

$X_k=\sum _{n=0}^{N-1}{U}_{kn}{x}_n$

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

$\sum _{n=0}^{N-1}{x}_n{y}_n^{*}=\sum _{k=0}^{N-1}{X}_k{Y}_k^{*}.$

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:

$\sum _{n=0}^{N-1}|x_n{|}^2=\sum _{k=0}^{N-1}|X_k{|}^2.$

Autovettori e autovalori

Template:Vedi anche Si consideri la trasformazione unitaria $𝐔$ definita in precedenza per la DFT di lunghezza $N$:

${𝐔}_{m,n}=\frac{1}{\sqrt{N}}{\omega }_N^{(m-1)(n-1)}=\frac{1}{\sqrt{N}}{e}^{-\frac{2\pi i}{N}(m-1)(n-1)}.$

La matrice associata soddisfa l'equazione:

${𝐔}^4=𝐈,$

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

${\lambda }^4=1.$

Quindi, gli autovalori di $𝐔$ sono le radici quarte dell'unità: $\lambda$ è +1, −1, $i$, o $-i.$ Dal momento che vi sono quattro autovalori distinti per una matrice $N\times N$, essi possiedono una certa molteplicità algebrica. Nella seguente tabella si mostra la molteplicità degli autovalori $\lambda$ della matrice $𝐔$ che rappresenta la DFT unitaria in funzione della lunghezza $N$ 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 $𝐔$ è:

$\det (\lambda I-𝐔)=(\lambda -1{)}^{\lfloor \frac{N+4}{4}\rfloor }(\lambda +1{)}^{\lfloor \frac{N+2}{4}\rfloor }(\lambda +i{)}^{\lfloor \frac{N+1}{4}\rfloor }(\lambda -i{)}^{\lfloor \frac{N-1}{4}\rfloor }.$

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

In alto: funzione $x(t)$ e sua ripetizione periodica. In basso: trasformata $X(\omega )$ di $x(t)$ 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 $x(t)$ dotata di trasformata di Fourier $X(\omega )$, e si costruiscono le ripetizioni periodiche:

$x_p(t)=\sum _{i=-\mathrm{\infty }}^{+\mathrm{\infty }}x(t-i{T}_p),X_p(\omega )=\sum _{i=-\mathrm{\infty }}^{+\mathrm{\infty }}X(\omega -i{\omega }_p),$

con periodi $T_p$ e ${\omega }_p$ legati dalla relazione $T_p{\omega }_p=2\pi N$. Indicando inoltre:

$\mathrm{\Delta }t=\frac{T_p}{N}=\frac{2\pi }{{\omega }_p},\mathrm{\Delta }\omega =\frac{{\omega }_p}{N}=\frac{2\pi }{T_p},$

che soddisfano la relazione $\mathrm{\Delta }t\cdot \mathrm{\Delta }\omega =\frac{2\pi }{N}$, si definiscono le due $n$-ple di numeri:

$\mathrm{\Delta }t\cdot x_p(n\mathrm{\Delta }t),n=0,1,\dots ,N-1,X_p(q\mathrm{\Delta }\omega ),q=0,1,\dots ,N-1.$

Valgono allora le seguenti uguaglianze:

$\mathrm{\Delta }t\cdot x_p(n\mathrm{\Delta }t)={ℱ}_d^{-1}(X_p(q\mathrm{\Delta }\omega )),X_p(q\mathrm{\Delta }\omega )={ℱ}_d(\mathrm{\Delta }t\cdot x_p(n\mathrm{\Delta }t)).$

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

Bibliografia

• Template:Cita libro
• Template:Cita libro
• Template:Cita libro
• Template:Cita libro esp. section 30.2: The DFT and FFT, pp. 830–838.
• Template:Cita pubblicazione
• Template:Cita pubblicazione
• Template:Cita pubblicazione (Note that this paper has an apparent typo in its table of the eigenvalue multiplicities: the +i/−i columns are interchanged. The correct table can be found in McClellan and Parks, 1972, and is easily confirmed numerically.)
• Template:Cita pubblicazione
• Template:Cita pubblicazione
• Template:Cita pubblicazione
• Template:Cita pubblicazione
• Template:Cita pubblicazione
• Template:Cita pubblicazione
• Template:Cita pubblicazione
• Template:Cita pubblicazione
• Template:Cita pubblicazione

Voci correlate

• Analisi armonica
• Analisi di Fourier
• Matrice di Fourier
• Trasformata di Fourier
• Trasformata di Fourier a tempo discreto
• Trasformata di Fourier veloce
• Trasformata zeta

Collegamenti esterni

• Template:Collegamenti esterni
• Template:FOLDOC
• Template:Cita web
• Template:Cita web
• Template:Cita web
• Template:Cita web
• Template:Cita web
• Template:Cita web