Hispanopedia Wiki
Articulo de referencia

Algoritmo de diseño de filtros de Parks-McClellan

Bandas de paso y de rechazo de un filtro diseñado por el algoritmo de Parks-McClellan. El eje y es la respuesta en frecuencia H (ω) y el eje x son las distintas frecuencias angu...

Hispanopedia WikiContenido en espanolLectura gratuita
Bandas de paso y de rechazo de un filtro diseñado por el algoritmo de Parks-McClellan. El eje y es la respuesta en frecuencia H (ω) y el eje x son las distintas frecuencias angulares, ωi . Se puede observar que las dos frecuencias marcadas en el eje x, ωp y ωs . ωp indica la frecuencia de corte de la banda de paso y ωs indica la frecuencia de corte de la banda de rechazo. La gráfica ondulada en la parte superior izquierda es la ondulación de la banda de paso y la ondulación en la parte inferior derecha es la ondulación de la banda de rechazo. Las dos líneas discontinuas en la parte superior izquierda de la gráfica indican δp y las dos líneas discontinuas en la parte inferior derecha indican δs . Todas las demás frecuencias enumeradas indican las frecuencias extremas de la gráfica de respuesta en frecuencia. Como resultado, hay seis frecuencias extremas, luego agregamos las frecuencias de la banda de paso y de la banda de rechazo para dar un total de ocho frecuencias extremas en la gráfica.

El algoritmo de Parks-McClellan , publicado por James McClellan y Thomas Parks en 1972, es un algoritmo iterativo para encontrar el filtro de respuesta de impulso finito (FIR) de Chebyshev óptimo . Este algoritmo se utiliza para diseñar e implementar filtros FIR eficientes y óptimos. Emplea un método indirecto para hallar los coeficientes óptimos del filtro.

El objetivo del algoritmo es minimizar el error en las bandas de paso y rechazo mediante la aproximación de Chebyshev. El algoritmo de Parks-McClellan es una variación del algoritmo de intercambio de Remez , con la particularidad de que está diseñado específicamente para filtros FIR. Se ha convertido en un método estándar para el diseño de filtros FIR.

Historia

Historia del diseño óptimo de filtros FIR

En la década de 1960, los investigadores en el campo del diseño de filtros analógicos utilizaban la aproximación de Chebyshev para el diseño de filtros. En ese momento, era bien sabido que los mejores filtros presentaban una característica de ondulación uniforme en la magnitud de su respuesta en frecuencia , y el filtro elíptico (o filtro de Cauer) era óptimo con respecto a la aproximación de Chebyshev. Cuando comenzó la revolución de los filtros digitales en la década de 1960, los investigadores utilizaron una transformación bilineal para producir filtros elípticos digitales de respuesta impulsional infinita (IIR). También reconocieron el potencial del diseño de filtros FIR para lograr la misma tarea de filtrado, y pronto se inició la búsqueda del filtro FIR óptimo utilizando la aproximación de Chebyshev. [ 1 ]

Era bien sabido, tanto en matemáticas como en ingeniería, que la respuesta óptima exhibiría un comportamiento de ondulación uniforme y que el número de ondulaciones podía contarse utilizando la aproximación de Chebyshev. Entre 1962 y 1971 se realizaron varios intentos para desarrollar un programa de diseño para el filtro FIR de Chebyshev óptimo. [ 1 ] A pesar de los numerosos intentos, la mayoría no tuvieron éxito, generalmente debido a problemas en la implementación algorítmica o en la formulación del problema. Otto Herrmann, por ejemplo, propuso un método para diseñar filtros de ondulación uniforme con bordes de banda restringidos. [ 1 ] Este método obtenía una respuesta en frecuencia de ondulación uniforme con el número máximo de ondulaciones resolviendo un conjunto de ecuaciones no lineales. Otro método introducido en ese momento implementaba una aproximación de Chebyshev óptima, pero el algoritmo se limitaba al diseño de filtros de orden relativamente bajo. [ 1 ]

De forma similar al método de Herrmann, Ed Hofstetter presentó un algoritmo que diseñaba filtros FIR con la mayor cantidad posible de ondulaciones. Este algoritmo se conoce como el algoritmo de Ondulación Máxima. El algoritmo de Ondulación Máxima imponía una condición de error alternante mediante interpolación y luego resolvía un conjunto de ecuaciones que la solución alternante debía satisfacer. [ 1 ] Una limitación notable del algoritmo de Ondulación Máxima era que los bordes de banda no se especificaban como entradas al procedimiento de diseño. En cambio, el conjunto de frecuencias inicial { ω i } y la función deseada D ( ω i ) definían implícitamente la banda de paso y la banda de rechazo. A diferencia de los intentos anteriores de diseñar un filtro óptimo, el algoritmo de Ondulación Máxima utilizaba un método de intercambio que intentaba encontrar el conjunto de frecuencias { ω i } donde el mejor filtro tenía sus ondulaciones. [ 1 ] Por lo tanto, el algoritmo de Ondulación Máxima no era un diseño de filtro óptimo, pero tuvo un impacto bastante significativo en cómo se formularía el algoritmo de Parks-McClellan.

Historia de los parques – McClellan

En agosto de 1970, James McClellan ingresó a la escuela de posgrado de la Universidad Rice con una especialización en modelos matemáticos de diseño de filtros analógicos y se matriculó en un nuevo curso llamado "Filtros Digitales" debido a su interés en el diseño de filtros. [ 1 ] El curso fue impartido conjuntamente por Thomas Parks y Sid Burrus . En ese momento, el DSP era un campo emergente y, como resultado, las clases a menudo incluían artículos de investigación publicados recientemente. El semestre siguiente, la primavera de 1971, Thomas Parks ofreció un curso llamado "Teoría de la Señal", que McClellan también tomó. [ 1 ] Durante las vacaciones de primavera de ese semestre, Parks condujo desde Houston hasta Princeton para asistir a una conferencia, donde escuchó la presentación de Ed Hofstetter sobre un nuevo algoritmo de diseño de filtros FIR (algoritmo de Ondulación Máxima). Llevó el artículo de Hofstetter, Oppenheim y Siegel de regreso a Houston, pensando en la posibilidad de usar la teoría de aproximación de Chebyshev para diseñar filtros FIR. [ 1 ] Escuchó que el método implementado en el algoritmo de Hofstetter era similar al algoritmo de intercambio de Remez y decidió seguir el camino de usar el algoritmo de intercambio de Remez. Los estudiantes del curso de "Teoría de Señales" debían realizar un proyecto y, dado que la aproximación de Chebyshev era un tema principal del curso, la implementación de este nuevo algoritmo se convirtió en el proyecto del curso de James McClellan. Esto finalmente condujo al algoritmo de Parks-McClellan, que involucraba la teoría de la aproximación óptima de Chebyshev y una implementación eficiente. Para el final del semestre de primavera, McClellan y Parks estaban intentando escribir una variación del algoritmo de intercambio de Remez para filtros FIR. Les tomó alrededor de seis semanas desarrollarlo y algunos filtros óptimos se habían diseñado con éxito para finales de mayo.

El algoritmo

El algoritmo de Parks-McClellan se implementa siguiendo los siguientes pasos: [ 1 ]

  1. Inicialización: Elija un conjunto extremo de frecuencias {ω i (0) }.
  2. Aproximación de conjuntos finitos : Calcular la mejor aproximación de Chebyshev.

F(incógnita)≈∑i=0nortedoiTi(incógnita){\displaystyle f(x)\approx \sum _{i=0}^{n}c_{i}T_{i}(x)}, donde c 𝑖 son los coeficientes de Chebyshev en el conjunto extremo actual, que dan un valor δ (m) para el error min-max en el conjunto extremo actual.

  1. Interpolación: Calcule la función de error E(ω) sobre todo el conjunto de frecuencias Ω utilizando (2).
  2. Busque máximos locales de | E (m) (ω) | en el conjunto Ω.
  3. Si max (ω∈Ω) | E (m) (ω) | > δ (m) , entonces actualice el conjunto extremo a { ω i (m+1) } seleccionando nuevas frecuencias donde | E (m) (ω) | tenga sus máximos locales. Asegúrese de que el error alterne en el conjunto ordenado de frecuencias como se describe en (4) y (5). Regrese al paso 2 e itere.
  4. Si max (ω∈Ω) | E (m) (ω) | ≤ δ (m) , entonces el algoritmo está completo. Utilice el conjunto {ω i (0) } y la fórmula de interpolación para calcular una transformada discreta de Fourier inversa y obtener los coeficientes del filtro.

El algoritmo de Parks-McClellan se puede reformular como los siguientes pasos: [ 2 ]

  1. Haz una estimación inicial de las L+2 frecuencias extremas.
  2. Calcula δ usando la ecuación dada.
  3. Utilizando la interpolación de Lagrange, calculamos el conjunto denso de muestras de A(ω) sobre la banda de paso y la banda de rechazo .
  4. Determina los L+2 extremos más grandes nuevos.
  5. Si no se satisface el teorema de alternancia, entonces volvemos a (2) e iteramos hasta que se satisfaga el teorema de alternancia.
  6. Si se cumple el teorema de alternancia, entonces calculamos h(n) y hemos terminado.

Para obtener una comprensión básica del algoritmo de Parks-McClellan mencionado anteriormente, podemos reescribir el algoritmo anterior de una forma más simple como:

  1. Supongamos que las posiciones de los extremos están espaciadas uniformemente en la banda de paso y en la banda de rechazo.
  2. Realizar una interpolación polinómica y reestimar las posiciones de los extremos locales.
  3. Mueva los extremos a nuevas posiciones e itere hasta que los extremos dejen de cambiar.

Explicación

La imagen superior derecha muestra las distintas frecuencias extremas de la gráfica. Estas frecuencias extremas corresponden a los puntos máximo y mínimo en las bandas de rechazo y de paso. La ondulación de la banda de rechazo se encuentra en la parte inferior derecha de la gráfica, mientras que la ondulación de la banda de paso se encuentra en la parte superior izquierda. Las líneas discontinuas que atraviesan la gráfica indican el error máximo (δ). Conociendo las posiciones de las frecuencias extremas, existe una fórmula para el error óptimo (δ). Dado que desconocemos el δ óptimo o las posiciones exactas de los extremos en el primer intento, iteramos. En esencia, asumimos inicialmente las posiciones de los extremos y calculamos δ. Luego, reestimamos y desplazamos los extremos y recalculamos δ, es decir, el error. Repetimos este proceso hasta que δ deja de variar. El algoritmo hará que el error δ converja, generalmente en un plazo de diez a doce iteraciones. [ 3 ]

Notas adicionales

Antes de aplicar la aproximación de Chebyshev, era necesario seguir una serie de pasos:

  1. Defina el conjunto de funciones base para la aproximación, y
  2. Aprovechar el hecho de que las bandas de paso y de rechazo de los filtros de paso de banda siempre estarán separadas por regiones de transición. [ 1 ]

Dado que los filtros FIR se pueden reducir al caso de la suma de cosenos, se puede utilizar el mismo programa principal para implementar todos los filtros FIR de fase lineal posibles. A diferencia del método de máxima ondulación, ahora se pueden especificar los bordes de banda con antelación.

Para lograr una implementación eficiente del diseño óptimo del filtro utilizando el algoritmo de Parks-McClellan, es necesario superar dos dificultades:

  1. Definir una estrategia de intercambio flexible y
  2. Implementación de un método de interpolación robusto. [ 1 ]

En cierto sentido, la programación implicó la implementación y adaptación de un algoritmo conocido para su uso en el diseño de filtros FIR. Se tomaron dos aspectos de la estrategia de intercambio para hacer el programa más eficiente:

  1. Asignar las frecuencias extremas entre las bandas de paso y de rechazo, y
  2. Permitir el movimiento de los extremos entre las bandas a medida que el programa iteraba. [ 1 ]

En la inicialización, el número de extremos en las bandas de paso y de parada se podía asignar utilizando la relación de los tamaños de las bandas. Además, el borde de las bandas de paso y de parada siempre se ubicaría en el conjunto de extremos, y la lógica del programa mantenía esas frecuencias de borde en dicho conjunto. El movimiento entre bandas se controlaba comparando la magnitud de los errores en todas las frecuencias extremas candidatas y tomando la mayor. El segundo elemento del algoritmo era el paso de interpolación necesario para evaluar la función de error . Utilizaron un método llamado interpolación de Lagrange baricéntrica, que resultó ser muy robusto.

Todas las condiciones para el algoritmo de Parks-McClellan se basan en el teorema de alternancia de Chebyshev. El teorema de alternancia establece que el polinomio de grado L que minimiza el error máximo tendrá al menos L+2 extremos. La respuesta de frecuencia óptima apenas alcanzará los límites máximos de rizado. [ 3 ] Los extremos deben ocurrir en los bordes de la banda de paso y de parada y en ω=0 o ω=π o ambos. La derivada de un polinomio de grado L es un polinomio de grado L−1, que puede ser cero como máximo en L−1 lugares. [ 3 ] Por lo tanto, el número máximo de extremos locales es los L−1 extremos locales más los 4 bordes de banda, lo que da un total de L+3 extremos.

Referencias

  1. 1 2 3 4 5 6 7 8 9 10 11 12 13 McClellan , JH; Parks, TW (2005). "Una historia personal del algoritmo de Parks-McClellan". IEEE Signal Processing Magazine . 22 (2): 82– 86. Bibcode : 2005ISPM...22...82M . doi : 10.1109/MSP.2005.1406492 . S2CID 15400093 . 
  2. ↑ Jones, Douglas (2007), Diseño de filtros FIR de Parks–McClellan , consultado el 29 de marzo de 2009.
  3. 1 2 3 Lovell, Brian (2003), Método Parks–McClellan (PDF) , consultado el 30 de marzo de 2009

Referencias adicionales

Los siguientes enlaces adicionales proporcionan información sobre el algoritmo de Parks-McClellan, así como sobre otras investigaciones y artículos escritos por James McClellan y Thomas Parks:

  1. Aproximación de Chebyshev para filtros digitales no recursivos con fase lineal
  2. Breve guía sobre el diseño de filtros paso bajo FIR de Parks-McClellan utilizando MATLAB.
  3. Introducción al DSP Archivado el 23/04/2014 en Wayback Machine
  4. La documentación de MathWorks MATLAB
  5. Apuntes de clase de ELEC4600 ( enlace original , archivado el 15 de abril de 2012)
  6. Implementación en código C (Licencia LGPL) – Por Jake Janovetz
  7. Iowa Hills Software. "Ejemplo de código C" .Archivado el 11 de mayo de 2021 en Wayback Machine.
  8. Algoritmo revisado y ampliado de McClellan, Parks y Rabiner, 1975; código Fortran .