Post on 16-Apr-2017
transcript
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