Nueva variante del algoritmo NLMS/F de bajo
costo computacional
New variant of NLMS/F algorithm with low computational cost
Laura Jazmín Hidalgo Hernández
#1
, Ángel Alfonso Vázquez Piña
#2
, Xochitl Maya Rosales
#3
, Juan Gerardo
Avalos Ochoa
#4
, Giovanny Sánchez Rivera
#5
#
Sección de Estudios de Posgrado e Investigación, Instituto Politécnico Nacional
Ciudad de México, México
1
lhidalgoh1300@alumno.ipn.mx
2
avazquezp1301@alumno.ipn.mx
3
xmayar1300@alumno.ipn.mx
4
javaloso@ipn.mx
5
gsanchezriv@ipn.mx
Abstract— Ad
aptive filters are used in a wide variety of signal
processing applications (e.g., acoustic echo cancellation, system
identification, channel equalization, etc.). Adaptive algorithms
are an essential part of adaptive filters since they update the
filter coefficients to model the desired response. Therefore,
adaptive algorithms must have low computational cost and high
speed of convergence. In this paper, a new variant of the
Normalized Least-Mean-Fourth (NLMF) algorithm based on
set membership is presented, in addition, a method to
automatically adjust the step size is presented. To evaluate its
performance, the algorithm was simulated in system
identification and acoustic echo cancellation applications. The
results demonstrate that the proposed algorithm improves the
convergence speed and exhibits low computational cost
compared to the conventional NLMS/F algorithm.
Keywords: NLMF algorithm; NLMS/F algorithm; set
membership; adaptive filtering.
Resumen—El filtrado adaptativo es utilizado ampliamente
en aplicaciones de procesamiento de señales, entre las que se
encuentran: cancelación de eco acústico, identificación de
sistemas, ecualización de canales, entre otras. El elemento más
importante de un filtro adaptativo es el algoritmo adaptativo, el
cual tiene la función de ajustar los coeficientes del filtro para
minimizar la señal de error. Por tal motivo, es necesario un
algoritmo adaptativo que presente una baja carga
computacional y una alta velocidad de convergencia. En este
artículo, se presenta una nueva variante del algoritmo de
mínimos promediados de cuarto orden normalizado (NLMF -
Normalized Least-Mean-Fourth) basado en el conjunto de
membresías, además, se propone un método que permite ajustar
el factor de convergencia de forma automática. Para evaluar su
funcionamiento, el algoritmo se simuló en un identificador de
sistemas y un cancelador de eco acústico. Los resultados
obtenidos demuestran que el algoritmo propuesto mejora la
velocidad de convergencia, además de exhibir un bajo costo
computacional en comparación con el algoritmo NLMS/F
convencional.
Palabras clave: Algoritmo NLMF; algoritmo NLMS/F;
conjunto de membresías; filtrado adaptativo.
I. INTRODUCCIÓN
El
objetivo de un algoritmo adaptativo es ajustar los
coeficientes de un filtro variante en el tiempo con el fin de
minimizar un criterio previamente establecido. Uno de los
algoritmos más conocidos es el algoritmo de mínimos
cuadrados promediados normalizado (NLMS - Normalized
Least-Mean-Square) debido a que su bajo costo
computacional permite su implementación en una gran
variedad de aplicaciones [1-4]. Asimismo, existen variantes
que mejoran las propiedades de convergencia de dicho
algoritmo, como el algoritmo de mínimos promediados de
cuarto orden normalizado (NLMF - Normalized Least-Mean-
Fourth). No obstante, su costo computacional e inestabilidad
son mayores con respecto al algoritmo NLMS [5-7]. Por tal
motivo, han surgido variantes como el algoritmo NLMS/F
[8,9], el cual regula el comportamiento del algoritmo
dependiendo de la señal de error y un parámetro previamente
establecido.
En años recientes, diversos autores han propuesto métodos
para reducir el costo computacional de los algoritmos
adaptativos. Una de las técnicas más eficientes es la de
conjunto de membresías (SM - Set-Membership) [10-12], en
la cual los algoritmos actualizan los coeficientes del filtro si la
señal de error es mayor a un umbral previamente establecido,
por lo tanto, el número de operaciones se disminuye
considerablemente una vez que la potencia del error se ha
reducido.
En este trabajo se presenta una nueva variante del algoritmo
NLMS/F basado en la técnica del conjunto de membresías.
Adicionalmente, se propone un método que ajusta de forma
dinámica un parámetro que permite regular el
comportamiento del algoritmo, facilitando de esta forma su
implementación en diversas aplicaciones. Los resultados
obtenidos demuestran que el algoritmo propuesto reduce la
carga computacional, además, de mejorar la velocidad de
convergencia con respecto a su vers
ión convencional.
Revista elektron, Vol. 6, No. 2, pp. 96-100 (2022)
ISSN 2525-0159
96
Recibido: 04/10/22; Aceptado: 01/12/22
Creative Commons License - Attribution-NonCommercial-
NoDerivatives 4.0
International (CC BY-NC-ND 4.0)
https://doi.org/10.37537/rev.elektron.6.2.163.2022
Original Article
II. COMBINACIÓN DE LOS ALGORITMOS NLMS Y NLMF
La expresión general del algoritmo NLMS para la
actualización de los coeficientes del filtro está dada por:
𝐰(𝑛+1)'='𝐰(𝑛)'+
!
"
!
#
$
%
"
#
$
%
&'
𝐱(𝑛)𝑒(𝑛)
(1)
donde
𝐰(𝑛+1)
es el vector de coeficientes en el instante
de tiempo
𝑛+1
,
𝜇
es el factor de convergencia,
𝐱(𝑛)
es la
señal de entrada al filtro,
𝜌
es una constante pequeña usada
para evitar la indeterminación y
𝑒(𝑛)
es la señal de error, la
cual se obtiene mediante:
𝑒(𝑛)=𝑑
(
𝑛
)
−𝐰
(
(
𝑛
)
𝐱
(
𝑛
)
+𝜂(𝑛)
(2)
donde
𝑑
(
𝑛
)
es la señal deseada y
𝜂 (𝑛)
representa la señal
de ruido aditivo. La función de costo del algoritmo NLMS se
define como:
𝐿
)
(
𝑛
)
=
)
*
𝑒
*
(𝑛)
(3)
Por otro lado, la actualización de los coeficientes del filtro
y la función de costo del algoritmo NLMF se presenta en (4)
y (5), respectivamente.
𝐰(𝑛+1)'='𝐰(𝑛)'+
!
"
"
#
+
%
"
#
$
%
&'
𝐱(𝑛)𝑒
,
(𝑛)
(4)
𝐿
*
(
𝑛
)
=
)
*
𝑒
-
(𝑛)
(5)
Uniendo las funciones de costo de los algoritmos LMS y
NLMF, se obtiene la siguiente función de costo:
𝐿
,
(
𝑛
)
=
)
*
𝑒
*
(
𝑛
)
−
)
*
𝜀'ln'(𝑒
*
(
𝑛
)
+𝜀)
(6)
donde
𝜀
es un parámetro que permite conmutar entre
ambos algoritmos, por lo tanto, regula la velocidad de
convergencia y el rendimiento del algoritmo, al cual se le
asigna un valor positivo
𝜀>0
. De esta forma, la ecuación de
actualización de coeficientes del algoritmo NLMS/F se
expresa como:
𝐰(𝑛+1)'='𝐰(𝑛)'+
!
"
"
#
$
%
"
#
$
%
&'
𝐱(𝑛)𝛽(𝑛)
(7)
donde
𝛽 (𝑛)
es definida por:
𝛽 (𝑛)='
.
#
#$%
.
$
#
$
%
&/
(8)
Como se puede observar en (8), cuando
𝜀≫𝑒
*
(
𝑛
)
, el
algoritmo NLMS/F se comporta como un algoritmo NLMF
con un factor de convergencia de
𝜇/𝜀
, y cuando
𝜀≪𝑒
*
(
𝑛
)
,
se comporta como un algoritmo NLMS con un factor de
convergencia de
𝜇
. Por lo tanto, el valor de
𝜀
es crucial para
determinar el comportamiento del algoritmo.
III. F
ILTRADO ADAPTATIVO POR CONJUNTO DE MEMBRESÍAS
La estrategia denominada conjunto de membresías
establece una regla para la actualización de los coeficientes
del filtro, en la cual se requiere que la magnitud de la señal del
error sea menor o igual a un umbral preestablecido,
𝛾
;, de
modo que los coeficientes del filtro pertenezcan a un conjunto
de soluciones factibles definidos mediante:
𝛩=
⋂
{
𝐰∈ℛ
0
:''
|
𝑑−𝐰
1
𝐱
|
'≤''𝛾
;
}
'
2
#
345
%
67
(9)
donde
𝑆
denota el conjunto de todos los posibles valores de
𝒙
y
𝑑
. En algunas aplicaciones no es posible acceder a
𝑑
, por
lo que es necesario definir un conjunto de restricciones
denominado
ℋ(𝑛)
, el cual se expresa como:
ℋ(𝑛)=
{
𝐰∈ℛ
0
:''
|
𝑑(𝑛)−𝐰
1
𝐱(𝑛)
|
'≤''𝛾
;
}
(10)
Los límites de
ℋ(𝑛)
, son considerados como un conjunto
de hiperplanos paralelos
e
(
n
)
=±'𝛾
;, donde la intersección
entre el conjunto de restricciones y los hiperplanos es
denominado conjunto de membresías
𝜓
(
𝑛
)
.
𝜓
(
𝑛
)
=
⋂
ℋ(𝑖)
$
8 9:
(11)
Específicamente, si el conjunto
𝜓
(
𝑛
)
se encuentra en
ℋ(𝑖)
, no se requiere calcular los coeficientes del vector
𝐰
, ya
que estos se encuentran dentro del conjunto solución.
IV. A
LGORITMO SM-NLMS/F
Para aplicar la teoría SM en el algoritmo NLMS/F, se
sustituye la función de error,
𝛽 (𝑛)
, en el cálculo del factor de
convergencia del algoritmo SM-NLMS convencional [12], la
cual se expresa como:
𝜇(𝑛)=
L
1−
;
<
=
># $%
=
𝑠𝑖'
|
𝛽 (𝑛)
|
>𝛾
;
0 𝐶𝑎𝑠𝑜'𝑐𝑜𝑛𝑡𝑟𝑎𝑟𝑖𝑜
(12)
Al aplicar la regla descrita en (12), se reduce el costo
computacional del algoritmo ya que cuando
|
𝛽 (𝑛)
|
<𝛾
;, el
factor de convergencia es igual a cero, por lo tanto, no se
requiere realizar la actualización de los coeficientes del filtro.
𝜀(𝑛)=
U
𝛽
*
(𝑛) 𝑠𝑖'
|
𝛽 (𝑛)
|
>𝛾
;
𝜀(𝑛−1) 𝐶𝑎𝑠𝑜'𝑐𝑜𝑛𝑡𝑟𝑎𝑟𝑖𝑜
(13)
El valor
𝛾
; se propone cercano a
𝛾
;
=
V
5σ
?
*
, donde
σ
?
*
denota la varianza del ruido aditivo.
Por otra parte, cabe mencionar que el comportamiento de
la señal
𝑒
*
(
𝑛
)
en las primeras iteraciones del algoritmo
NLMS/F suele ser mayor a
𝜀
, debido a que a
𝜀
se le asigna un
valor pequeño. Además, al establecer que
𝜀
(
𝑛
)
=𝛽
*
(
𝑛
)
el
valor de
𝜀
aumentará garantizando que
𝜀≫𝑒
*
(
𝑛
)
, por lo
tanto, el algoritmo tendrá una tendencia a comportarse como
un algoritmo NLMF y al aplicar la técnica de conjunto de
membresías, el número de actualizaciones se reducirá
considerablemente debido a que solo actualizará al algoritmo
cuando
|
𝛽
(
𝑛
)
|
supere el umbral
𝛾
;.
V. R
ESULTADOS
Para demostrar el funcionamiento del algoritmo propuesto,
se realizaron dos pruebas, en las cuales se comparó el
funcionamiento del algoritmo propuesto y el algoritmo
NLMS/F en una estructura de identificador de sistemas y
cancelación de eco acústico.
Revista elektron, Vol. 6, No. 2, pp. 96-100 (2022)
ISSN 2525-0159
97
http://elektron.fi.uba.ar
A. Identificador de sistemas
En la Fig. 1 se muestra la estructura utilizada como
identificador de sistemas, donde la señal de entrada es ruido
blanco Gaussiano con varianza unitaria. El sistema
desconocido es un filtro de respuesta finita al impulso (FIR -
Finite Impulse Response) pasa bajas. Se realizaron tres
pruebas diferentes para comprobar el funcionamiento de la
propuesta, donde la señal deseada es afectada por un ruido
Gaussiano aditivo con una relación señal a ruido (SNR –
Signal to Noise Ratio) de 15dB, 20dB y 33dB. El filtro
adaptativo y el sistema desconocido contaron con 16
coeficientes. Para el algoritmo NLMS/F se eligió
𝜇=0.4
y
𝜖=0.000001
, dichos valores se obtuvieron a prueba y error,
y se establecieron de tal forma que el algoritmo presentará la
mayor velocidad de convergencia. Para evaluar el
funcionamiento de los algoritmos se obtuvo el nivel de error
cuadrático medio (MSE - Mean Square Error) al promediar 50
experimentos. Adicionalmente, durante el proceso de
adaptación se realizó un cambio abrupto a la mitad de las
iteraciones, al multiplicar los coeficientes del sistema
desconocido por -1, esto con la finalidad de evaluar las
capacidades de seguimiento del algoritmo.
Fig. 1. Diagrama general de la estructura de un identificador de sistemas.
Como se muestra en la Fig. 2(a-c), el algoritmo propuesto
presenta la mayor velocidad de convergencia tanto al inicio
del experimento como al momento de realizar el cambio de
coeficientes en el sistema desconocido. Además, el nivel de
MSE es similar para ambos algoritmos. Sin embargo, al
aplicar la técnica de conjunto de membresías el algoritmo
propuesto no requiere de actualizar los coeficientes del filtro
durante todo el proceso. Como se puede observar en la Tabla
I, para este experimento el número de actualizaciones
disminuye considerablemente mientras que el algoritmo
NLMS/F requiere el cálculo de sus coeficientes durante todo
el proceso.
TABLA I
P
ORCENTAJE DE ACTUALIZACIONES DEL ALGORITMO SM-NLMS/F
UTILIZANDO COMO SEÑAL DE ENTRADA RUIDO BLANCO
GAUSSIANO
Algoritmo
SM-NLMS/F
Fig. 2. Nivel de MSE de los algoritmos NMLS/F y SM-NLMS/F
utilizando como señal de entrada ruido blanco Gaussiano y (a) SNR
de 15dB, (b) SNR de 20dB, (c) SNR de 33dB.
Para el segundo experimento, se utilizó como señal de
entrada el ruido de una turbina de avión. El sistema
desconocido es un filtro FIR pasa bajas, en este caso tanto el
filtro adaptativo como el desconocido contaron con 32
coeficientes. Para probar el rendimiento del algoritmo se
realizaron tres pruebas donde a la salida del sistema
desconocido se añadió ruido aditivo con una SNR de 15dB,
20dB y 33dB. Para el algoritmo NLMS/F se estableció
𝜇=
0.5
y
𝜖=0.00005
, ya que estos valores entregaron el mejor
desempeño del algoritmo. Las curvas de aprendizaje se
obtuvieron al promediar 200 experimentos, de igual forma
que en el primer experimento se realizó un cambio abrupto a
la mitad de las iteraciones para probar las capacidades de
seguimiento del algoritmo.
Fig. 3. Nivel de MSE de los algoritmos NMLS/F y SM-NLMS/F
utilizando como señal de entrada el ruido de una turbina de avión y
(a) SNR de 15dB, (b) SNR de 20dB, (c) SNR de 33dB.
Revista elektron, Vol. 6, No. 2, pp. 96-100 (2022)
ISSN 2525-0159
98
http://elektron.fi.uba.ar
Como se muestra en la Fig. 3(a-c), la velocidad de
convergencia y el nivel de MSE de ambos algoritmos es muy
similar. No obstante, como se observa en la Tabla II, el
algoritmo propuesto disminuye ampliamente el número de
actualizaciones, a pesar de los diferentes niveles de SNR.
TABLA II
P
ORCENTAJE DE ACTUALIZACIONES DEL ALGORITMO SM-NLMS/F
UTILIZANDO COMO SEÑAL DE ENTRADA EL RUIDO DE UNA
TURBINA DE AVIÓN
Algoritmo
SM-NLMS/F
B. Cancelador de eco acústico
Para esta prueba se simuló un sistema de cancelación de
eco acústico, la estructura de dicho sistema se muestra en la
Fig. 4. Para modelar la trayectoria de eco de una habitación se
utilizó la función de transferencia obtenida de [13], la cual fue
modelada con un filtro FIR de 1024 coeficientes. Se utilizó
como señal de extremo lejano una grabación de voz
muestreada a 8kHz con una duración de 9.25 segundos. La
señal deseada es la suma del ruido de fondo,
𝜂 (𝑛)
, y la señal
de eco,
𝑦(𝑛)
. Donde
𝜂 (𝑛)
se estableció como una señal
independiente de ruido blanco Gaussiano con una SNR de 20
dB. El rendimiento de los algoritmos NLMS/F y SM-NLMS/F
se evaluó en términos de la mejora de pérdida de retorno del
eco (ERLE- Echo Return Loss Enhancement). El algoritmo
NLMS/F se ajustó con los siguientes parámetros:
𝜇=0.6
y
𝜖=0.0001
.
Fig. 4. Estructura general de un sistema cancelador de eco acústico.
En la Fig. 5 se muestran los resultados del experimento,
como se puede observar ambos algoritmos tienen un
rendimiento similar, a pesar de ello el algoritmo propuesto
actualiza sus coeficientes únicamente en 28,378 iteraciones,
es decir, reduce en un 61% el computo de sus coeficientes,
mientras que el algoritmo NLMS/F realiza el 100% de las
actualizaciones.
Fig. 5. Nivel de ERLE de los algoritmos NLMS/F y SM-NLMS/F
utilizando una grabación de voz como señal de entrada.
TABLA
IIII
N
ÚMERO DE OPERACIONES POR ITERACIÓN
Algoritmo
Multiplicaciones
Sumas
NLMS/F
3N+4
3N+1
SM-NLMS/F
3N+4
3N+2
En la Tabla 1 se muestra el número de operaciones
requeridas por los algoritmos NLMS/F y SM-NLMS/F, donde
N representa la longitud del filtro adaptativo. Como se puede
observar el algoritmo NLMS/F requiere 3N+4
multiplicaciones y 3N+1 sumas, mientras que el algoritmo
propuesto precisa de 3N+4 multiplicaciones y 3N+2 sumas.
Cabe mencionar que el algoritmo propuesto no requiere el
cálculo de sus coeficientes durante todo el proceso, por lo que
el costo computacional se reduce al aplicar la técnica del
conjunto de membresías.
VI. C
ONCLUSIONES
En este artículo se presentó una variante del algoritmo
adaptativo NLMS/F basado en el conjunto de membresías.
Adicionalmente, se propuso un método para establecer de
manera automática el factor de convergencia del algoritmo.
Los resultados experimentales demuestran que el algoritmo
propuesto alcanza una mayor velocidad de convergencia y un
nivel de MSE similar con respecto al algoritmo NLMS/F.
Además, el número de multiplicaciones y sumas realizadas al
ejecutar el algoritmo propuesto se reducen significativamente,
debido a que no se requiere calcular los coeficientes del filtro
durante todo el proceso adaptativo, por lo que lo convierte en
una gran opción para el desarrollo de sistemas prácticos.
AGRADECIMIENTOS
Los autores agradecen al Consejo Nacional de Ciencia y
Tecnología (CONACYT) y al Instituto Politécnico Nacional
(IPN) por el apoyo financiero para la realización de este
trabajo.
R
EFERENCIAS
[1] S. S. Haykin, Adaptive filter theory, Fifth edition, International edition.
Upper Saddle River Boston Columbus San Francisco New York:
Pearson, 2014.
[2] S. Li, S. Wu, Y. Wang, W. Guo, y Y. Zhou, "An improved NLMS
algorithm based on speech enhancement", en 2015 IEEE Advanced
Information Technology, Electronic and Automation Control
Conference (IAEAC), Chongqing, China, dic. 2015, pp. 896-899. doi:
10.1109/IAEAC.2015.7428686.
Revista elektron, Vol. 6, No. 2, pp. 96-100 (2022)
ISSN 2525-0159
99
http://elektron.fi.uba.ar
[3] F. Wang, Q. Wang, F. Liu, J. Chen, L. Fu, y F. Zhao, "Improved
NLMS-based adaptive denoising method for ECG signals", THC, vol.
29, n.º 2, pp. 305-316, mar. 2021, doi: 10.3233/THC-202659.
[4] J. Benesty, C. Paleologu, S. Ciochina, E. V. Kuhn, K. J. Bakri, y R.
Seara, "LMS and NLMS Algorithms for the Identification of Impulse
Responses with Intrinsic Symmetric or Antisymmetric Properties", en
ICASSP 2022 - 2022 IEEE International Conference on Acoustics,
Speech and Signal Processing (ICASSP), Singapore, Singapore, may
2022, pp. 5662-5666. doi: 10.1109/ICASSP43922.2022.9747430.
[5] A. Zerguine, "Convergence and steady-state analysis of the normalized
least mean fourth algorithm", Digital Signal Processing, vol. 17, n.º 1,
pp. 17-31, ene. 2007, doi: 10.1016/j.dsp.2006.01.005.
[6] E. Eweda y N. J. Bershad, "Stochastic Analysis of a Stable Normalized
Least Mean Fourth Algorithm for Adaptive Noise Canceling With a
White Gaussian Reference", IEEE Trans. Signal Process., vol. 60, n.º
12, pp. 6235-6244, dic. 2012, doi: 10.1109/TSP.2012.2215607.
[7] A. Zerguine, "Convergence behavior of the normalized least mean
fourth algorithm", en Conference Record of the Thirty-Fourth
Asilomar Conference on Signals, Systems and Computers (Cat.
No.00CH37154), Pacific Grove, CA, USA, 2000, vol. 1, pp. 275-278.
doi: 10.1109/ACSSC.2000.910958.
[8] B. Mohanty, H. K. Sahoo, y B. Patnaik, "Block NLMS/F-based
equalizer design and channel capacity analysis for indoor IEEE 802.11
fading wireless channels", SIViP, vol. 13, n.º 4, pp. 693-701, jun. 2019,
doi: 10.1007/s11760-018-1398-2.
[9] B. Mohanty, H. K. Sahoo, y B. Patnaik, "NLMS/F Based Adaptive
Beam former for Indoor Wireless Channel", en 2017 Ninth
International Conference on Advanced Computing (ICoAC), Chennai,
dic. 2017, pp. 87-91. doi: 10.1109/ICoAC.2017.8441186.
[10] P. S. R. Diniz, "Set-Membership Adaptive Filtering", en Adaptive
Filtering: Algorithms and Practical Implementation, P. S. R. Diniz, Ed.
Cham: Springer International Publishing, 2020, pp. 189-229. doi:
10.1007/978-3-030-29057-3_6.
[11] I. Hassani, M. Arezki, y A. Benallal, "A novel set membership fast
NLMS algorithm for acoustic echo cancellation", Applied Acoustics,
vol. 163, p. 107210, jun. 2020, doi: 10.1016/j.apacoust.2020.107210.
[12] S. Gollamudi, S. Nagaraj, S. Kapoor and Yih-Fang Huang, "Set-
membership filtering and a set-membership normalized LMS
algorithm with an adaptive step size," in IEEE Signal Processing
Letters, vol. 5, no. 5, pp. 111-114, May 1998, doi: 10.1109/97.668945.
[13] C. Paleologu, S. Ciochina and J. Benesty, "Variable Step-Size NLMS
Algorithm for Under-Modeling Acoustic Echo Cancellation," in IEEE
Signal Processing Letters, vol. 15, pp. 5-8, 2008, doi:
10.1109/LSP.2007.910276.
Revista elektron, Vol. 6, No. 2, pp. 96-100 (2022)
ISSN 2525-0159
100
http://elektron.fi.uba.ar