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},\qquad 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 ${\mathcal {F}}$, usato come $\mathbf {X} ={\mathcal {F}}\left\{\mathbf {x} \right\}$ o ${\mathcal {F}}\left(\mathbf {x} \right)$ o ${\mathcal {F}}\mathbf {x}$.

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},\qquad 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 $\phi _{k}$ da modulo e argomento di $X_{k}$, rispettivamente:

$A_{k}=|X_{k}|={\sqrt {\operatorname {Re} (X_{k})^{2}+\operatorname {Im} (X_{k})^{2}}},\qquad \varphi _{k}=\arg(X_{k})=\operatorname {atan2} {\big (}\operatorname {Im} (X_{k}),\operatorname {Re} (X_{k}){\big )}.$

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)},\qquad 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}\left(\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)\right)$

dove $\omega _{N_{\ell }}=\exp(-2\pi i/N_{\ell })$. In modo più compatto, definendo $\mathbf {n} =(n_{1},n_{2},\dots ,n_{d})$ e $\mathbf {k} =(k_{1},k_{2},\dots ,k_{d})$ come vettori $d$-dimensionali con indice che va da 0 a $\mathbf {N} -1$, dove:

$\mathbf {N} -1=(N_{1}-1,N_{2}-1,\dots ,N_{d}-1)$

si ha:

$X_{\mathbf {k} }=\sum _{\mathbf {n} =0}^{\mathbf {N} -1}e^{-2\pi i\mathbf {k} \cdot (\mathbf {n} /\mathbf {N} )}x_{\mathbf {n} },$

dove la divisione $\mathbf {n} /\mathbf {N}$ è $\mathbf {n} /\mathbf {N} =(n_{1}/N_{1},\dots ,n_{d}/N_{d})$.

La trasformata inversa è, analogamente al caso unidimensionale:

$x_{\mathbf {n} }={\frac {1}{\prod _{\ell =1}^{d}N_{\ell }}}\sum _{\mathbf {k} =0}^{\mathbf {N} -1}e^{2\pi i\mathbf {n} \cdot (\mathbf {k} /\mathbf {N} )}X_{\mathbf {k} }.$

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 è $\mathbf {k} /\mathbf {N}$ e l'ampiezza $X_{\mathbf {k} }$.

Proprietà

La trasformata discreta di Fourier è una trasformazione lineare invertibile ${\mathcal {F}}\colon \mathbb {C} ^{N}\to \mathbb {C} ^{N}$ che gode delle proprietà esposte nel seguito.

Ortogonalità

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

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

dove $~\delta _{kk'}$ è il delta di Kronecker. Tale condizione consente di ricavare la formula per la IDFT dalla definizione di DFT.

Teoremi di Plancherel e Parseval

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 {def} }{=}}\ \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}\underbrace {e^{-2\pi in}} _{1}=\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

${\mathcal {F}}(\{x_{n}\})_{k}=X_{k},$

allora:

${\mathcal {F}}(\{x_{n}\cdot e^{{\frac {2\pi i}{N}}nm}\})_{k}=X_{k-m},\qquad {\mathcal {F}}(\{x_{n-m}\})_{k}=X_{k}\cdot e^{-{\frac {2\pi i}{N}}km}.$

Convoluzione circolare 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 $N$ si ha:

${\mathcal {F}}^{-1}\left\{\mathbf {X\cdot Y} \right\}_{n}\ =\sum _{l=0}^{N-1}x_{l}\cdot (y_{N})_{n-l}\ \ {\stackrel {\mathrm {def} }{=}}\ \ (\mathbf {x*y_{N}} )_{n}.$

Si tratta della convoluzione della successione $\mathbf {x}$ con una successione $\mathbf {y}$ estesa tramite sommazione periodica:

$(\mathbf {y_{N}} )_{n}\ {\stackrel {\mathrm {def} }{=}}\ \sum _{p=-\infty }^{\infty }y_{(n-pN)}=y_{n{\pmod {N}}}.$

In modo analogo, la correlazione incrociata di $\mathbf {x}$ e $\mathbf {y_{N}}$ è data da:

${\mathcal {F}}^{-1}\left\{\mathbf {X^{*}\cdot Y} \right\}_{n}=\sum _{l=0}^{N-1}x_{l}^{*}\cdot (y_{N})_{n+l}\ \ {\stackrel {\mathrm {def} }{=}}\ \ (\mathbf {x\star y_{N}} )_{n}.$

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

Inoltre, si mostra che:

${\mathcal {F}}\left\{\mathbf {x\cdot y} \right\}_{k}\ {\stackrel {\mathrm {def} }{=}}\sum _{n=0}^{N-1}x_{n}\cdot y_{n}\cdot e^{-{\frac {2\pi i}{N}}kn}={\frac {1}{N}}(\mathbf {X*Y_{N}} )_{k}.$

Si tratta della convoluzione circolare di $\mathbf {X}$ e $\mathbf {Y}$.

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:

$\mathbf {F} ={\begin{bmatrix}\omega _{N}^{0\cdot 0}&\omega _{N}^{0\cdot 1}&\ldots &\omega _{N}^{0\cdot (N-1)}\\\omega _{N}^{1\cdot 0}&\omega _{N}^{1\cdot 1}&\ldots &\omega _{N}^{1\cdot (N-1)}\\\vdots &\vdots &\ddots &\vdots \\\omega _{N}^{(N-1)\cdot 0}&\omega _{N}^{(N-1)\cdot 1}&\ldots &\omega _{N}^{(N-1)\cdot (N-1)}\\\end{bmatrix}}$

dove:

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

La trasformata inversa è data dalla matrice inversa:

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

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

$\mathbf {U} =\mathbf {F} /{\sqrt {N}},\qquad \mathbf {U} ^{-1}=\mathbf {U} ^{*},\qquad |\det(\mathbf {U} )|=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 $\mathbf {X}$ è definita come la DFT unitaria di $\mathbf {x}$ 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 $\mathbf {x} =\mathbf {y}$ 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

Si consideri la trasformazione unitaria $\mathbf {U}$ definita in precedenza per la DFT di lunghezza $N$:

$\mathbf {U} _{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:

$\mathbf {U} ^{4}=\mathbf {I} ,$

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

$\lambda ^{4}=1.$

Quindi, gli autovalori di $\mathbf {U}$ 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 $\mathbf {U}$ 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 $\mathbf {U}$ è:

$\det(\lambda I-\mathbf {U} )=(\lambda -1)^{\left\lfloor {\tfrac {N+4}{4}}\right\rfloor }(\lambda +1)^{\left\lfloor {\tfrac {N+2}{4}}\right\rfloor }(\lambda +i)^{\left\lfloor {\tfrac {N+1}{4}}\right\rfloor }(\lambda -i)^{\left\lfloor {\tfrac {N-1}{4}}\right\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=-\infty }^{+\infty }x\left(t-iT_{p}\right),\qquad X_{p}(\omega )=\sum _{i=-\infty }^{+\infty }X\left(\omega -i\omega _{p}\right),$

con periodi $T_{p}$ e $\omega _{p}$ legati dalla relazione $T_{p}\omega _{p}=2\pi N$. Indicando inoltre:

$\Delta t={\frac {T_{p}}{N}}={\frac {2\pi }{\omega _{p}}},\qquad \Delta \omega ={\frac {\omega _{p}}{N}}={\frac {2\pi }{T_{p}}},$

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

$\Delta t\cdot x_{p}(n\Delta t),\quad n=0,1,\dots ,N-1,\qquad X_{p}(q\Delta \omega ),\quad q=0,1,\dots ,N-1.$

Valgono allora le seguenti uguaglianze:

$\Delta t\cdot x_{p}(n\Delta t)={\mathcal {F}}_{d}^{-1}(X_{p}(q\Delta \omega )),\qquad X_{p}(q\Delta \omega )={\mathcal {F}}_{d}(\Delta t\cdot x_{p}(n\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

• (EN) E. Oran Brigham, The fast Fourier transform and its applications, Englewood Cliffs, N.J., Prentice Hall, 1988, ISBN 0-13-307505-2.
• (EN) Oppenheim, Alan V.; Schafer, R. W.; and Buck, J. R., Discrete-time signal processing, Upper Saddle River, N.J., Prentice Hall, 1999, ISBN 0-13-754920-2.
• (EN) Steven W. Smith, Chapter 8: The Discrete Fourier Transform, in The Scientist and Engineer's Guide to Digital Signal Processing, Second, San Diego, Calif., California Technical Publishing, 1999, ISBN 0-9660176-3-3.
• (EN) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Chapter 30: Polynomials and the FFT, in Introduction to Algorithms, Second, MIT Press and McGraw-Hill, 2001, pp. 822–848, ISBN 0-262-03293-7. esp. section 30.2: The DFT and FFT, pp. 830–838.
• (EN) P. Duhamel, B. Piron, and J. M. Etcheto, On computing the inverse DFT, in IEEE Trans. Acoust., Speech and Sig. Processing, vol. 36, n. 2, 1988, pp. 285–286, DOI:10.1109/29.1519.
• (EN) J. H. McClellan and T. W. Parks, Eigenvalues and eigenvectors of the discrete Fourier transformation, in IEEE Trans. Audio Electroacoust., vol. 20, n. 1, 1972, pp. 66–74, DOI:10.1109/TAU.1972.1162342.
• (EN) Bradley W. Dickinson and Kenneth Steiglitz, Eigenvectors and functions of the discrete Fourier transform, in IEEE Trans. Acoust., Speech and Sig. Processing, vol. 30, n. 1, 1982, pp. 25–31, DOI:10.1109/TASSP.1982.1163843. (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.)
• (EN) F. A. Grünbaum, The eigenvectors of the discrete Fourier transform, in J. Math. Anal. Appl., vol. 88, n. 2, 1982, pp. 355–363, DOI:10.1016/0022-247X(82)90199-8.
• (EN) Natig M. Atakishiyev and Kurt Bernardo Wolf, Fractional Fourier-Kravchuk transform, in J. Opt. Soc. Am. A, vol. 14, n. 7, 1997, pp. 1467–1477, DOI:10.1364/JOSAA.14.001467.
• (EN) C. Candan, M. A. Kutay and H. M.Ozaktas, The discrete fractional Fourier transform, in IEEE Trans. on Signal Processing, vol. 48, n. 5, 2000, pp. 1329–1337, DOI:10.1109/78.839980.
• (EN) Magdy Tawfik Hanna, Nabila Philip Attalla Seif, and Waleed Abd El Maguid Ahmed, Hermite-Gaussian-like eigenvectors of the discrete Fourier transform matrix based on the singular-value decomposition of its orthogonal projection matrices, in IEEE Trans. Circ. Syst. I, vol. 51, n. 11, 2004, pp. 2245–2254, DOI:10.1109/TCSI.2004.836850.
• (EN) Shamgar Gurevich and Ronny Hadani, On the diagonalization of the discrete Fourier transform, in Applied and Computational Harmonic Analysis, vol. 27, n. 1, 2009, pp. 87–99, DOI:10.1016/j.acha.2008.11.003, arXiv:0808.3281, preprint at.
• (EN) Shamgar Gurevich, Ronny Hadani, and Nir Sochen, The finite harmonic oscillator and its applications to sequences, communication and radar, in IEEE Transactions on Information Theory, vol. 54, n. 9, 2008, pp. 4239–4253, DOI:10.1109/TIT.2008.926440, arXiv:0808.1495, preprint at.
• (EN) Juan G. Vargas-Rubio and Balu Santhanam, On the multiangle centered discrete fractional Fourier transform, in IEEE Sig. Proc. Lett., vol. 12, n. 4, 2005, pp. 273–276, DOI:10.1109/LSP.2005.843762.
• (EN) J. Cooley, P. Lewis, and P. Welch, The finite Fourier transform, in IEEE Trans. Audio Electroacoustics, vol. 17, n. 2, 1969, pp. 77–85, DOI:10.1109/TAU.1969.1162036.
• (EN) F.N. Kong, Analytic Expressions of Two Discrete Hermite-Gaussian Signals, in IEEE Trans. Circuits and Systems –II: Express Briefs., vol. 55, n. 1, 2008, pp. 56–60, DOI:10.1109/TCSII.2007.909865.

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

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file sulla trasformata discreta di Fourier

Collegamenti esterni

• DFT, su Treccani.it – Enciclopedie on line, Istituto dell'Enciclopedia Italiana.
• DFT, in Dizionario delle scienze fisiche, Istituto dell'Enciclopedia Italiana, 1996.
• (EN) discrete Fourier transform, in Free On-line Dictionary of Computing, Denis Howe. Disponibile con licenza GFDL
• (EN) Matlab tutorial on the Discrete Fourier Transformation, su nbtwiki.net.
• (EN) Interactive flash tutorial on the DFT, su fourier-series.com. URL consultato l'11 giugno 2013 (archiviato dall'url originale il 23 maggio 2016).
• (EN) Mathematics of the Discrete Fourier Transform by Julius O. Smith III, su ccrma.stanford.edu.
• (EN) Fast implementation of the DFT - coded in C and under General Public License (GPL), su fftw.org.
• (EN) The DFT “à Pied”: Mastering The Fourier Transform in One Day, su dspdimension.com.
• (EN) Explained: The Discrete Fourier Transform, su web.mit.edu.