# Trasformata di Fourier a tempo discreto

In matematica, la trasformata di Fourier a tempo discreto, spesso abbreviata con DTFT (acronimo del termine inglese Discrete-Time Fourier Transform), è una trasformata che a partire da un segnale discreto ne fornisce una descrizione periodica nel dominio della frequenza, analogamente alla trasformata di Fourier tradizionale (definita per funzioni continue).
Si tratta di un caso particolare della trasformata zeta:
    $X(z)=\sum _{n=-\infty }^{\infty }x[n]z^{-n}$
che si ottiene ponendo $z=e^{i\omega }$ ($\omega$ è inteso come angolo). Dal momento che $|e^{i\omega }|=1,$ la trasformata di Fourier a tempo discreto è la valutazione della trasformata zeta sul cerchio unitario nel piano complesso.

## Definizione

Dato un insieme di numeri interi complessi $x[n]$, con $n\in \mathbb {Z}$, la sua trasformata di Fourier a tempo discreto è la serie:
    $X(\omega )=\sum _{n=-\infty }^{\infty }x[n]e^{-i\omega n}.$
La trasformata inversa permette di ottenere la funzione originale a partire dalla sua trasformata:
    $x[n]={\frac {1}{2\pi }}\int _{2\pi }X(\omega )\cdot e^{i\omega n}d\omega .$

## Relazione con il campionamento

La trasformata di Fourier a tempo discreto ha un ruolo rilevante quando si studiano segnali campionati, ovvero segnali a tempo discreto ottenuti da un segnale a tempo continuo considerandone il valore assunto in precisi istanti di tempo, solitamente separati da un intervallo temporale fisso $T$. La procedura che permette di ottenere un segnale discreto a partire da uno continuo è detta campionamento, ed è alla base della conversione analogico-digitale (ADC). Essa trasforma una funzione continua $x(t)$ nel segnale discreto:
    $x[n]{\stackrel {\text{def}}{=}}x(nT),\qquad \forall \,n\in \mathbb {Z}$
con $1/T$ la frequenza di campionamento. Il teorema del campionamento pone un limite alla massima frequenza del segnale continuo, che non può essere superiore ad $1/(2T)$ se si vuole evitare perdita di informazione (fenomeno di aliasing). La trasformata a tempo discreto fornisce un'approssimazione della trasformata di Fourier ${\mathcal {F}}$:
    ${\mathcal {F}}(x(t))(f)=X(f)=\int _{-\infty }^{\infty }x(t)\cdot e^{-i2\pi ft}dt.$
Infatti, considerando la formula di sommazione di Poisson, che mostra come ottenere una sommazione periodica di una funzione $X(f)$ a partire dai campioni di una funzione tempo-continua, si ha:
    $X_{1/T}(f)\ {\stackrel {\mathrm {def} }{=}}\ \sum _{k=-\infty }^{\infty }X\left(f-k/T\right)\equiv \sum _{n=-\infty }^{\infty }\underbrace {T\cdot x(nT)} _{x[n]}\underbrace {e^{-i2\pi fTn}} _{{\mathcal {F}}\{\delta (t-nT)\}}={\mathcal {F}}\left\{\sum _{n=-\infty }^{\infty }x(t)\cdot \delta (t-nT)\right\},$
dove $X_{1/T}(f)$ include copie esatte di $X(f)$ traslate di un multiplo di $f_{s}$ e combinate per addizione. Per $f_{s}$ sufficientemente grande il termine $K=0$ può essere osservato nella regione $[-f_{s}/2,f_{s}/2]$, con distorsione minima o nulla. Un altro modo per verificare questo fatto è il seguente:
    ${\begin{aligned}{\mathcal {F}}\left\{\sum _{n=-\infty }^{\infty }T\cdot x(nT)\cdot \delta (t-nT)\right\}&={\mathcal {F}}\left\{x(t)\cdot T\sum _{n=-\infty }^{\infty }\delta (t-nT)\right\}\\&=X(f)*\underbrace {{\mathcal {F}}\left\{T\sum _{n=-\infty }^{\infty }\delta (t-nT)\right\}} _{\sum _{k=-\infty }^{\infty }\delta (f-k/T)}=\sum _{k=-\infty }^{\infty }X\left(f-{\frac {k}{T}}\right)\end{aligned}}$
Calcolando la trasformata di Fourier inversa di entrambi i membri dell'equazione precedente, inoltre, si ottiene il pettine di Dirac modulato:
    $\sum _{n=-\infty }^{\infty }x[n]\cdot \delta (t-nT)={\mathcal {F}}^{-1}\left\{X_{1/T}(f)\right\}\ {\stackrel {\mathrm {def} }{=}}\ \int _{-\infty }^{\infty }X_{1/T}(f)\cdot e^{i2\pi ft}df$
con
    $x[n]=T\int _{\frac {1}{T}}X_{1/T}(f)\cdot e^{i2\pi fnT}df={\frac {1}{2\pi }}\int _{2\pi }X(\omega )\cdot e^{i\omega n}d\omega .$

### Ingresso periodico

Se la successione in ingresso $x[n]$ è periodica con periodo $N$ è possibile espandere il pettine di Dirac in serie di Fourier, ottenendo la trasformata discreta di Fourier (DFT):
    ${\mathcal {F}}\left\{\sum _{n=-\infty }^{\infty }x[n]\cdot \delta (t-nT)\right\}={\mathcal {F}}\left\{\underbrace {\sum _{k=-\infty }^{\infty }X[k]\cdot e^{i2\pi {\frac {k}{NT}}t}} _{\text{serie di Fourier}}\right\}=\underbrace {\sum _{k=-\infty }^{\infty }X[k]\cdot \delta \left(f-{\frac {k}{NT}}\right)} _{\text{DTFT}}.$
Tale relazione mostra che la periodicità nel tempo rende discontinua la trasformata di Fourier a tempo discreto. Si può tuttavia ridurre la formula integrale in una somma di $N$ termini:
    $X[k]\ {\stackrel {\text{def}}{=}}\ {\frac {1}{NT}}\int _{NT}\left[\sum _{n=-\infty }^{\infty }x[n]\cdot \delta (t-nT)\right]e^{-i2\pi {\frac {k}{NT}}t}dt={\frac {1}{NT}}\sum _{n=-\infty }^{\infty }x[n]\cdot \int _{NT}\delta (t-nT)\cdot e^{-i2\pi {\frac {k}{NT}}t}dt$
    $={\frac {1}{NT}}\underbrace {\sum _{N}x[n]\cdot e^{-i2\pi {\frac {k}{N}}n}} _{\text{DFT}}={\frac {1}{N}}\underbrace {\sum _{N}x(nT)\cdot e^{-i2\pi {\frac {k}{N}}n}} _{\text{DFT}}$
che è periodica in $k$.

### Campionamento della DTFT

Se la trasformata di Fourier a tempo discreto è una funzione continua, si usa spesso considerare un numero arbitrario di campioni di un ciclo della funzione periodica $X_{1/T}$:
    $\underbrace {X_{1/T}\left({\frac {k}{NT}}\right)} _{X_{k}}=\sum _{n=-\infty }^{\infty }x[n]\cdot e^{-i2\pi {\frac {kn}{N}}}=\underbrace {\sum _{N}x_{N}[n]\cdot e^{-i2\pi {\frac {kn}{N}}}} _{\text{DFT}},\qquad \quad k=0,\dots ,N-1,$
dove $X_{N}$ è la somma periodica:
    $x_{N}[n]{\stackrel {\text{def}}{=}}\sum _{m=-\infty }^{\infty }x[n-mN].$
La successione $x_{N}$ è l'inversa della trasformata discreta di Fourier. In questo modo il campionamento così effettuato comporta che la trasformata inversa sia periodica.
Per valutare numericamente un ciclo di $x_{N}$ è richiesta una successione $x[n]$ di lunghezza finita. A tal fine spesso si tronca una successione per mezzo di una funzione finestra di lunghezza opportuna.

## Trasformate notevoli

Siano $n$ il dominio tempo-discreto, $\omega$ la frequenza angolare (un numero reale in $(-\pi ,\pi )$ misurato in radianti / campione), $u[n]$ il gradino di Heaviside tempo-discreto, $\operatorname {sinc} (t)$ la funzione sinc normalizzata, $\delta (\omega )$ la delta di Dirac, $\delta [n]$ la delta di Kronecker, $\operatorname {rect} (t)$ la funzione rettangolo:
    $\mathrm {rect} (t)=\sqcap (t)={\begin{cases}0&{\text{se }}|t|>{\frac {1}{2}}\\[3pt]{\frac {1}{2}}&{\text{se }}|t|={\frac {1}{2}}\\[3pt]1&{\text{se }}|t|<{\frac {1}{2}}\end{cases}}$
e $\operatorname {tri} (t)$ la funzione triangolo:
    $\operatorname {tri} (t)=\land (t)={\begin{cases}1+t&-1\leq t\leq 0\\1-t&0<t\leq 1\\0&{\text{altrimenti}}\end{cases}}$
| Dominio temporale $x[n]$ | Dominio della frequenza $X(\omega )$ | Remarks |
| $\delta [n]$ | $1$ | |
| $\delta [n-M]$ | $e^{-i\omega M}$ | $M$ intero |
| $\sum _{m=-\infty }^{\infty }\delta [n-Mm]$ | $\sum _{m=-\infty }^{\infty }e^{-i\omega Mm}={\frac {1}{M}}\sum _{k=-\infty }^{\infty }\delta \left({\frac {\omega }{2\pi }}-{\frac {k}{M}}\right)$ | $M$ intero |
| $u[n]$ | ${\frac {1}{1-e^{-i\omega }}}+\sum \limits _{k=-\infty }^{\infty }\pi \delta (\omega -2\pi k)$ | Il termine $1/(1-e^{-i\omega })$ deve essere interpretato come una distribuzione. |
| $a^{n}u[n]$ | ${\frac {1}{1-ae^{-i\omega }}}$ | $0<|a|<1$ |
| $e^{-ian}$ | $2\pi \delta (\omega +a)$ | $a\in \mathbb {R}$ |
| $\cos(an)$ | $\pi \left[\delta (\omega -a)+\delta (\omega +a)\right]$ | $a\in \mathbb {R}$ |
| $\sin(an)$ | ${\frac {\pi }{i}}\left[\delta (\omega -a)-\delta (\omega +a)\right]$ | $a\in \mathbb {R}$ |
| $\mathrm {rect} \left[{(n-M/2) \over M}\right]$ | ${\sin[\omega (M+1)/2] \over \sin(\omega /2)}e^{-i\omega M/2}$ | $M$ intero |
| $\operatorname {sinc} [(a+n)]$ | $e^{ia\omega }$ | $a\in \mathbb {R}$ |
| $W\cdot \operatorname {sinc} ^{2}(Wn)$ | $\operatorname {tri} \left({\omega \over 2\pi W}\right)$ | $0<W\leq 0,5\quad \in \mathbb {R}$ |
| $W\cdot \operatorname {sinc} (Wn)$ | $\operatorname {rect} \left({\omega \over 2\pi W}\right)$ | $0<W\leq 1\quad \in \mathbb {R}$ |
| ${\begin{cases}0&n=0\\{\frac {(-1)^{n}}{n}}&{\text{altrimenti}}\end{cases}}$ | $j\omega$ | Filtro differenziatore |
| ${\frac {W}{(n+a)}}\left\{\cos[\pi W(n+a)]-\operatorname {sinc} [W(n+a)]\right\}$ | $j\omega \cdot \operatorname {rect} \left({\omega \over \pi W}\right)e^{ja\omega }$ | $0<W\leq 1\quad \in \mathbb {R} \qquad a\in \mathbb {R}$ |
| ${\frac {1}{\pi n^{2}}}[(-1)^{n}-1]$ | $|\omega |$ | |
| ${\begin{cases}0;&n{\text{ pari}}\\{\frac {2}{\pi n}};&n{\text{ dispari}}\end{cases}}$ | ${\begin{cases}j&\omega <0\\0&\omega =0\\-j&\omega >0\end{cases}}$ | Trasformata di Hilbert |
| ${\frac {C(A+B)}{2\pi }}\cdot \operatorname {sinc} \left[{\frac {A-B}{2\pi }}n\right]\cdot \operatorname {sinc} \left[{\frac {A+B}{2\pi }}n\right]$ | | $A,B\in R,\quad B\in \mathbb {C}$ |

## Proprietà

Siano $*$ la convoluzione discreta di due successioni e $x[n]^{*}$ il complesso coniugato di $x[n]$.
| Proprietà | Dominio temporale $x[n]$ | Dominio della frequenza $X(\omega )$ | Remarks |
| Linearità | $ax[n]+by[n]$ | $aX(e^{i\omega })+bY(e^{i\omega })$ | |
| Traslazione temporale | $x[n-k]$ | $X(e^{i\omega })e^{-i\omega k}$ | $k$ intero |
| Traslazione in frequenza | $x[n]e^{ian}$ | $X(e^{i(\omega -a)})$ | $a\in \mathbb {R}$ |
| Inversione temporale | $x[-n]$ | $X(e^{-i\omega })$ | |
| Coniugazione temporale | $x[n]^{*}$ | $X(e^{-i\omega })^{*}$ | |
| Inversione temporale e coniugazione | $x[-n]^{*}$ | $X(e^{i\omega })^{*}$ | |
| Derivata | ${\frac {n}{i}}x[n]$ | ${\frac {dX(e^{i\omega })}{d\omega }}$ | |
| Integrale | ${\frac {i}{n}}x[n]$ | $\int _{-\pi }^{\omega }X(e^{i\vartheta })d\vartheta$ | |
| Convoluzione | $x[n]*y[n]$ | $X(e^{i\omega })\cdot Y(e^{i\omega })$ | |
| Moltiplicazione | $x[n]\cdot y[n]$ | ${\frac {1}{2\pi }}\int _{-\pi }^{\pi }{X(e^{i\vartheta })\cdot Y(e^{i(\omega -\vartheta )})d\vartheta }$ | Convoluzione periodica |
| Cross-correlazione | $\rho _{xy}[n]=x[-n]^{*}*y[n]$ | $R_{xy}(\omega )=X(e^{i\omega })^{*}\cdot Y(e^{i\omega })$ | |
| Teorema di Parseval | $E=\sum _{n=-\infty }^{\infty }{x[n]\cdot y^{*}[n]}$ | $E={\frac {1}{2\pi }}\int _{-\pi }^{\pi }{X(e^{i\omega })\cdot Y^{*}(e^{i\omega })d\omega }$ | |
La trasformata può essere inoltre decomposta sia in parte reale e immaginaria, sia in due funzioni rispettivamente pari e dispari:
    $X(e^{i\omega })=X_{R}(e^{i\omega })+iX_{I}(e^{i\omega })\qquad X(e^{i\omega })=X_{E}(e^{i\omega })+X_{O}(e^{i\omega }).$
| Dominio del tempo $x[n]$ | Dominio della frequenza $X(e^{i\omega })$ |
| $x^{*}[n]$ | $X^{*}(e^{-i\omega })$ |
| $x^{*}[-n]$ | $X^{*}(e^{i\omega })$ |