Elaborazione numerica dei segnali/Sistemi LTI a tempo discreto

Classificazione dei sistemi a tempo discreto

Un sistema per i segnali a tempo discreto è definito tramite la sua relazione ingresso-uscita:

$y\left(n\right)=L\left[x\left(n\right)\right]$

Sistemi lineari

Un sistema è lineare se soddisfa il principio di sovrapposizione degli effetti:

$L\left[\alpha _{1}x_{1}\left(n\right)+\alpha _{2}x_{2}\left(n\right)\right]=\alpha _{1}L\left[x_{1}\left(n\right)\right]+\alpha _{2}L\left[x_{2}\left(n\right)\right]$

Sistemi tempo-invarianti o stazionari

Un sistema è tempo-invariante (o stazionario) se un ritardo/anticipo $n_{0}$ sull'ingresso $x\left(n\right)$ si traduce in un ritardo/anticipo uguale sull'uscita $y\left(n\right)$ senza che cambi la forma del segnale di uscita $y\left(n\right)$:

$L\left[x\left(n-n_{0}\right)\right]=y\left(n-n_{0}\right)\quad \forall n_{0}$

Sistemi passivi

Un sistema è passivo se a un ingresso $x\left(n\right)$ con energia finita $E_{x}$ corrisponde un segnale $y\left(n\right)$ con energia $E_{y}$ minore o uguale all'energia dell'ingresso:

$E_{y}=\sum _{n=-\infty }^{+\infty }{\left|y\left(n\right)\right|}^{2}\leq E_{x}=\sum _{n=-\infty }^{+\infty }{\left|x\left(n\right)\right|}^{2}\in \mathbb {R}$

Il sistema è senza perdite se la relazione vale con il segno di uguaglianza: tutta l'energia dell'ingresso $x\left(n\right)$ viene conservata:

$E_{y}=E_{x}$

Sistemi causali

Un sistema è causale se l'uscita $y\left(n\right)$ non dipende dai valori futuri dell'ingresso $x\left(n\right)$, ma solo da quelli passati e da quello corrente.

Il comportamento di sistemi LTI causali a tempo discreto può essere descritto da un'equazione alle differenze finite e coefficienti costanti, che esprime l'uscita $y\left(n\right)$ all'istante corrente come combinazione lineare degli ingressi agli istanti passati e a quello corrente e delle uscite agli istanti passati (di solito $a_{0}=1$):

$a_{0}y\left(n\right)=-\sum _{k=1}^{M}a_{k}y\left(n-k\right)+\sum _{k=0}^{N}b_{k}x\left(n-k\right)=-a_{1}y\left(n-1\right)-a_{2}y\left(n-2\right)-\ldots -a_{M}y\left(n-M\right)+b_{0}x\left(n\right)+b_{1}x\left(n-1\right)+b_{2}x\left(n-2\right)+\ldots +b_{N}x\left(n-N\right)$

• Il sistema è ricorsivo se l'uscita $y\left(n\right)$ dipende da almeno un valore dell'uscita in istanti precedenti.
• Il sistema è non ricorsivo se tutti i coefficienti $a_{i}$ sono nulli.

L'equazione alle differenze di un sistema causale permette di trovare i valori di $y\left(n\right)$ per $n\geq 0$, noti i valori di $x\left(n\right)$ e le condizioni iniziali $y\left(-1\right),\ldots ,y\left(-M\right)$:

$y\left(n\right)=-\sum _{k=1}^{M}a_{k}y\left(n-k\right)+\sum _{k=0}^{N}b_{k}x\left(n-k\right)=y_{\text{so}}\left(n\right)+y_{\text{io}}\left(n\right)$

Risposta forzata

$y_{\text{so}}\left(n\right)$ è detta risposta allo stato nullo, e rappresenta l'evoluzione del sistema con condizioni iniziali nulle, tenendo conto solo degli ingressi:

$y_{\text{so}}\left(n\right)=-\sum _{k=0}^{M}a_{k}y_{\text{so}}\left(n-k\right)+\sum _{k=0}^{N}b_{k}x\left(n-k\right)$

Trascurare le condizioni iniziali significa studiare il comportamento del sistema a regime (sistema scarico).

Risposta libera

$y_{\text{io}}$ è detta risposta all'ingresso nullo, e rappresenta l'evoluzione del sistema con ingresso nullo, ma tenendo conto delle condizioni iniziali:

${\begin{cases}y_{\text{io}}\left(n\right)=-\sum _{k=0}^{M}a_{k}y\left(n-k\right)\\y_{\text{io}}\left(k\right)=y\left(k\right)\quad k=-M,\ldots ,-1\end{cases}}$

Per sistemi LTI stabili, $y_{\text{io}}\left(n\right)$ è anche detta risposta al transitorio perché siccome l'ingresso è nullo tende a smorzarsi nel tempo fino ad annullarsi.

Sistemi senza memoria

Un sistema è senza memoria se l'uscita $y\left(n\right)$ dipende solo dal valore corrente dell'ingresso $x\left(n\right)$.

Il sistema non ricorsivo:

$y\left(n\right)=\sum _{k=0}^{N}a_{k}x\left(n-k\right)$

ha memoria pari a $N$, perché l'uscita $y\left(n\right)$ dipende anche da $N$ valori passati dell'ingresso $x\left(n\right)$.

Sistemi LTI

Risposta all'impulso

I sistemi LTI causali scarichi sono caratterizzati da una risposta all'impulso $h\left(n\right)$, che è la risposta del sistema quando in ingresso è presente la sequenza $x\left(n\right)=\delta \left(n\right)$:

$h\left(n\right)=L\left[\delta \left(n\right)\right]$

La risposta all'impulso $h\left(n\right)$ lega l'ingresso $x\left(n\right)$ e l'uscita $y\left(n\right)$ del sistema:

$y\left(n\right)=x\left(n\right)*h\left(n\right)=\sum _{i=-\infty }^{+\infty }h\left(i\right)x\left(n-i\right)$

Dimostrazione

$y\left(n\right)=L\left[x\left(n\right)\right]=L\left[\sum _{i=-\infty }^{+\infty }x\left(i\right)\delta \left(n-i\right)\right]=$

Sfruttando il fatto che il sistema è lineare:

$=\sum _{i=-\infty }^{+\infty }x\left(i\right)L\left[\delta \left(n-i\right)\right]=$

Sfruttando il fatto che il sistema è tempo-invariante:

$=\sum _{i=-\infty }^{+\infty }x\left(i\right)h\left(n-i\right)$

Tutti i sistemi LTI possono essere quindi espressi in forma non ricorsiva, dove $b_{k}=h\left(k\right)$.

L'uscita del sistema dipende dai contributi causale ($i\geq 0$) e anticausale ($i<0$):

$y\left(n\right)=\sum _{i=-\infty }^{+\infty }h\left(i\right)x\left(n-i\right)=\sum _{i=-\infty }^{-1}h\left(i\right)x\left(n-i\right)+\sum _{i=0}^{+\infty }h\left(i\right)x\left(n-i\right)$

Siccome il sistema è causale, la parte anticausale è nulla:

$y\left(n\right)=\sum _{i=0}^{+\infty }h\left(i\right)x\left(n-i\right)$

Risposta in frequenza

Ipotesi

• $x\left(n\right)$ e $h\left(n\right)$ sono trasformabili mediante DTFT;
• si trascura la risposta al transitorio $y_{\text{so}}\left(n\right)$.

La DTFT del segnale in uscita $y\left(n\right)$ è pari al prodotto delle DTFT del segnale in ingresso $x\left(n\right)$ e della risposta all'impulso $h\left(n\right)$ del sistema LTI:

$Y\left(e^{j\omega }\right)=H\left(e^{j\omega }\right)\cdot X\left(e^{j\omega }\right)$

Dimostrazione

$Y\left(e^{j\omega }\right)=\sum _{n=-\infty }^{+\infty }y\left(n\right)e^{-j\omega n}=\sum _{n=-\infty }^{+\infty }\left[x\left(n\right)*h\left(n\right)\right]e^{-j\omega n}=\sum _{n=-\infty }^{+\infty }\left[\sum _{i=-\infty }^{+\infty }x\left(i\right)h\left(n-i\right)\right]e^{-j\omega n}=\sum _{i=-\infty }^{+\infty }h\left(i\right)\left[\sum _{n=-\infty }^{+\infty }x\left(n-i\right)e^{-j\omega n}\right]=$

Effettuando il cambio di variabile $m=n-i$ nella sommatoria interna:

$=\sum _{i=-\infty }^{+\infty }h\left(i\right)\left[\sum _{m=-\infty }^{+\infty }x\left(m\right)e^{-j\omega \left(m+i\right)}\right]=\left[\sum _{i=-\infty }^{+\infty }h\left(i\right)e^{-j\omega i}\right]\left[\sum _{m=-\infty }^{+\infty }x\left(m\right)e^{-j\omega n}\right]=H\left(e^{j\omega }\right)\cdot X\left(e^{j\omega }\right)$

La DTFT $H\left(e^{j\omega }\right)$ della risposta all'impulso $h\left(n\right)$ è detta risposta in frequenza del sistema LTI:

$H\left(e^{j\omega }\right)=\sum _{i=-\infty }^{+\infty }h\left(i\right)e^{-j\omega i}={\frac {Y\left(e^{j\omega }\right)}{X\left(e^{j\omega }\right)}}$

Interconnessione di sistemi LTI

Serie		$y\left(n\right)=x\left(n\right)*h_{1}\left(n\right)*h_{2}\left(n\right)$ $Y\left(e^{j\omega }\right)=X\left(e^{j\omega }\right)H_{1}\left(e^{j\omega }\right)H_{2}\left(e^{j\omega }\right)$
Parallelo		$y\left(n\right)=x\left(n\right)*\left[h_{1}\left(n\right)+h_{2}\left(n\right)\right]$ $Y\left(e^{j\omega }\right)=X\left(e^{j\omega }\right)\left[H_{1}\left(e^{j\omega }\right)+H_{2}\left(e^{j\omega }\right)\right]$
Con reazione		$y\left(n\right)=\left[x\left(n\right)-y\left(n\right)*h_{2}\left(n\right)\right]*h_{1}\left(n\right)$ $Y\left(e^{j\omega }\right)=X\left(e^{j\omega }\right){\frac {H_{1}\left(e^{j\omega }\right)}{1+H_{1}\left(e^{j\omega }\right)H_{2}\left(e^{j\omega }\right)}}$

Risposta a esponenziali complessi

Gli esponenziali complessi sono delle autofunzioni dei sistemi LTI, perché a un ingresso a esponenziale complesso corrisponde ancora un'uscita a esponenziale complesso:

$x\left(n\right)=e^{j\omega _{0}n}\Rightarrow y\left(n\right)=e^{j\omega _{0}n}H\left(e^{j\omega _{0}}\right)=\left|H\left(e^{j\omega 0}\right)\right|\cdot e^{j\omega _{0}n+j\arg {\left[H\left(e^{j\omega _{0}}\right)\right]}}$

Dimostrazione

$y\left(n\right)=x\left(n\right)*h\left(n\right)=\sum _{i=-\infty }^{+\infty }h\left(i\right)e^{j\omega _{0}\left(n-i\right)}=e^{j\omega _{0}n}\sum _{i=-\infty }^{+\infty }h\left(i\right)e^{-j\omega _{0}i}$

Se la risposta all'impulso $h\left(n\right)$ è reale, e la sinusoide $x\left(n\right)$ è reale:

$x\left(n\right)=\cos {\left(\omega _{0}n+\theta \right)}\Rightarrow y\left(n\right)=\left|H\left(e^{j\omega _{0}}\right)\right|\cos {\left(\omega _{0}n+\theta +\arg {\left[H\left(e^{j\omega _{0}}\right)\right]}\right)}$

Dimostrazione

$x\left(n\right)=\cos {\left(\omega _{0}n+\theta \right)}={\frac {e^{j\omega _{0}n+j\theta }+e^{-j\omega _{0}n-j\theta }}{2}}$

Applicando il risultato precedente a ciascuno dei due esponenziali complessi:

$y\left(n\right)={\frac {1}{2}}\left\{e^{j\theta }\left|H\left(e^{j\omega _{0}}\right)\right|\cdot e^{j\omega _{0}n+j\arg {\left[H\left(e^{j\omega _{0}}\right)\right]}}+e^{-j\theta }\left|H\left(e^{-j\omega _{0}}\right)\right|\cdot e^{-j\omega _{0}n+j\arg {\left[H\left(e^{-j\omega _{0}}\right)\right]}}\right\}=$

Ricordando le proprietà di simmetria della DTFT della sequenza reale $h\left(n\right)$ (modulo pari e fase dispari):

$={\frac {1}{2}}\left|H\left(e^{j\omega _{0}}\right)\right|\left\{e^{j\theta }e^{j\omega _{0}n+j\arg {\left[H\left(e^{j\omega _{0}}\right)\right]}}+e^{-j\theta }e^{-j\omega _{0}n-j\arg {\left[H\left(e^{j\omega _{0}}\right)\right]}}\right\}$

Sistemi IIR

L'uscita $y\left(n\right)$ di un sistema IIR dipende non solo dal segnale in ingresso $x\left(n\right)$, ma anche dai campioni del segnale in uscita $y\left(n\right)$:

$y\left(n\right)=-\sum _{k=1}^{M}a_{k}y\left(n-k\right)+\sum _{k=0}^{N}b_{k}x\left(n-k\right)\Rightarrow Y\left(e^{j\omega }\right)=X\left(e^{j\omega }\right){\frac {\sum _{k=0}^{N}b_{k}e^{-j\omega k}}{1+\sum _{k=1}^{M}a_{k}e^{-j\omega k}}}$

La risposta in frequenza $H\left(e^{j\omega }\right)$ del sistema si può scrivere:

$H\left(e^{j\omega }\right)={\frac {Y\left(e^{j\omega }\right)}{X\left(e^{j\omega }\right)}}={\frac {\sum _{k=0}^{N}b_{k}e^{-j\omega k}}{1+\sum _{k=1}^{M}a_{k}e^{-j\omega k}}}$

Sistemi IIR puramente ricorsivi

Un sistema IIR è puramente ricorsivo se:

$y\left(n\right)=x\left(n\right)-\sum _{k=1}^{M}a_{k}y\left(n-k\right)\quad b_{k}=0\;\forall k\neq 0$

La risposta all'impulso $h\left(n\right)$ di un sistema IIR puramente ricorsivo è a supporto illimitato.

Esempio: risposta all'impulso di un sistema IIR puramente ricorsivo

$y\left(n\right)={\frac {1}{3}}y\left(n-1\right)+x\left(n\right)\Rightarrow h\left(n\right)={\left({\frac {1}{3}}\right)}^{n}u\left(n\right)$

Calcoli

$Y\left(e^{j\omega }\right)={\frac {1}{3}}Y\left(e^{j\omega }\right)e^{-j\omega }+X\left(e^{j\omega }\right)$

$H\left(e^{j\omega }\right)={\frac {Y\left(e^{j\omega }\right)}{X\left(e^{j\omega }\right)}}={\frac {1}{1-{\frac {1}{3}}e^{-j\omega }}}$

Sistemi FIR

L'uscita $y\left(n\right)$ di un sistema FIR dipende solo dal segnale d'ingresso $x\left(n\right)$:

$-\sum _{k=1}^{M}a_{k}y\left(n-k\right)=0\Rightarrow y\left(n\right)=\sum _{k=0}^{N}b_{k}x\left(n-k\right)$

$H\left(e^{j\omega }\right)=\sum _{k=0}^{N}b_{k}e^{-j\omega k}$

La risposta all'impulso $h\left(n\right)$ di un sistema FIR è a supporto finito $\left[0,N\right]$:

$h\left(n\right)\triangleq \sum _{k=0}^{N}b_{k}\delta \left(n-k\right)=b_{0}\delta \left(n\right)+b_{1}\delta \left(n-1\right)+\ldots +b_{N}\delta \left(n-N\right)$

Stabilità

Un sistema è stabile secondo il criterio BIBO (o BIBO-stabile) se e solo se ad ogni ingresso $x\left(n\right)$ di ampiezza limitata corrisponde un'uscita $y\left(n\right)$ di ampiezza limitata:

$\left|x\left(n\right)\right|\in \mathbb {R} \Leftrightarrow \left|y\left(n\right)\right|\in \mathbb {R}$

La risposta al transitorio di un sistema BIBO-stabile tende a smorzarsi al crescere di $n$.

Teorema

Un sistema LTI è BIBO-stabile se e solo se la sua risposta all'impulso $h\left(n\right)$ è sommabile in modulo:

${\text{stabile }}\Leftrightarrow \sum _{n=-\infty }^{+\infty }\left|h\left(n\right)\right|\in \mathbb {R}$

Dimostrazione condizione sufficiente

$\sum _{n=-\infty }^{+\infty }\left|h\left(n\right)\right|\in \mathbb {R} \Rightarrow {\text{ stabile}}$

Considerando un ingresso $x\left(n\right)$ di ampiezza limitata, il valore dell'uscita $y\left(n\right)$ è:

$\left|y\left(n\right)\right|=\left|h\left(n\right)*x\left(n\right)\right|=\left|\sum _{k=-\infty }^{+\infty }h\left(k\right)x\left(n-k\right)\right|\leq \sum _{k=-\infty }^{+\infty }\left|h\left(k\right)\right|\left|x\left(n-k\right)\right|\in \mathbb {R}$

Dimostrazione condizione necessaria

${\text{stabile }}\Rightarrow \sum _{n=-\infty }^{+\infty }\left|h\left(n\right)\right|\in \mathbb {R}$

Considerando l'ingresso $x\left(n\right)$ di ampiezza limitata:

$x\left(n\right)={\begin{cases}{\frac {h^{*}\left(-n\right)}{\left|h\left(-n\right)\right|}}&h\left(-n\right)\neq 0\\0&h\left(-n\right)=0\end{cases}}\Rightarrow \left|x\left(n\right)\right|={\begin{cases}{\frac {\left|h^{*}\left(-n\right)\right|}{\left|h\left(-n\right)\right|}}=1&h\left(-n\right)\neq 0\\0&h\left(-n\right)=0\end{cases}}$

il valore dell'uscita $y\left(n\right)$ in $n=0$ è:

${\begin{cases}y\left(0\right)=\sum _{k=-\infty }^{+\infty }h\left(k\right)x\left(-k\right)=\sum _{k=-\infty }^{+\infty }h\left(k\right){\frac {h^{*}\left(k\right)}{\left|h\left(k\right)\right|}}=\sum _{k=-\infty }^{+\infty }{\frac {{\left|h\left(k\right)\right|}^{2}}{\left|h\left(k\right)\right|}}=\sum _{k=-\infty }^{+\infty }\left|h\left(k\right)\right|\\{\text{stabile }}\Rightarrow y\left(n\right)\in \mathbb {R} \end{cases}}\Rightarrow \sum _{k=-\infty }^{+\infty }\left|h\left(k\right)\right|\in \mathbb {R}$

Realizzabilità fisica

Un sistema LTI è fisicamente realizzabile se l'equazione alle differenze è causale e i coefficienti $a_{i}$ e $b_{i}$ della sua equazione alle differenze sono tutti reali:

$y\left(n\right)=\sum _{k=1}^{M}a_{k}y\left(n-k\right)+\sum _{k=0}^{N}b_{k}x\left(n-k\right)\quad \forall k:\,a_{k},b_{k}\in \mathbb {R}$

Un sistema è fisicamente realizzabile se la sua risposta all'impulso $h\left(n\right)$ è reale e causale:

${\begin{cases}h\left(n\right)\in \mathbb {R} &\forall n\geq 0\\h\left(n\right)=0&\forall n<0\end{cases}}$

La risposta in frequenza $H\left(e^{j\omega }\right)$ di un sistema fisicamente realizzabile è unilatera:

$H^{+}\left(e^{j\omega }\right)=\sum _{n=0}^{+\infty }h\left(n\right)e^{-j\omega n}$

ed ha le seguenti relazioni di parità:

• la parte reale e il modulo sono pari;
• la parte immaginaria e la fase sono dispari.

Esempio: filtro passa-basso

Si vogliono confrontare tre sistemi LTI che hanno risposte all'impulso $h_{1}\left(n\right)$, $h_{2}\left(n\right)$ e $h_{3}\left(n\right)$:

$h_{i}\left(n\right)=r_{i}^{n}\quad n=0,\ldots ,N-1$

dove:

${\begin{cases}r_{1}=0,8\\r_{2}=0,5\\r_{3}=0,2\end{cases}}$

$h_{1}\left(n\right)$

$h_{2}\left(n\right)$

$h_{3}\left(n\right)$

La risposta in frequenza $H_{i}\left(e^{j\omega }\right)$ è pari a:

$H_{i}\left(e^{j\omega }\right)=\sum _{n=-\infty }^{+\infty }h_{i}\left(n\right)e^{-j\omega n}=\sum _{n=0}^{N-1}r_{i}^{n}e^{-j\omega n}={\frac {1-{\left(r_{i}e^{-j\omega }\right)}^{N}}{1-r_{i}e^{-j\omega }}}$

$\left|H_{i}\left(e^{j\omega }\right)\right|$

Si introduce come ingresso $x\left(n\right)$ una porta:

$x\left(n\right)=u\left(n\right)-u\left(n-N\right)\Rightarrow X\left(e^{j\omega }\right)=\sum _{n=-\infty }^{+\infty }x\left(n\right)e^{-j\omega n}={\frac {\sin {\left(\pi fN\right)}}{\sin {\left(\pi f\right)}}}e^{-j\pi f\left(N-1\right)}$

Il filtro passa-basso smorza le alte frequenze. L'uscita $y_{i}\left(n\right)$ appare più simile all'ingresso $x\left(n\right)$ con il filtro $h_{3}\left(n\right)$:

$\left|Y_{i}\left(e^{j\omega }\right)\right|$

$y_{1}\left(n\right)$

$y_{2}\left(n\right)$

$y_{3}\left(n\right)$

L'ingresso $x\left(n\right)$ risulta quindi meno smorzato con il filtro $h_{3}\left(n\right)$:

$E\left(x\right)=\sum _{n=-\infty }^{+\infty }x^{2}\left(n\right)=\sum _{n=0}^{N-1}1=N=11$

$E\left(y_{1}\right)=\sum _{n=-\infty }^{+\infty }y_{1}^{2}\left(n\right)\cong 8$

$E\left(y_{2}\right)=\sum _{n=-\infty }^{+\infty }y_{2}^{2}\left(n\right)\cong 9,7$

$E\left(y_{3}\right)=\sum _{n=-\infty }^{+\infty }y_{3}^{2}\left(n\right)\cong 10,6$

Questo sistema LTI è di tipo passivo perché l'energia dell'uscita $y_{i}\left(n\right)$ è sempre minore dell'energia dell'ingresso $x\left(n\right)$.

Distorsione

• Se il modulo della risposta in frequenza $\left|H\left(e^{j\omega }\right)\right|$ non è costante, il sistema introduce una distorsione in ampiezza.
• Se la fase della risposta in frequenza $\arg {\left[H\left(e^{j\omega }\right)\right]}$ non è lineare in $\omega =2\pi f$, il sistema introduce una distorsione di fase.

Si definisce ritardo di gruppo $\tau \left(\omega \right)$ il ritardo medio subito dalle componenti armoniche del segnale in ingresso $x\left(n\right)$:

$\tau \left(\omega \right)=-{\frac {d}{d\omega }}\arg {\left[H\left(e^{j\omega }\right)\right]}$

Sistema LTI non distorcente

Si vuole realizzare un amplificatore non distorcente:

$y\left(n\right)=A\cdot x\left(n-N\right)$

dove:

• $N$ è il tempo impiegato dal segnale in ingresso $x\left(n\right)$ per attraversare il sistema (ritardo);
• $A$ è l'amplificazione.

La sua risposta in frequenza $H\left(e^{j\omega }\right)$:

$H\left(e^{j\omega }\right)={\frac {Y\left(e^{j\omega }\right)}{X\left(e^{j\omega }\right)}}=Ae^{-j\omega N}$

ha:

• modulo $A$ costante;
• rotazione di fase $-\omega N$ lineare in $\omega$.

La sua risposta all'impulso $h\left(n\right)$:

$h\left(n\right)=A\delta \left(n-N\right)$

è una delta di ampiezza $A$ centrata in $N$.

Se il ritardo di gruppo $\tau \left(\omega \right)$ è costante, cioè le componenti armoniche nel segnale di ingresso $x\left(n\right)$ subiscono lo stesso ritardo costante, allora la fase è lineare e il sistema è non distorcente.

Analisi tramite DFT

L'uscita $y\left(n\right)$ di un sistema LTI si può ottenere dalla IDTFT del prodotto tra la DTFT dell'ingresso $x\left(n\right)$ e la risposta in frequenza $H\left(e^{j\omega }\right)$:

$Y\left(e^{j\omega }\right)=X\left(e^{j\omega }\right)\cdot H\left(e^{j\omega }\right)\Rightarrow y\left(n\right)=x\left(n\right)*h\left(n\right)\quad n\in \left[0,N_{x}+N_{h}-2\right]$

dove $N_{x}$ e $N_{h}$ sono i supporti rispettivamente di $x\left(n\right)$ e $h\left(n\right)$.

Se si vuole sostituire la DTFT con la DFT, la IDFT non restituisce lo stesso risultato:

$Y\left(k\right)=X\left(k\right)\cdot H\left(k\right)\Rightarrow y\left(n\right)\neq x\left(n\right)\otimes h\left(n\right)\quad n\in \left[0,\max {\left\{N_{x},N_{h}\right\}}-1\right]$

perché la convoluzione circolare ha un supporto diverso dalla convoluzione lineare.

Per far sì che il risultato coincida con la convoluzione lineare, occorre procedere all'inserimento di zeri (zero padding) nelle due sequenze $x\left(n\right)$ e $h\left(n\right)$, in numero tale da garantire la lunghezza di una convoluzione lineare:

$x_{z}\left(n\right)={\begin{cases}x\left(n\right)&n\in \left[0,N_{x}-1\right]\\0&n\in \left[N_{x},N_{x}+N_{h}-2\right]\end{cases}}$

$h_{z}\left(n\right)={\begin{cases}h\left(n\right)&n\in \left[0,N_{h}-1\right]\\0&n\in \left[N_{h},N_{x}+N_{h}-2\right]\end{cases}}$

In questo modo la convoluzione circolare ottenuta dalla IDFT coincide con la convoluzione lineare, e quindi con l'uscita del sistema $y\left(n\right)$:

$x_{z}\left(n\right)\otimes h_{z}\left(n\right)=x\left(n\right)*h\left(n\right)=y\left(n\right)\quad n=0,\ldots ,N_{x}+N_{h}-2$

Dimostrazione

$x\left(n\right)*h\left(n\right)=x_{z}\left(n\right)*h_{z}\left(n\right)=\sum _{m=-\infty }^{+\infty }x_{z}\left(m\right)h_{z}\left(n-m\right)=$

Poiché $x_{z}\left(m\right)$ ha supporto finito $\left[0,N_{y}-1\right]$:

$=\sum _{m=0}^{N_{y}-1}x_{z}\left(m\right)h_{z}\left(n-m\right)$

• Se $n<0$:

  $h_{z}\left(n-m\right)=0\quad m\geq 0\Rightarrow x_{z}\left(m\right)h_{z}\left(n-m\right)=0\quad \forall m\geq 0$

• Se $n=N_{y}$:

  ${\begin{cases}h_{z}\left(n-m\right)=0&m\in \left[0,N_{y}-N_{h}\right]=\left[0,N_{x}-1\right]\\x_{z}\left(m\right)=0&m\geq N_{x}\end{cases}}\Rightarrow x_{z}\left(m\right)h_{z}\left(n-m\right)=0\quad \forall m\geq 0$

• Se $n=N_{y}+k$ ($k>0$):

  ${\begin{cases}h_{z}\left(n-m\right)=0&m\in \left[0,N_{y}+k-N_{h}\right]=\left[0,N_{x}+k-1\right]\\x_{z}\left(m\right)=0&m\geq N_{x}\end{cases}}\Rightarrow x_{z}\left(m\right)h_{z}\left(n-m\right)=0\quad \forall m\geq 0$

Se il supporto $N_{y}=N_{x}+N_{h}-1$ viene scelto come potenza di 2, si può impiegare la FFT per il calcolo delle 3 DFT, con complessità finale proporzionale a $N_{y}\log _{2}{\left(N_{y}\right)}$, invece della complessità dell'ordine di $N_{h}N_{x}$ operazioni per il calcolo della convoluzione nel dominio del tempo.