Convolutia

    Convolutia este o modalitate matematica de a combina doua semnale pentru a forma un al treilea. Ea este singura tehnica importanta in procesarea digitala a semnalelor. Folosind strategia descompunerii in impulsuri, sistemele sunt descris de un semnal numit raspuns la impuls. Convolutia este importanta deoarece leaga cele trei semnal de interes: semnalul de intrare, semnalul de iesire si raspunsul la impuls. Acest capitol prezinta convolutia din doua puncte diferite de vedere, numite algoritmul de intrare si algoritmul de iesire.

Functia delta si raspunsul la impuls

Figura de mai jos ilustreaza definitia a doi termeni importanti in DSP: functia delta si raspunsul la impuls.

Functia delta		Raspunsul la impuls

Functia delta este un impuls normalizat Toate esantioanele sale au valoarea zero cu exceptia unuia singur care are valoarea unu.

Raspunsul la impuls al unui sistem liniar, notat de regula prin h[n], este semnalul de iesire al unui sistem liniar atunci cand la intrarea s-a aplicat un semnal impuls unitar (functia delta).

Doua sisteme liniare vor avea desigur doua raspunsuri diferite la aplicarea functiei delta. Pe scurt doua raspunsuri la impuls diferite.

Orice impuls poate fi exprimat in functie de functia delta. Spre exemplu, un impuls a[n] care ia valoarea -3 pentru esantionul 7 se poate scrie

Daca h[n] este raspunsul la impul al unui sistem liniar ne putem intreba care este impulsul acestui sistem la semnalul anterior a[n]. Datorita proprietatilor sistemelor liniare se poate arata usor ca raspunsul sistemului este acum

Cu alte cuvinte semnalul de iesire este scalat si deplasat cu aceleasi valori ca si impulsul de intrare.

Convolutia

Sa rezumam acum modul in care un sistem modifica un semnal de intrare pentru a forma semnalul de iesire. 

1. Semnalul de intrare poate fi descompus intr-un set de impulsuri, fiecare dintre ele putand fi privit ca fiind obtinut printr-o scalare si o deplasare a functiei delta.
2. Semnalul de iesire rezultat din fiecare imuls este o versiune scalata si deplasata a functiei de raspuns la impuls.
3. Semnalul de iesire complet poate fi gasit prin adunarea acestor raspunsuri scalate si deplasate.

Cu alte cuvinte, daca cunoastem raspunsul la semnalul delta, putem calcula care va fi raspunsul la orice semnal de intrare posibil. Aceasta insamna ca suntem in posesia intregii informatii despre sistemul liniar. In clar, raspunsul la impuls caracterizeaza complet un sistem liniar.

In anumite aplicatii specifice, functia raspuns la impuls mai poate fi intalnita si sub alte denumiri.

Daca sistemul este considerat un filtru, raspunsul la impuls este numit nucleul filtrului (the filter kernel), nucleul de convolutie, sau simplu nucleu.

In procesarea de imagine, functia raspuns la impuls este numita functia de imprastiere a punctului (the point spread function). 

In toate aceste cazuri, aceste denumiri se refera la acelasi lucru: semnalul produs de un sistem liniar la functia delta.

Convolutia este deci o peratie matematica formala precum adunarea, inmultirea sau integrarea. Asa cum o operatie matematica binara preia doi operanzi pentru a produce un al treilea, analog, convolutia combina doua semnale pentru a forma un al treilea semnal.

Convolutia este utilizata in matematica in multe domenii precum: calculul probabilitatilor si statistica. La sistemele liniare, convolutia este folosita pentru a descrie relatia dintre trei semnale de interes: semnalul de intrare, semnalul de raspuns la impuls i semnalul de iesire.

Figura urmatoare prezinta notatia folosita pentru semnale si pentru operatia de convolutie in cazul sistemelor liniare.

Un semnal de intrare, x[n], ce intra intr-un sistem liniar al carui raspuns la functia delta este h[n] produce la iesire un semnal y[n] care este rezultatul aplicarii operatie de convolutie asupra functiilor x[n] si h[n]

Cu alte cuvinte semnalul de intrare convolutat cu semnalul de raspuns la impuls reprezinta semnalul de iesire. De regula operatia de convolutie este notata folosind caracterul steluta (*) care, din nefericire, in toate limbajele de programare, desemneaza operatia de inmultire.

Fie doua exemple notabile:

Filtrul trece jos

Filtrul trece sus

Atenuatorul inversor

Derivata discreta

    Sa intram acum in detaliile matematice ale convolutiei. In domeniul procesarii digitale a semnalelor, convolutia poate fi inteleasa in doua moduri distincte.

• Primul priveste convolutia din punctul de vedere al semnalului de intrare. Acesta analizeaza modul in care fiecare esantion din semnalul de intrare contribuie la valoarea mai multor puncte ale semnalului de iesire.
• Al doilea mod priveste convolutia din punctul de vedere al semnalului de iesire. Acesta analizeaza modul in care fiecare esantion al semnalului de iesire a primit informatie de la mai multe puncte ale semnalului de intrare.

De retinut ca aceste doua perspective reprezinta moduri diferite de concepere a aceleiasi operatie matematica.

    Primul punct de vedere este important deoarece el permite o intelegere conceptuala a modului in care convolutia opereaza in domeniul procesarii digitale a semnalelor. Al doilea punct de vedere descrie principiile matematice ale convolutiei.

Convolutia din punctul de vedere al semnalului de intrare

Observam ca daca x_k este esantionul k al semnalului de intrare x[n] atunci acesta contribuie la iesire cu un semnal yy^k = x_k h[n-k] (prin h[n-k] intelegem semnalul functie de raspuns deplasat la dreapta cu k unitati).

    Mai precis, daca nucleul are M elemente de valori h_j, cu j intre 1 si M, vor fi afectate elementele cu indicii de la k la k+M-1 ale semnalului de iesire prin adaugarea valorilor

(yy^k)_i+k-1= x_k h_i, cu i de la 1 la M.

Astfel, algoritmul de calcul al convolutiei semnalului de intrare x[n] format din N esantioane cu un nucleu h[n] de M elemente se poate scrie

1. Pentru k de la 1 la N+M-1 initializeaza y_k = 0.
2. Pentru k de la 1 la N si i de la 1 la M calculeaza y_i+k-1 = y_i+k-1 + x_k h_i.

Exemplu de convolutie 9x4

Fie convolutia unui semnal format din 9 esantioane convolutat cu un nucleu format din 4 esantioane.

Componentele semnalului de iesire pentru aceasta convolutie sunt urmatoarele

Exemplu de convolutie 4x9

Inversam acum nucleul cu semnalul de intrare din exemplul anterior. Avem astfel convolutia unui semnal format din 4 esantioane convolutat cu un nucleu format din 9 esantioane.

Componentele semnalului de iesire pentru aceasta convolutie sunt urmatoarele

Convolutia este o operatie comutativa

O simpla comparare a semnalelor de iesire din exemplele anterioare arata ca ele reprezinta o aceeasi functie. Concluzia nu poate fi decat una singura: convolutia este o operatie comutativa. Adica 

a[n]*b[n] = b[n]*a[n]

Algoritmul de convolutie din punctul de vedere al semnalului de intrare

Deoarece in limbajul C vectorii incep cu indicele 0 algoritmul de mai sus trebuie rescris

1. Pentru k de la 0 la N+M-2 initializeaza y_k = 0.
2. Pentru k de la 0 la N-1 si i de la 0 la M-1 calculeaza y_i+k = y_i+k + x_k h_i.

Se obtine astfel algoritmul

#define N 81
#define M 31

long double x[N],h[M],y[N+M-1];

for(int k=0;k<N+M-1;k++)y[k]=0;
for(int k=0;k<N;k++)
  for(int i=0;i<M;i++)
    y[i+k]=y[i+k]+x[k]*h[i];
  }

Programul e mai sus permite convolutarea unui semnal de intrare format din 81 de esantioane cu o functie de raspuns de 31 puncte si produce la iesire un semnal format din 111 puncte (adica 81+31-1).

Convolutia din punctul de vedere al semnalului de iesire

Suntem acum interesati de a analiza care sunt contributiile la fiecare element al semnalului de iesire.

In algoritmul de convolutie identificat anterior

1. Pentru k de la 1 la N+M-1 initializeaza y_k = 0.
2. Pentru k de la 1 la N si i de la 1 la M calculeaza y_i+k-1 = y_i+k-1 + x_k h_i.

observam ca elementul j = i+k-1 primeste contributii de forma x_j-i+1 h_i, pentru i de la 1 la M. Din punct de vedere matematica asta inseamna 

pentru toate valorile j de la 1 la N+M-1 cu j-i+1>0 si j-i+1<=N (deoarece indicii semnalului x[n] trebuie sa fie mai mari sau egali cu 1). Astfel observam ca:

y₁ = h₁x₁
y₂ = h₁x₂ + h₂x₁
y₃ = h₁x₃ + h₂x₂+ h₃x₁
...
y_M = h₁x_M + h₂x_M-1 + ... + h_Mx₁
y_M+1 = h₁x_M+1 + h₂x_M + ... + h_Mx₂
...
y_N = h₁x_N + h₂x_N-1 + ... + h_Mx_N-M+1
...
y_M+N-3 = h_M-2x_N + h_M-1x_N-1  + h_Mx_N-2
y_M+N-2 = h_M-1x_N + h_Mx_N-1
y_M+N-1 = h_Mx_N

Algoritmul de convolutie din punctul de vedere al semnalului de iesire

Pe baza observatiilor anterioare se poate construi algoritmul

#define N 81
#define M 31

long double x[N],h[M],y[N+M-1];

for(int j=0;j<N+M-1;j++)y[j]=0;
for(int j=0;j<N+M-1;j++)
  for(int i=0;i<M;i++)
    if(j-i>=0 && j-i<N) y[j]=y[j]+x[j-i]*h[i];
  }

Adica datorita indicilor bazati la 0 in C algoritmul anterior se traduce in

y₀ = h₀x₀
y₁ = h₀x₁ + h₁x₀
y₂ = h₀x₂ + h₁x₁+ h₂x₀
...
y_M-1 = h₀x_M-1 + h₁x_M-2 + ... + h_M-1x₀
y_M = h₀x_M + h₁x_M-1 + ... + h_M-1x₁
...
y_N-1 = h₀x_N-1 + h₁x_N-2 + ... + h_M-1x_N-M
...
y_M+N-4 = h_M-3x_N-1 + h_M-2x_N-2  + h_M-1x_N-3
y_M+N-3 = h_M-2x_N-1 + h_M-1x_N-2
y_M+N-2 = h_M-1x_N-1

© Cornel Mironel Niculae, 2004-2005

25-Mar-2008