Capitolul 1: Bancuri de ﬁltre - schur.pub.roschur.pub.ro/download/pas/P_fb.pdfCuprins • Bancuri...

Prelucrarea avansata a semnalelor

Capitolul 1: Bancuri de filtre

Bogdan Dumitrescu

Facultatea de Automatica si Calculatoare

Universitatea Politehnica Bucuresti

PAS cap. 1: Bancuri de filtre – p. 1/75

Cuprins

• Bancuri de filtre cu doua canale◦ Decimare si interpolare◦ Identitati remarcabile◦ Reprezentarea polifaza◦ Reconstructie perfecta◦ Bancuri de filtre ortogonale◦ Bancuri de filtre biortogonale◦ Lifting◦ Metode de proiectare

• Bancuri de filtre cu mai multe canale◦ Proprietati generale◦ Bancuri de filtre modulate


Obiectul principal de studiu

• Banc de filtre (BF) cu doua canale• Semnalul de intrare x[n] este filtrat, apoi decimat

• Filtrul H0(z) este de obicei trece-jos, H1(z) trece-sus• Semnale din sub-benzi, y0 si y1, pot fi prelucrate (la început

o sa presupunem ca nu sunt alterate)• Bancul de sinteza face interpolare, apoi filtrare• Ideal, iesirea x[n] este o versiune întârziata a intrarii

-

-

-

-

��

��

��

��

↓2

↓2

↑2

↑2

H0(z)

H1(z)

F0(z)

F1(z)

-

-

-

d- ? --

x y0 x0

y1 x1 x

Banc de analiza Banc de sinteza


Decimare

• Decimatorul cu factorul M efectueaza operatia

-x[n] y[n] = x[Mn]

-��↓M

• Iesirea pastreaza doar fiecare al M -lea esantion al intrarii,eliminându-le pe celelalte

• Relatia între transformatele Z ale intrarii si iesirii este

Y (z) =1

M

M−1∑

ℓ=0

X(

z1/MwℓM

)

, wM = e−j2π

M (1)

• În cazul M = 2 se obtine Y (z) =1

2

(

X(z1/2) + X(−z1/2))


Demonstratie (1)

• Relatie elementara între radacinile de ordinul M ale unitatii

M−1∑

ℓ=0

w−ℓnM =

M−1∑

ℓ=0

ej2πℓn/M =

{

M, daca n mod M = 0

0, altfel(2)

• Daca n mod M = 0, atunci toti termenii din suma sunt 1• Altfel

M−1∑

ℓ=0

ej2πℓn/M =1 − ej2πn

1 − ej2πn/M= 0


Demonstratie (2)

• Termenul drept din (1) poate fi scris

1

M

M−1∑

ℓ=0

X(

z1/MwℓM

)

=1

M

M−1∑

ℓ=0

∞∑

n=−∞

x[n](

z1/MwℓM

)−n

=1

M

∞∑

n=−∞

x[n]z−n/MM−1∑

ℓ=0

w−ℓnM

(2)=

∞∑

n=−∞

x[n]z−n/Mδ[n mod M ]

n←Mn=

∞∑

n=−∞

x[Mn]z−n

= Y (z)


Decimare fara pierderi

• Presupunem ca semnalul initial are spectrul limitat la banda[−π/M,π/M ], deci X(ω) = 0 pentru π/M < |ω| ≤ π

• Spectrul semnalului decimat este

Y (ω) =1

MX(ω/M), ω ∈ [−π, π]

• Spectrul semnalului decimat are aceeasi forma ca spectrulsemnalului initial, dar expandata pe întreg intervalul [−π, π]

• Intuitiv, nu se pierde informatie prin decimare• Aceasta ar fi situatia în bancurile de filtre, daca filtrele ar fi

ideale• Problema (cazul canalului pentru frecvente înalte): luând

M = 2, cum se transforma spectrul unui semnal pentru careX(ω) = 0 pentru |ω| ≤ π/2 ?


Decimare fara pierderi—exemplu

ω

−π π 2π 3π

|Y( ω)|

1/M... ...

ω

−π π−π/M π/M 2π 3π

|X( ω)|1

... ...


Aliere

• Daca spectrul semnalului initial se întinde dincolo defrecventa π/M , atunci spectrul semnalului decimat nu maiare aceeasi forma ca spectrul semnalului initial

• Spectrul semnalului decimat este suma unor portiuni(expandate) ale spectrului initial

• Apare fenomenul de aliere


Aliere—exemplu

ω

−π π−π/M π/M 2π 3π

|X( ω)|1

... ...

ω

−π π 2π 3π

|Y( ω)|

1/M... ...


Interpolare

• Interpolatorul cu factorul M introduce M − 1 zerouri întrefiecare doua esantioane ale semnalului de intrare

y[n] =

{

x[n/M ], daca n mod M = 0

0, altfel

• Notatie uzuala

��↑M -

x[n] y[n]-

• Relatia între transformatele Z ale intrarii si iesirii este

Y (z)def=

∞∑

n=−∞

y[n]z−n =

∞∑

k=−∞

x[k]z−Mk = X(zM )


Transformarea spectrului la interpolare

• Relatia între spectre: Y (ω) = X(Mω)

• Pe intervalul [−π, π], spectrul semnalului interpolat esteobtinut prin alaturarea a M copii (fiecare comprimata de Mori) ale unei perioade a spectrului semnalului initial

• Fenomenul este numit replicare (engl. replication, imaging)• Aplicarea unui filtru trece-jos (ca pe primul canal al BF)

elimina replicile inutile


Transformarea spectrului la interpolare—exemplu

• Pentru M = 3:

ω

−π π

|X( ω)|1

... ...

ω

−π π−π/M π/M

|Y( ω)|1

... ...

ω

−π π−π/M π/M

M

... ...


Ilustrarea ın frecventa a functionarii BF cu doua canale

• Figura—la tabla !• Daca filtrele sunt ideale, atunci semnalele filtrate de H0(z)

si H1(z) ocupa fiecare doar jumatate din spectru• Decimarea cu 2 nu pierde informatie• (Numarul de esantioane în sub-benzi este acelasi cu al

intrarii, deci speram de la început sa nu se piardainformatie)

• Interpolarea extinde spectrul util din fiecare sub-banda petot intervalul [−π, π]

• Filtrele ideale F0(z) si F1(z) pastreaza doar jumatatea utila,în intervalul de frecventa adecvat

• Prin sumare se reface spectrul initial

• Întrebare naturala: ce se întâmpla daca filtrele nu suntideale ?


Interconexiuni cu decimatoare si interpolatoare

• Superpozitie

- --

- --

��

��

��↓M

↓M

↓M

bb bb

bb bb

"" ""

"" ""

- -

- -

u1 u1

u2 u2

- --

a1 a1

a2 a2

v v⇐⇒

• Decimatorul cu factor M si interpolatorul cu factor L comutadoar daca M si L sunt coprimi (demonstratie !)

- -��

��

��

��

↑L ↓M↓M ↑L- -- -⇐⇒?


Identitatile nobile—interpolare

• Daca G(z) e o functie de transfer oarecare, atunci

- -��

��

↑M ↑M- -- -⇐⇒G(z) G(zM )

• Demonstratie: notam u intrarea, v iesirea

• În stânga, dupa filtrare se obtine G(z)U(z), deciV (z) = G(zM )U(zM )

• În dreapta, dupa interpolare se obtine U(zM ), deci din nouV (z) = G(zM )U(zM )

• Demonstrati folosind relatiile în timp !


Identitatile nobile—decimare

• În cazul decimarii, ordinea se inverseaza:

-- ��

��

↓M↓M -- -- ⇐⇒ G(zM )G(z)

• Demonstratie: notam u intrarea, v iesirea

• În stânga se obtine (vezi (1))

V (z) =1

MG(z)

M−1∑

ℓ=0

U(

z1/MwℓM

)

• În dreapta, obtinem aceeasi relatie deoarece, aplicând (1)pentru G(zM ) si tinând seama ca wℓM

M = 1, rezulta

1

M

M−1∑

ℓ=0

G(

zwℓMM

)

= G(z)


Reprezentarea polifaza

• Consideram M = 2

• Fie G(z) un filtru, pe care îl scriem folosind componentelepolifaza

G(z) = G0(z2) + z−1G1(z

2)

• Exemplu: daca G(z) = 1 + 2z−1 + 3z−2 + 4z−3, atunciG0(z) = 1 + 3z−1 si G1(z) = 2 + 4z−1

• Filtrul poate fi implementat prin schema echivalenta

- -

-

-

⇐⇒G(z)

G1(z2)

G0(z2)

z−1?

-?

• Deocamdata nu rezulta nici un avantaj, ba dimpotriva


Reprezentarea polifaza si decimarea

• Filtrarea unui semnal, urmata de decimare, poate firealizata prin schema echivalenta

-��

��

↓2

↓2

↓2

-

-

-

-

-

-

⇐⇒G(z)

G1(z)

G0(z)

z−1?

-?

• Echivalenta este imediata: sumarea comuta cu decimarea,apoi se aplica identitatea nobila pentru decimare, pe fiecareramura a schemei de pe pagina precedenta (G0(z

2),respectiv G1(z

2), comuta cu decimatorul, devenind G0(z),G1(z))


Avantaje

• Avantajul implementarii polifaza este ca operatiile de filtrarese executa la frecventa de doua ori mai mica, cu filtre maiscurte

• În plus, nu se fac operatii inutile• Atunci când decimarea avea loc dupa filtrare, jumatate din

operatiile efectuate la filtrare erau inutile, din moment cejumatate din esantioane erau ignorate


Reprezentarea polifaza si interpolarea

• La interpolare se foloseste de obicei reprezentarea polifazade tip II (componentele polifaza apar în ordine inversa)

G(z) = G1(z2) + z−1G0(z

2)

• Filtrarea unui semnal interpolat poate fi realizata prinschema echivalenta

-��

��

↑2

↑2

↑2

-

-

-

-

-

-

⇐⇒G(z)

G1(z)

G0(z)

z−1?

-?

• Demonstratia se face similar, pe baza comutativitatii si aidentitatii nobile


BF cu doua canale—reprezentare polifaza

• Scriem filtrele BF cu doua canale în reprezentare polifaza• Bancul de analiza, tip I

H0(z) = H00(z2) + z−1H01(z

2)

H1(z) = H10(z2) + z−1H11(z

2)

• Bancul de sinteza, tip II (atentie la indici !)

F0(z) = F10(z2) + z−1F00(z

2)

F1(z) = F11(z2) + z−1F01(z

2)

• Aplicam apoi schemele precedente pentru transformareabancului de filtre


BF cu doua canale—reprezentare polifaza

• Se obtine schema

��

↑2

↑2

-

-

z−1?

-?��

↓2

↓2

-

-

-

-

z−1?

A(z) S(z)

-

-

x

x

y0

y1

• Matricea polifaza de analiza este

A(z) =

[

H00(z) H01(z)

H10(z) H11(z)

]

• Matricea polifaza de sinteza

S(z) =

[

F00(z) F01(z)

F10(z) F11(z)

]


Reconstructie perfecta

• Un banc de filtre poseda reconstructie perfecta (RP) daca

x[n] = x[n − D],

unde D este un întreg pozitiv—întârzierea• O prima conditie este evidenta din reprezentarea polifaza

S(z)A(z) = z−τI2

• Întârzierea este D = 2τ + 1 (deci impara !)• Cea mai simpla solutie A(z) = S(z) = I, adica (verificati !)

H0(z) = 1, H1(z) = z−1, F0(z) = z−1, F1(z) = 1

• Rezulta D = 1

• Aceste filtre sunt inutile, doar arata ca RP este posibila


Exemplu

• Luam A(z) =

[

34z−1 − 1

8(1 + z−2) 14(1 + z−1)

−14(1 + z−1) 1

2

]

si

S(z) =

[

1 −12(1 + z−1)

12(1 + z−1) 3

2z−1 − 14(1 + z−2)

]

• Rezulta S(z)A(z) = z−1I, deci se obtine RP cu D = 3

• Filtrele corespunzatoare sunt

H0(z) = 34z−2 − 1

8(1 + z−4) + 14z−1(1 + z−2) = (−1

8 , 14 , 3

4 , 14 ,−1

8)

H1(z) = −14(1 + z−2) + 1

2z−1 = (−14 , 1

2 ,−14)

F0(z) = z−1 + 12(1 + z−2) = (1

2 , 1, 12)

F1(z) = −12z−1(1 + z−2) + 3

2z−2 − 14(1 + z−4) = (−1

4 ,−12 , 3

2 ,−12 ,−1

8)

• Acestea sunt filtrele 5/3 (LeGall) din JPEG2000


Alta abordare a RP

• Conditia pe matricea polifaza este compacta, dar mai greude manevrat si mai putin intuitiva

• Cautam conditii direct pe filtre• Aplicând (1) obtinem (în schema BF de baza)

Y0(z) =1

2

[

H0(z1/2)X(z1/2) + H0(−z1/2)X(−z1/2)

]

• Dupa interpolare si filtrare pe primul canal, rezulta

X0(z) =1

2F0(z) [H0(z)X(z) + H0(−z)X(−z)]

• Similar, pe al doilea canal

X1(z) =1

2F1(z) [H1(z)X(z) + H1(−z)X(−z)]


Functii de transfer ın BF

• Relatie intrare-iesire poate fi scrisa

X(z) = Td(z)X(z) + Ta(z)X(−z)

• Functia de transfer de distorsie (se aplica direct intrarii)

Td(z) =1

2[H0(z)F0(z) + H1(z)F1(z)]

• Functia de transfer de aliere (se aplica intrarii modulate)

Ta(z) =1

2[H0(−z)F0(z) + H1(−z)F1(z)]

• Valorile ideale sunt Td(z) = z−D, Ta(z) = 0

• Problema: ce semnal are transformata Z egala cu X(−z) ?Cum arata spectrul lui ?


Eliminarea structurala a alierii

• Erorile de RP datorate alierii pot fi eliminate prin alegerea

F0(z) = H1(−z)

F1(z) = −H0(−z)(3)

• Rezulta Ta(z) = 0

• Reamintire: daca G(z) e filtru trece-jos, atunci G(−z) estetrece-sus

• Observam deci ca relatiile de mai sus nu contrazic cerintaca H0(z) si F0(z) sa fie trece-jos iar H1(z) si F1(z) trece-sus

• Mai departe presupunem conditia (3) satisfacuta

• Deci RP se rezuma la conditia Td(z) = z−D, unde

Td(z) =1

2[H0(z)H1(−z) − H0(−z)H1(z)] (4)


Reconstructie aproape perfecta

• Uneori se poate renunta la cerinta îndeplinirii exacte aconditiei de RP, pentru a simplifica proiectarea sau a obtinefiltre cu performante mai bune

• De asemenea, depinzând de natura prelucrarii semnalelordin sub-benzi, e posibil ca RP sa fie inutila

• In aceste situatii se lucreaza cu reconstructie aproximativa(notata RAP, reconstructie aproape perfecta; în engleza,nearly perfect reconstruction)

• RAP se poate obtine euristic sau impunând conditii precisede tipul

‖Td(z) − z−D‖ ≤ ε

• De exemplu, folosind norma infinit

|Td(ω) − e−jDω| ≤ ε, ∀ω ∈ [−π, π]


BF ortogonale

• Vom discuta doar despre filtre FIR. Notam N0 si N1 gradelelui H0(z) and H1(z)

• BF ortogonale au N0 = N1 = N impar si se bazeaza pealegerea

H1(z) = −z−NH0(−z−1) (5)

• Daca H0(z) =∑N

k=0 hkz−k, atunci

H1(z) =∑N

k=0(−1)khN−kz−k

• In plus, din relatia (3), rezulta ca

F0(z) = H1(−z) = −(−z)−NH0(z−1) = z−NH0(z

−1)

F1(z) = −H0(−z) = z−NH1(z−1)

(6)

• Deci filtrele de sinteza sunt inversele celor de analiza


BFO—raspunsuri ın frecventa

• Din (5) rezulta|H1(ω)| = |H0(π − ω)|

• Deci raspunsul în frecventa al filtrului trece-sus este cel alfiltrului trece-jos oglindit fata de ω = π/2

• Din (6), conditia de RP Td(z) = z−N se poate scrie

H0(z)H0(z−1) + H1(z)H1(z

−1) = 2

• Rezulta|H0(ω)|2 + |H1(ω)|2 = 2, ∀ω

• Deci raspunsurile celor doua filtre sunt "complementare"


BFO—exemplu de raspunsuri ın frecventa

• Un exemplu de BFO cu N = 19

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1−80

−70

−60

−50

−40

−30

−20

−10

0

10

Frequency (ω / π)

Mag

nitu

de (

dB)


BFO—conditia de RP

• Folosind (5) and (6), functia de transfer de distorsie este

Td(z) = z−N[

H0(z)H0(z−1) + H0(−z)H0(−z−1)

]

• Notam (filtrul produs, simetric)

P (z) = H0(z)H0(z−1) =

∑Nk=−N pkz

−k

• Pentru ca P (z) + P (−z) are toti coeficientii puterilor impareegali cu zero, conditia de RP este

p2ℓ = δℓ, ∀ℓ = 0 : (N − 1)/2 (7)

• Rezulta Td(z) = z−N , deci RP cu D = N

• Coeficientii pk depind patratic de cei ai lui H0(z), deciimpunerea conditiei (7) nu e simpla


Conditie pe componentele polifaza

• Scriem H0(z) = H00(z2) + z−1H01(z

2)

• Filtrul produs capata forma

P (z) = H00(z2)H00(z

−2) + H01(z2)H01(z

−2)

+ z−1H01(z2)H00(z

−2) + zH00(z2)H01(z

−2)

• Primii doi termeni contin puterile impare, deci conditia deRP este

P0(z)def= H00(z)H00(z

−1) + H01(z)H01(z−1) = 1 (8)


BFO—matricea polifaza de analiza

• Punând H1(z) = H10(z2) + z−1H11(z

2), din (5) rezulta ca(notam N = (N − 1)/2)

H10(z) = z−NH01(z−1), H11(z) = −z−NH00(z

−1)

• Matricea polifaza de analiza are deci forma

A(z) =

[

H00(z) H01(z)

z−NH01(z−1) −z−NH00(z

−1)

]

• Tinând seama de (8) rezulta ca

AT (z−1)A(z) = I

• Matricea A(z) este paraunitara (definitie)


Ce ınseamna ortogonalitate ?

• Punând z = ejω, rezulta ca

AT (e−jω)A(ejω) = I

• Deci matricea A(ejω) este unitara pentru orice frecventa ω

• Sistemul (cu 2 intrari, 2 iesiri) A(z) este lossless• Rezulta ca energia (puterea) semnalului de intrare se

conserva la iesire

• Într-un BFO, energia (totala) în sub-benzi este identica cucea de la intrare


BFO—matricea polifaza de sinteza

• Se poate demonstra (exercitiu !) ca matricea polifaza desinteza are forma

S(z) = z−NAT (z−1)

• Rezulta caS(z)A(z) = z−NI

• Se confirma RP, cu întârzierea D = 2N + 1 = N


BFO—reprezentarea latice

• Se poate demonstra ca orice matrice FIR lossless se poatedescompune astfel

A(z) = GN+1∆(z)GN . . .G2∆(z)G1

cu

Gk =

[

ck −sk

sk ck

]

, ∆(z) =

[

1 0

0 z−1

]

• Matricele Gk sunt rotatii Givens (c2k + s2

k = 1), deci matriceortogonale

• Matricea ∆(z) e lossless


BFO—implementare de tip latice

• Bancul de analiza

��

↓2

↓2

-

-

z−1

z−1 z−1

?

xβ

^ ^ ^

� � �

α1 α2 αN+1

−α1 −α2 −αN+1

-

-

- -

-

-

-

· · ·

• Matricele Gk se împart la ck

• Rezulta un factor de corectie β

• Bancul de sinteza

z−1 z−1

^ ^^

� ��

−α2 −α1−αN+1

α2 α1αN+1

· · ·

��

↑2

↑2

z−1?

-? y

- - - -

- -


Bancuri de filtre QMF

• Bancurile de filtre QMF (quadrature mirror filter) suntcaracterizate de alegerea H1(z) = H0(−z)

• Istoric, au fost primele propuse, datorita implementariisimple

• Raspunsurile în frecventa au proprietati similare BFO• Spre deosebire de BFO, nu se poate obtine RP în general

• Singurul BF QMF cu RP este cel cu H0(z) = (1 + z−1)/2

• Reprezentare polifaza: H0(z) = H00(z2) + z−1H01(z

2)

• Rezulta H1(z) = H00(z2) − z−1H01(z

2)


Implementare eficienta


A(z) =

[

H00(z) H01(z)

H00(z) −H01(z)

]

• Deci implementarea BF QMF se poate face prin schema(verificati partea de sinteza !)

��

↑2

↑2

z−1?

-?��

↓2

↓2

-

-

z−1?

x

y

-

-

H00(z) H01(z)

H01(z) H00(z)

-

-

-

-^ ^

� �

−1 −1- -


BF biortogonale

• Bancurile de filtre în care matricele polifaza nu suntortogonale se numesc biortogonale

• Presupunând RP, relatia S(z)A(z) = z−τI spune camatricele S(z) si A(z) sunt ortogonale una pe cealalta

• In cazul RAP, clasificarea ortogonal-biortogonal se aplicaprin extensie, desi formal incorect

• (Deci QMF ar intra la biortogonale . . . )• Filtrele 5/3 sunt un exemplu simplu de BF biortogonal


Alte proprietati dorite ale BF

• Faza liniara (filtrele au coeficienti simetrici)◦ poate fi obtinuta pentru BF biortogonale (dar nu e

obligatorie)◦ imposibila pentru BF ortogonale

• H0(z) nu schimba semnalul constant si taie completsemnalul de frecventa maxima (−1)n, adica H0(1) = 1,H0(−1) = 0

• H1(z) are proprietati inverse: H1(1) = 0, H1(−1) = 1

• Conditii similare pentru F0(z), F1(z) (cu 2 în loc de 1)• Aceste conditii pot fi impuse pentru toate tipurile de BF• Justificarea lor: constructia de wavelets


Proprietati generale—recapitulare

• Bancurile de filtre cu doua canale au urmatoarele proprietatireferitoare la faza, întârziere si reconstructie perfecta

Tip Relatii Faza D RP

Ort. H1(z) = −z−NH0(−z−1) NL N RP, RAP

QMF H1(z) = H0(−z) L, NL ≤ N RAP

Biort. H0(z), H1(z) L, NL ≤ N0+N1

2 RP, RAP

• De obicei se doreste întârziere mica a BF• Cu RAP, se poate obtine si întârziere fractionara


Lifting

• Schema de lifting în doi pasi

��

↑2

↑2

-

-

z−1?

-?��

↓2

↓2

-

-

z−1? ? ?

? ?

x

x

Λ1(z) Λ1(z)Λ2(z) Λ2(z)

+ −

6 6

6 6

+ −

y0

y1

• Acest BF poseda RP prin constructie !• Orice numar de pasi este acceptabil• Filtrele Λi(z) sunt de obicei FIR si scurte• Orice BF FIR poate fi reprezentat prin lifting• De obicei, aceasta reprezentare este cea mai eficienta

pentru implementare


Relatia cu matricea polifaza


A(z) =

[

1 Λ2

0 1

][

1 0

Λ1 1

]

=

[

1 + Λ2Λ1 Λ2

Λ1 1

]

• Matricea polifaza de analiza a filtrelor 5/3 (scalata sideplasata în timp, ceea ce se poate usor realiza cu blocuride întârziere suplimentare) se obtine cu

Λ1(z) = −1

2(1 + z−1), Λ2(z) =

1

4(1 + z)


Transformari reversibile prin lifting

• Schema de lifting ramâne RP chiar daca blocurilecomponente sunt neliniare !

• Un BF este reversibil (integer-to-integer)◦ daca semnalul de intrare x[n] are valori întregi, atunci

semnalele din sub-benzi, y0[n] si y1[n] au valori întregi◦ daca poseda RP

• Utilitate: codare fara pierderi


Lifting cu rotunjire

• Daca Λ1(z) este FIR, primul pas de lifting este

y{1}1 [n] = y

{0}1 [n] +

∑

i λ1[i]y{0}0 [n − i]

• Pentru a obtine valori întregi atunci când intrarea are valoriîntregi, se rotunjeste rezultatul la cel mai apropiat întreg

• Deci, se înlocuieste expresia de mai sus prin

y{1}1 [n] = y

{0}1 [n] +

⌊

12 +

∑

i λ1[i]y{0}0 [n − i]

⌋

• Facând aceeasi modificare pentru toti pasii, se obtine otransformare reversibila

• În "frecventa" (transformarea fiind neliniara, nu se poatevorbi despre frecventa în sens propriu), transformarea nueste departe de proprietatile BF original


DWT—transformarea wavelet discreta

• Formal, DWT este obtinuta prin prelucrarea (recursiva a)semnalului din sub-banda joasa cu acelasi BF

• Deci, semnalul y0 este prelucrat de BF de analiza,obtinându-se semnalele y00 si y01

• Mai departe, y00 este prelucrat de BF de analiza,obtinându-se semnalele y000 si y001, etc.

• Practic se folosesc doar câteva nivele (trei, mai sus)• Reconstructia se face cu BF de sinteza, în ordine inversa (si

cu grija la sincronizare, datorita întârzierilor posibil diferite)

• În cazul unor filtre ideale, benzile de frecventa sunt: [0, π/8]pentru y000, [π/8, π/4] pentru y001, [π/4, π/2] pentru y01,[π/2, π] pentru y1

• Mai multe despre wavelets—în semestrul viitor


Proiectarea bancurilor de filtre

• Tipuri de metode◦ Rapide si simple, care nu garanteaza un rezultat optim

din nici un punct de vedere◦ Bazate pe optimizare

• In general, doar optimizarea BF ortogonale poate fiformulata ca o problema convexa (obtinându-se deci BFoptim pentru probleme de dimensiuni moderate—gradulfiltrelor de ordinul sutelor)

• Pentru filtrele QMF si biortogonale se utilizeaza metode deoptimizare locala (initializate "inteligent")

• BF ortogonale si QMF sunt caracterizate de un singur filtru,iar cele biortogonale de doua; optimizarea acestor filtreproduce rezultate optime si pentru celelalte

• Discutam doar cazul filtrelor FIR


Criterii de optimizare (1)

• Optimizarea unui filtru trece-jos H(z) se poate face prinminimizarea energiei în banda de oprire

E2 =

∫ π

ωs

|H(ω)|2dω

• Banda de oprire este [ωs, π], cu ωs putin mai mare decât π/2

• Notam h = [h0 h1 . . . hN ]T vectorul coeficientilor filtrului• Energia în banda de oprire poate fi scrisa în forma patratica

E2 = hTCh

• Matricea C este Toeplitz, simetrica si pozitiv definita, deciE2 este functie convexa de h

• Elementul de pe diagonala k este∫ πωs

cos(kω)dω


Criterii de optimizare (2)

• Pentru fitrele trece-sus, banda de oprire este [0, ωs], cu ωs

putin mai mic decât π/2

• Un criteriu alternativ este cel minimax, în care seminimizeaza valoarea maxima a raspunsului în frecventa înbanda de oprire

• Criteriul de minimizat este (convex !)

Em = maxω∈[ωs,π]

|H(ω)|

• Minimizarea energiei este în general mai simpla si (uneori)se poate face exact

• Minimizarea erorii maxime este mai dificila; se poate face◦ exact, utilizând programarea semidefinita◦ aproximativ, prin discretizare


Restrictii

• În afara RP (sau RAP), celelalte restrictii ale problemei deoptimizare au fost mentionate anterior

• Faza liniara reduce complexitatea problemei (dar nu si pecea a gasirii solutiei), prin reducerea numarului de variabile(coeficientii filtrului sunt simetrici)

• Impunerea unei radacini în e.g. z = −1 se face punând

H(z) = (1 + z−1)H(z)

• Coeficientii lui H(z) devin variabilele problemei deoptimizare

• Impunerea unei valori e.g. H(0) = 1 produce o restrictieliniara

• Deci doar RP produce dificultati


Proiectarea BF ortogonale

• BFO depinde de un singur filtru, H0(z) (FIR, de ordin Nimpar)

• Notând P (z) = H0(z)H0(z−1), conditia de RP este p2ℓ = δℓ,

∀ℓ = 0 : (N − 1/2)

• Se observa ca P (ω) = |H(ω)|2 ≥ 0, ∀ω

• Notam p = [p0 p1 p2 . . . pN ]T (P (z) e simetric)• Energia în banda de oprire este

E2 =

∫ π

ωs

|H(ω)|2dω =

∫ π

ωs

P (ω)dω = cTp

unde c0 = π − ωs si

ck = 2∫ πωs

cos(kω)dω = −2 sin(kωs)k


Problema de optimizare BFO

• Se obtine urmatoarea problema de optimizare

min cTp

s.t. p2ℓ = δℓ, ℓ = 0 : (N − 1/2)

P (ω) ≥ 0,∀ω

(9)

• Dupa rezolvarea (9), H0(z) se obtine prin factorizarespectrala (discutata mai târziu)

• Dificultatea devine acum conditia de pozitivitate (altfelcriteriul si prima restrictie sunt liniare)

• Totusi, problema de optimizare este convexa (multimeapolinoamelor trigonometrice pozitive este convexa)

• Vom prezenta doua variante de rezolvare◦ aproximativa (propusa initial)◦ exacta, utilizând SDP


Optimizare aproximativa a BFO

• Ideea originara (potrivita utilizarii unui criteriu minimax): seproiecteaza P (ω) în sens minimax, impunând conditiap2ℓ = δℓ

• Se obtine |P (ω)| ≤ ε, ∀ω ∈ [ωs, π]

• Atunci P (z) = P (z) + ε ≥ 0, ∀ω (ilustrarea raspunsului înfrecventa, la tabla)

• Evident, ε poate fi determinat doar aproximativ, deci înpractica se alege o valoare mai mare decât cea necesarapentru a obtine pozitivitatea


Varianta cu discretizare

• Versiune evoluata: se rezolva (9) prin discretizare• Se impune conditia de pozitivitate pe o grila de I + 1

frecvente ωi = iπ/K

• Se obtine o problema de programare liniara

• Totusi solutia P (ω) obtinuta poate fi negativa (si de obiceieste) între punctele de discretizare

• Deci din nou trebuie adaugata o constanta pozitiva mica laP (z) (de obicei ajustând valoarea adunata pâna când esteposibila factorizarea spectrala)

• În concluzie, nu se poate garanta optimalitatea solutiei


Spre rezolvarea exacta

• Notam ψ(z) = [1 z z2 . . . zN ]T

• Daca P (z) = H(z)H(z−1), atunci putem scrie

P (z) = ψ(z−1)Th · hTψ(z) = hTΨ(z)h (10)

unde

Ψ(z) = ψ(z−1)ψ(z)T =

1 z z2 . . . zN

z−1 1 z. . . zN−1

.... . . . . . . . .

......

. . . . . . 1 z

z−N . . . . . . z−1 1

(11)


Parametrizarea polinoamelor trigonometrice pozitive

• Teorema: un polinom P (z) este pozitiv (adica P (ω) ≥ 0, ∀ω)daca si numai daca exista o matrice pozitiv definita Q dedimensiune (N + 1) × (N + 1) astfel încât

pk = tr[ΘkQ] (12)

• Matricea Θk este Toeplitz elementara, cu 1 pe diagonala ksi zero în rest

• De exemplu, pentru N = 2

Θ1 =

0 1 0

0 0 1

0 0 0

, Θ−2 =

0 0 0

0 0 0

1 0 0

• De ce e (12) buna ? Pentru ca relatia dintre coeficientii luiP (z) si elementele lui Q este liniara


Observatie preliminara

• Observam întâi ca (12) este echivalenta cu

P (z) = ψ(z−1)TQψ(z) (13)

• Într-adevar

P (z) =

N∑

k=−N

pkzk (12)

=

N∑

k=−N

tr[ΘkQ]zk

= tr

[(

N∑

k=−N

Θkzk

)

Q

]

= tr [Ψ(z)Q] = tr[

ψ(z−1)ψ(z)TQ]

= ψ(z)TQψ(z−1) = ψ(z−1)TQψ(z)


Demonstratie

• "⇒": daca P (z) este pozitiv, atunci admite factorizarespectrala, deci relatia (10) e adevarata

• Din (10) rezulta ca relatia (13), deci si (12), este adevaratapentru Q = hhT

• "⇐": daca (12) are loc pentru Q � 0, atunci din (13) rezultaca

P (ω) = ψ(e−jω)TQψ(ejω) = ψ(ejω)HQψ(ejω) ≥ 0, ∀ω

• Deci polinomul este pozitiv, Q.E.D.• Completare: în cazul în care polinomul P (z) are coeficienti

complecsi, dar ia valori reale pe cercul unitate (decip−k = p∗k), teorema este valabila cu Q hermitica


Optimizarea BFO—problema SDP

• Folosind parametrizarea (12), problema (9) capata forma

min cTp

s.t. p2ℓ = δℓ, ℓ = 0 : (N − 1/2)

pk = tr[ΘkQ], Q � 0

(14)

• Aceasta este o problema SDP• Dupa rezolvarea ei, filtrul H0(z) se calculeaza prin

factorizare spectrala• Problema (14) se poate rezolva în timp rezonabil pentru N

de ordinul sutelor


Factorizare spectrala

• Teorema (existenta factorizarii spectrale): dacaP (z) =

∑Nk=−N pkz

k, cu p−k = pk, este pozitiv pe cercul

unitate (P (ω) ≥ 0, ∀ω), atunci exista H(z) =∑N

k=0 hkz−k

astfel încât P (z) = H(z)H(z−1)

• Demonstratie: se bazeaza în esenta pe faptul ca dacaradacinile lui P (z) (care sunt simetrice fata de cerculunitate, datorita simetriei coeficientilor) sunt pe cerc, atunciele sunt duble

• Atunci H(z) se poate alege de faza minima, având toateradacinile lui P (z) din cercul unitate si jumatate din cele depe cerc

• În general, H(z) poate fi ales în mai multe feluri (regula dealocare: daca H(z) are o radacina, atunci H(z−1) aresimetrica ei)


Algoritmi de factorizare spectrala

• Cel mai simplu: se calculeaza radacinile lui P (z), dintrecare se aleg jumatate ca mai sus

• Dezavantaj: destul de dificil de a decide numericmultiplicitatea radacinilor de pe cerc (mai ales ca de multeori nu se stie a priori daca P (z) e pozitiv)

• Factorizarea spectrala nu este o problema bine conditionatanumeric, deci orice algoritm poate înâmpina probleme

• Alti algoritmi◦ Newton-Raphson: simplu si neasteptat de precis◦ Utilizând SDP (relativ imprecisa si lenta)◦ Cu ecuatia Riccati (precisa, dar lenta pentru N mare)◦ Metoda Bauer (factorizare Cholesky a unor matrice

Toeplitz din ce în ce mai mari)


Bancuri de filtre cu mai multe canale

• Schema generala

-

-

-

-

-

-

��

��

��

��

��

��

↓R0

↓R1

↓RM−1

↑R0

↑R1

↑RM−1

H0(z)

H1(z)

HM−1(z)

F0(z)

F1(z)

FM−1(z)

-

-

-

-

-

-

x y0 x0

y1

yM−1

x1

xM−1 x?

......

-

-


Definitii si notatii

• M—numarul de canale

• BF este esantionat critic dacaM−1∑

i=0

1

Ri= 1

• În acest caz, numarul de esantioane din sub-benzi esteegal cu numarul de esantioane de intrare

• BF este supraesantionat daca mai sus e semnul "≥".Atunci, numarul de esantioane din sub-benzi este mai maredecât la intrare

• (Semnul "≤" nu apare practic, RP nefiind posibila)• BF este uniform daca Ri = R, ∀i = 0 : M − 1

• Altfel, BF este neuniform


Raspunsuri ın frecventa

• Într-un BF uniform banda de trecere a filtrelor Hi(z) si Fi(z)este (tipic) [iπ/M, (i + 1)π/M ]

• Într-un BF neuniform, benzile de trecere pot avea diverselatimi (vezi exemplul DWT, în care aparea un BF neuniformcu 4 canale)

• Ilustrarea raspunsurilor—la tabla !


Functii de transfer

• Similar cu cazul M = 2, relatia de intrare-iesire este

X(z) =

M−1∑

i=0

Fi(z)1

Ri

Ri−1∑

ℓ=0

Hi(zwℓRi

)X(zwℓRi

)

• Pentru BF uniforme, relatia devine

X(z) = T0(z)X(z) +∑R−1

ℓ=1 Tℓ(z)X(zwℓR) (15)

• Functia de transfer de distorsie este

T0(z) = 1R

∑M−1i=0 Hi(z)Fi(z) (16)

• Functiile de transfer de aliere sunt

Tℓ(z) =∑M−1

i=0 Fi(z)Hi(zwℓR), ℓ = 1 : R − 1 (17)


Conditii de reconstructie perfecta

•• Conditiile de RP sunt

T0(z) = z−D, Tℓ(z) = 0, ℓ = 1 : R − 1

• În general ele sunt greu de îndeplinit (simultan cu obtinereade raspunsuri în frecventa bune ale filtrelor), fiind înlocuitede diverse aproximatii

• Totusi, libertate mai mare decât în cazul M = 2, de exempluse poate obtine ortogonalitate cu filtre cu faza liniara


Reprezentarea polifaza

• Ne ocupam în continuare de BF uniforme critic esantionate(deci R = M )

• Reprezentarea polifaza de tip I (pentru BF de analiza)

Hi(z) =

M−1∑

j=0

z−jHij(zM )

• Matricea polifaza de analiza este A(z) = [Hij(z)]i,j=0:M−1

• Reprezentarea polifaza de tip II (pentru BF de sinteza)

Fi(z) =

M−1∑

j=0

zM−j−1Fji(zM )

• Matricea polifaza de sinteza este S(z) = [Fij(z)]i,j=0:M−1


BF ın forma polifaza

• Utilizând identitatile nobile, se obtine schema de mai jos

• Conditia de RP este S(z)A(z) = z−τ , caz în care rezultaD = M(τ + 1) − 1

��

��

��

↑M

↑M

↑M

-

-

-

z−1?

-

��

��

��

↓M

↓M

↓M

-

-

-

-

-

-

z−1

z−1 z−1

z−1 z−1

?

?

-

-

-

x

x

y0

y1

yM−1

? ?

? ?

?-

?

A(z) S(z)...

...


Bancuri de filtre modulate

• Deoarece proiectarea si implementarea a 2M filtre diferiteeste complicata, se prefera utilizarea BF modulate, caresunt definite de unul sau doua filtre prototip

• Notam H(z) si F (z) cele doua filtre prototip, ambele FIR deordin N

• Notam h[n], f [n] coeficientii lor• Un banc de filtre cos modulat are filtrele definite prin

hi[n] = h[n] cos[(

i + 12

)

πM

(

n − D2

)

+ (−1)i π4

]

fi[n] = f [n] cos[(

i + 12

)

πM

(

n − D2

)

− (−1)i π4

]

• D este întârzierea BF• Uneori se ia H(z) = F (z), pentru simplificarea proiectarii

(dar cu rezultate în principiu mai proaste)


Comentarii

• Raspunsurile în frecventa—la tabla• BF se poate implementa folosind DCT (de altfel forma

prototipurilor este special aleasa în acest scop)• Problema de proiectare: gasirea prototipurilor astfel încât sa

se obtina RAP

• Întârzierea poate fi aleasa în intervalul [M, 2N − M ]

• Optimizarea este în general dificila (problema nu e nici pedeparte convexa)


BF modulate prin DFT

• BF DFT modulate sunt definite prin

hi[n] = h[n] exp(jπin/M)

fi[n] = f [n] exp(jπin/M)

• Interpretarea în frecventa este acum evidenta• Daca H(z) are coeficienti reali si banda de trecere egala cu

[−π/2M,π/2M ], atunci Hi(z) are banda de treceredeplasata cu iπ/M , adica de latime π/M , centrata în iπ/M

• Filtrele au coeficienti complecsi, în general, deci chiar dacasemnalul de intrare e real, semnalele din sub-benzi suntcomplexe

• Totusi, acest BF se poate implementa eficient• Singura problema: nu este un BF uniform pe [0, π] !


BF GDFT modulate

• Generalizarea bancurilor de filtre DFT se face prin alegerea

hi[n] = h[n] exp [jπ(i + i0)(n + n0)/M ]

fi[n] = f [n] exp [jπ(i + i0)(n + n0)/M ]

• Daca H(z) are coeficienti reali si banda de trecere egala cu[−π/2M,π/2M ], atunci Hi(z) are banda de trecere delatime π/M , centrata în (i + i0)π/M

• Un BF uniform pe [0, π] se obtine alegând i0 = 1/2

• Parametrul n0 influenteaza doar întârzierea


Capitolul 1: Bancuri de ﬁltre - schur.pub.roschur.pub.ro/download/pas/P_fb.pdfCuprins • Bancuri...

Documents

Transcript of Capitolul 1: Bancuri de ﬁltre - schur.pub.roschur.pub.ro/download/pas/P_fb.pdfCuprins • Bancuri...