3.TEORIA FILTRĂRII LI IARE OPTIMALE - comm.pub.ro · PDF file= (matricea de autocorelaţie)

transcript

3.TEORIA FILTRĂRII LI IARE OPTIMALE

3.1 CRITERIUL DE OPTIMIZARE

x(n) y(n) d(n)

Se cunoaşte semnalul staţionar în sens larg, de medie nulă

+ , Semnal util Perturbaţie Dorim un filtru care să extragă semnalul util.

x(n) y(n) d(n)

( ) 1,...,1,0,* −== �nwnh n

( ) ( )( ) ( ) ,....1,0,1

* =−=∗= ∑−

=nknxwnxhny

( ) ( ) ( )∑−

−−=1

kk knxwndne

x(n) y(n) d(n)

Cu notaţiile ( ) ( ) ( )[ ]T�nxnxn 1,..., +−=x ;

[ ] ;,...,, 110

T�www −=w

�� = �� − ��

Funcţie cost: eroarea medie pătratică

� = � �� − ��∗�� − �� = � ��∗�� + �� − �� ∗�� −

−� ��

� ��∗�� = ��2

( ){ } ( ) ( ){ }neneneJ *2 EE ==

� = � �� + � � �� − � � �� −

−� ��

� ��∗�� = ��2 (puterea semnalului dorit)

� �� = � (matricea de autocorelaţie)

� ��∗�� = � (vectorul corelaţiei între semnalul de

intrare şi semnalul dorit)

[ ] ;)1(),...,1(),0( Txdxdxd �rrr +−−=p

Rwwwppw HHHdJ +−−= 2σ

3.2 ECUAŢIILE WIE ER-HOPF

J - funcţie de gradul doi de variabilele complexe wk=ak+jbk, k=0,...,�-1.

0=∇⇒ JJmin J∇ - gradientul complex,

∂∂∂

JJJJ ,...,, 0=

∂∂

=∇−�w

110,...,,

1 1-j ; +j

2 2i i i i i i

J J J J J J

w a b w a b∗

∂ ∂ ∂ ∂ ∂ ∂= = ∂ ∂ ∂ ∂ ∂ ∂

( ) ( ) ( ) ( )

k k0 0

1j jb jb

� �

k xd k xd

k ki i

a r k a r ka b

− −

∂+ =

∂ ∂ = + − − + + − = ∂ ∂

∑ ∑

w p p w

( )xdr i= −

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

( ) ( ) ( )1 1

1j jb j

� �

k l l xx

a a b r l ka b

− −

∂ ∂ = + − + − = ∂ ∂

∑∑

2 k l l xx

k li i

w r l i

∂ ∂

∑∑

∑{ } ;H∇ =w Rw Rw

J∇ = − + =p R w 0

Hessianul transformării: RH 22 =∇= J pozitiv semidefinit, J(w) reprezintă o suprafaţă de forma unui paraboloid având un minim Jmin pentru w=wo care anulează gradientul

pRw =o

pRpwppwwppw

Rwwwppw1222

−−=−=+−−=

=+−−=H

σσσ

( )∑−

=−=−=−

0, 1,...,0),(

lxdxxlo �iirilrw

3.3 PRI CIPIUL ORTOGO ALITĂŢII

Pentru filtrul optim: ( ) ( )nny H

oo xw=

( ) ( ) ( )nndne Hoo xw−=

( ) ( ){ } ( ) ( ){ } ( ) ( ){ }* *E E E H

o o on e n n d n n n= −x x x x w

( ) ( ){ }*Eo o

n e n = − =x p Rw 0

� eroarea este ortogonală pe eşantioanele intrării.

( ) ( ){ } 0x =nen o*E

( ) ( ){ } 1,...,0,0E * −==− �kneknx o

3.3 PRI CIPIUL ORTOGO ALITĂŢII

� ieşirea yo(n) şi eroarea eo(n) corespunzătoare sunt ortogonale

x(n) x(n-1)

x(n-�-1)

( ) ( ){ } 0E * =neny oo

x(n) x(n-1) x(n-�-1)

∗1,ow

∗2,ow

∗−2,�ow

∗−1,�ow

( )nyo

∗0,ow

4. PREDICŢIA LI IARĂ

4.1 Predicţia înainte (directă)

x(n) y(n)

_ + H(z)

x(n-1)

x(n) un proces aleator staţionar cu valoare medie nulă. Se cunosc N eşantioane anterioare Se cunosc N eşantioane anterioare

( ) ( ) ( ) 1,...,2,1 −⇒−−− nX�nxnxnx Pe baza lor se doreşte o estimare a lui :

( ) ( ) ( ),1ˆ1

*1 ∑

=− −=−

Hkn nknxw=Xnx xw

( ) ( ) ( ) ( )[ ] [ ]T�T

www�nxnxnxn ,...,,,,...,2,11 21=−−−=− wx

eroarea de predicţie:

( ) ( ) ( )1ˆ −−= nf� Xnxnxne

Puterea erorii de predicţie: Puterea erorii de predicţie:

( ) .E2

= nePf��

Analogii cu problema filtrării optimale: ( ) ( )nxnd ⇒

( ) ( )1−⇒ nn xx

( ) ( )nenef�⇒ ( ) ( )nene �⇒

�PJ ⇒min

( ) ( ){ } RxxR =−−⇒ 11E nn H

( ) ( ){ } ( ) ( ) ( )[ ]Txxxxxx �rrrnxn −−−=−=⇒ ,...,2,11E *xrp

( ){ } ( )0E 222xxxd rnx === σσ

Se pot prelua direct următoarele rezultate: - ecuaţia Wiener-Hopf (ecuaţia normală)

rRwrRw 1sau −== oo - principiul ortogonalităţii

( ) ( ){ } ( ) ( ){ } 0ˆE1E *1

* ==− − neXnxnenf�n

f� 0x

- Expresia puterii erorii de predicţie, în cazul coeficienţilor optimi,

( ) ( ) oH

x� rrP wrwrwr −=−=−= 002σ

Filtrul predictor:

x(n) x(n-1) x(n-N)

∗−1�w

∗�w

( )1ˆ −nXnx

Filtrul erorii de predicţie inainte

∑ ∑= =

−=−−=�

kk�ko

f� knxaknxwnxne

*, )()()()(

ka k� ,...,1,

=�kw

k� ,...,1,*,

x(n) x(n-1) x(n-�)

1,�a 1, −��a

��a ,

)(nef�

10, =�a

Ecuaţiile Wiener-Hopf extinse:

0o− =r Rw ( )0 H

o �r P− =r w

H Pr 1)0(

��

o� w

şi RN+1 este matricea de autocorelaţie extinsă, de dimensiuni (�+1)x(�+1)

4.2. PREDICŢIA Î APOI (I VERSĂ)

Se cunosc:

( ) ( ) ( ) nX�nxnxnx ⇒+−− 1,,1, ⋯

Se doreşte un estimat al lui

x(n) y(n)

_ + H(z)

x(n-N)

( ) ( )∑=

+−=−�

kkn knxgX�nx

Eroarea de predicţie:

( ) ( ) ( )nb� X�nx�nxne −−−= ˆ

[ ]T= [ ]T�ggg ,...,, 21=g Puterea erorii de predicţie

2E neP b

��

4.2. PREDICŢIA Î APOI (I VERSĂ)Analogii cu problema filtrării optimale:

( ) ( )

( ) ( )�

�nxnd

−⇒

( ) ( ){ } ( ) ( ) ( )[ ] .1...,,1,E ** Txxxxxx

B r�r�r�nxn −=−=⇒ xrp ( ) ( ){ } ( ) ( ) ( )[ ] .1...,,1,E xxxxxx r�r�r�nxn −=−=⇒ xrp

Se preiau:

� Ecuaţia normală

� Puterea erorii de predicţie

*BrRg =

( ) grBT� rP −= 0

� Principiul ortogonalităţii ,

( ) ( ){ } 0x =nen b�

( ) ( ){ } 1,...,1,0,0E * −==− �kneknx b�

4.2. PREDICŢIA Î APOI (I VERSĂ)Filtrul ce realizează predicţia inversă

( ) ( )∑=

+−=−�

kkn knxgX�nx

x(n) x(n-1) x(n-�)

∗�g

)(ˆ 1−− nX�nx

4.2. PREDICŢIA Î APOI (I VERSĂ)Filtrul erorii de predicţie înapoi.

( ) ( ) ( ) ( )∑ ∑= =

−=+−−−=�

kk�k

b� knxcknxg�nxne

−=−=

�kgc k

k�,1

1,...,01,

x(n) x(n-1) x(n-�)

1,�c 1, −��c

)(neb�

0,�c 1, =��c

4.2. PREDICŢIA Î APOI (I VERSĂ)Ecuaţiile Wiener-Hopf extinse pentru predicţia inversă

*B− + =Rg r 0

( )0 BT�r P− =r g

B 0grR *

BT Prr 10

��

4.2. PREDICŢIA Î APOI (I VERSĂ)Relaţie între coeficienţii filtrelor de predicţie directă şi inversă

rRgrgRrgRrRg =⇒=⇒=⇒= **** BBHBTB

gwwg =⇔= ** BB sau

�kwg k�k ,...,1,*1 == +−

�� ac = sau

�kac k��k� ,...,0,*,, == −

( ) ⇒==== wrgrgrgrgr HBHBTBTBT **

puterile erorilor de predicţie sunt identice în cele două cazuri.

4.3 ALGORITMI EFICIE ŢI DE REZOLVARE A ECUAŢIEI ORMALE

A FILTRĂRII LI IARE OPTIMALE

Ecuaţia normală este un sistem Rezolvat prin metoda Gauss rezultă o complexitate de tip Algoritm rapid ar însemna Algoritm rapid ar însemna

4.3.1 Algoritmul Levinson-Durbin

Vom căuta o constantă km, astfel încât să fie posibilă o relaţie de forma:

m m Bm

k−∗−

sau sau

mkakaa kmmmkmkm ,...,0,*,1,1, =+= −−−

0,1 ,10,1 == −− mmm aa

−−−+ *

1000 m

mmmBTm

m mmm BT

−−+

=R aaRr a

Notăm

( )∑−

=−−− −==∆

BTmm mkraar

şi având în vedere forma extinsă a ecuaţiilor Wiener-Hopf pentru predictorul de ordin m-1,

−−

−−+ B

R −mmmm 1

==∆=

−−−−−

0cRaRar

−− 11 mmm

1 0; −−−− +∆=∆+= mmmmmmm PkkPP

1 0; −−−− +∆=∆+= mmmmmmm PkkPP ( )2−=

( )21 1 mmm kPP −= −

10 ≤⇒≥ mm kP

( ) ( ) ( ) ( )0; 000 rPnxnene bf ===

( )∏=

−=�

mm� kPP

4.3.1 Algoritmul Levinson-DurbinObservaţii

� Puterea erorii de predicţie scade o dată cu creşterea ordinului predictorului. � Coeficienţii km - coeficienţi de reflexie Pentru k=m,

mmm ak ,= � Se poate uşor arăta, folosind definiţiile şi principiul ortogonalităţii, că:

( ) ( ){ }nenefb *1E −=∆ ( ) ( ){ }nenef

*111 1E −−− −=∆

unde ( )nef

m 1− - răspunsul filtrului erorii de predicţie directă de ordinul m-1, pentru secvenţa de intrare ( ) ( ) ( ),1,...,1, +−− mnxnxnx

( )11 −− nebm - răspunsul filtrului erorii de predicţie inversă, de ordinul

m-1, la secvenţa ( ) ( ) ( )mnxnxnx −−− ,...,2,1 .

4.3.1 Algoritmul Levinson-DurbinObservaţii

� Având în vedere că: ( ) ( ) ( )nxnene bf == 00

( ) ( ){ } ( ) ( ){ } ( ) ( )111E1E ***000 rrnxnxnenefb =−=−=−=∆

� Cunoscând ∆o şi Po se pot calcula, folosind relaţiile de recurenţă

( )( )

( ) ( )( )01

Pk −=−=

∆−=

( ) ( )�m

:1:1for

1;0 *00

−∆−=

( )21 1 mmm kPP −= −

for mk :1:1=

,1,1, kmmmkmkm akaa −−− +=

( )∑=

−−=∆m

kkmm mkra

4.3.1 Algoritmul Levinson-DurbinComplexitatea aritmetică a algoritmului

În pasul m al algoritmului trebuie efectuate: o împărţire; 2m+1 înmulţiri (două pentru calculul lui Pm, m-1 pentru

reactualizarea coeficienţilor am,k , şi m pentru calculul lui m∆ ). 2m adunări. Pentru efectuarea întregului algoritm, rezultă

∑�

+=+�

��m1

2 3)22(

înmulţiri / împărţiri şi

��m1

Dacă se utilizează o singură unitate aritmetică şi aceasta efectuează o operaţie aritmetică într-o unitate de timp, timpul total de calcul este O(�2) . Când se dispune de � unităţi aritmetice ce pot lucra în paralel timpul de calcul este ( )�� 2logO

4.3.2 Algoritmul Schur -definirea funcţiilor de tip ‘f’

Răspunsul filtrului erorii de predicţie de ordin m la secvenţa de autocorelaţie

∗=−=m

kxximxxkm

fm irakiraiy

0,, )()()(

=k 0 Conform ecuaţiei Wiener_Hopf pentru predictorul de ordin m

Elementele matricei de autocorelaţie sunt

4.3.2 Algoritmul Schur –

definirea funcţiilor de tip ‘f’

==−m

kxxkm mikira

0, ,...,1,0)(

miiy f ,...,1,0)( ==

miiy fm ,...,1,0)( ==

4.3.2 Algoritmul Schur –definirea funcţiilor de tip ‘f’

rezultă că rezultă că

( ) ,0

0 ( )fm

xx mm kk

y a r k P=

= − =∑

definirea funcţiilor de tip ‘b’

Pornind de la predicţia inversă

∗=−=m

kxximxxkm

bm irckirciy

0,, )()()(

Dar *= *

,, kmmkm ac −= aşa încât

)()( * imyiy fm

bm −=

1,...,0,0)( −== miiybm

mbm Pmy =)(

relaţii de recurenţă

Din relaţiile

1,1,1*

,1,1, −−−−−− +=+= kmmkmkmmmkmkm ckaakaa

1,1,1*

, −−− += kmkmmkm cakc se obţin nişte relaţii de recurenţă asemănătoare pentru aceste funcţii: se obţin nişte relaţii de recurenţă asemănătoare pentru aceste funcţii:

)1()()( 11 −+= −− iykiyiy bmm

)1()()( 11* −+= −− iyiykiy b

cu condiţiile iniţiale: )()()( 00 iriyiy xx

4.3.2 Algoritmul Schur –coeficientul de reflexie

În particular 0)1()(0)( 11 =−+⇒= −− mykmymy b

m de unde

)(− myf

−−=

4.3.2 Algoritmul Schur

�k :0for =

)()()( 00 krkyky xxbf ==

end �m :1for =

−−=

)1(1 −− mym

�mi :1for +=

)1()()( 11 −+= −− iykiyiy bmm

end �mi :for =

)1()()( 11* −+= −− iyiykiy b

end end

)(�yP b�� =

4.3.2 Algoritmul Schur –complexitate aritmetică

În pasul m se efectuează: o împărţire, pentru calculul lui mk ; �-m înmulţiri şi �-m adunări, în primul ciclu după i; �-m+1 înmulţiri şi �-m+1 adunări, în al doilea ciclu după i. Rezultă un număr de 2�-2m+2 înmulţiri / împărţiri şi 2�-2m+1 adunări, deci în total deci în total

+=+−�

��m�1

2)222(

înmulţiri / împărţiri şi

=+−�

�m�1

2)122(

adunări.

4.3.2 Algoritmul Schur –Modalitate practică de calcul

Iniţializarea algoritmului. Se constituie “matricea generatoare”

)(...)2()1()0()(...)2()1(0

0�rrrr

�rrr

xxxxxxxx

xxxxxxG

Se constituie matricea

Se calculează

)(...)2()1(0)(...)2(00

'' 11011

�yyy

�yybbb

)(...)2()1(0 111

011�yyy bbb

unde s-au avut în vedere relaţiile de recurenţă şi faptul că 0)1(1 =f

Prin deplasarea spre dreapta cu o unitate a liniei a doua se obţine

=)1(...)1()0(0

)(...)2()1(0'0

�rrr

xxxxxx

xxxxxxG

Raportul elementelor coloanei a doua, cu semnul schimbat, determină primul coeficient de reflexie, k1 .

În continuare se repetă ultimele trei operaţii, deci în pasul m: • Se formează G’m din Gm prin deplasarea spre dreapta cu o

poziţie a liniei a doua. • Se calculează 1+mk ca raport cu semnul schimbat a 1+m

elementelor coloanei m+2 şi se formează matricea 1+mK . • Se calculează

mmm '11 GKG ++ = Procedeul se reia până se calculează toţi coeficienţii de reflexie.

4.3.2 Algoritmul Schur –Variantă paralel de implementare a algoritmului Schur

r y k k

rxx(1) rxx(N-1)

F1 F2 F

rxx(N)

rxx(0) rxx(1) rxx(N-1)

F1 F2 F

B1 B2 B

Variantă paralel de implementare a algoritmului Schur

F2,…,FN,B1,…,BN F1

1 COM a k

2 COM a

4.4 FILTRELE ERORII DE PREDICŢIE4.4.1 Proprietăţi ale filtrelor erorii de predicţie

Vom nota funcţiile de transfer ale filtrelor erorii de predicţie directă şi inversă de ordinul m cu:

( ) ( ) ∑ ∑∑= =

−−

− ===m

fm zazczHzazH

1) Între funcţiile de transfer ale celor două filtre există relaţia

zHzzH f

2) Caracteristicile amplitudine-frecvenţă ale celor două filtre sunt identice.

( ) ( ) ( ) ( )ωωωωω jfm

jmjbm HHHH eeeee * =⇒= −

3) Relaţie de recurenţă. Având în vedere formulele mkakaa kmmmkmkm ,...,0,*

,1,1, =+= −−− rezultă:

( ) ( ) ( )zHzkzHzH bff 1−+= ( ) ( ) ( )zHzkzHzH bmm

11 −

−− +=

4) Filtrul erorii de predicţie directă este de fază minimă. Pentru demonstraţie vom avea în vedere faptul că │km│<1, ceea ce, ţinând seama şi de proprietatea 2 conduce la:

( ) ( ) ( ) 1zpe1111 ==< −−−

− zHzHzHzk fm

Teorema lui Rouché: Teorema lui Rouché: Dacă două funcţii F(z), G(z), sunt analitice pe conturul C din planul z şi în interiorul conturului, şi │G(z)│<│F(z)│ pe contur, atunci funcţia F(z)+G(z) are acelaşi număr de zerouri în interiorul conturului C ca şi F(z).

Fie conturul C cercul │z│=1 şi vom aplica teorema aceasta pentru funcţiile: ( ) ( ) ( ) ( )zHzkzGzHzF b

1 , −−

− ==

C în sens direct trigonometric { } { }1int <=⇒ zC

C în sens invers trigonometric { } { }1int >=⇒ zC

( )fConform teoremei enunţate, dacă ( )zHf

m 1− nu are zerouri în │z│>1,

de aceeaşi proprietate se bucură şi ( )zH fm . Cum ( ) 10 =zH

f , rezultă

prin inducţie completă că ( )zH fm nu are zerouri în afara cercului │z│=1.

5) Filtrul erorii de predicţie inversă este de fază maximă (are toate zerourile în exteriorul cercului │z│=1). Dacă se exprimă ( )zH f

m sub forma

( ) ( ) 1,11

1 <−=∏=

fm zzzzH

1=iavând în vedere proprietatea 1, rezultă

( ) ( ) ( )∏∏=

− −=−=m

mbm zzzzzzH

Nulurile acestei funcţii de transfer sunt de forma 1/zi*, i=1,...,m, şi sunt evident

situate în │z│>1, simetric faţă de zi în raport cu cercul │z│=1.

4.4 FILTRELE ERORII DE PREDICŢIE4.4.2 Forma "latice" de realizare a filtrului erorii de predicţie

( ) ( ) ( )

[ ] ( )( )

[ ] ( )( )1

−−

Relaţii de recurenţă pentru eroarea de predicţie

[ ]( )

( ) ( )1

−−

mBHmmm

( ) ( ) ( )111 111 −=−=− −−− nenn b

BHm xcxa

( ) ( ) ( )111 −+= −− neknene b

4.4 FILTRELE ERORII DE PREDICŢIE

4.4.2 Forma "latice" de realizare a filtrului erorii de predicţie

În mod asemănător se găseşte:

( ) ( ) ( )11 1*

1 −+−= −− neknenef

Cele două relaţii pot fi grupate

( )( )

)(1 nef

)(1 nebm−

)(nebm

)(ne fm

)(0 nef

)(1 nef

)(2 nef

)(nef�

( ) ( ) ( )nxnene bf == 00 - intrarea filtrului

1k �k 2k

)(0 neb )(1 neb

)(2 neb )(neb

Se poate pune problema calculului coeficienţilor kk, cunoscând a�,1,...,a�,�. Pentru aceasta vom porni de la ecuaţia:

mkakaa kmmmkmkm ,...,1,0,*,1,1, =+= −−−

căreia îi vom alătura ecuaţia obţinută din aceasta prin conjugare complexă şi înlocuind k cu m-k. Rezultă sistemul: conjugare complexă şi înlocuind k cu m-k. Rezultă sistemul:

*,1,1,

kmmkmmkmm

kmmmkmkm

−−−−

−−−

din care se calculează am-1,k,

kmmmmkm

kmmmkmkm

−= −−

Cunoscând setul de coeficienţi corespunzători predictorului de ordin �, {a�,k}, se trece, cu formula de mai sus, la cei corespunzători predictorului de ordin �-1, {a�-1,k} şi se determină km-1=am-1,m-1, şi aşa mai departe până la �=1. determină km-1=am-1,m-1, şi aşa mai departe până la �=1.

Cunoscând setul de coeficienţi corespunzători predictorului de ordin �, {a�,k}, se trece, cu formula de mai sus, la cei corespunzători predictorului de ordin �-1, {a�-1,k} şi se determină km-1=am-1,m-1, şi aşa mai departe până la �=1. determină km-1=am-1,m-1, şi aşa mai departe până la �=1. Problema inversă – se cunosc coeficienţii de reflexie ( de exemplu s-au determinat cu alggoritmul Schur) şi se doresc coeficienţii filtrului erorii de predicţie în forma tranversală. Se pormeşte în sens invers, de la filtrul de ordinul 1, pentru care se cunosc şi se măreşte succesiv ordinul.

O proprietate remarcabilă a structurii latice este aceea că se poate mări ordinul predictorului, adăugând pur şi simplu încă o celulă, fără a modifica în rest structura existentă. Faptul că toate celulele au aceeaşi structură este favorabil din punctul de vedere al posibilităţilor de integrare favorabil din punctul de vedere al posibilităţilor de integrare pe scară foarte largă.

3.TEORIA FILTRĂRII LI IARE OPTIMALE - comm.pub.ro · PDF file= (matricea de autocorelaţie)

Documents