controlul inteligent

Capitolul 4. Sisteme adaptive

CuprinsCuprinsNoţiuni introductiveTeoria filtrării optimaleTeoria filtrării optimaleFiltre adaptive bazate pe minimizarea erorii medii pătraticepFiltre adaptive bazate pe optimizarea în sensul celor mai mici pătrateExemple de aplicaţii

2

Noţiuni introductiveNoţiuni introductiveFiltru adaptiv = filtru capabil să-și modifice parametrii pe baza unui algoritm recursiv, în scopul optimizării unor caracteristici ale sale.

d(n)

Filtru digital

x(n) y(n) e(n)+−

Algoritm adaptivadaptiv

( ) ( ) ( )e n d n y n= − Funcţie cost J(e(n)) ↓ minimizată( ) ( ) ( )y Funcţie cost J(e(n)) ↓ minimizată

3

• Exemple de funcţii cost:

{ }2( )- eroarea medie pătratică: { }2( )E e n

- suma ponderată a pătratelor erorilor:2( )

nn k e kλ −∑

1k=∑

• Criterii de performanţă:- viteza de convergenţă: numărul de iteraţii necesare pentru a se

j l l ţi fi i t d i tă d ti ăajunge la o soluţie suficient de apropiată de cea optimă; - dezadaptarea: exprimă măsura în care valoarea finală a erorii

medii pătratice diferă faţă de cea dată de filtrul optim;

- capacitatea de urmărire a variaţiilor statistice ale semnalelor,în condiţiile în care acestea nu sunt staţionare;

- complexitatea aritmetică: numărul de operaţii aritmeticeefectuate în fiecare iteraţie şi capacitatea de memorie necesară;efecte ale calcului numeric: erori de cuantizare stabilitate numerică- efecte ale calcului numeric: erori de cuantizare, stabilitate numerică,precizie numerică în reprezentarea coeficienţilor.

4

Identificarea sistemelor

Filtruadaptiv

y(n)−

Sistemx(n)

y(n)

d(n)

e(n)

+Sistem

necunoscutx(n)

Exemplu de aplicaţie: modelarea canalului radio.

5

Modelarea inversă

Filtru adaptiv

Sistem necunoscut

x(n)

y(n)e(n)

−

Întârziere

d(n)+

Exemplu de aplicaţie: egalizarea adaptivă a canalelor de comunicaţii.6

Predicţia

Filtru adaptiv

x(n)Întârziere

Ieşirea 2

y(n)e(n)

−Ieşirea 1

d(n)+

Exemplu de aplicaţie: codarea predictivă a semnalelor vocale.

7

Suprimarea interferenţelor

( ) Filtruadaptiv

x(n)

( )

Semnalul secundar(zgomot)

y(n)

d(n)

e(n)

+

−

d(n)+Semnalul

primar(util + zgomot)

Exemplu de aplicaţie: reducerea zgomotului de fond.

8

Reducerea zgomotului de fond

Sursa de zgomot

voce

g

zgomot 1 zgomot 2

microfon 1 microfon 2

Filtru adaptiv

z2(n)

p

v(n) + z1(n)

≈ z1(n)+

–

vr(n) ≈ v(n)

9

1

0 0.5 1 1.5 2 2.5 3 3.5 4-1

0a1

0 0 5 1 1 5 2 2 5 3 3 5 4-1

0b

0 0.5 1 1.5 2 2.5 3 3.5 4

1

0

1

c

0 0.5 1 1.5 2 2.5 3 3.5 4-1

0

1

d

0 0.5 1 1.5 2 2.5 3 3.5 4-1

secunde

(a) semnalul original; (b) semnalul “corupt” (AWGN - SNR = 10dB);(c) semnalul refăcut - NLMS; (d) semnalul refăcut - RLS.

10

1

0 0.5 1 1.5 2 2.5 3 3.5 4-1

0a1

0 0.5 1 1.5 2 2.5 3 3.5 4-1

0b

0 0.5 1 1.5 2 2.5 3 3.5 4

1

0

1

c

0 0.5 1 1.5 2 2.5 3 3.5 4-1

0

1

d

0 0.5 1 1.5 2 2.5 3 3.5 4-1

secunde

(a) semnalul original; (b) semnalul “corupt” (highway noise);(c) semnalul refăcut - NLMS; (d) semnalul refăcut - RLS.

11

1

0 0.5 1 1.5 2 2.5 3 3.5 4-1

0a1

0 0 5 1 1 5 2 2 5 3 3 5 4-1

0

1b

0 0.5 1 1.5 2 2.5 3 3.5 4

1

0

1

c

0 0.5 1 1.5 2 2.5 3 3.5 4-1

0

1

d

0 0.5 1 1.5 2 2.5 3 3.5 4-1

secunde

(a) semnalul original; (b) semnalul “corupt” (car engine noise);(c) semnalul refăcut - NLMS; (d) semnalul refăcut - RLS.

12

Compensarea ecoului acustic

x(n)x(n)

hCale de ecou acusticĥ(n)

Filtru adaptiv

ZgomotEcou

acustic-Zgomot

ambiental

e(n)d(n)

microfon v(n)

13

(a)

0

0.005

0.01

0 100 200 300 400 500 600 700 800 900 1000-0.01

-0.005

0

30

-20(b)

esantioane

-50

-40

-30

dB

0 0.5 1 1.5 2 2.5 3 3.5 4-60

frecventa [kHz]

Cale de ecou acustic: (a) răspunsul la impuls; (b) răspunsul în frecvenţă.

14

0.1(a)

0.05

0 100 200 300 400 500 600 700 800 900 1000-0.05

0

esantioane

0

(b)

40

-20dB

0 0.5 1 1.5 2 2.5 3 3.5 4

-40

frecventa [kHz]

Cale de ecou acustic: (a) răspunsul la impuls; (b) răspunsul în frecvenţă.

15

(a)

0

0.05

0.1

0 500 1000 1500 2000 2500 3000-0.1

-0.05

0

0 500 1000 1500 2000 2500 3000esantioane

10(b)

-20

-10

0

dB

0 0.5 1 1.5 2 2.5 3 3.5 4-30

20

frecventa [kHz]

Cale de ecou acustic: (a) răspunsul la impuls; (b) răspunsul în frecvenţă.

16

CuprinsCuprinsNoţiuni introductiveTeoria filtrării optimaleTeoria filtrării optimaleFiltre adaptive bazate pe minimizarea erorii medii pătraticepFiltre adaptive bazate pe optimizarea în sensul celor mai mici pătrateExemple de aplicaţii

17

Formularea problemei. NotaţiiFormularea problemei. Notaţiid(n)

Filtru digital

x(n) y(n) e(n)+−digital

Datele:Datele:

{ x(0), x(1), x(2), … } semnalul de intrare

{ d(0), d(1), d(2), … } semnalul “dorit”

Procese aleatoare staţionare în sens larg,Procese aleatoare staţionare în sens larg,cu valori medii nule.

18

Formularea problemei (2)d(n)

wk*

(k 0 N 1)

x(n) y(n) e(n)+−(k = 0,...,N-1)

Notaţii:

N = lungimea filtrului (nr de coeficienţi)N lungimea filtrului (nr. de coeficienţi)

x(n) = [x(n), x(n – 1), …, x(n – N + 1)]T vectorul semnaluluide intrarede intrare

w = [w0, w1, …, wN – 1]T vectorul coeficienţilor filtrului

sistem invariant în timp ( ! NU adaptiv )

19

Formularea problemei (3)d(n)

wk*

(k = 0 N-1)

x(n) y(n) e(n)+−

Relaţii:

semnalul de ieşire

(k 0,...,N 1)

( ) ( )( ) ( ) ( )1

*

0

NH

kk

y n x w n w x n k n−

= ∗ = − =∑ w x

- semnalul de ieşire

0k=

( ) ( ) ( ) ( ) ( ) ( ) ( )1

*N

Hke n d n y n d n w x n k d n n

−= − = − − = −∑ w x

- semnalul eroare:( ) ( ) ( ) ( ) ( ) ( ) ( )

0k

ke n d n y n d n w x n k d n n

=∑ w x

20

Formularea problemei (4)d(n)

wk* = ?

(k = 0,...,N-1)

x(n) y(n) e(n)+−

Problema:* ? tf l î ât ( ) d( )wk* = ? astfel încât y(n) ≈ d(n)

Soluţia:

- minimizarea unei funcţii “cost” J = f{e(n)}

Criteriul de optimizare

21

Criteriul de optimizared(n)

wk* = ?

(k = 0,...,N-1)

x(n) y(n) e(n)+−

Definim funcţia cost:

( ){ }2 di ă i ă( ){ }2J E e n= eroarea medie pătratică

( ! pot fi folosite şi alte funcţii cost )

Scopul anularea gradientului complex

1, , ....,T

NJ J JJ ×

⎡ ⎤∂ ∂ ∂∇ = =⎢ ⎥w 0 1

0 1 1, , ...., N

NJ

w w w ×−

∇ ⎢ ⎥∂ ∂ ∂⎣ ⎦w 0

22

Criteriul de optimizare (2)

( ){ } ( ) ( ){ }2 *J E e n E e n e n= =

( ) ( ) ( ) ( )1 1

* * *

0 0

N Nk k

k kE d n w x n k d n w x n k

− −⎧ ⎫⎡ ⎤ ⎡ ⎤⎪ ⎪= − − ⋅ − −⎢ ⎥ ⎢ ⎥⎨ ⎬⎢ ⎥ ⎢ ⎥⎪ ⎪⎣ ⎦ ⎣ ⎦⎩ ⎭

∑ ∑0 0k k= =⎢ ⎥ ⎢ ⎥⎪ ⎪⎣ ⎦ ⎣ ⎦⎩ ⎭

( ) ( ){ } ( ) ( ){ }1

* *N

kE d n d n w E x n k d n−

= − −∑( )( )*

dxr k( ) ( ){ } ( ) ( ){ }

( ) ( ){ } ( ) ( ){ }0

1 1 1* * * *

kk

N N Nk k i

E d n d n w E x n k d n

w E x n k d n w w E x n k x n i

=− − −

=

− + − −

∑

∑ ∑ ∑2dσ

( )*xdr k= −

( ) ( ){ } ( ) ( ){ }0 0 0

k k ik k i

w E x n k d n w w E x n k x n i= = =

+∑ ∑ ∑dσ

( )xdr k− ( )xxr i k−23

Criteriul de optimizare (3)

( ) ( ) ( )1 1 1 1

2 * * *N N N N

J w r k w r k w w r i k− − − −

= +∑ ∑ ∑ ∑σ ( ) ( ) ( )0 0 0 0

d k xd k xd k i xxk k k i

J w r k w r k w w r i k= = = =

= − − − − + −∑ ∑ ∑ ∑σ

Notaţii:

( ) ( ){ } ( ) ( ) ( )* 0 , 1 , ...., ( 1) Txd xd xdE n d n r r r N= = − − −⎡ ⎤⎣ ⎦p x

Notaţii:

( ) ( ){ }HE n n=R x x

2 H H HdJ = − − +w p p w w Rwσ

24

Ecuaţiile Wiener-Hopfţ p

2 H H HJ + R Funcţia cost2 H H HdJ = − − +w p p w w Rwσ Funcţia cost

Funcţie de gradul doi de variabile complexe wk = ak+jbk

(k = 0, 1, …, N – 1)Minimului funcţiei J anularea gradientului complex:Minimului funcţiei J anularea gradientului complex:

1, , ....,T

NJ J JJ ×

⎡ ⎤∂ ∂ ∂∇ = =⎢ ⎥∂ ∂ ∂⎣ ⎦

w 0 10 1 1

NNw w w ×−

⎢ ⎥∂ ∂ ∂⎣ ⎦w

1J J Jj⎛ ⎞∂ ∂ ∂

= −⎜ ⎟ *1J J Jj⎛ ⎞∂ ∂ ∂

= +⎜ ⎟2k k k

jw a b

= ⎜ ⎟∂ ∂ ∂⎝ ⎠* 2 k kk

ja bw

⎜ ⎟∂ ∂∂ ⎝ ⎠25

Ecuaţiile Wiener-Hopf (2)ţ p ( )

2 H H HJ + R2 H H HdJ = − − +w p p w w Rwσ

{ }H H∂ { }*

1 11

H H

iN N

w− −

∂+

∂

⎧ ⎫⎛ ⎞∂ ∂ ⎪ ⎪

w p p w

( ) ( ) ( ) ( )

( )

1 1*

0 0

12

N Nk k xd k k xd

i i k kj a jb r k a jb r k

a b

i= =

⎧ ⎫⎛ ⎞∂ ∂ ⎪ ⎪= + − − + + −⎨ ⎬⎜ ⎟∂ ∂ ⎪ ⎪⎝ ⎠⎩ ⎭∑ ∑

( )xdr i= −

{ }H H∇ + =w p p w p{ }∇ + =w w p p w p

26

Ecuaţiile Wiener-Hopf (3)

2 H H HdJ = − − +w p p w w Rwσ

{ }*H∂ w Rw{ }

( )( ) ( )

*

1 11i

N Nk k l l xx

w

j a jb a jb r l k− −

∂

⎧ ⎫⎛ ⎞∂ ∂ ⎪ ⎪= + − + −⎨ ⎬⎜ ⎟ ∑ ∑ ( )( ) ( )

( )

0 01

2 k k l l xxi i k l

Nl xx

j j ja b

w r l i

= =−

⎨ ⎬⎜ ⎟∂ ∂ ⎪ ⎪⎝ ⎠⎩ ⎭

= −

∑ ∑

∑ ( )0

l xxl

w r l i=∑

{ }H∇ =w w Rw Rw{ }w

27

Ecuaţiile Wiener-Hopf (4)ţ p ( )2 H H HdJ = − − +w p p w w Rwσ

{ }H

{ }2 { }H H

{ }H∇ =w w Rw Rw

{ }21d Nσ ×∇ =w 0 { }H H∇ − − = −w w p p w p

J∇ = − +w p Rw

2(Pozitiv semidefinit)

J(w) = suprafaţă de forma unui paraboloid, având un minim

Hessianul transformării 2 2J= ∇ =wH R p.s.d

( ) p ţ p ,care anulează gradientul.

28

Ecuaţiile Wiener-Hopf (5)ţ p ( )

J∇ = − +w p Rw Gradientul funcţiei cost

( ) ( )min 0 oJJ J J∇ =

= =w wfi i ţii ti i0J∇w coeficienţii optimi

Ecuaţiile1N oJ ×∇ = ⇒ =w 0 Rw p Ecuaţiile

Wiener-Hopf

( ) ( )1

0, 0,1,..., 1

Nol xx xd

lw r l i r i i N

−− = − = −∑

0l=

29

Ecuaţiile Wiener-Hopf (6)ţ p ( )1

o o−= ⇒ =Rw p w R p Coeficienţii

optimi

2 H H HdJ = − − +w p p w w Rwσ

( ) ( )min 0 oJJ J J∇ =

= =w

w w

2 H H Hd o o o oσ= − − +w p p w w Rw

2 Hd oσ= −p w

2 1H −RJmin = varianţa erorii minime

2 1Hdσ= −p R p

30

Principiul ortogonalităţiip g ţd(n)

wo

x(n) yo(n) eo(n)+−

Filtrul optim

( ) ( )H( ) ( )Ho oy n n= w x ieşirea filtrului optim

( ) ( ) ( )Ho oe n d n n= −w x eroarea filtrului optim( ) ( ) ( )o o p

( ) ( ){ }* ?oE n e n =x ( ) ( ){ }o

31

Principiul ortogonalităţii (2)d(n)

wo

x(n) yo(n) eo(n)+−

Filtrul optim

{ }( ) ( ){ } ( ) ( ) ( ){ }* * Ho oE n e n E n d n n⎡ ⎤= −⎣ ⎦x x x w

{ } { }* H( ) ( ){ } ( ) ( ){ }* HoE n d n E n n= −x x x w

1= − =p Rw 0 1o N×= − =p Rw 0

32

Principiul ortogonalităţii (3)d( )

( )

d(n)

( )wo

x(n) yo(n) eo(n)+−

Filtrul optim

( ) ( ){ }*E n e nx 0 P i i i l t lităţii( ) ( ){ } 1o NE n e n ×=x 0 Principiul ortogonalităţii

În cazul filtrării optimaleÎn cazul filtrării optimale,eroarea este ortogonală pe eşantioanele intrării.

( ) ( ){ } ( ) ( ){ }* *HE E 0Consecinţă: ( ) ( ){ } ( ) ( ){ } 1H

o o o o NE y n e n E n e n ×= =w x 0Consecinţă:

33

Aplicaţiid(n)

1.

wo = ?x(n) y(n) e(n)+− J(w) = ?

J ?Se cunosc:

l i filt l i N 2

Jmin = ?

- lungimea filtrului N = 2

- varianţa semnalului dorit σd2 = 0.9486

1 1 0 5⎡ ⎤- matricea de autocorelaţie a semnalului de intrare

- vectorul de corelaţie

1.1 0.50.5 1.1⎡ ⎤

= ⎢ ⎥⎣ ⎦

R0.5272⎡ ⎤

= ⎢ ⎥pvec o u de co e ţ e0.4458⎢ ⎥−⎣ ⎦

p

34

Aplicaţii 1. (continuare)p ţ

( ) 2 H H HdJ σ= − − +w w p p w w Rw( ) dJ σ= +w w p p w w Rw

( ) [ ] [ ] 00 1 0 1

1

0.5272, 0.9486 0.5272 0.4458

0.4458w

J w w w ww⎡ ⎤⎡ ⎤

= − − − ⎢ ⎥⎢ ⎥−⎣ ⎦ ⎣ ⎦

[ ] 00 1

1

1.1 0.50.5 1.1

ww w

w

⎣ ⎦⎡ ⎤⎡ ⎤

+ ⎢ ⎥⎢ ⎥⎣ ⎦ ⎣ ⎦1⎣ ⎦ ⎣ ⎦

( ) ( )2 2( ) ( )2 20 1 0 1 0 1 0 1, 0.9486 1.0544 0.8961 1.1J w w w w w w w w= − + + + +

35

Aplicaţii 1. (continuare)

60

40

50

30

40

J(w0,w1)

10

20

02

4 -4-2

0

0

-4-2

0 02

4 w0w136

Aplicaţii 1. (continuare)

1o o

−= ⇒ =Rw p w R p Coeficienţiioptimi

EcuaţiileWiener-Hopf optimiWiener Hopf

101.1 0.5 0.5272 0.8363 ow− ⎡ ⎤⎡ ⎤ ⎡ ⎤ ⎡ ⎤

= = = ⎢ ⎥⎢ ⎥ ⎢ ⎥ ⎢ ⎥w10.5 1.1 0.4458 0.7854o

ow= ⋅ = = ⎢ ⎥⎢ ⎥ ⎢ ⎥ ⎢ ⎥− −⎣ ⎦ ⎣ ⎦ ⎣ ⎦ ⎣ ⎦

w

( ) ( )min 0 oJJ J J∇ =

= =w

w w Varianţa erorii minime

( ) ( )2 20 1 0 1 0 1 0 1, 0.9486 1.0544 0.8961 1.1

0 1579

o o o o o o o oJ w w w w w w w w

J

= − + + + +

min0.1579 J= =

37

Aplicaţii(! necorelate)

?≈ q(n)q(n) + v(n)2.

(! necorelate)

semnal util zgomot albσv

2 cunoscut

d(n) = q(n)Abordare pe baza filtrului optim:

x(n) = q(n) + v(n)

d(n) q(n)

y(n) e(n)+wo = ?

x(n) q(n) v(n) y(n) e(n)+−

! D t l t di ibil! Doar acest semnal este disponibil

38

Aplicaţii 2. (continuare)

1o o

−= ⇒ =Rw p w R p Coeficienţiioptimi

EcuaţiileWiener Hopf o op p

optimiWiener-Hopf

( ) ( ){ } ( ) ( ) ( ){ }* * *E n d n E n x n v n⎡ ⎤= =p x x( ) ( ){ } ( ) ( ) ( ){ }( ) ( ){ } ( ) ( ) ( ){ }* *

E n d n E n x n v n

E n x n E n n v n

⎡ ⎤= = −⎣ ⎦

= − +⎡ ⎤⎣ ⎦

p x x

x u v{ } { }( ) ( ){ } ( ) ( ){ } ( ) ( ){ }* * *E n x n E n v n E n v n= − −x u v

= 0 = σ 2[1 0 0]T 0 σv [1, 0, …, 0]

( ) ( ){ } [ ]* 2 1, 0, , 0 TvE n x n σ= −p x …

! Depinde doar de parametrii disponibili39

Aplicaţii 2 ( i )

1

Aplicaţii 2. (continuare)

1o

−=w R p

( ) ( ){ } [ ]1 * 1 2 1 0 0 TE n x n σ− −R x R( ) ( ){ } [ ]1, 0, , 0vE n x n σ= −R x R …

[ ]2 1 1 0 0 T−⎡ ⎤[ ]2 1 1, 0, , 0 To vσ

−⎡ ⎤= −⎣ ⎦w I R …

! Depinde doar de parametrii disponibili:- inversa matricei de autocorelaţie a semnalului de intrare- varianţa zgomotuluivarianţa zgomotului

40

CuprinsCuprinsNoţiuni introductiveTeoria filtrării optimaleTeoria filtrării optimaleFiltre adaptive bazate pe minimizarea erorii medii pătraticepFiltre adaptive bazate pe optimizarea în sensul celor mai mici pătrateExemple de aplicaţii

41

IntroducereIntroducere

d(n)Teoria filtrării Wiener optimale:

x(n)

d(n)

y(n)wo

x(n) y(n) e(n)+−

1o o

−= ⇒ =Rw p w R p Coeficienţiioptimi

EcuaţiileWiener-Hopf o o⇒Rw p w R p optimiWiener-Hopf

( ) ( ){ }*E d( ) ( ){ }HER ( ) ( ){ }E n d n=p x( ) ( ){ }HE n n=R x x

42

Introducere (continuare)Introducere (continuare)

Limitările filtrării Wiener optimale:

- necesită evaluarea matricei de autocorelaţie Rşi a vectorului de corelaţie p.

- necesită evaluarea matricei inverse R–1.

- nu este adecvată mediilor nestaţionare / variabile în timp.

Soluţia:Soluţia:

- determinarea iterativă a coeficienţilor optimi.

w(0) … w(n) w(n +1) … wo

43

Introducere (continuare)( )

d(n)Filtrul Wiener optimal:

wo

x(n) y(n) e(n)+−

Filtru “iterativ” (adaptiv): d(n)

w(n)x(n) y(n) e(n)+

−

44

Metoda pantei descendente maximeMetoda pantei descendente maxime(Steepest descent)

d(n)

x(n)

d(n)

y(n) e(n)+w(n)

x(n) y(n) e(n)+−

( ) ( )1n n Jμ+ = − ∇w wNe “deplasăm” pe suprafaţa de cost,în direcţia inversă pantei maxime de creştere a gradientului,

( ) ( )1n n Jμ+ = ∇ww w

în direcţia inversă pantei maxime de creştere a gradientului,cu un anumit pas μ.

45

Metoda pantei descendente maxime(continuare)

( ) ( )1n n Jμ+ = − ∇ww w

J∇ = − +w p Rw

( ) ( ) ( )1+ +⎡ ⎤⎣ ⎦w w p Rw( ) ( ) ( )1n n nμ+ = − − +⎡ ⎤⎣ ⎦w w p Rw

Notaţie: ( ) ( ) on n= −c w w vectorul eroare a coeficienţilor( ) ( ) o

( ) ( ) ( )1n n nμ+ − = − − − + − +⎡ ⎤ ⎡ ⎤ ⎡ ⎤⎣ ⎦ ⎣ ⎦ ⎣ ⎦w w w w p Rw Rw Rw( ) ( ) ( )1 o o o on n nμ+ − = − − − + − +⎡ ⎤ ⎡ ⎤ ⎡ ⎤⎣ ⎦ ⎣ ⎦ ⎣ ⎦w w w w p Rw Rw Rw

( ) ( ) ( )1 on n nμ+ = − − + +⎡ ⎤⎣ ⎦c c p Rc Rw

( ) ( ) ( )1n nμ+ = −c I R c (ecuaţiile Wiener-Hopf)

46

Metoda pantei descendente maxime(continuare)

( ) ( ) ( )1n n nμ+ = − − +⎡ ⎤⎣ ⎦w w p Rw

( ) ( ) ( )1n nμ+ = −c I R c

⎣ ⎦Pasul μ poate lua orice valoare?

• Analiza stabilităţii algoritmuluiH=R QΛQ descompunerea matricei de autocorelaţieR QΛQ descompunerea matricei de autocorelaţie

0 1 1[ , ,..., ]N−=Q q q q0 1 1diag[ , ,..., ]Nλ λ λ −=Λ

matricea vectorilor proprii (! QHQ = I)matricea valorilor proprii

( )det 0 , 0, 1i i Nλ λ− = ⇒ = −R IH!

0 1 1[ , , , ]NQ q q q p p ( )matriceunitară

, 0, 1 0,Hi i i j ii N i jλ= = − = ≠Rq q q q

!47

Metoda pantei descendente maxime(continuare)(continuare)

( ) ( ) ( )1n nμ+ = −c I R cHR QΛQ

( ) ( ) ( )1 Hn nμ+ = −c I QΛQ c=R QΛQ

( )( ) ( ) ( )1H Hn nμ+ = −Q c I Λ Q c

Notaţie: ( ) ( )Hn n=v Q c vectorul eroare rotit

( ) ( ) ( )1n nμ+ = −v I Λ v

( ) ( ) ( )1 1 , 0, 1k k kv n v n k Nμλ+ = − = −

Condiţii iniţiale: ( ) ( ) ( )0 0 0H Ho= = −⎡ ⎤⎣ ⎦v Q c Q w w

( ) ( ) ( ) , ,k k kμ

( ) ( ) ( )1 0 0 1n k Nλ( ) ( ) ( )1 0 , 0, 1nk k kv n v k Nμλ= − = −

48

Metoda pantei descendente maxime(continuare)

( ) ( ) ( )1 0 , 0, 1nk k kv n v k Nμλ= − = −

(continuare)

Convergenţă (stabilitate):

( ) 0 1 1, 0, 1k kv n k Nμλ→ ⇒ − < = −( ) 0 1 1, 0, 1k knv n k Nμλ→∞

→ ⇒ <

0 2 0 1k Nμλ< < =0 2, 0, 1k k Nμλ< < = −

2 C diţi d

max

20 μλ

< <Condiţia destabilitate

{ }max 0 1 1max , ,..., Nλ λ λ λ −=49

Metoda pantei descendente maxime(continuare)(continuare)

• Analiza convergenţei algoritmului

( ) ( ) ( )1 0 , 0, 1nk k kv n v k Nμλ= − = −

( ) ( )/n τ( ) ( )/ 01 0 1

knk k

k

v n e v

k N

τ

τ

−=

= − = −, 0, 1ln 1k

kk Nτ

μλ= =

−

( ) ( ) ( )H Hn n n⎡ ⎤⎣ ⎦v Q c Q w w ( ) ( )n n= +w w Qv( ) ( ) ( ) on n n= = −⎡ ⎤⎣ ⎦v Q c Q w w ( ) ( )on n= +w w Qv

( ) ( ) ( )/ 0kN N

no k k o k kn v n e vτ−= + = +∑ ∑w w q w q( ) ( ) ( )

1 10o k k o k k

k kn v n e v

= =+ +∑ ∑w w q w q

50

Metoda pantei descendente maxime(continuare)

!( ) ( )/

10k

Nn

o k kk

n e vτ−

== + ∑w w q 0 | n → ∞

!

1 , 0, 1l 1k k Nτ

λ= − = −

ln 1kkμλ−

1 1τ≤ ≤0, 1max minln 1 ln 1k k Nτ

μλ μλ= −− ≤ ≤ −− −

“rapid” “lent”

51

Metoda pantei descendente maxime(continuare)(continuare)

, 0 2αμ αλ

= < <maxλ

"lent"1 1τλ

= − = −

( )min

maxln 1 ln 1

λ ααλ χ

− −R

Numărul condiţionalal matricei R

( ) max

min

λχ

λ=R

min

Matrice “rău” condiţionatămax minλ λ>>

! convergenţă lentă52

Metoda pantei descendente maxime(continuare)(continuare)

• Curba de “învăţare” (learning curve) a algoritmului

( ) ( ){ }2 ?J n E e n= =

( ) ( ) on n= −c w w

( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )H H He n d n n n d n n n n n= =w x w x c x( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )oe n d n n n d n n n n n= − = − −w x w x c x

( ) ( ) ( )Hoe n n n= − c x eroarea filtrului optim

( ) ( ){ } ( ) ( ){ }2 *J n E e n E e n e n= =

{ }*H H⎡ ⎤ ⎡ ⎤( ) ( ) ( ) ( ) ( ) ( ){ }*H Ho oE e n n n e n n n⎡ ⎤ ⎡ ⎤= − −⎣ ⎦ ⎣ ⎦c x x c

53

Metoda pantei descendente maxime(continuare)

( ) ( ) ( ){ } ( ) ( ) ( ){ }* Ho o oJ n E e n e n E e n n n= − x c( ) ( ) ( ){ } ( ) ( ) ( ){ }

( ) ( ) ( ){ } ( ) ( ) ( ) ( ){ }*

o o o

H H HoE n n e n E n n n n− +c x c x x cJmin

= 0(principiul ortogonalităţii)

R

( ) ( ) ( )minHJ n J n n= + c Rc

( ) ( )minH HJ n n= + c QΛQ c

( ) ( )HJ n n= + v Λv( ) ( )minJ n n= + v Λv

54

Metoda pantei descendente maxime(continuare)

( ) ( ) ( )minHJ n J n n= + v Λv( ) ( ) ( )min

( )1 2

min0

Nk k

kJ v nλ

−= + ∑

0k=

( ) ( )1 22

min 1 0N n

k k kJ vλ μλ−

= + −∑ ( ) ( )0k=∑

( )1 22 /

min 0kN

nk kJ e vτλ

−−= + ∑

( )J J în condiţii de stabilitate

( )min0

k kk=∑

( ) minnJ n J→∞

= în condiţii de stabilitate

55

Metoda pantei descendente maxime(continuare)

• AplicaţieSe cunosc:Se cunosc:

- lungimea filtrului N = 2

- valorile iniţiale ale coeficientilor ( )1

01−⎡ ⎤

= ⎢ ⎥−⎣ ⎦w

- matricea de autocorelaţie a semnalului de intrare

- vectorul de corelaţie1.1 0.50 5 1 1⎡ ⎤

= ⎢ ⎥⎣ ⎦

R

⎣ ⎦

0.5 1.1⎣ ⎦0.52720.4458

⎡ ⎤= ⎢ ⎥−⎣ ⎦

p

Măsura performanţei:( ) 2

1020log o n−w w- dezalinierea (misalignment) normată = [dB]10

220log

ow( g ) [ ]

56

Metoda pantei descendente maxime(continuare)(continuare)

• Aplicaţie (continuare)

1o o

−= ⇒ =Rw p w R p Coeficienţiioptimi

EcuaţiileWiener-Hopf

101.1 0.5 0.5272 0.8363

0 5 1 1 0 4458 0 7854o

ow− ⎡ ⎤⎡ ⎤ ⎡ ⎤ ⎡ ⎤

= ⋅ = = ⎢ ⎥⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎣ ⎦ ⎣ ⎦ ⎣ ⎦ ⎣ ⎦

w10.5 1.1 0.4458 0.7854o

ow⎢ ⎥⎢ ⎥ ⎢ ⎥ ⎢ ⎥− −⎣ ⎦ ⎣ ⎦ ⎣ ⎦ ⎣ ⎦

2 Condiţia deAlgoritmul

max

20 μλ

< <Condiţia destabilitate

Algoritmulsteepest descent

( )d λ λ λ( ) 0 1det 0 0.6 1.6 1.25λ λ λ μ− = ⇒ = = ⇒ <R I57

Metoda pantei descendente maxime(continuare)

• Aplicaţie (continuare)

Algoritmul steepest descent

Iniţializare: w(0)

Date: R, p, μ

( ) ( ) ( )⎡ ⎤

ţ ( )

For n = 0, 1, 2, …, nr_iteraţii

( ) ( ) ( )1n n nμ+ = − − +⎡ ⎤⎣ ⎦w w p Rwend

58

Metoda pantei descendente maxime(continuare)

• Aplicaţie (continuare)

Cod MATLAB:

R=[1.1 0.5;0.5 1.1];p=[0.5272;-0.4458];wo=[0.8363;-0.7854];w=[-1;-1];mu=0.01;mu 0.01;W=w;for n=1:1000

w=w+mu*(p-R*w);[ ]W=[W w];

m(n)=20*log10(norm(wo-w)/norm(wo));end

59

Metoda pantei descendente maxime(continuare)

• Aplicaţie (continuare) μ = 0.01

1.5

0

10

0.5

1

-10

0

dB]

-0.5

0h 1

-30

-20

mis

alig

nmen

t [d

w1

-1

0.5

-50

-40

-1.5 -1 -0.5 0 0.5 1 1.5-1.5

h0

0 100 200 300 400 500 600 700 800 900 1000-60

Iteratiiw060

Metoda pantei descendente maxime(continuare)

• Aplicaţie (continuare) μ = 1

1

1.5

-10

0

0.5

1

-40

-30

-20

[dB

]-0.5

0h 1

70

-60

-50

mis

alig

nmen

t

w1

-1

-90

-80

-70

-1.5 -1 -0.5 0 0.5 1 1.5-1.5

h0

0 100 200 300 400 500 600 700 800 900 1000-100

Iteratiiw061

Metoda pantei descendente maxime(continuare)

• Aplicaţie (continuare) μ = 1.3 (! μ < 1.25)

1.5

600

700

0.5

1

400

500

600

[dB

]-0.5

0h 1

300

400

mis

alig

nmen

t [

w1

-1

0.5

100

200

-1.5 -1 -0.5 0 0.5 1 1.5-1.5

h0

0 100 200 300 400 500 600 700 800 900 10000

Iteratiiw062

Metoda pantei descendente maxime(continuare)

• Aplicaţie (continuare) μ = 0.001

1.5

4

5

0.5

1

1

2

3

dB]

-0.5

0h 1

-1

0

1

mis

alig

nmen

t [d

w1

-1

0.5

-4

-3

-2

-1.5 -1 -0.5 0 0.5 1 1.5-1.5

h0

0 100 200 300 400 500 600 700 800 900 1000-5

Iteratiiw063

Algoritmul LMS (Least Mean Square)Algoritmul LMS (Least Mean Square)

Metoda steepest descent :

i ă l i i i R 1

- permite determinarea iterativă a coeficienţilor optimi.

- necesită cunoaşterea matricei de autocorelaţie Ri t l i d l ţi

- nu necesită evaluarea matricei inverse R–1.

şi a vectorului de corelaţie p.

Soluţia:Soluţia:

- estimarea matricei de autocorelaţie R şi avectorului de corelaţie p.

64

Algoritmul LMS (Least Mean Square) (continuare)(continuare)

( ) ( ) ( )1 ⎡ ⎤R

Metoda steepest descent :

( ) ( ) ( )1n n nμ+ = − − +⎡ ⎤⎣ ⎦w w p Rw

Cea mai simplă metodă de estimare:

( ) ( ){ } ( ) ( )ˆH HE n n n n= → =R x x R x x

p

( ) ( ){ } ( ) ( )* *ˆE n d n n d n= → =p x p x

⎡ ⎤( ) ( ) ( ) ( ) ( ) ( ) ( )*1 Hn n n d n n n nμ ⎡ ⎤+ = − − +⎣ ⎦w w x x x w

( ) ( ) ( ) ( ) ( )* Hn n d n n nμ ⎡ ⎤= + −⎣ ⎦w x x w( ) ( ) ( ) ( ) ( )n n d n n nμ ⎡ ⎤= + ⎣ ⎦w x x we*(n)

65

Algoritmul LMS (Least Mean Square) (continuare)(continuare)

Algoritmul LMS:

( ) ( ) ( ) ( )*1n n n e nμ+ = +w w x

d(n)

w(n)x(n) y(n) e(n)+

− Filtruadaptiv

LMS

AlgoritmAlgoritmadaptiv

66

Algoritmul LMS (Least Mean Square) (continuare)

Algoritmul LMS

Date: μ

Iniţializare: w(0) = 0N x 1

For n = 0, 1, 2, …, nr_iteraţii

( ) ( ) ( )e n d n y n= −

( ) ( ) ( )Hy n n n= w x N x , N – 1 +

1 +

end( ) ( ) ( ) ( )*1n n n e nμ+ = +w w x( ) ( ) ( )y

N + 1 x , N +

2N + 1 x 2N +2N + 1 x , 2N +

67

Algoritmul LMS (Least Mean Square) (continuare)

• Analiza convergenţei algoritmului LMS• Analiza convergenţei algoritmului LMS

Criteriul 1 Convergenţa în medie

( ){ } onE n

→∞=w w

Criteriul 2 Convergenţa în medie pătratică

( ) ( ) constantnJ n J→∞

= ∞ =

68

Algoritmul LMS (Least Mean Square) (continuare)(continuare)

• Convergenţa în medie a algoritmului LMS

( ) ( ) ( ) ( )*1n n n e nμ+ = +w w x* H⎡ ⎤( ) ( ) ( ) ( ) ( )* Hn n d n n nμ ⎡ ⎤= + −⎣ ⎦w x x w

( ) ( ) ( ) ( ) ( )*Hn n n n d nμ μ⎡ ⎤= − +⎣ ⎦I x x w x( ) ( ) ( ) ( ) ( )n n n n d nμ μ+⎣ ⎦I x x w x

( ){ } ( ) ( ){ }1E n E nμ μ+ = − +w I R w p( ){ } ( ) ( ){ }μ μp

( ) ( ) on n= −c w w

( ){ } ( ) ( ){ }( ){ } ( ) ( ){ }1E n E nμ+ = −c I R c69

Algoritmul LMS (Least Mean Square) (continuare)( )

( ){ } ( ) ( ){ }1E n E nμ+ = −c I R cHH=R QΛQ

( ) ( )Hn n=v Q c( ){ } ( ) ( ){ }1E n E nμ+ = −v I Λ v

( ){ } ( ) ( ){ }1 0 , 0, 1nk k kE v n E v k Nμλ= − = −{ } { }

( ){ } 0 1 1, 0, 1knE n k Nμλ

→∞→ ⇒ − < = −v

max

20 μλ

< < ( ){ } onE n

→∞=w w

Condiţia de convergenţă în medie

70

Algoritmul LMS (Least Mean Square) (continuare)

• Convergenţa în medie pătratică a algoritmului LMSConvergenţa în medie pătratică a algoritmului LMS

( ) ( ) constantnJ n J→∞

= ∞ =

( ) ( ) ( ) ( )He n d n n n= −w xH H H⎡ ⎤( ) ( ) ( ) ( )H H Ho od n n n n⎡ ⎤= − − −⎣ ⎦w x w w x

( ) ( ) ( )Hoe n n n= − c x( ) ( ) ( )oe n n nc x

( ) ( ) ( ) ( )*1n n n e nμ+ = +w w x* H⎡ ⎤( ) ( ) ( ) ( ) ( )* Hon n e n n nμ ⎡ ⎤= + −⎣ ⎦w x x c

71

Algoritmul LMS (Least Mean Square) (continuare)( )

( ) ( ) ( ) ( ) ( ) ( ) ( )*1 Hon n n e n n n nμ μ+ = + −w w x x x c

– wo – wo

( ) ( ) ( ) ( ) ( ) ( ) ( )*1 Hon n n e n n n nμ μ+ = + −c c x x x c

wo wo

*H⎡ ⎤( ) ( ) ( ) ( ) ( )*Hon n n n e nμ μ⎡ ⎤= − +⎣ ⎦I x x c x

Notaţii: ( ) ( ) ( ){ }Hn E n n=K c c matricea de autocorelaţieNotaţii: ( ) ( ) ( ){ }n E n n=K c c ţa vectorului c(n)

( ) ( ){ }*min o oJ E e n e n= varianţa erorii minime

( ) ( ) ( ){ }1 1 1Hn E n n+ = + + =K c c …2

{ }

( ) ( )( ) 2minn Jμ μ μ= − − +I R K I R R

72

Algoritmul LMS (Least Mean Square) (continuare)

( ) ( ){ } ( ) ( ){ }2 *J n E e n E e n e n= =

( ) ( ) ( ) ( ) ( ) ( ){ }*H HE ⎡ ⎤ ⎡ ⎤( ) ( ) ( ) ( ) ( ) ( ){ }H Ho oE e n n n e n n n⎡ ⎤ ⎡ ⎤= − −⎣ ⎦ ⎣ ⎦c x x c

( ) ( ) ( ) ( ){ }minH HJ E n n n n= + c x x c( ) ( ) ( ) ( ){ }min

( )min exJ J n= + eroarea în exces

( ) ( ) ( ) ( ) ( ){ }exH HJ n E n n n n= c x x c Pp. x(n) – secvenţă aleatoare

gaussiană

{ }⎡ ⎤( ) ( ) ( ) ( ) ( ){ }ex tr H HJ n E n n n n⎡ ⎤= ⎣ ⎦c x x c tr urma unei matrice= Σ valorilor proprii

( ) ( ){ } ( ) ( ){ } ( )tr tr 0H HE n n E n n n⎡ ⎤ >⎡ ⎤⎣ ⎦⎢ ⎥x x c c RK( ) ( ){ } ( ) ( ){ } ( )tr tr 0E n n E n n n⎡ ⎤= = >⎡ ⎤⎣ ⎦⎢ ⎥⎣ ⎦x x c c RK

73

Algoritmul LMS (Least Mean Square) (continuare)

⎡ ⎤( ) ( )ex trJ n n= ⎡ ⎤⎣ ⎦RKH=R QΛQ ( ) ( )tr trH n n⎡ ⎤= = ⎡ ⎤⎣ ⎦⎣ ⎦ΛQ K Q ΛZ

( ) ( )ex tr HJ n n⎡ ⎤= ⎣ ⎦QΛQ K

Q Q ( ) ( )tr trn n⎡ ⎤⎣ ⎦⎣ ⎦ΛQ K Q ΛZ

( ) ( )ex ,1

Nl l l

lJ n z nλ

== ∑

QH H

elementele diagonalei matricei Z(n)

( ) ( ) ( )( ) 2min1n n Jμ μ μ+ = − − +K I R K I R R

1l=QH· QH··Q ·Q

( ) ( ) ( )( ) 21 J+ +Z I Λ Z I Λ Λ( ) ( ) ( )( ) 2min1n n Jμ μ μ+ = − − +Z I Λ Z I Λ Λ

( ) ( ) ( )2 2, , min1 1 , 0, 1l l l l l lz n z n J l Nμλ μ λ+ = − + = −

convergentă dacă 1 1, 0, 1l l Nμλ− < = −20 μ< < Condiţia de convergenţă

max0 μ

λ< <

în medie pătratică

74

Algoritmul LMS (Least Mean Square) (continuare)

( ) ( ) ( )2 2, , min1 1 , 0, 1l l l l l lz n z n J l Nμλ μ λ+ = − + = −

( )

n → ∞ ( ) ( ) ( )2 2, , min1l l l l l lz z Jμλ μ λ∞ = − ∞ +

( ) minJμ( ) min, , 0, 1

2l ll

Jz l N

μμλ

∞ = = −−

( ) ( )1 1N N

lμλ− −

∑ ∑( ) ( )ex , min0 0 2

ll l l

ll lJ z J

μλλ

μλ= =∞ = ∞ =

−∑ ∑

( ) ( ) ( )iJ n J J J= ∞ = + ∞( ) ( ) ( )min exnJ n J J J→∞

= ∞ = + ∞

1min 1 constant

NlJ

μλ−⎛ ⎞= + =⎜ ⎟⎜ ⎟∑min

0 2 ll μλ=⎜ ⎟⎜ ⎟−⎝ ⎠

∑75

Algoritmul LMS (Least Mean Square) (continuare)

• Criterii pentru alegerea pasului algoritmului LMS

2 ?!max

20 μλ

< < ?! λmax – dificil de determinat în practică

1N−[ ]

1max

0tr

Nl

lλ λ

−

== >∑R

[ ] ( ) 22

20xN

μσ

< <

[ ] ( ) 2tr 0xx xNr Nσ= =R x

Dezadaptarea (misadjustment): ( ) 1ex

NlJ

mμλ−∞

= = ∑min 0 2 llJ μλ= −∑

Dacă μ << 1/λ1

2N

lm Nμ μλ σ−

≈ =∑Dacă μ << 1/λmax

02 2l xl

m Nλ σ=

≈ =∑76

Algoritmul LMS (Least Mean Square) (continuare)

• Performanţele algoritmului LMS depind de:

- Pasul de adaptare μ(compromis între viteza de convergenţă şi dezadaptare:pas mare convergenţă rapidă dar dezadaptare mare;pas mic dezadaptare scăzută dar convergenţă lentă.)

- Valorile proprii ale matricei de autocorelaţie asemnalului de intrare(matrice rău condiţionată convergenţă lentă)(matrice rău condiţionată convergenţă lentă)

- Lungimea filtrului adaptiv Ng p(lungime mare convergenţă lentă, dezadaptare mare)

77

Algoritmul LMS (Least Mean Square) (continuare)

• AplicaţieIdentificare de sistem

Filtruadaptiv

y(n)

Si tx(n)

y(n)

d(n)

e(n)

+

−

Sistem necunoscut

x(n)

v(n) zgomot78

Algoritmul LMS (Least Mean Square) (continuare)( )

S l l d i t ( )zgomot alb gaussian [randn]

• Aplicaţie (continuare)

Semnalul de intrare x(n)semnal AR(1) (autoregresiv de ordinul 1)

x(n) = ax(n – 1) + g(n) zg. alb gauss.

[x = filter(1,[1, -a],g)]

N = 640 15

0.2

0.25

Sistemul necunoscut

0 10 20 30 40 50 60-0.1

-0.05

0

0.05

0.1

0.15

E santioane

N = 1280 . 0 6

căi de ecou electric(ITU-T G168)

N = 128

0 2 0 4 0 6 0 8 0 1 0 0 1 2 0- 0 . 0 6

- 0 . 0 4

- 0 . 0 2

0

0 . 0 2

0 . 0 4

E s a n t i o a n e

Zgomotul v(n) zgomot alb gaussian [randn], σv2 = 0.001.

79

Algoritmul LMS (Least Mean Square) (continuare)

• Aplicaţie (continuare)

Funcţie MATLAB pentru algoritmul LMS:Funcţie MATLAB pentru algoritmul LMS:

function [m]=lms(x,d,mu,N,wo);L=length(x);g ( );xf=zeros(N,1);w=zeros(N,1);m=zeros(L,1);m zeros(L,1);for n=1:L

xf=[x(n);xf(1:N-1)];y=w'*xf;y w xf;e=d(n)-y;w=w+mu*xf*e';m(n)=20*log10(norm(wo-w)/norm(wo));m(n)=20*log10(norm(wo-w)/norm(wo));

end80

Algoritmul LMS (Least Mean Square) (continuare)

1 5

N = 64x(n) - randn• Aplicaţie (continuare)

5

1 0 μ = 0 . 0 0 5μ = 0 . 0 1μ = 0 . 0 1 5μ = 0 . 0 3

22 0.0312

xNμ

σ< =

-5

0

nmen

t [dB

]

-1 5

-1 0

Mis

alig

n

3 0

-2 5

-2 0

0 5 0 0 1 0 0 0 1 5 0 0 2 0 0 0 2 5 0 0 3 0 0 0-3 0

It e ra t i i

81

Algoritmul LMS (Least Mean Square) (continuare)( )

1 5

N = 128x(n) - randn• Aplicaţie (continuare)

5

1 0

μ = 0 . 0 0 5μ = 0 . 0 1μ = 0 . 0 1 5 2

2 0.0156xN

μσ

< =

0

5

men

t [dB

]

-1 0

-5

Mis

alig

nm

2 0

-1 5

0 5 0 0 1 0 0 0 1 5 0 0 2 0 0 0 2 5 0 0 3 0 0 0-2 0

It e ra t i i

82

Algoritmul LMS (Least Mean Square) (continuare)

N = 64x(n) - AR(1), a = 0,6• Aplicaţie (continuare)

1 5

5

1 0μ = 0 . 0 0 5

μ = 0 . 0 1μ = 0 . 0 1 5 2

2 0.0186xN

μσ

< =

-5

0

men

t [dB

]

-1 5

-1 0

Mis

alig

nm

3 0

-2 5

-2 0

0 5 0 0 1 0 0 0 1 5 0 0 2 0 0 0 2 5 0 0 3 0 0 0-3 0

It e ra t i i

83

Algoritmul LMS (Least Mean Square) (continuare)

N = 64x(n) - AR(1), a = 0,7• Aplicaţie (continuare)

1 5 0 0 0 5

5

1 0μ = 0 . 0 0 5

μ = 0 . 0 1μ = 0 . 0 1 5

2

-5

0

nmen

t [dB

] 22 0.0077

xNμ

σ< =

-1 5

-1 0

Mis

alig

n

3 0

-2 5

-2 0

0 5 0 0 1 0 0 0 1 5 0 0 2 0 0 0 2 5 0 0 3 0 0 0-3 0

It e ra t i i

84

Variante ale algoritmului LMSg

• Algoritmul NLMS (Normalized LMS)g ( )

Algoritmul LMS: ( ) ( ) ( ) ( )*1n n n e nμ+ = +w w xg ( ) ( ) ( ) ( )1n n n e nμ+ = +w w x

Avantaj: simplitate / complexitate redusă

Problema: alegerea pasului algoritmuluiProblema: alegerea pasului algoritmului

μ = constant = ?

Soluţia: alegerea unui pas “variabil” μ(n)85

Variante ale algoritmului LMS (continuare)

( ) ( ) ( ) ( ) ( )*1n n n e nnμ+ = +w w x

( ) ( ) ( ) ( )He n d n n n= −w x eroarea a priori

( ) ( ) ( ) ( )1Hn d n n nε = − +w x eroarea a posteriori

Scopul: ε(n) = 0 ( ) ( ) ( )1Hd n n n= +w xp ( )

( ) ( ) ( ) ( ) ( ) ( ) ( )H Hn d n n n n e n nε μ⎡ ⎤= − +⎣ ⎦w x x

( ) ( ) ( )1d n n n+w x

⎣ ⎦

( ) ( ) ( ) ( ) ( ) ( ) ( )H Hd n n n n n n e nμ= − −w x x x

( ) ( ) ( ) ( )1 H⎡ ⎤( ) ( ) ( ) ( )1 Hn n n e nμ⎡ ⎤= −⎣ ⎦x x86

Variante ale algoritmului LMS (continuare)Variante ale algoritmului LMS (continuare)

[ e(n) ≠ 0 ]( ) ( ) ( ) ( ) ( )1 0Hn n n e nn με ⎡ ⎤= ⎣ ⎦ =x x [ e(n) ≠ 0 ]( ) ( ) ( ) ( ) ( )1 0n n n e nn με ⎡ ⎤= ⎣ ⎦ =− x x

1( )( ) ( )

1Hn

n nμ =

x x

( ) ( ) ( ) ( )1 2 2

20

NH

kn n x n k n

−

== − =∑x x x

02 pentru 1

k

xN Nσ=

≈ >>

μ(n) depinde de “puterea” semnalului de intrareμ(n) depinde de puterea semnalului de intrare

87

Variante ale algoritmului LMS (continuare)

Consideraţii practice:

( )( ) ( )Hnn n

ηδ

μ =+ x x

Pasul algoritmului NLMS1.

η – pasul normalizat

realizează “compromisul”

δ – parametrul de regularizare

evită împărţirea prin numere miciîntre viteza de convergenţăşi dezadaptare

în situaţia când xH(n)x(n) ≈ 0

Se poate calcula recursiv:2 Se poate calcula recursiv:

( ) ( ) ( ) ( ) ( ) ( )2 21 1H Hn n n n x n x n N= − − + − −x x x x

2.

1 x , 2 +N x , N – 1 +88

Variante ale algoritmului LMS (continuare)

Stabilitatea algoritmului NLMS

g

⎡ ⎤( ) ( ) ( ) ( ) ( )1 Hn n n n e nε μ⎡ ⎤= −⎣ ⎦x x

( ) η ( ) [ ] ( )1n e nε η= −( )

( ) ( )Hnn nημ =

x x(Pp. δ = 0)

Condiţia de stabilitate: ( ) ( )n e nε < 1 1η− <

0 2η< <Parametrul de regularizare δ > 0gnu influenţează stabilitatea algoritmului

89

Variante ale algoritmului LMS (continuare)

Algoritmul NLMS

Date: 0 < η < 2 δ > 0

Iniţializare: w(0) = 0N x 1

For n = 0 1 2 nr iteraţii

Date: 0 < η < 2 , δ > 0

For n = 0, 1, 2, …, nr_iteraţii

( ) ( ) ( )( ) ( ) ( )Hy n n n= w x N x , N – 1 +

( ) ( ) ( )e n d n y n= − 1 +

( )( ) ( )Hn ημ

δ= 1 x , 3 + , 1 /

end( ) ( ) ( ) ( ) ( )*1n n n n e nμ+ = +w w x

( )( ) ( )H n nδ + x x

N + 1 x , N +

end2N + 2 x , 2N + 3 + , 1 /

90

Variante ale algoritmului LMS (continuare)

Observaţie:

Algoritmul NLMS poate fi privit ca o problemă deoptimizare cu constrângeri.

Funcţia cost:

( ) ( ) ( ) ( ) ( ) ( ){ }221 Re 1HJ n n n d n n nλ ⎡ ⎤= + − + − +⎣ ⎦w w w x{ }2 ⎣ ⎦

constrângerea ε(n) = 0norma variaţieimultiplicator Lagrangecoeficienţilor

( ) ( )J n∇ = 0Anularea

( ) ( )( ) ( ) ( )11 1HNn d n n n

J n ×+ = +∇ =w w x

0gradientului:

91

Variante ale algoritmului LMS (continuare)

( ) ( ) ( ) ( ) ( )1112n J n n n nλ+∇ = + − −⎡ ⎤⎣ ⎦w w w x

1N×= 0

( ) ( ) ( )11 λxH(n) · xH(n) ·

( ) ( ) ( )112

n n nλ+ = +w w x

( ) ( ) ( ) ( ) ( ) ( )1H H Hd*(n) – d*(n) –

( ) ( ) ( ) ( ) ( ) ( )112

H H Hn n n n n nλ+ = +x w x w x x

( ) ( ) ( )* 10 Hλ ( )*2e nλ( ) ( ) ( )0

2He n n nλ= − x x ( )

( ) ( )H n nλ =

x x

( ) ( ) ( ) ( )*11n n n e n+ = +w w x NLMS( ) ( )( ) ( )

( ) ( )1 Hn n n e nn n

+ = +w w xx x

NLMS

92

Variante ale algoritmului LMS (continuare)

• AplicaţieIdentificare de sistem

Filtruadaptivadaptiv

y(n)e(n)−

zg. alb gauss.

Sistem necunoscut

x(n) d(n)+zg. alb gauss.[randn]

l AR(1)

v(n)2 0 001

(ITU-T G168)N = 64 / N = 128

semnal AR(1)zg. alb gauss.x(n) = ax(n – 1) + g(n)

t ITU T G168 zg. alb gauss. σv2 = 0.001css_st – ITU-T G168

93

Variante ale algoritmului LMS (continuare)

5

N = 64x(n) - randn• Aplicaţie (continuare)

0

5

η = 0 .1η = 0 .5

!-1 0

-5

nmen

t [dB

]

η = 1η = 1 .5η = 2

!

-2 0

-1 5

Mis

alig

n

-3 0

-2 5

0 5 0 0 1 0 0 0 1 5 0 0 2 0 0 0 2 5 0 0 3 0 0 0It e ra t i i

94

Variante ale algoritmului LMS (continuare)

N = 128x(n) - randn• Aplicaţie (continuare)

5

0 1

0

5 η = 0 . 1η = 0 . 5η = 1η = 1 . 5

2

-1 0

-5

nmen

t [dB

]

η = 2

-2 0

-1 5

Mis

alig

n

-3 0

-2 5

0 5 0 0 1 0 0 0 1 5 0 0 2 0 0 0 2 5 0 0 3 0 0 0It e ra t i i

95

Variante ale algoritmului LMS (continuare)

N = 64x(n) - AR(1), a = 0,7• Aplicaţie (continuare)

0

5

η = 0 . 1η = 0 . 5

-1 0

-5

men

t [dB

]

ηη = 1η = 1 . 5η = 2

-2 0

-1 5

Mis

alig

nm

-3 0

-2 5

0 5 0 0 1 0 0 0 1 5 0 0 2 0 0 0 2 5 0 0 3 0 0 0It e ra t i i

96

Variante ale algoritmului LMS (continuare)

N = 64x(n) - randn• Aplicaţie (continuare)

0 L M S - μ = 0 0 1 5

-5

L M S - μ = 0 . 0 1 5N L M S - η = 1

-1 0

nmen

t [dB

]

-1 5

Mis

alig

0 5 0 0 1 0 0 0 1 5 0 0 2 0 0 0 2 5 0 0 3 0 0 0-2 5

-2 0

0 5 0 0 1 0 0 0 1 5 0 0 2 0 0 0 2 5 0 0 3 0 0 0

It e ra t i i

97

Variante ale algoritmului LMS (continuare)

N = 64x(n) - randn• Aplicaţie (continuare)

6 0 L M S 0 0 1 5x(1500)↑

4 0

5 0L M S - μ = 0 . 0 1 5N L M S - η = 1

x(1500)↑

2 0

3 0

nmen

t [dB

]

0

1 0

Mis

alig

n

3 0

-2 0

-1 0

0 5 0 0 1 0 0 0 1 5 0 0 2 0 0 0 2 5 0 0 3 0 0 0-3 0

It e ra t i i

98

Variante ale algoritmului LMS (continuare)

N = 64x(n) – css_st• Aplicaţie (continuare)(G168)2

-2

0

L M S μ = 0 0 1 5

-6

-4

nmen

t [dB

]

L M S - μ = 0 . 0 1 5N L M S - η = 1

-1 0

-8Mis

alig

n

1 4

-1 2

0

0 5 0 0 1 0 0 0 1 5 0 0 2 0 0 0 2 5 0 0 3 0 0 0-1 4

It e ra t i i

99