Post on 08-Oct-2019
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
PAS cap. 1: Bancuri de filtre – p. 2/75
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
PAS cap. 1: Bancuri de filtre – p. 3/75
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))
PAS cap. 1: Bancuri de filtre – p. 4/75
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
PAS cap. 1: Bancuri de filtre – p. 5/75
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)
PAS cap. 1: Bancuri de filtre – p. 6/75
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 ?
PAS cap. 1: Bancuri de filtre – p. 7/75
Decimare fara pierderi—exemplu
ω
−π π 2π 3π
|Y( ω)|
1/M... ...
ω
−π π−π/M π/M 2π 3π
|X( ω)|1
... ...
PAS cap. 1: Bancuri de filtre – p. 8/75
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
PAS cap. 1: Bancuri de filtre – p. 9/75
Aliere—exemplu
ω
−π π−π/M π/M 2π 3π
|X( ω)|1
... ...
ω
−π π 2π 3π
|Y( ω)|
1/M... ...
PAS cap. 1: Bancuri de filtre – p. 10/75
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 )
PAS cap. 1: Bancuri de filtre – p. 11/75
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
PAS cap. 1: Bancuri de filtre – p. 12/75
Transformarea spectrului la interpolare—exemplu
• Pentru M = 3:
ω
−π π
|X( ω)|1
... ...
ω
−π π−π/M π/M
|Y( ω)|1
... ...
ω
−π π−π/M π/M
M
... ...
PAS cap. 1: Bancuri de filtre – p. 13/75
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 ?
PAS cap. 1: Bancuri de filtre – p. 14/75
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- -- -⇐⇒?
PAS cap. 1: Bancuri de filtre – p. 15/75
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 !
PAS cap. 1: Bancuri de filtre – p. 16/75
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)
PAS cap. 1: Bancuri de filtre – p. 17/75
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
PAS cap. 1: Bancuri de filtre – p. 18/75
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))
PAS cap. 1: Bancuri de filtre – p. 19/75
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
PAS cap. 1: Bancuri de filtre – p. 20/75
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
PAS cap. 1: Bancuri de filtre – p. 21/75
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
PAS cap. 1: Bancuri de filtre – p. 22/75
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)
]
PAS cap. 1: Bancuri de filtre – p. 23/75
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
PAS cap. 1: Bancuri de filtre – p. 24/75
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
PAS cap. 1: Bancuri de filtre – p. 25/75
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)]
PAS cap. 1: Bancuri de filtre – p. 26/75
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 ?
PAS cap. 1: Bancuri de filtre – p. 27/75
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)
PAS cap. 1: Bancuri de filtre – p. 28/75
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ω| ≤ ε, ∀ω ∈ [−π, π]
PAS cap. 1: Bancuri de filtre – p. 29/75
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
PAS cap. 1: Bancuri de filtre – p. 30/75
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"
PAS cap. 1: Bancuri de filtre – p. 31/75
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)
PAS cap. 1: Bancuri de filtre – p. 32/75
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
PAS cap. 1: Bancuri de filtre – p. 33/75
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)
PAS cap. 1: Bancuri de filtre – p. 34/75
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)
PAS cap. 1: Bancuri de filtre – p. 35/75
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
PAS cap. 1: Bancuri de filtre – p. 36/75
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
PAS cap. 1: Bancuri de filtre – p. 37/75
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
PAS cap. 1: Bancuri de filtre – p. 38/75
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
- - - -
- -
PAS cap. 1: Bancuri de filtre – p. 39/75
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)
PAS cap. 1: Bancuri de filtre – p. 40/75
Implementare eficienta
• Matricea polifaza de analiza este
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- -
PAS cap. 1: Bancuri de filtre – p. 41/75
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
PAS cap. 1: Bancuri de filtre – p. 42/75
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
PAS cap. 1: Bancuri de filtre – p. 43/75
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
PAS cap. 1: Bancuri de filtre – p. 44/75
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
PAS cap. 1: Bancuri de filtre – p. 45/75
Relatia cu matricea polifaza
• Matricea polifaza de analiza este
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)
PAS cap. 1: Bancuri de filtre – p. 46/75
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
PAS cap. 1: Bancuri de filtre – p. 47/75
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
PAS cap. 1: Bancuri de filtre – p. 48/75
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
PAS cap. 1: Bancuri de filtre – p. 49/75
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
PAS cap. 1: Bancuri de filtre – p. 50/75
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ω
PAS cap. 1: Bancuri de filtre – p. 51/75
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
PAS cap. 1: Bancuri de filtre – p. 52/75
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
PAS cap. 1: Bancuri de filtre – p. 53/75
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
PAS cap. 1: Bancuri de filtre – p. 54/75
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
PAS cap. 1: Bancuri de filtre – p. 55/75
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
PAS cap. 1: Bancuri de filtre – p. 56/75
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
PAS cap. 1: Bancuri de filtre – p. 57/75
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)
PAS cap. 1: Bancuri de filtre – p. 58/75
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
PAS cap. 1: Bancuri de filtre – p. 59/75
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)
PAS cap. 1: Bancuri de filtre – p. 60/75
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
PAS cap. 1: Bancuri de filtre – p. 61/75
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
PAS cap. 1: Bancuri de filtre – p. 62/75
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)
PAS cap. 1: Bancuri de filtre – p. 63/75
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)
PAS cap. 1: Bancuri de filtre – p. 64/75
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?
......
-
-
PAS cap. 1: Bancuri de filtre – p. 65/75
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
PAS cap. 1: Bancuri de filtre – p. 66/75
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 !
PAS cap. 1: Bancuri de filtre – p. 67/75
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)
PAS cap. 1: Bancuri de filtre – p. 68/75
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
PAS cap. 1: Bancuri de filtre – p. 69/75
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
PAS cap. 1: Bancuri de filtre – p. 70/75
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)...
...
PAS cap. 1: Bancuri de filtre – p. 71/75
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)
PAS cap. 1: Bancuri de filtre – p. 72/75
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)
PAS cap. 1: Bancuri de filtre – p. 73/75
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, π] !
PAS cap. 1: Bancuri de filtre – p. 74/75
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
PAS cap. 1: Bancuri de filtre – p. 75/75