GELE2511_Chapitre6

GELE2511 Chapitre 6 :Convolution discrete

Gabriel Cormier, Ph.D., ing.

Universite de Moncton

Hiver 2013

Gabriel Cormier (UdeM) GELE2511 Chapitre 6 Hiver 2013 1 / 38

Introduction

Contenu

Contenu

Convolution discrete

Convolution de sequences finies

Proprietes

Correlation

Auto-correlation

Applications


Convolution

Convolution

La convolution est une methode pour combiner deux signaux et enproduire un troisieme.

C’est la technique la plus importante en traitement de signaux.

La convolution permet de relier l’entree, la sortie et la reponseimpulsionnelle d’un systeme.

x[n]Systemeh[n]

y[n]

y[n] = x[n] ∗ h[h]


Convolution

Convolution

On a deja vu comment un systeme peut etre caracterise par sareponse impulsionnelle.

Si on connaıt la reponse impulsionnelle d’un systeme, alors on connaıtsa sortie pour n’importe quelle entree.

La convolution permet de calculer la sortie d’un systeme etant donnesl’entree et la reponse impulsionnelle.

Rappel : x[n] ∗ h[n] veut dire la convolution de x[n] et h[n].


Convolution

Signaux discrets et convolution

On peut representer un signal discret comme une somme d’impulsions.

n 0

3

0

3

3δ[n]

x[n]

3δ[n-1]

3δ[n-2] 1δ[n-5] 3δ[n-3]

2δ[n-4]

x[n] = 3δ[n] + 3δ[n− 1] + 3δ[n− 2] + 3δ[n− 3] + 2δ[n− 4] + δ[n− 5]

De facon generale,

x[n] =

∞∑k=−∞

x[k]δ[n− k]


Convolution

Signaux discrets et convolution

Par superposition, la sortie y[n] d’un systeme est la somme des reponsesimpulsionnelles aux entrees x[n] :

0

3

3δ[n]

3δ[n-1]

3δ[n-2] 1δ[n-5] 3δ[n-3]

2δ[n-4]

Système h0[n]

Système h1[n]

Système h2[n]

+

+

+

y[n]

y[n] =

∞∑k=−∞

x[k]h[n− k] = x[n] ∗ h[n]


Convolution Exemples

Exemple 1

Entree : sinusoıde + rampe. Systeme : filtre passe-bas.

0 20 40 60 80−1

0

1

2

3x[n]

n0 10 20 30

0

0.01

0.02

0.03

0.04

0.05h[n]

n0 50 100

−0.5

0

0.5

1

1.5y[n]

n

Sortie : sinusoıde fortement attenue. La sequence de sortie est 111echantillons : Le + Lh − 1, ou Le est la longueur de l’entree (81 ici) et Lh

est la longueur du systeme (31 ici). 81 + 31− 1 = 111.


Convolution Exemples

Exemple 2

Entree : sinusoıde + rampe. Systeme : filtre passe-haut.

0 20 40 60 80−1

0

1

2

3x[n]

n0 10 20 30

−0.5

0

0.5

1h[n]

n0 50 100

−2

−1

0

1

2y[n]

n

Sortie : sinusoıde. La sequence de sortie est 111 echantillons.


Impact de l’entree


On va analyser la convolution d’un systeme simple en detail : oncherche a voir l’impact de chaque entree sur la sortie finale.

On utilisera un systeme simple ayant 4 echantillons, et une entree de6 echantillons.




La sortie a une longueur de 9 echantillons (6 + 4− 1).

0 1 2 3 4 5−2

−1

0

1

2x[n]

n0 1 2 3

−2

−1

0

1

2h[n]

n0 1 2 3 4 5 6 7 8

−2

−1

0

1

2y[n]

n

Selon l’equation de la convolution, la sortie est la somme de chaque entreemultipliee par le systeme complet.




La sortie totale est la somme de chaque sortie yk[n].

0 2 4 6 8−2

−1

0

1

2

y1[n]

n0 2 4 6 8

−2

−1

0

1

2

y2[n]

n0 2 4 6 8

−2

−1

0

1

2

y3[n]

n

0 2 4 6 8−2

−1

0

1

2

y4[n]

n0 2 4 6 8

−2

−1

0

1

2

y5[n]

n0 2 4 6 8

−2

−1

0

1

2

y6[n]

nPoint bleu = l’entree multipliee par le systeme.Point rouge = 0 ajoute pour avoir la bonne longueur de sequence.




On va analyser la sortie produite par la convolution.

On cherche a voir comment chaque point de la sortie est affecte parles entrees et le systeme.




On va analyser le point y[4].

4 points bleuscontribuent a y[4].

y[4] = x[1]h[3]

+ x[2]h[2]

+ x[3]h[1]

+ x[4]h[0]

0 2 4 6 8−2

−1

0

1

2

y1[n]

n0 2 4 6 8

−2

−1

0

1

2

y2[n]

n0 2 4 6 8

−2

−1

0

1

2

y3[n]

n

0 2 4 6 8−2

−1

0

1

2

y4[n]

n0 2 4 6 8

−2

−1

0

1

2

y5[n]

n0 2 4 6 8

−2

−1

0

1

2

y6[n]

n




On va analyser le point y[7].

2 points bleuscontribuent a y[7].

y[4] = x[4]h[3]

+ x[5]h[2]

⇒ base sur moinsd’information.

0 2 4 6 8−2

−1

0

1

2

y1[n]

n0 2 4 6 8

−2

−1

0

1

2

y2[n]

n0 2 4 6 8

−2

−1

0

1

2

y3[n]

n

0 2 4 6 8−2

−1

0

1

2

y4[n]

n0 2 4 6 8

−2

−1

0

1

2

y5[n]

n0 2 4 6 8

−2

−1

0

1

2

y6[n]

n



Convolution : problemes

Les M − 1 points aux bouts sont bases sur moins d’information.(M est la longueur de h[n])

Ceci peut causer des problemes ; il peut y avoir des erreurs dans lesbouts des signaux, a cause de la convolution.

En general, il faut s’attendre que l’information aux bouts d’un signalne soit pas utilisable.



Convolution : problemes

Exemple : une sinusoıde avec un niveau CC, qu’on filtre avec un filtrepasse-haut. Il ne devrait rester que la sinusoıde.

0 20 40 60 80 100−4

−2

0

2

4y[n]

n0 20 40 60 80

−4

−2

0

2

4x[n]

n0 10 20 30

−0.5

0

0.5

1

1.5h[n]

n

utilisable

Seule la region centrale est utilisable.


Sequences finies

Convolution de sequences finies

Il existe quelques methodes pour faire la convolution de sequencesfinies.

La convolution de sequences finies x[n] et h[n] donne une sequencefinie y[n].

Quelques regles a suivre :

L’indice de debut de y[n] est la somme des indices de debut de x[n] eth[n].L’indice de fin de y[n] est la somme des indices de fin de x[n] et h[n].La longueur de y[n] est la somme des longueurs de x[n] et h[n] moins1 : Ly = Lx + Lh − 1


Sequences finies

Methode 1 : Somme des colonnes

Cette methode ressemble un peu a la multiplication faite a la main.

Exemple : Faire la convolution de h[n] = {1↑, 2, 2, 3} et x[n] = {2

↑,−1, 3}.

En appliquant la methode,

h[n] = 1 2 2 3x[n] = 2 -1 3

2 4 4 6-1 -2 -2 -3

3 6 6 9

2 3 5 10 3 9

La sortie est y[n] = {2↑, 3, 5, 10, 3, 9}.


Sequences finies

Methode 2 : ruban glissant

On deplace x[−n] devant h[n] en multipliant a chaque fois.

Exemple : h[n] = {2↑, 5, 0, 4} et x[n] = {4

↑, 1, 3}.

2 5 0 43 1 4

8y[0] = somme = 8

2 5 0 43 1 4

2 20y[1] = somme = 22

2 5 0 43 1 46 5 0

y[2] = somme = 11

2 5 0 43 1 4

15 0 16y[3] = somme = 31

2 5 0 43 1 40 4

y[4] = somme = 4

2 5 0 43 1 4

12y[5] = somme = 12

La sortie est y[n] = {8↑, 22, 11, 31, 4, 12}.


Sequences finies

Methode 3 : polynomes

La convolution est la meme procedure que la multiplication de polynomes.

Exemple : h[n] = {2↑, 5, 0, 4} et x[n] = {4

↑, 1, 3}.

On peut considerer h[n] et x[n] comme des polynomes :

h(z) = 2z3 + 5z2 + 4

x(z) = 4z2 + z + 3

On fait la multiplication (2z3 + 5z2 + 4)(4z2 + z + 3) :

y(z) = 8z5 + 22z4 + 11z3 + 31z2 + 4z + 12

La sortie est y[n] = {8↑, 22, 11, 31, 4, 12}.


Sequences finies

Matlab

La convolution est tres facile avec Matlab. Il s’agit d’utiliser la commandeconv.

>> h = [2 5 0 4];

>> x = [4 1 3];

>> y = conv(h,x)

y =

8 22 11 31 4 12


Proprietes

Proprietes de la convolution

Convolution avec une impulsion :

x[n] ∗ δ[n] = x[n]

Dephasage :x[n] ∗ δ[n− s] = x[n− s]

Convolution avec un echelon :

x[n] ∗ u[n] =∞∑k=0

x[k] = r[k]


Proprietes

Proprietes de la convolution

Commutativite :a[n] ∗ b[n] = b[n] ∗ a[n]

Associativite :

(a[n] ∗ b[n]) ∗ c[n] = a[n] ∗ (b[n] ∗ c[n])

Distributivite :

a[n] ∗ b[n] + a[n] ∗ c[n] = a[n] ∗ (b[n] + c[n])


Convolution periodique


La convolution normale de deux signaux qui sont tous 2 periodiquesn’existe pas.

Il faut alors faire la convolution periodique ou circulaire en utilisantdes moyennes.

Si x[n] et h[n] sont tous deux periodiques avec la meme periode N ,alors leur convolution periodique produira une sequence y[n] qui estperiodique aussi, ayant la meme periode N .




La convolution periodique est notee :

yp[n] = xp[n]~ hp[n]

ou xp[n] veut dire que x[n] est periodique.

Il y a parfois un facteur de normalisation 1/N dans la convolutioncirculaire.




Pour faire la convolution periodique, il faut :

Faire la convolution normale d’une periode de x[n] et h[n]

La reponse aura 2N − 1 echantillons. On ajoute un zero a la fin pouravoir 2N echantillons.

On coupe la reponse en deux moities.

On fait la somme des deux moities.



Exemple

Faire la convolution de hp[n] = {1, 2, 3, 1} et xp[n] = {1, 0, 1, 1}.

h[n] = 1 2 3 1x[n] = 1 0 1 1

1 2 3 10 0 0 0 0

1 2 3 11 2 3 1

1 2 4 4 5 4 1

Premiere moitie 1 2 4 4Deuxieme moitie 5 4 1 0

6 6 5 4

yp[n] = {6, 6, 5, 4}


Correlation

Correlation

La correlation est une methode pour mesurer la similitude entre deuxsignaux.

C’est une technique tres similaire a la convolution.

On l’utilise beaucoup pour enlever le bruit dans des signaux etdetecter des composantes periodiques.


Correlation

Correlation

La correlation permet de comparer deux signaux.

rxh = x[n] ∗ ∗h[n] =∞∑

k=−∞x[k]h[k − n] =

∞∑k=−∞

x[n+ k]h[k]

Il s’agit de faire la convolution de x[n] et h[−n].Remarquer que x[n] ∗ ∗h[n] 6= h[n] ∗ ∗x[n], mais plutotrxh[n] = rhx[−n].


Correlation

Exemple

Pour detecter un avion, on envoie unpulse a un moment donne, puis onrecoit une version attenuee de cepulse, decale dans le temps, etcontenant beaucoup de bruit.

La distance de l’objet depend de l’instant auquel on recoit le pulse.


Correlation

Exemple

Systeme radar : cas ideal.

0 20 40 60 80 100 120 140 160 180 2000

0.5

1Pulse

0 20 40 60 80 100 120 140 160 180 2000

0.5

1Pulse reçu idéal

0 50 100 150 200 250 300 350 400 4500

10

20

Corrélation idéale


Correlation

Exemple

Systeme radar : cas avec bruit.

0 20 40 60 80 100 120 140 160 180 2000

0.5

1Pulse

0 20 40 60 80 100 120 140 160 180 200−5

0

5Signal reçu avec bruit

0 50 100 150 200 250 300 350 400 450

0

10

20

Corrélation


Correlation

Correlation

L’amplitude de chaque echantillon dans le signal de correlation estune mesure de combien le signal recu ressemble au signal original a cepoint-la.

Ceci veut dire qu’un pic se produit a chaque endroit ou le signaloriginal est present dans le signal recu.

L’amplitude du signal de correlation est maximale au point ou lesignal voulu est aligne avec le signal recu.


Correlation

Correlation

La forme du pic dans le signal de correlation n’a pas besoin deressembler au signal voulu. Le but n’est pas recreer le signal original,mais plutot de le detecter.

La correlation est la meilleure facon de detecter un signal connu dansun signal ayant du bruit.

Le pic est plus eleve au-dessus du bruit en utilisant la correlation quetoute autre methode lineaire.

L’utilisation de la correlation pour detecter un signal connu estsouvent appele le filtrage adaptatif (matched filtering).


Auto-correlation

Auto-correlation

Si on fait la correlation d’un signal avec lui-meme, on appelle cecil’auto-correlation.

L’auto-correlation permet d’identifier un signal periodique qui estcache dans du bruit.

Ceci ne permet pas necessairement d’identifier le signal periodique,mais plutot de trouver la periode.

Ensuite, on peut recuperer le signal original par d’autres methodes.


Auto-correlation

Exemple

0 20 40 60 80 100 120 140 160 180 200−4

−2

0

2

4Signal avec bruit

n

0 20 40 60 80 100 120 140 160 180 200−500

0

500Auto−Corrélation

n


Auto-correlation

Exemple 2

On identifie la periodepar auto-correlation.

La correlation du signalbruite avec un traind’impulsions ayant labonne periode permet derecuperer le signaloriginal.

0 20 40 60−1

0

1

2

3Signal original

0 20 40 60−1

0

1

2

3Signal avec bruit

0 20 40 60100

150

200

250

300Autocorrélation

0 20 40 600

5

10

15Corrélation avec train d’impulsions


Conclusion

Conclusion

Les points cles de ce chapitre sont :

Calcul de la convolution

Applications de la convolution.

Calcul de la correlation.


Documents

GELE2511_Chapitre6