nhmax

ESTRUTURA PARA FILTRAGEM ADAPTATIVA UTILIZANDO WAVELETS E
FILTROS ESPARSOS
Julio Cesar B. Torres, Mariane R. Petraglia
Universidade Federal do Rio de Janeiro
COPPE - Departamento de Engenharia Eletr^onica, EE
CP 68564, CEP 21945-970, Rio de Janeiro, RJ - Brazil
E-mails: [email protected], [email protected]
Resumo| O objetivo deste artigo e apresentar uma nova estrutura para ltragem adaptativa, baseada na
utilizac~ao de ltros esparsos e de uma transformada wavelet. Mostra-se como uma estrutura convencional com
ltros esparsos deve ser modicada para utilizar uma transformada wavelet em substituica~o as transformadas
uniformes (tais como DCT e DFT). Toda a descrica~o do algoritmo e suas particularidades s~ao fornecidas neste
trabalho, tais como numero mnimo de coecientes adaptativos necessarios e atraso introduzido no sinal de
sada. E tambem apresentado um criterio de converg^encia que permite selecionar a wavelet adequada para uma
determinada aplicac~ao, baseado nas caractersticas do sinal de entrada e nos par^ametros da estrutura adaptativa
(esparsidade e numero de coecientes de cada subltro). Finalmente s~ao apresentadas simulac~oes com diferentes
sinais de entrada para ilustrar o comportamento de converg^encia do algoritmo e vericar a analise teorica.
Abstract| The main goal of this paper is to present a new structure for adaptive ltering which employs
sparse lters and wavelet transforms. We show how a standard structure with sparse adaptive lters can be
modied to use a wavelet transform instead of a uniform transform (such as DCT or DFT). The algorithm
description with its particularities, such as the delay introduced in the output signal and the minimum number
of adaptive coecients required, is given. We also present a convergence criterium which allows choosing the
adequate wavelet transform according to the input signal characteristics and the structure parameters (sparsity
and number of coecients of the adaptive sublters). Finally, simulations with collored input signals are presented
to illustrate the convergence behavior of the algorithm and to verify the theoretical analysis.
Key Words| Adaptive Filtering; Wavelet Transform; System Identication.
1 Introduc~ao
Este artigo apresenta uma estrutura para ltragem adaptativa que alia as vantagens das transformadas wavelets com as dos ltros adaptativos
esparsos. A transformada wavelet discreta pode
ser interpretada como um banco de ltros n~ao
uniforme (Vetterli e Herley, 1992) e ser implementada de forma eciente, tornando-se atraente em
aplicac~oes cujo sinal de entrada possui espectro de
pot^encia colorido e que requerem ltros adaptativos de ordens elevadas, tais como cancelamento
de ecos acusticos e equalizac~ao de canais de comunicac~oes. A Fig. 1 mostra a estrutura de ltragem adaptativa no domnio da transformada
(Petraglia e Mitra, 1993), onde temos o sinal de
entrada x(n) modicado atraves da transformac~ao
T, onde cada sada da transformada serve de entrada para um ltro adaptativo esparso que e
atualizado utilizando-se o erro na sada do sistema.
2 Estrutura Adaptativa Utilizando
Wavelets e Filtros Esparsos
2.1 Transformaca~o do Vetor de Entrada
Estruturas em oitavas (ou em arvore), como as
da Fig. 2 s~ao muito utilizadas na implementac~ao
de transformadas wavelet discretas (Vetterli e Kovacevic, 1995). Tais estruturas podem ser subs-
d(n)
-∆
Z
x(n)
z-1
-1
z
d(n- ∆)
Transformada
Filtro Adaptativo
T
Σ
W
Σ
y(n)
z-1
e(n)
Figura 1. Esquema basico para ltragem adaptativa no
domnio da transformada
titudas por uma estrutura paralela que utiliza um
banco de ltros equivalentes Hm (z ). Para a estrutura em arvore da Fig. 2, os ltros de analise
equivalentes Hm (z ) est~ao relacionados aos ltros
prototipos G0 (z ) e G1 (z ) atraves das seguintes
equac~oes:
HJ (z ) =
JY
?1
k=0
Hi (z ) = G1 (z 2i )
G0 (z 2k );
iY
?1
k=0
G0 (z 2k );
(1)
(2)
para i = 0; ; J ? 1 e k 0, onde J corresponde
ao numero de estagios da estrutura em arvore. A
estrutura correspondente para o banco de sntese
e mostrada na Fig. 3.
Utilizando a recurs~ao descrita nas equac~oes
(1) e (2), onde o sinal de sada do ltro g0 (n)
g1 (n)
2
g1 (n)
g0 (n)
2
g1(n)
2
g0(n)
2
2
g0 (n)
2
Figura 2. Estrutura em oitavas para analise da wavelet
utilizando 3 estagios
H0(z)
G1(z)
G0(z) G1 (z 2)
H1(z)
+
G0(z)
G0(z 2)
G0(z) G0(z
2)
+
(z 4 )
H2(z)
G0(z 4 )
H3(z)
G1
Figura 3. Estruturas equivalentes para implementaca~o do
banco de sntese de uma wavelet com 3 estagios
H0 (z)
H0 (z)
L0
-L 0
-L 0
z
z
-L 1
z
-L 2
z
H1 (z)
L1
H1 (z)
z
H2 (z)
L2
H2 (z)
z
(a)
-L 0
z
-L 1
-L 2
(b)
Figura 4. (a) Banco de analise correspondente a transformada wavelet com decimac~ao; (b) Estrutura adaptativa
com fatores de esparsidades diferentes
e sempre decomposto em dois ramos, sucessivamente a cada novo estagio (ou nova escala), o ltro
de maior comprimento sera sempre obtido em um
dos dois ramos do ultimo estagio, ou seja, HJ (z )
ou HJ ?1 (z ). E o menor ltro sera o obtido no
primeiro estagio, que coincide com o proprio ltro
G1 (z ), isto e, H0 (z ) = G1 (z ).
Na estrutura esparsa, a decimac~ao apresentada na Fig. 2 e substituda pelo fator de esparsidade do ltro adaptativo, conforme mostrado
na Fig. 4. O ltro esparso da banda m possuira, portanto, Lm zeros (coecientes nulos) entre cada coeciente adaptativo efetivo. Assim, se
uma banda possui um fator de decimac~ao igual a
4, por exemplo, o ltro adaptativo tera um fator
de esparsidade maximo igual a 4.
2.2 Atraso na Estrutura
O banco de ltros de analise equivalente a wavelet na estrutura proposta produz um atraso que deve ser considerado no calculo do erro, pois
o ltro adaptativo deve, alem de realizar a ltragem do sinal de entrada, incorporar o banco
de reconstruca~o (ou de sntese) correspondente a
transformac~ao. Os comprimentos dos ltros do
banco de sntese dependem dos comprimentos dos
ltros equivalentes nas sadas mais extremas do
cascateamento dos ltros prototipos para uma estrutura em arvore completa (cascateando todos os
ltros ate o ultimo estagio).
A equac~ao abaixo estabelece uma relac~ao entre o atraso e os comprimentos dos ltros equivalentes da wavelet
= NHmax +2 NHmin ? 2J + 1
(3)
onde NHmax e NHmin representam, respectivamente, a maior e a menor ordem dos ltros equivalentes Hm (z ), quando a estrutura e decomposta
completamente em arvore (em todos os ramos e
ate o ultimo estagio).
2.3 Numero Mnimo de Coecientes
Para que a estrutura funcione corretamente, e necessario que haja um numero mnimo de coecientes adaptativos na estrutura esparsa. Este valor
dependera do fator de esparsidade utilizado em
cada ramo do ltro adaptativo, como veremos a
seguir.
A resposta impulsional total do sistema c(n)
e dada pelo somatorio das respostas impulsionais
equivalentes dos M ramos da estrutura, ou seja,
c(n) =
MX
?1
m=0
hm (n) wm (n);
(4)
onde hm (n) e wm (n) s~ao as sequ^encias correspondentes as respostas impulsionais dos ltros de
analise Hm (z ) e dos subltros esparsos Wm (z Lm ),
respectivamente. O numero de coecientes dos ltros adaptativos deve garantir que as convoluc~oes
da equac~ao (4) produzam uma sequ^encia c(n) cujo
comprimento NC seja pelo menos igual ao tamanho da resposta impulsional do sistema que se deseja modelar.
Para que haja converg^encia do ltro adaptativo e preciso tambem que o numero total de coecientes adaptativos seja maior ou igual ao numero
de coecientes do sistema que se deseja modelar.
Assim temos que
MX
?1
m=0
Km N;
(5)
onde Km e o numero de coecientes adaptativos
n~ao-nulos na m-esima banda e N e o comprimento
do sistema que se deseja modelar. O banco de ltros equivalente possui ltros com diferentes comprimentos NHm . O fator de esparsidade a ser empregado em cada ramo corresponde ao fator de
decimaca~o da estrutura em oitavas deste ramo. A
resposta impulsional deve ser obtida levando em
conta estes fatores e o atraso inerente ao banco de
ltros em oitavas. A convoluc~ao do ltro adaptativo esparso com o respectivo ltro equivalente
(em cada ramo) devera garantir que o sistema desejado seja modelado incluindo o atraso . Em
cada ramo m da estrutura, o comprimento Nm da
convoluc~ao de Hm (z ) com Wm (z Lm ) e dado por
Nm = NHm + NWm ? 1
(6)
para m = 0; 1; ; M ? 1, onde NHm e NWm correspondem aos comprimentos dos ltros Hm (z ) e
Wm (z Lm ), respectivamente, sendo
NWm = (Km ? 1)Lm + 1:
(7)
O comprimento total Nm do ltro equivalente
ao ramo m devera ser N (tamanho da resposta
impulsional do sistema desejado) mais o atraso da
estrutura em oitavas, ou seja,
Nm = N + (8)
Substituindo (6) e (7) em (8), obtemos
Km = (N + ? NHm )=Lm + 1:
(9)
Caso Km em (9) n~ao seja um numero inteiro, este
devera ser aproximado para o proximo numero inteiro.
Devido aos diferentes fatores de esparsidades e
diferentes numeros de coecientes em cada banda,
as respostas impulsionais provenientes da convoluc~ao dos ltros Hm (z ) e Wm (z Lm ) n~ao ter~ao,
obrigatoriamente, sempre o mesmo tamanho. Assim, o tamanho da resposta impulsional obtida
atraves de (4) sera na maioria dos casos maior do
que a do sistema que se deseja identicar. Em
aplicac~oes onde o comprimento do sistema a ser
identicado e conhecido (ou pre-denido), podese descartar os coecientes excedentes de c(n)
sem nenhum prejuzo, pois estes dever~ao convergir
para valores muito proximos de zero.
Em alguns casos, porem, mesmo com o
numero correto de coecientes em cada banda, o
sistema n~ao e plenamente modelado, devido a escolha de ltros interpoladores (wavelet) que n~ao
satisfazem a propriedade de reconstruc~ao perfeita
(PR) (Strang e Nguyen, 1997).
3 Algoritmo Adaptativo e Analise de
Converg^encia
Primeiro deniremos um vetor de entrada aumentado xaum (n) como sendo
xaum(
n)
=
x(n) x(n
? 1) x(n
?
ma x )
N
T
(10)
onde Nmax = maxfNHm + Lm(Km ? 1)g, para
m = 0; 1; :::; M ? 1. Deniremos, tambem, a matriz Hm de dimens~ao Km Nmax ; que contem na
primeira linha os coecientes do ltro Hm (z ) seguidos de Nmax ? NHm zeros e sendo as demais
linhas compostas pelas linhas anteriores deslocadas circularmente de Lm amostras, ou seja,
2
3
0
m;0
m;NHm ?1
60 m;0
m;NHm ?1 7
7
Hm = 64 ..
..
.
.
5
m;NHm ?1
0
m;0
h
h
h
h
:
h
h
(11)
Desta forma, o vetor xm (n) que contem as amostras do sinal transformado na m-esima banda
pode ser escrito como
2
6
xm(n) = 664
3
xm (n)
xm (n ? Lm )
7
7
7
5
..
.
xm (n ? (Km ? 1)Lm)
= Hm xaum (n):
(12)
Utilizando a notac~ao acima e denindo o vetor que
contem os coecientes adaptativos de cada subltro
2
3
wm;0 (n)
6 w
(n) 77
(13)
wm(n) = 664 m;..1
7;
5
.
wm;Km ?1 (n)
e o vetor aumentado de coecientes que contem
todos os coecientes adaptativos
2
6
w(n) = 664
3
w0 (n)
w1 (n)
7
7
7
5
..
.
wM ?1(n)
;
(14)
pode-se escrever a sada do sistema y(n) como
sendo
y(n) =
=
MX
?1
m=0
MX
?1
m=0
wmT (n)xm (n)
wmT (n)Hmxaum (n)
2
= wT (n) 64
H0
..
.
HM ?1
3
7
5
xaum (n)
(15)
A adaptac~ao dos coecientes dos ltros
Wm (z Lm ) e dada pela seguinte equac~ao:
wm;k (n) = wm;k (n ? 1)+ m(n)e(n)xm (n ? Lmk);
(16)
para m = 0; 1; : : :; M ? 1 e k = 0; 1; : : :; Km ? 1,
onde
e(n) = d(n ? ) ? y(n);
(17)
sendo que o atraso depende da ordem dos ltros
prototipos g0 (n) e g1 (n) utilizados nos bancos de
ltros e da forma em que s~ao dispostos (cascateados) para formar a wavelet, conforme descrito na
Sec~ao 2.2. Re-escrevendo a equac~ao (16) na forma
vetorial, usando os vetores previamente denidos,
obtemos a seguinte equac~ao para a adaptac~ao de
todos os coecientes dos sub-ltros Wm (z Lm ) :
2
H0
3
w(n) = w(n ? 1) + (n)e(n) 64 ... 75 xaum(n):
HM ?1
(18)
Tirando o valor esperado da equac~ao de atualizac~ao acima e assumindo que os sinais s~ao estacionarios, n~ao havendo correlac~ao entre o vetor de
entrada xaum (n) e o vetor de coecientes do ltro adaptativo w(n), podemos armar que, para
a estrutura em sub-bandas, o desempenho do algoritmo adaptativo esparso em sub-bandas e governado pela raz~ao entre os autovalores maximo
e mnimo (max =min ), n~ao-nulos, da matriz de
correlac~ao do vetor de entrada transformado, dada
por
2
H0
3
Rt = 64 ... 75 Rx HT0 HTM ?1 ; (19)
HM ?1
sendo Rx a matriz de correlac~ao do vetor de en-
trada aumentado, i.e.,
Rx = E xaum (n)xaum (n)T : (20)
Na formac~ao das matrizes Hm em (11), os fatores de esparsidade s~ao levados em considerac~ao.
A escolha do fator de esparsidade para cada
banda, bem como dos ltros prototipos e do
numero de estagios, altera os auto-valores da matriz Rt e, portanto, o desempenho da estrutura.
E possvel selecionar os ltros prototipos G0 (z ) e
G1 (z ) para uma dada aplicac~ao, conhecendo-se o
tipo de sinal de entrada e os par^ametros da estrutura (fatores de esparsidade e numero de coecientes adaptativos).
Para vericarmos a eci^encia dos ltros
prototipos que servir~ao de base para a transformada wavelet, podemos usar como criterio de desempenho para a estrutura a relac~ao entre os autovalores da matriz Rt da equac~ao (19).
4 Simulac~oes
Foram selecionadas algumas wavelets discretas
(Vetterli e Kovacevic, 1995) para vericar o desempenho da estrutura quando submetida a um
sinal colorido passa-baixas. Este sinal colorido
corresponde a um processo auto-regressivo de 1a
ordem, obtido passando-se um rudo branco, com
media zero e vari^ancia unitaria, por um ltro IIR
com polo em 0,9. O sistema a ser identicado possui comprimento N = 140.
Dois tipos de ltros prototipos foram utilizados para esta avaliac~ao de desempenho: ltros
Daubechies de comprimento 4, 6, 8 e 12 (Daub4,
Daub6, Daub8 e Daub12, respectivamente) e os
ltros Biortogonais descritos na tabela 1.
O desempenho da estrutura pode ser observado nas Figs. 5 a 7, utilizando-se um numero
diferente de estagios. A estrutura utilizada neste
exemplo decomp~oe somente a banda de mais baixas frequ^encias de cada estagio. Para um estagio,
teremos apenas duas bandas, cujos fatores de esparsidade devem ser L0 = L1 = 2. Para dois
estagios, temos 3 bandas, com fatores de esparsidade L0 = 2, L1 = 4 e L2 = 4, correspondentes aos fatores de decimac~ao da wavelet. Da
mesma forma, para 3 estagios, os fatores de esparsidade a serem utilizados ser~ao L0 = 2, L1 = 4, e
L2 = L3 = 8.
Da Fig. 5 observa-se que a estrutura proposta
com duas bandas e prototipos Daubechies possui,
praticamente, o mesmo desempenho que o algoritmo LMS normalizado, assim como os prototipos
biortogonais Bio6-2 e Bio10-6. Quando se utiliza
os ltros biortogonais Bio5-3 e Bio9-7, a estrutura
apresenta taxa de converg^encia superior a do LMS
normalizado (aproximadamente -50dB).
Quando se acrescenta mais um estagio na estrutura proposta, as taxas de converg^encia com os
prototipos Biortogonais e Daubechies melhoram
ligeiramente, com excec~ao da converg^encia com os
ltros Bio5-3 e Bio9-7 que apresentam uma signicante acelerac~ao, atingindo o valor mnimo do
erro medio quadratico aproximadamente em 8000
iterac~oes.
Ao utilizarmos 3 estagios para a decomposic~ao
do sinal de entrada, obtivemos taxas de converg^encia ainda melhores que para 2 estagios. O
algoritmo, utilizando 3 estagios e os prototipos
Bio5-3 e Bio9-7, consegue processar o rudo colorido como se fosse um rudo branco, ou seja,
a transformac~ao realizada pela wavelet consegue,
praticamente, \branquear" o sinal colorido de entrada. Isto pode ser observado na Fig. 7, onde ambos os prototipos atingem o valor mnimo do erro
quadratico em aproximadamente 5500 iteraco~es.
A complexidade do algoritmo esparso e a
mesma do algoritmo LMS convencional, acrescida
do numero de operac~oes necessarias para a implementac~ao da transformac~ao wavelet. Quanto
maior o numero de estagios e o comprimento dos
ltros prototipos, maior sera a complexidade computacional do algoritmo. Note que se zermos
M = 1 e K = N , o algoritmo esparso se reduz
ao algoritmo LMS convencional.
Na tabela 2 e mostrada a relac~ao entre os autovalores maximo e mnimo da matriz de autocorrelac~ao Rt do sinal transformado pela wavelet
correspondente a estrutura da Fig. 2, com ate tr^es
estagios (J = 1; 2; 3).
Comparando a tabela 2 e as Figs. 5 a 7, vemos
que a relac~ao entre os autovalores nos fornece uma
boa ideia sobre a taxa de converg^encia da estrutura, servindo como um fator de selec~ao de ltros
prototipos e dos par^ametros da estrutura (estagios
e decomposic~ao de bandas) para ltragem adap-
colorido, com taxa de converg^encia proxima a obtida com um rudo branco, ou seja, \branquear" o
sinal de entrada, sem que o custo computacional
se torne extremamente elevado quando comparado
ao LMS convencional.
0
-20
-40
MSE (dB)
tativa utilizando transformadas wavelets. E importante ressaltar que quanto menor for a relaca~o
entre os autovalores maximo e mnimo da matriz
Rt, melhor sera a converg^encia do algoritmo e,
a medida que esta relac~ao se aproxima do valor
unitario, melhor estara sendo o desempenho da
transformac~ao em branquear o sinal de entrada.
Na Fig. 8 s~ao mostradas as curvas de converg^encia para o algoritmo utilizando 3 estagios
e o prototipo Bio5-3, para o sinal de entrada colorido descrito anteriormente e para rudo branco
com vari^ancia unitaria e media zero.
-60
-80
Coecientes
g0 (n) = 18 f?1 1 8 8 1 ? 1g
g1 (n) = 18 f1 ? 1g
Bio5-3 g0 (n) = 14 f?1 2 6 2 ? 1g
g1 (n) = 14 f?1 2 ? 1g
Bio9-7 g0 (n) = 641 f1 0 ? 8 16 46 16 ? 8 0 1g
g1 (n) = 641 f?1 0 ? 9 16 ? 9 0 1g
1 f1 1 ? 8 8 62 62 8 ? 8 1 1g
Bio10-6 g0 (n) = 128
1 f?1 ? 1 8 ? 8 1 1g
g1 (n) = 128
-100
-120
0
67,38
58,75
55,09
52,88
92,63
22,53
34,28
61,63
24,42
18,17
15,90
14,66
50,64
6,13
13,95
19,32
Tabela 2. Relac~ao de autovalores para diferentes numeros
de estagios e ltros prototipos
3000
5000
6000
7000
8000
4000
5000
6000
7000
8000
Bio6-2
Bio5-3
Bio9-7
Bio10-6
NLMS
-120
0
1000
Amostras
Figura 5. Converg^encia utilizando wavelet com 1 estagio
para prototipos Daubechies e binarios biortogonais - rudo
colorido
0
-20
-40
-60
-80
-100
Daub4
Daub6
Daub8
Daub12
NLMS
-120
5 Conclus~oes
-140
-160
0
1000
2000
3000
4000
5000
6000
7000
8000
4000
5000
6000
7000
8000
0
-20
-40
-60
MSE (dB)
Uma nova estrutura para ltragem adaptativa,
que utiliza uma transformada wavelet e ltros esparsos, foi proposta neste artigo. O desempenho desta estrutura depende da escolha dos ltros prototipos que comp~oem a transformada wavelet discreta e dos demais par^ametros da estrutura (fatores de esparsidade e numero de coecientes adaptativos). Um criterio de converg^encia
foi derivado, que permite avaliar a eci^encia de
diferentes wavelets na melhoria da taxa de converg^encia do algoritmo adaptativo para um dado
sinal de entrada. Foi mostrado atraves de simulac~oes que, escolhendo-se adequadamente a
transformada, o algoritmo proposto e capaz de
realizar a adaptac~ao, para um sinal de entrada
2000
4000
-60
-80
MSE (dB)
175,01
175,12
175,23
175,45
175,34
87,54
101,42
175,25
3000
-40
-100
max =min
J =1 J =2 J =3
2000
-20
Tabela 1. Filtros prototipos biortogonais
Filtro
Prototipo
Daub4
Daub6
Daub8
Daub12
Bio6-2
Bio5-3
Bio9-7
Bio10-6
1000
0
MSE (dB)
Filtro
Bio6-2
Daub4
Daub6
Daub8
Daub12
NLMS
-80
-100
Bio6-2
Bio5-3
Bio9-7
Bio10-6
NLMS
-120
-140
-160
0
1000
2000
3000
Amostras
Figura 6. Converg^encia utilizando wavelet com 2 estagios
para prototipos Daubechies e binarios biortogonais - rudo
colorido
0
-20
-40
MSE (dB)
-60
-80
-100
Daub4
Daub6
Daub8
Daub12
NLMS
-120
-140
-160
0
1000
2000
3000
4000
5000
6000
7000
8000
4000
5000
6000
7000
8000
0
-20
-40
MSE (dB)
-60
-80
-100
Bio6-2
Bio5-3
Bio9-7
Bio10-6
NLMS
-120
-140
-160
0
1000
2000
3000
Amostras
Figura 7. Converg^encia utilizando wavelet com 3 estagios
para prototipos Daubechies e binarios biortogonais - rudo
colorido
0
-20
-40
MSE (dB)
-60
-80
-100
Ruido Branco
Ruido Colorido
-120
-140
-160
0
1000
2000
3000
4000
Amostras
5000
6000
7000
8000
Figura 8. Converg^encia utilizando wavelet com 3 estagios
para o prototipo Bio5-3 para rudo branco e colorido
Refer^encias Bibliogracas
Petraglia, M. R. e Mitra, S. K. (1993). Adaptive
r lter structure based on the generalized
subband decomposition of r lters, Vol. Vol
- 40 No 6, pp. 354{362.
Strang, G. e Nguyen, T. (1997). Wavelets and
Filter Banks, Wellesley-Cambrigde-Press.
Vetterli, M. e Herley, C. (1992). Wavelets and
lter banks: Theory and design, Vol. Vol 40
- No 9, pp. 2207{2231.
Vetterli, M. e Kovacevic, J. (1995). Wavelets and
Subband Coding, Prentice-Hall, Englewood
Clis, New Jersey.