Sistemi LTI e convoluzione discreta

Qui si definiscono le due proprietà che rendono trattabile un sistema (linearità e invarianza temporale), si ricava la somma di convoluzione e se ne vedono il calcolo, le proprietà e due applicazioni (serie storiche e immagini). La convoluzione è già trattata in ConvoluzioneLa convoluzione $xy(t)=\int x(u),y(t-u),du$ combina due segnali ribaltando e traslando il secondo, moltiplicando e integrando. È commutativa, associativa, lineare; l'area del risultato è il prodotto delle aree; l'estensione è la somma delle estensioni (estremo con estremo); l'impulso $\delta$ è l'elemento neutro; la convoluzione con il gradino integra. Per due segnali periodici di uguale periodo si usa la convoluzione ciclica (integrale su un periodo). È l'operazione del filtraggio: l'uscita di un filtro è la convoluzione dell'ingresso con la risposta impulsiva.Convoluzione → (con $T$ esplicito) e il quadro dei sistemi LTI in Sistemi lineari tempo-invarianti e risposta impulsivaUna tf lineare e tempo-invariante (LTI, filtro) ha nucleo h(t,u) = g(t-u): l'uscita è la convoluzione y = gx con la risposta impulsiva g (uscita all'impulso ideale nell'origine). Causale se e solo se g è causale; stabile BIBO se e solo se g è assolutamente integrabile (sommabile); reale se e solo se g è reale. Cascata: g = g2g1; parallelo: g1+g2; retroazione: Ge = G/(1+HG) in frequenza.Sistemi lineari tempo-invarianti e risposta impulsiva → e Sistemi LTI, risposta impulsiva e convoluzioneUn sistema lineare tempo-invariante (LTI) è completamente descritto dalla sua risposta impulsiva $h=\Sigma[\delta]$: l'uscita è la convoluzione $y=xh$, cioè $y(t)=\int x(u)h(t-u)du$ (somma $\sum_k x(k)h(n-k)$ nel discreto). Il teorema discende da linearità e tempo-invarianza applicate alla scomposizione del segnale in impulsi.Sistemi LTI, risposta impulsiva e convoluzione →: qui si lavora direttamente con $T=1$.

Linearità e invarianza temporale

Definizione (invarianza temporale, time invariance). Un sistema è tempo-invariante se traslare l'ingresso traslando la stessa quantità l'uscita: $x[n]\to y[n]$ implica $x[n-n_0]\to y[n-n_0]$ per ogni intero $n_0$.

Definizione (linearità, linearity). Se $x_1\to y_1$ e $x_2\to y_2$ allora $\alpha x_1+\beta x_2\to\alpha y_1+\beta y_2$ per ogni $\alpha,\beta$. Sono due proprietà insieme: scalamento (raddoppiare $x$ raddoppia $y$) e sovrapposizione (la risposta a una somma è la somma delle risposte).

Definizione (sistema LTI). Un sistema lineare e tempo-invariante (linear time-invariant).

Test dell'invarianza. Si confrontano due percorsi: (A) prima il sistema, poi il ritardo dell'uscita, $y[n-n_0]$; (B) prima il ritardo dell'ingresso, $w[n]=x[n-n_0]$, poi il sistema, $T\{w[n]\}$. Il sistema è tempo-invariante se i due risultati sono uguali per ogni ingresso. Attenzione: nel percorso A il ritardo sostituisce $n$ con $n-n_0$ ovunque nell'espressione di $y[n]$, anche dove $n$ compare come coefficiente.

Esempio svolto ($y[n]=n\,x[n]$). Percorso A: $y[n-n_0]=(n-n_0)\,x[n-n_0]$. Percorso B: $w[n]=x[n-n_0]$ e poi $n\,w[n]=n\,x[n-n_0]$. I due risultati sono diversi (il coefficiente $n$ nel secondo non è stato traslato), quindi non è tempo-invariante. Controllo numerico: con $x=\delta[n]$ e $n_0=1$ il percorso A dà $(n-1)\delta[n-1]=0$, il percorso B dà $n\,\delta[n-1]=\delta[n-1]$.

Esempio ($y[n]=x[n]^2$). A: $y[n-n_0]=x[n-n_0]^2$. B: $w[n]^2=x[n-n_0]^2$. Uguali: tempo-invariante. Ma non è lineare: con $x=\delta$, $(2\delta)^2=4\delta\neq2\delta^2=2\delta$ (verificato).

Esempio ($y[n]=x[-n]$, ribaltamento). A: $y[n-n_0]=x[-(n-n_0)]=x[-n+n_0]$. B: $w[n]=x[n-n_0]$ e $w[-n]=x[-n-n_0]$. Diversi (anticipo contro ritardo): non è tempo-invariante. È però lineare, perché $x_1[-n]+x_2[-n]$ e $\alpha x[-n]$ si comportano bene.

I filtri FIR sono LTI. Invarianza: con $v[n]=x[n-n_0]$, $w[n]=\sum_{k=0}^Mb_kv[n-k]=\sum_kb_kx[(n-n_0)-k]=y[n-n_0]$. Linearità: con $x=\alpha x_1+\beta x_2$, $y[n]=\sum_kb_k(\alpha x_1[n-k]+\beta x_2[n-k])=\alpha y_1[n]+\beta y_2[n]$. Non tutti i sistemi LTI sono descritti da un'equazione di questa forma finita (i filtri IIR hanno anche termini in $y[n-k]$), ma tutti quelli che lo sono sono LTI.

La somma di convoluzione

Sia $h[n]$ la risposta impulsiva di un sistema LTI, cioè l'uscita per $x=\delta[n]$. Per l'invarianza, $\delta[n-k]\to h[n-k]$ per ogni intero $k$. Per la linearità, $x[k]\delta[n-k]\to x[k]h[n-k]$, e sommando su tutti i $k$ (si accetta la sovrapposizione anche di infiniti termini): $$x[n]=\sum_{k=-\infty}^{\infty}x[k]\delta[n-k]\ \longrightarrow\ y[n]=\sum_{k=-\infty}^{\infty}x[k]\,h[n-k].$$ Non si è supposto che $x$ o $h$ siano di durata finita: la formula vale per ogni LTI.

Formula (somma di convoluzione, convolution sum). $$y[n]=x[n]*h[n]=\sum_{k=-\infty}^{\infty}x[k]\,h[n-k]=\sum_{k=-\infty}^{\infty}x[n-k]\,h[k].$$ Un sistema LTI è completamente determinato da $h[n]$. Nel corso la convoluzione si indica con $*$ (sulle slide anche $\circledast$).

Per un FIR di ordine $M$ si ritrova $y[n]=\sum_{k=0}^Mh[k]x[n-k]$ con $h[k]=b_k$: i coefficienti sono la risposta impulsiva. In generale la somma è finita (quindi calcolabile) se almeno uno dei due segnali ha lunghezza finita.

Esempio. $x*\delta[n-n_0]=x[n-n_0]$: convolvere con un impulso traslato traslare il segnale. Per questo un ritardo di $n_0$ campioni è l'LTI con $h=\delta[n-n_0]$.

Come si calcola

Per ogni $n$:

1. si ribalta $h[k]\to h[-k]$;
2. si trasla di $n$ a destra (se $n>0$) o a sinistra: si ottiene $h[n-k]$;
3. si moltiplica campione per campione per $x[k]$, $v[k]=x[k]h[n-k]$;
4. si sommano tutti i campioni di $v[k]$: è $y[n]$.

Regola di controllo: in ogni prodotto $x[k]h[n-k]$ la somma degli indici vale $n$.

Esempio svolto. $x=\{-2,0,1,-1,3\}$ e $h=\{1,2,0,-1\}$, entrambi a partire da $n=0$ (esempio delle lezioni).

• $y[n]=0$ per $n<0$: per $n\le-1$ il $h[n-k]$ ribaltato non si sovrappone a $x$.
• $y[0]=x[0]h[0]=-2$.
• $y[1]=x[0]h[1]+x[1]h[0]=-4+0=-4$.
• $y[2]=x[0]h[2]+x[1]h[1]+x[2]h[0]=0+0+1=1$.
• $y[3]=x[0]h[3]+x[1]h[2]+x[2]h[1]+x[3]h[0]=2+0+2-1=3$.
• $y[4]=x[1]h[3]+x[2]h[2]+x[3]h[1]+x[4]h[0]=0+0-2+3=1$.
• $y[5]=x[2]h[3]+x[3]h[2]+x[4]h[1]=-1+0+6=5$.
• $y[6]=x[3]h[3]+x[4]h[2]=1+0=1$; $y[7]=x[4]h[3]=-3$; $y[n]=0$ per $n>7$.

Risultato (verificato con Python): $y=\{-2,-4,1,3,1,5,1,-3\}$, $n=0,\dots,7$. Le slide del corso riportano gli stessi valori finali; solo nel passaggio intermedio di $y[3]$ i singoli prodotti sono stampati male ($2+0+0+1$ invece di $2+0+2-1$), ma il totale è giusto.

Lunghezza. Se $x$ ha lunghezza $N$ e $h$ lunghezza $L$ (o $x$ ha $N$ campioni e il filtro è di ordine $M=L-1$), $y$ ha lunghezza $N+L-1=N+M$. Con $N=5$ e $L=4$: $8$.

Il metodo tabellare

Per sequenze finite si moltiplicano i due segnali come due numeri su carta, senza riporto. Con $g=\{g_0,\dots,g_3\}$ e $h=\{h_0,h_1,h_2\}$ si scrivono le righe $g_kh_0$, poi $g_kh_1$ spostata di una colonna, poi $g_kh_2$ di due, e si sommano le colonne: $y[0]=g_0h_0$, $y[1]=g_1h_0+g_0h_1$, ..., $y[5]=g_3h_2$.

Esempio. $g=\{1,2,3,4\}$, $h=\{1,-1,2\}$: $y=\{1,1,3,5,2,8\}$ (colonne: $1$; $2-1=1$; $3-2+2=3$; $4-3+4=5$; $-4+6=2$; $8$; verificato). È lo stesso conto del prodotto di polinomi in $z^{-1}$: $(1+2z^{-1}+3z^{-2}+4z^{-3})(1-z^{-1}+2z^{-2})$, legame che la trasformata zeta rende esatto (Proprietà della trasformata zetaProprietà della zeta bilatera con le ROC: linearità (ROC ⊇ intersezione), ritardo x[n-n0] → z^{-n0}X(z) (unilatera: + termini iniziali), convoluzione → prodotto, stabilità BIBO ⇔ circonferenza unitaria nella ROC di H, coniugato X*(z*), inversione temporale X(1/z) con ROC invertita, derivazione n x[n] → -z X'(z), moltiplicazione per a^n → X(z/a) (ROC scalata di |a|), teoremi del valore iniziale e finale (ipotesi sul polo in 1). Con la tabella delle coppie notevoli.Proprietà della trasformata zeta →).

Proprietà della convoluzione e cascata di sistemi

Teorema (proprietà algebriche). Commutativa $x*h=h*x$; associativa $(x_1*x_2)*x_3=x_1*(x_2*x_3)$; distributiva $x*(h_1+h_2)=x*h_1+x*h_2$.

Esempio. $a=\{1,2\}$, $b=\{3,0,1\}$, $c=\{1,-1\}$: $(a*b)*c=a*(b*c)=\{3,3,-5,1,-2\}$ (verificato).

Conseguenza sui sistemi: se l'uscita del primo LTI diventa l'ingresso del secondo (cascata), $y=(x*h_1)*h_2=x*(h_1*h_2)$. Quindi la cascata è equivalente a un solo LTI con $$h_{eq}[n]=h_1[n]*h_2[n],$$ e per la commutatività l'ordine dei due sistemi non conta. Il parallelo (stesso ingresso, uscite sommate) ha $h=h_1+h_2$ per la distributività.

Esempio. Tre sistemi in cascata: $S_1$: $y=x[n]-x[n-1]$; $S_2$: $y=x[n]+x[n-2]$; $S_3$: $y=x[n-1]+x[n-2]$. Le risposte impulsive sono $h_1=\{1,-1\}$, $h_2=\{1,0,1\}$, $h_3=\{0,1,1\}$ e $h_1*h_2=\{1,-1,1,-1\}$, $h=h_1*h_2*h_3=\{0,1,0,0,0,-1\}$, cioè $h[n]=\delta[n-1]-\delta[n-5]$ e $y[n]=x[n-1]-x[n-5]$ (verificato). Una catena di tre filtri si riduce a due soli ritardi.

Applicazione: media mobile di una serie storica

Per smussare una serie rumorosa $x[n]$ (nell'esempio delle lezioni, l'indice Dow Jones in settimane) si usa una media mobile di $L=51$ punti. La versione causale $y[n]=\frac1{51}\sum_{k=0}^{50}x[n-k]$ produce una curva liscia ma spostata a destra di $25$ campioni: il ritardo è $\frac M2=\frac{50}2=25$ (il centro della finestra sta $25$ campioni indietro). La versione centrata $\tilde y[n]=\frac1{51}\sum_{k=-25}^{25}x[n-k]$ è non causale ma sta sulla curva originale. In formule, $\tilde y=y*\delta[n+25]=x*(h*\delta[n+25])$, cioè $\tilde h[n]=h[n+25]$: il filtro centrato è il causale anticipato di $25$ campioni.

Applicazione: filtraggio di immagini (2D)

Per un'immagine il segnale ha due indici, $x[m,n]$ (riga, colonna), e il filtro è una doppia somma: $$y[m,n]=\sum_{k=-M}^{M}\sum_{\ell=-N}^{N}b_{k,\ell}\,x[m-k,n-\ell].$$ I coefficienti formano una piccola matrice, il nucleo (kernel), che scorre sull'immagine. Qui la causalità non ha senso (non c'è un "passato" spaziale) e si usano nuclei simmetrici attorno al pixel centrale.

Rilevamento dei bordi (edge detection). In una dimensione la differenza prima $y[n]=x[n]-x[n-1]$ dà valori positivi sulle salite, negativi sulle discese e zero dove il segnale è costante. In 2D il nucleo $$\begin{pmatrix}\tfrac14&-1&\tfrac14\\-1&3&-1\\\tfrac14&-1&\tfrac14\end{pmatrix}$$ fa lo stesso. I filtri di questo tipo sono passa-alto (high-pass): i coefficienti hanno segno alternato e la loro somma è zero ($4\cdot\frac14+4\cdot(-1)+3=0$). È la condizione perché le zone uniformi, dove tutti i pixel hanno lo stesso valore $c$, diano uscita $c\cdot0=0$ (nero).

Esempio. Su un'immagine con colonne $0$ a sinistra e $10$ a destra di un bordo verticale, l'uscita vale $0$ lontano dal bordo, $-5$ sulla colonna appena a sinistra e $+5$ su quella appena a destra; su un'immagine tutta uguale a $7$ l'uscita è $0$ ovunque (verificato con scipy.signal.convolve2d). Se la somma dei coefficienti non fosse zero, anche le regioni piatte comparirebbero come luminose.

Il comportamento di un LTI su sinusoidi, che spiega perché un nucleo con somma zero tolga le zone costanti (frequenza zero), è il tema di Risposta in frequenza dei sistemi FIRSe all'ingresso di un FIR c'è un esponenziale complesso A e^{jφ} e^{jω̂n} (per ogni n), l'uscita è lo stesso esponenziale moltiplicato per H(ω̂) = Σ b_k e^{-jω̂k}: la frequenza non cambia, ampiezza e fase sono modificate da |H| (guadagno) e ∠H (sfasamento). Per sovrapposizione si trattano somme di sinusoidi. H è periodica di periodo 2π e, per coefficienti reali, hermitiana (|H| pari, fase dispari). La cascata ha H = H1·H2. Esempi: ritardo (fase lineare), differenza prima (passa-alto), {1,2,1} (passa-basso), media mobile di L punti (Dirichlet: |H| = |sin(Lω̂/2)/(L sin(ω̂/2))|, fase lineare -(L-1)ω̂/2).Risposta in frequenza dei sistemi FIR →.

Domande d'esame

1. Mostrare che un sistema LTI è completamente caratterizzato dalla risposta impulsiva e ricavare la somma di convoluzione. Traccia: scomposizione $x=\sum x[k]\delta[n-k]$; invarianza ($\delta[n-k]\to h[n-k]$); linearità e sovrapposizione; formula; osservare che non serve che $x$ e $h$ siano finiti; proprietà commutativa, associativa, distributiva e cascata ($h_{eq}=h_1*h_2$, ordine ininfluente).
2. Definire invarianza temporale e linearità e verificarle per $y[n]=nx[n]$, $y[n]=x[n]^2$, $y[n]=x[-n]$. Traccia: confronto dei percorsi A e B (ritardo dopo / prima del sistema); risultati: nessuno dei tre è LTI ($nx[n]$: lineare ma non tempo-invariante; $x^2$: tempo-invariante ma non lineare; $x[-n]$: lineare ma non tempo-invariante); dimostrare che il FIR è LTI.
3. Calcolare la convoluzione di due sequenze finite e dire quanto è lunga. Traccia: metodo ribalta-trasla-moltiplica-somma o tabella; lunghezza $N+L-1$; regola della somma degli indici.