Home

Federica EU

1/12

Sergio Cavaliere » 4.Sistemi LTI: convoluzione

Rappresentazione delle sequenze discrete

Vale la relazione:

$x[n] = \sum ^ \infty _{k=- \infty} x[k] \delta [n-k]$

Questa si può verificare considerando le sequenze s_k[n]= x[k]δ[n-k] ognuna delle quali è nulla dappertutto fuorchè per n=k dove vale x[k].

Sommando una infinità numerabile di queste sequenze otterremo il segnale di partenza.

In altro modo per ogni n si può scrivere una relazione analoga alla seguente scritta per n=2:

x[2]= ……+x[-1]δ[2-(-1)]+x[0]δ[2-0]+

x[1]δ[2-1]+x[2]δ[2-2]+x[3]δ[2-+3]+ …..=

….x[-1]·0+x[0]·0+x[1]·0+x[2]·1+x[3]·0+……

Un segnale come somma di impulsi unitari opportunamente ritardati e di ampiezza opportuna.

Somma di convoluzione

Consideriamo la relazione

$x[n]= \sum ^ \infty _{k=- \infty} x[k] \delta [n-k]$

Chiamiamo h_k[n] la risposta del sistema all’impulso unitario ritardato di k: δ[n-k]. Supponiamo cioè che valga la:

$\delta [n-k] \stackrel{transferfunction}{\longrightarrow} h_k[n]$

Se il sistema e lineare allora alla combinazione lineare di impulsi δ[n-k] con coefficienti x[k]. Corrisponderà la combinazione lineare con gli stessi coefficienti delle risposte h_k[n] sarà cioè:

$x[n]\stackrel{transferfun}{\longrightarrow}y[n]= \sum^ \infty _{k=- \infty} x[k]h_k[n]$

Somma di convoluzione (segue)

Se il sistema oltre ad essere lineare è tempo invariante, la risposta laa’impulso ritardato δ[n-k]. Sarà uguale alla risposta all’impulso nell’origine δ[n] ritardata di k. Se quindi chiamiamo h[n] la risposta all’impulso unitario δ[n]

$\delta[n]\stackrel{transferfunction}{\longrightarrow} h[n]$

Sarà

$y[n]= \sum ^ \infty _{k=- \infty} x[k]h[n-k]$

L’operazione fatta sui due segnali x[n] ed h[n] si chiama convoluzione e si denota con il simbolo *. Si può scrivere quindi:

y[n]=x[n] * h[n]

Implementazione della convoluzione

L’operazione di convoluzione può essere interpretata mediante lo schema a fianco:

la risposta impulsiva h[k] vien invertita nel tempo h[-k];
questa h[-k] viene usata come finestra scorrevole (sliding window) lungo il segnale h[n-k];
h[-k] forma i pesi con cui i campioni corrispondenti del segnale vengono moltiplicati per essere accumulati.

La convoluzione quindi può essere vista come una media pesata dei campioni nell’intorno dell’istante di tempo in cui viene calcolata;
Per il calcolo della risposta all’istante k sono utilizzati i campioni immediatamente prima e dopo.

Naturalmente, se la risposta impulsiva ha durata illimitata (IIR) il numero di campioni utilizzato per la convoluzione è infinito e non è fisicamente realizzabile se non con precisione finita cioè trascurando i campioni più lontani.

Nel caso di sistemi FIR, a risposta impulsiva finita, la convoluzione invece è fisicamente realizzabile

Proprietà della convoluzione

Proprietà commutativa

x[n]*h[n]=h[n]*x[n]

In un sistema LTI si possono scambiare segnale e risposta impulsiva senza che il risultato venga alterato.
Inoltre l’ordine in cui vengono messi due sistemi in cascata è irrilevanteProprietà associativa.

Proprietà associativa

x[n]*(h[n]*g[n])=(x[n]*h[n])*g[n]=x[n]*h[n]*g[n]

Proprietà distributiva della convoluzione rispetto alla somma

x[n]*(h[n] + g[n])= x[n]*h[n] + x[n] *g[n]

Le proprietà enunciate permettono le trasformazioni illustrate in figura nella rappresentazione a blocchi dei sistemi.

Realizzazione della convoluzione

Le operazioni necessarie alla convoluzione tra un segnale in ingresso ed un sistema caratterizzzato da una risposta impulsiva sono descritte dal diagramma a blocchi in figura.

Il segnale x[n] entra in una catena di ritardi (registri o locazioni di memoria) organizzati come un registro a scorrimento.

Ad ogni passo i campioni x[n] x[n-1]…….x[n-M+1] sono moltiplicati rispettivamente per i campioni:
h[0] h[1] h[M-1].

Questi prodotti sono sommati per dare il campione n-mo y[n] dell’uscita.

La convoluzione per sistemi di risposta impulsiva lunga M richiede quindi M prodotti ed M addizioni; essa è quindi computazionalmente relativamente costosa.

Per questo a volte si preferisce come vedremo una elaborazione in Frequenza.

Diagramma a blocchi della convoluzione.

Casualità per sistemi LTI

Si dice causale un sistema la cui risposta dipende solo dal valore presente e da quelli passati dell’ingresso.

Nel caso LTI per cui vale la:

$y[n]=x[n] \otimes h[n] = \sum ^ \infty _{k=- \infty} x[k]h[n-k]$

se l’output dipende solo dai valori passati e presente dell’ingresso saranno nulli i coefficienti h[n-k] in cui k>n e quindi n-k<0 cioè posto l=n-k:

h[l] = 0 per l<0

La risposta impulsiva dunque deve avere campioni nulli per tempi negativi.
Questo si verifica anche nella figura relativa all’operazione di convoluzione già vista in cui, una risposta non nulla per tempi negativi causa l’uso di campioni futuri x[n] x[n+1] ….. per il calcolo del campione n-mo.

In tal modo il sistema non è causale in quanto non rispetta il principio di causa/effetto per cui l’effetto non può anticipare la causa.

Casualità per sistemi LTI (segue)

Abbiamo dato in precedenza una definizione di stabilità per sistemi in generali. Vediamo ora questa che cosa comporta per sistemi LTI-
Un sistema con ingresso x[n] ed uscita y[n] si dice stabile (per ingressi limitati) se

$\exists X:|x[n]|< X \Rightarrow \exists Y :|y[n]|Y \forall n \in Z$

se cioè ad ingresso limitato in modulo corrisponde uscita limitata.

Si può dimostrare (la dimostrazione è riportata estesamente nel materiale allegato alla lezione) che:

Condizione necessaria e sufficiente per la stabilità di un sistema LTI è che la risposta impulsiva sia sommabile in modulo cioè

$\sum ^{k= \infty} _{k= - \infty} |h[k]| < \infty$

Una conseguenza immediata è che i sistemi FIR a risposta impulsiva finita sono stabili, e che i sistemi a risposta impulsiva non tendente a 0 al divergere del tempo non sono stabili. Tra i sistemi visti fino ad ora il sistema accumulatore non è stabile, il sistema media di 2M+1 campioni

$y[n]= \sum ^{k=M} _{k= - M} |x[k]|$

è invece stabile.

Sistemi LTI in 2D

Per segnali in più di una dimensione, come nel caso delle immagini o anche nel caso meno comune 3D, si estendono i concetti e le definizioni viste nel caso di segnali uni-dimensionali.
La ricostruzione di un segnale a partire dai suoi campioni si ottiene dalla formula:

$x[n,m]= \sum ^{k= \infty} _{k=- \infty} \sum ^{\infty} _{l= - \infty} x[k,l] \delta [n-k, n-l]$

in cui l’impulso unitario è definito in modo ovvio.
Ragionando in modo analogo rispetto al caso 1D si ricava quindi la formula che lega ingresso ed uscita di un sistema LTI bidimensionale:

y[n,m]=x[n,m]*δ[n,m]

$y[n,m]= \sum ^{k= \infty} _{k=- \infty} \sum ^ {\infty} _{l=- \infty} x [k,l]h[n-k, n-l]$

Anche in questo caso si può fare riferimento al modello di convoluzione che usa una finestra scorrevole sui dati (sliding window) che appunto è la risposta all’impulso unitario.

Sistemi LTI in 2D (segue)

Nel caso, ad esempio, del filtro che calcola la media in 2D la risposta impulsiva ha l’aspetto in figura: i valori dell’immagine usati per la media sono i punti in cui la risposta impulsiva è non nulla e sono oltre al punto corrente di coordinate (n,m) gli otto punti ad esso adiacenti sul piano dell’immagine, in tutto 3×3 cioè 9 punti. Nel caso generale questa risposta impulsiva può avere come supporto un numero arbitrario di punti nelle due dimensioni; la risposta impulsiva può avere in linea di principio estensione infinita. Nel caso delle immagini rispetto al caso unidimensionale le risposte impulsive di sistemi usati in pratica sono decisamente meno estesi. Una durata di k campioni nel caso monodimensionale diventa una maschera di estensione k² nel caso bidimensionale, con conseguente esplosione del numero di operazioni necessarie alla convoluzione.
Se si tiene presente poi che le immagini sono esse stesse caratterizzate dal quadrato, quando si passa dalle dimensioni dei due lati al numero di pixel, il numero di convoluzioni necessarie è molto più consistente di quello necessario nel caso monodimensional.
Un filtro di buone prestazioni in questo caso può avere anche durata di 128-256 o più campioni, nel caso delle immagini un filtro di dimensioni 3×3 o 4×4 è già un valore elevato.

La finestra scorrevole nel caso di un filtro media in 2D di dimensioni 3x3. L'immagine filtrata verrà costruita in modo tale che l'intensità di ogni suo punto sarà la media delle intensita di nove punti adiacenti.

Rappresentazione delle sequenze mediante impulsi

La relazione già vista

$x[n]= \sum ^{k= \infty} _{k= - \infty} x[k] \delta [n-k]$

può essere espressa mediante il prodotto di convoluzione:

x[n]= x[n]*δ[n]

Convoluzione come prodotto di polinomi
Dati due polinomi verificare che i campioni della convoluzione risultano essere i coefficienti del polinomio prodotto

Matlab possiede funzioni per la manipolazione di polinomi, rappresentati come array di coefficienti:

conv per il prodotto z=conv(p,q)
roots per ricavare le radici di un polinomio z=roots(p)
poly per ricavare numericamente i coefficienti del polinomio di sui si assegnano le radici. Se le radici sono nel vettore z si avrà p=poly(z)

verificare queste funzioni di Matlab, definendo polinomi arbitrari.

Convoluzione come prodotto di polinomi

Dati due polinomi

p(x)=a₂x²+a₁x+a₀

q(x)=b₂x²+b₁x+b₀

la convoluzione dei coefficienti visti come sequenze si sviluppa secondo lo schema solito in cui una sequenza viene invertita nel tempo (time reversed) e fatta scorrere rispetto all’altra.

I campioni della convoluzione risultano essere i coefficienti del polinomio prodotto:

a₂b₂x⁴+(a₂b₁+a₁b₂ )x³+(a₂b₀+a₁b₁+a₀b₂)x²+(a₁b₀+a₀b₁)x+a₀b₀