Trasformata di Fourier discreta

Da Wikipedia, l'enciclopedia libera.

La trasformata di Fourier discreta (spesso abbreviata a DFT, Discrete Fourier Transform) stabilisce una relazione biunivoca tra due n-ple di numeri (in generale complessi). Data una successione:

x_n con n = 0, 1, ..., N-1

si definisce sua trasformata di Fourier discreta la successione di

X_q con q = 0, 1, ..., N-1

espressa da:

$X_q = \mathcal{F}_d(x_n) = \sum_{k=0}^{N-1} x_k e^{-j\frac{2\pi}{N}kq}$ per q = 0, 1, ..., N-1

La formula di antitrasformazione (IDFT Inverse Discrete Fourier Transform) è:

$x_n = \mathcal{F}_d^{-1}(x_n) = \frac{1}{N}\sum_{k=0}^{N-1} x_k e^{+j\frac{2\pi}{N}kq}$ per n = 0, 1, ..., N-1

Dimostrazione:

$\sum_{k=0}^{N-1} x_k e^{-j\frac{2\pi}{N}kq}=\sum_{q=0}^{N-1}\sum_{k=0}^{N-1}x_ke^{-j\frac{2\pi}{N}kq}e^{j\frac{2\pi}{N}qn}=\sum_{k=0}^{N-1}x_k\sum_{q=0}^{N-1}e^{j\frac{2\pi}{N}q(n-k)}$

Ma si ha che:

$\sum_{q=0}^{N-1}e^{-j\frac{2\pi}{N}(n-k)} = \left\{\begin{matrix}N, & \mbox{se } k=n\\ \frac{1-e^{j2\pi(n-k)}}{1-e^{j\frac{2\pi}{N}(n-k)}}=0, & \mbox{se } k\not=n \end{matrix}\right.$

E quindi, sostituendo:

$\sum_{q=0}^{N-1}X_qe^{j\frac{2\pi}{N}qn}=Nx_n$

È da notare che la trasformata di Fourier discreta è 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. In effetti però il calcolo della DFT non viene mai implementata 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², per gli algoritmi ottimizzati (denominati trasformata di Fourier veloce, o in inglese FFT da Fast Fourier Transform) è proporzionale a N ln(N), e quindi il vantaggio nell'utilizzarli è tanto maggiore quanto più grande è N.

[modifica] Rapporto tra DFT e trasformata di Fourier continua

Segnale x(t) e con ripetizione nel tempo, sua trasformata X(ω) con sua ripetizione nelle frequenze e assenza di aliasing in entrambi i casi

Esiste un rapporto tra la trasformata di Fourier discreta e quella continua, che in particolare consente di ricavare l'una dall'altra. Riferiamoci ad un segnale x(t) continuo nel tempo dotato di trasformata di Fourier. Costruiamo le ripetizioni dei segnali: