Filtry adaptacyjne
Filtr adaptacyjny (FIR lub IIR) projektuje 'sam siebie' w oparciu o sygnał wejściowy (filtrowany) x[k] i pożądany
(odniesienia) d[k]. Proces przestrajania współczynników filtra zależy od adaptacyjnego algorytmu
minimalizującego błąd e[k] pomiędzy d[k] i y[k]. Kiedy, w wyniku kolejnych iteracji, wartość błędu e[k] osiąga
wartość minimalną proces adaptacji jest zakończony, a współczynniki filtra osiągają wartości zbieżne do
rozwiÄ…zania
Filter Design Toolbox, Version 3.0 - there are about 30 different adaptive filtering algorithms included
(N)LMS - (Normalized) Least Mean Squares Based FIR Adaptive Filters
RLS - Recursive Least Squares Based FIR Adaptive Filters
1
adaptfilt.lms Direct-form least-mean-square FIR adaptive filter
adaptfilt.nlms Direct-form Normalized LMS FIR adaptive filter
adaptfilt.dlms Direct-form delayed LMS FIR adaptive filter
adaptfilt.blms Block LMS FIR adaptive filter
adaptfilt.blmsfft FFT-based block LMS FIR adaptive filter
adaptfilt.ss Direct-form sign-sign FIR adaptive filter
adaptfilt.se Direct-form sign-error FIR adaptive filter
adaptfilt.sd Direct-form sign-data FIR adaptive filter
adaptfilt.filtxlms Filtered-X LMS FIR adaptive filter
adaptfilt.adjlms Adjoint LMS FIR adaptive filter
adaptfilt.lsl Least-squares lattice FIR adaptive filter
adaptfilt.qrdlsl QR-decomposition LS lattice FIR adaptive filter
adaptfilt.gal Gradient adaptive lattice FIR adaptive filter
adaptfilt.fdaf Frequency-domain FIR adaptive filter
adaptfilt.ufdaf Unconstrained frequency-domain FIR adaptive filter
adaptfilt.pbfdaf Partitioned-block FDAF
adaptfilt.pbufdaf Partitioned-block unconstrained FDAF
adaptfilt.tdafdft Transform-domain FIR adaptive filter using DFT
adaptfilt.tdafdct Transform-domain FIR adaptive filter using DCT
adaptfilt.rls Recursive least-squares FIR adaptive filter
adaptfilt.hrls Householder RLS FIR adaptive filter
adaptfilt.swrls Sliding-window RLS FIR adaptive filter
adaptfilt.hswrls Householder SWRLS FIR adaptive filter
adaptfilt.qrdrls QR-decomposition RLS FIR adaptive filter
adaptfilt.ftf Fast transversal least-squares FIR adaptive filter
adaptfilt.swftf Sliding-window FTF FIR adaptive filter
adaptfilt.ap Affine projection FIR adaptive filter
adaptfilt.bap Block AP FIR adaptive filter
adaptfilt.apru AP FIR adaptive filter with recursive matrix update
2
Filtracja (Haykin, Simon, Adaptive Filter Theory, Prentice-Hall, Inc., 1996)
Filtr jest urządzeniem (sprzętowym lub programowym) służącym do wydobycia z zakłóconego sygnału
informacji użytecznej. Filtr może być zastosowany do trzech zadań przetwarzania informacji:
1. Filtracji - określenie informacji użytecznej dla czasu t na podstawie pomiarów do czasu t (włącznie)
2. Wygładzania - określenie informacji użytecznej dla czasu t na podstawie pomiarów do czasu t oraz po czasie t
3. Predykcji - określenie informacji użytecznej dla czasu większego niż t na podstawie pomiarów do czasu t
(włącznie)
Dla sygnałów losowych stacjonarnych zakłada się znajomość parametrów statystycznych sygnałów (wartość
średniej i funkcji korelacji) zarówno dla sygnału użytecznego jak i zakłócającego.
Zadanie filtracji definiuje się w ten sposób, aby wejściem filtra był użyteczny sygnał zakłócony, a wyjściem
sygnał użyteczny z jak najlepiej usuniętym zakłóceniem.
Dla sygnałów stacjonarnych i średniokwadratowego kryterium jakości filtrem optymalnym jest filtr Wienera.
Dla sygnałów niestacjonarnych filtrem optymalnym jest filtr Kalmana.
Zarówno filtr Wienera jak i Kalmana są dobrze opisane w literaturze zarówno dla sygnałów ciągłych jak i
dyskretnych.
Projektowanie optymalnego filtra Wienera wymaga znajomości a priori parametrów statystycznych sygnału,
gdy parametry te nie są znane filtr nie jest optymalny. W takim przypadku można zastosować dwustopniową
procedurę polegającą na tym, że:
1) najpierw estymuje się parametry statystyczne odpowiednich sygnałów,
2) a następnie wylicza się (za każdym razem od nowa - algorytm nierekursywny) współczynniki filtra.
Powyższa procedura jest jednak zbyt czasochłonna, dlatego stosuje się filtry adaptacyjne, które uaktualniają
swoje współczynniki - algorytm rekursywny. Algorytm startuje z początkowego zestawu współczynników
(reprezentujÄ…cego wiedzÄ™ o sygnale).
3
Dla sygnału stacjonarnego algorytm jest zbieżny do optymalnego filtra Winera, a dla sygnałów niestacjonarnych
śledzi zmiany parametrów statystycznych (pod warunkiem, że są one wystarczająco wolne).
Ponieważ współczynniki filtra adaptacyjnego uaktualniają się w kolejnych iteracjach (zależą od danych), więc
jest on układem nieliniowym (nie spełnia zasady superpozycji). Pomimo tego filtr adaptacyjny określa się jako
liniowy jeżeli estymata sygnału użytecznego (sygnał wyjściowy) jest liczona adaptacyjnie jako liniowa
kombinacja dostępnych obserwacji (sygnałów wejściowych).
Literatura podaje wiele algorytmów rekursywnych dla liniowych filtrów adaptacyjnych. Podstawowe parametry
charakteryzujÄ…ce algorytm to:
- szybkość zbieżności (rate of convergence) - liczba iteracji algorytmu dla sygnału stacjonarnego dająca
rozwiÄ…zanie odpowiednio bliskie optymalnemu
- niedopasowanie (misadjustment) - różnica końcowej wartości błędu średniokwadratowego uśredniona dla
zbioru (ensemble) filtrów z błędem średniokwadratowym filtra Winera
- śledzenie (tracking) - dla sygnałów niestacjonarnych algorytm powinien śledzić parametry statystyczne
sygnału. Zdolność śledzenia zależy od: 1) szybkości zbieżności i 2) fluktuacji w stanie ustalonym
spowodowanych szumem
- odporność (robustness) - małe zaburzenia (o małej energii) powinny dawać małe błędy estymacji
- złożoność obliczeniowa (computational requirements) - liczba operacji ('.', '/', '+', '-'); rozmiar pomięci, czas
programowania (złożoności algorytmu)
- struktura (structure) - struktura przepływu informacji (modułowość, równoległość)
- właściwości numeryczne (numerical properties) - stabilność obliczeń, dokładność obliczeń. Wrażliwość na
błędy kwantyzacji (próbkowanie, precyzja obliczeń)
4
Struktury filtrów linowych
Filtracja adaptacyjna składa się z dwóch etapów:
1) filtracji i 2) adaptacji - mechanizmu zmiany (uaktualnienia) parametrów filtracji.
Stosowane są trzy struktury filtrów FIR w algorytmach adaptacyjnych:
1) Transversal filter
(tapped-delay line filter)
M -1
*
y[n] =
k
"w u(n - k)
k =0
2) Lattice predictor 3) Systolic array
5
Metody projektowania adaptacyjnych filtrów liniowych
Nie istnieje jednoznaczne rozwiązanie problemu adaptacyjnej filtracji liniowej. Dostępny jest natomiast zasób
algorytmów rekursywnych o różnych właściwościach. Algorytmu te są wyprowadzane w oparciu o jedną z
dwóch metod:
I) Stochastic Gradient Approach
Dla sygnałów stacjonarnych funkcja kosztu jest zdefiniowana jako wartość średniokwadratowa różnicy
M -1
*
pomiędzy wyjściem filtra y[n] ( y[n] = u(n - k) ), a sygnałem pożądanym d[n]. Funkcja kosztu zależy więc od
k
"w
k=0
współczynników filtra w drugiej potędze i może być przedstawiona jako wielowymiarowa parabola z minimum
występującym dla zestawu współczynników filtra Wienera. Algorytm rekursywny uaktualniania wag filtra
projektuje się w dwóch etapach:
1) modyfikacja układu równań Wienera-Hopfa (równanie macierzowe definiujące optymalne rozwiązanie
Wienera) za pomocÄ… metody najszybszego spadku (steepest descent). Metoda ta wykorzystuje wektor
gradientów, który zależy od dwóch parametrów: a) macierzy korelacji współczynników filtra i b) wektora
korelacji tych samych współczynników i sygnału pożądanego.
2) wykorzystanie bieżących wartości tych korelacji do estymowania wektora gradientu.
Algorytm LMS jest prosty i może osiągać dobre rezultaty (jest bardzo popularny w zastosowaniach). Głównym
jego ograniczeniem jest wolna zbieżność i wrażliwość na zmiany condition number macierzy korelacji (condition
6
A = A*
number macierzy hermitowskiej ( ) definiuje się jako iloraz największej wartości własnej do najmniejszej
wartości własnej). Algorytmy LMS posiadają dobre właściwości śledzenia.
II) Least - squares Estimation
Funkcja kosztu jest zdefiniowana jako suma ważonych kwadratów różnicy pomiędzy wyjściem filtra y[n]
M -1
*
( y[n] = u(n - k) ), a sygnałem pożądanym d[n].
k
"w
k=0
Do projektowania adaptacyjnych filtrów RLS wykorzystuje się dobrze rozwiniętą teorię filtrów Kalmana. Można
wyróżnić 3 rodzaje liniowych filtrów adaptacyjnych RLS:
1) standard RLS - zastosowanie filtra w postaci Transversal filter, wyprowadzenie standardowego algorytmu
RLS opiera się na twierdzeniu o odwrotności macierzy (matrix inversion lemma). To rozwiązanie ma takie same
wady i zalety jak filtr Kalmana. Do wad należy brak odporności numerycznej i złożoność obliczeniowa, które
stały się przyczyną powstania kolejnych dwóch rozwiązań
2) square-root RLS - oparte o QR-dekompozycjÄ™ macierzy wykonywanÄ… przez transformacjÄ™ Hauseholdera i
rotacje Givensa.
3) fast RLS - złożoność obliczeniowa algorytmów standard RLS i square-root RLS jest rzędu O(M2) (dla
porównania LMS O(M)), gdzie M jest liczbą współczynników filtra. Dla obniżenia złożoności obliczeniowej
algorytmów RLS wykorzystuje się redundancję macierzy danych wejściowych.
7
 8
Zastosowania filtracji adaptacyjnej
1. Identyfikacja systemu (np. odpowiedzi impulsowej kanału telekomunikacyjnego lub pomieszczenia
odsłuchowego itp.). Dla małych wartości e[k] filtr adaptacyjny zachowuje się jak nieznany system. Sygnałem
wejściowym x[k] może być szum (stosowany np. w modemach).
2. W celu wyznaczenia filtra odwrotnego do nieznanego
systemu filtr adaptacyjny jest włączany za badanym
systemem. Wprowadzenie dodatkowego opóz
nienia
(równego opóz
nieniu systemu) pozwala zachować
przyczynowość układu. Następnie filtr adaptacyjny
można wykorzystać do korekcji zniekształceń
wprowadzanych przez system (np. do korekcji linii
telefonicznej).
9
3. Sygnałem odniesienia dla układów redukcji szumu (lub innych zakłóceń) jest zakłócony sygnał d[k]=s[k]+n[k],
natomiast wejściem jest zakłócenie n'[k] skorelowane n[k]. W tym przypadku wyjściem jest sygnał błędu e[k],
który dąży do s[k].
4. W poniższym układzie filtr adaptacyjny przewiduje bieżącą próbkę na podstawie próbek poprzednich. Sygnał
s[k] musi być wolnozmienny. Układ taki można zastosować do usunięcia składowej deterministycznej z sygnału
losowego.
10
Usuwanie echa (Acoustic Echo Cancellation) (demo z Matlaba)
Przy audio telekonferencjach wymagajÄ…cych jednoczesnej (full-duplex transmission)
komunikacji sygnał z mikrofonu d[n] zawiera dwie składowe: sygnał bliski (near-end)
mowy v[n] i daleki (far-end) z głośnika dhat[n], dodatkowo sygnał z głośnika splata się
z odpowiedzią impulsową pomieszczenia. Zadanie polega na usunięciu sygnału dhat[n]
z sygnału mikrofonu (na podstawie znajomości sygnału mowy z far-end), tak żeby
tylko sygnał near-end był transmitowany do odbiorcy far-end.
Odpowiedz
impulsowa pomieszczenia Near-End Speech Signal v[n] Far-End Speech Signal dhat[n]
Wyniki uzyskano algorytmem Frequency-Domain Adaptive Filter (FDAF), który dobrze nadaje się do identyfikacji obiektów o
długich odpowiedziach impulsowych.
11
Filtry Wienera
Definicja problemu liniowej filtracji optymalnej: otrzymać błąd e[n] tak mały jak to tylko możliwe w sensie
przyjętego kryterium.
Założenia:
1. Filtr jest liniowy (co upraszcza analizÄ™ matematycznÄ…)
2. Filtr jest dyskretny (realizacja software/hardware)
"
*
y[n] =
k
"w u[n - k], n = 0,1,2,...
Wyjście filtra opisane jest przez odpowiedz
impulsowÄ…
k =0
Typu filtra (FIR lub IIR) wpływa na właściwości praktyczne natomiast rodzaj oraz przyjętego kryterium na
aparat matematyczny stosowany do analizy.
12
Jako kryterium stosuje się następujące funkcje kosztu:
1. Wartość średniokwadratowa e[n] - funkcja kosztu zależy w drugiej potędze od współczynników filtra i ma
minimum
2. Wartość oczekiwana modułu e[n]
3. Wartość oczekiwana trzeciej (lub wyższych) potęg modułu e[n]
Zaprojektować liniowy filtr dyskretny, którego wyjście y[n] estymuje sygnał pożądany d[n] na podstawie
ciągu wejściowego u[n] w taki sposób, że wartość średniokwadratowa błędu estymacji e[n]= d[n]-y[n]
jest minimalna.
Tak zdefiniowany problem optymalizacji statystycznej można rozwiązać dwoma sposobami:
1) principle of orthogonality
2) error-performance surface
Principle of orthogonality
Zakładamy, że wejście filtra u[n] i sygnał pożądany d[n] są realizacjami procesu stochastycznego stacjonarnego
w szerokim sensie z wartościami średnimi równymi zero. Błąd estymacji wynosi: e[n]=d[n]-y[n]
Do optymalizacji filtra wybieramy kryterium średniokwadratowe: J=E{e[n]e*[n]}=E{|e[n]|2}
Ponieważ w zastosowaniach często stosuje się sygnały zespolone, więc przyjmujemy, że współczynniki filtra
mogą być zespolone: wk = ak + jbk, k=0,1,2,...
13
"
Zdefiniujmy operator gradientu , którego k-ty element jest pochodną cząstkową pierwszego rzędu po części
" "
"k = + j , k = 0,1,2...
rzeczywistej i urojonej k-tego współczynnika filtra:
"ak "bk
"J "J
"k J = + j , k = 0,1,2...
StosujÄ…c operator gradientu do funkcji kosztu otrzymujemy:
"ak "bk
Funkcja kosztu ma wartości rzeczywiste. Warunek zespolony jest rozpatrywany jako dwa równoczesne warunki
"J
rzeczywiste. Aby funkcja kosztu osiągnęła minimum wszystkie elementy muszą się jednocześnie zerować:
"k J = 0, k = 0,1,2...
Spełniając powyższy zbiór warunków filtr jest filtrem optymalnym w sensie średniokwadratowym.
"J "J
"k J = + j , k = 0,1,2...
PodstawiajÄ…c J=E{e[n]e*[n]} do otrzymujemy:
"ak "bk
Å„Å‚"e[n] üÅ‚
"e*[n] "e[n] "e*[n]
"k J = EôÅ‚ e*[n] + e[n] + je*[n] + je[n]ôÅ‚
òÅ‚ żł
"ak "ak "bk "bk
ôÅ‚ ôÅ‚
ół þÅ‚
"
*
y[n] =
k
"w u[n - k], n = 0,1,2,...
KorzystajÄ…c z e[n]=d[n]-y[n] i (wk = ak + jbk, k=0,1,2,...)
k =0
"e[n] "e*[n]
= -u[n - k] = -u*[n - k]
,
"ak "ak
"e[n] "e*[n]
= ju[n - k] = - ju*[n - k]
"bk "bk
"k J
Podstawiając powyższe pochodne cząstkowe do , po przekształceniach: " J = -2E{u[n - k]e*[n]}
k
14
Jeżeli przez eo oznaczymy wartość błędu estymacji filtra optymalnego to:
*
E{u[n - k]eo[n]}= 0, k = 0,1,2,...
Warunkiem koniecznym i wystarczającym na to, aby funkcja kosztu J osiągnęła minimum jest
ortogonalność błędu estymacji eo[n] do każdej próbki sygnału wejściowego branej do estymacji w
chwili n (jest to tzw. principle of orthogonality).
k ="
Å„Å‚k =" üÅ‚
* * * *
E{y[n]eo[n]}= EôÅ‚ *u[n - k]eo[n]ôÅ‚ =
òÅ‚ żł
k k
"w "w E{u[n - k]eo[n]}
ôÅ‚k =0 ôÅ‚
ół þÅ‚ k =0
Kiedy filtr pracuje w warunkach optymalnych estymata y[n] jest ortogonalna do sygnału pożądanego
d[n].
15
Równania Wienera-Hopfa
*
E{u[n - k]eo[n]}= 0, k = 0,1,2,...
Warunek po podstawieniu jest następujący:
"
Å„Å‚ üÅ‚
ëÅ‚ öÅ‚
*
EôÅ‚u[n - k]ìÅ‚ d [n] -
òÅ‚
oi
"w u*[n - i]÷Å‚ôÅ‚ 0, k = 0,1,2,...
ìÅ‚ ÷łżł =
ôÅ‚
íÅ‚ i =0 Å‚Å‚ôÅ‚
ół þÅ‚
woi - i-ty współczynnik filtra optymalnego
Przekształcając powyższe równanie otrzymujemy:
"
*
oi
"w E{u[n - k]u*[n - i]}= E{u[n - k]d [n]}, k = 0,1,2,...
i =0
E{u[n - k]u*[n - i]}
1. Wartość oczekiwana jest równa funkcji autokorelacji sygnału wejściowego z
r[i - k] = E{u[n - k]u*[n - i]}
przesunięciem i-k:
*
E{u[n - k]d [n]}
2. Wartość oczekiwana jest równa korelacji pomiędzy sygnałem wejściowym u[n-k], a
*
p[-k] = E{u[n - k]d [n]}
sygnałem pożądanym d[n] z przesunięciem -k:
W rezultacie, jako warunek filtracji optymalnej, otrzymujemy nieskończony układ równań (dla filtra IIR), są to
równania Wienera-Hopfa:
"
oi
"w r(i - k) = p(-k), k = 0,1,2,...
i=0
Współczynniki filtra optymalnego są określone za pomocą dwóch funkcji korelacji: autokorelacji sygnału
wejściowego i korelacji pomiędzy sygnałem wejściowym, a pożądanym.
16
Rozwiązanie równań Wienera-Hopfa (dla linear transversal filter)
M -1
oi
"w r(i - k) = p(-k), k = 0,1,...M -1
i=0
Niech R oznacza macierz korelacji o rozmiarze MxM sygnałów wejściowych u[n], u[n-1],..., u[n-M+1] filtra:
r[0] r[1] L r[M -1]
îÅ‚ Å‚Å‚
ïÅ‚
r*[1] r[0] r[M - 2]śł
ïÅ‚ śł
R =
ïÅ‚ śł
M O M
ïÅ‚ śł
*
ðÅ‚r [M -1] r*[M - 2] L r[0] ûÅ‚
Niech p oznacza wektor korelacji pomiędzy sygnałami wejściowymi i sygnałem pożądanym o rozmiarze Mx1:
p = [p[0], p[-1],K, p[1 - M ]]T
Rwo = p
wo = [wo0,wo1,K,woM -1]T
Równania Wienera-Hopfa można zapisać w postaci: ,
wo = R-1p
RozwiÄ…zanie
17
Least Mean Square Algorithm
Główną zaletą algorytmu LMS jest prostota, nie wymaga on liczenia korelacji R, p ani odwracania macierzy.
Estymatę gradientu można otrzymać z zależności: Natomiast R i p można estymować na podstawie
wartości chwilowych:
Ć
R[n] = u[n]uH [n]
i
Ć
p[n] = u[n]d*[n]
.
W rezultacie chwilowa estymacja gradientu wynosi:
)
Ć
"J[n] = -2u[n]d*[n] + 2u[n]uH [n]w[n]
Steepest-descent algorithm (najszybszego spadku)
W zastosowaniu do poszukiwania minimum funkcji kosztu Jmin algorytm przebiega następująco:
1. Start z początkową wartością współczynników filtra w[0] (jeżeli nie dysponujemy wiedzą a priori w[0]=0)
2. Obliczenie wektora gradientu jako pochodnych cząstkowych błędu średniokwadratowego J[n] względem
współczynników filtra w[n] dla czasu n (n - tej iteracji)
3. Uaktualnienie współczynników filtra w kierunku przeciwnym do wektora gradientu
4. Powrót do 2.
1
w[n +1] = w[n] + µ(- "J[n])
2
)
u
[n +1] = u
[n]+ µ u[n](d*[n]- uH [n]w[n])
Dla LMS:
18
W algorytmie LMS dla dużych u[n] występuje problem wzmacniania szumu gradientu. W celu ograniczenia tego
zjawiska stosuje się normalizację, polegającą na tym, że wartość uaktualnienia wektora wag filtra jest
normowana przez kwadrat normy euklidesowej sygnału wejściowego u[n].
19
 20
 21