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 . El algoritmo Parks-McClellan se utiliza para diseñar e implementar filtros FIR eficientes y óptimos. Utiliza un método indirecto para encontrar los coeficientes de filtro óptimos.
El objetivo del algoritmo es minimizar el error en las bandas de paso y parada utilizando la aproximación de Chebyshev. El algoritmo Parks-McClellan es una variación del algoritmo de intercambio de Remez , con el cambio 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 del diseño óptimo de filtros FIR
En la década de 1960, los investigadores del campo del diseño de filtros analógicos utilizaban la aproximación de Chebyshev para el diseño de filtros. Durante este tiempo, era bien sabido que los mejores filtros contienen una característica de equiripulación en su magnitud de respuesta de frecuencia y el filtro elíptico (o filtro 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 transformada bilineal para producir filtros elípticos digitales de respuesta de impulso infinito (IIR). También reconocieron el potencial de diseñar 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 ondulaciones equitativas y que el número de ondulaciones podría contarse utilizando la aproximación de Chebyshev. En el período comprendido entre 1962 y 1971 se realizaron varios intentos para producir un programa de diseño para el filtro FIR de Chebyshev óptimo. [1] A pesar de los numerosos intentos, la mayoría no tuvo éxito, generalmente debido a problemas en la implementación algorítmica o la formulación de problemas. Otto Herrmann, por ejemplo, propuso un método para diseñar filtros de ondulación equitativa con bordes de banda restringidos. [1] Este método obtuvo una respuesta de frecuencia de ondulación equitativa con el número máximo de ondulaciones resolviendo un conjunto de ecuaciones no lineales. Otro método introducido en ese momento implementó una aproximación óptima de Chebyshev, pero el algoritmo se limitó al diseño de filtros de orden relativamente bajo. [1]
Similar al método de Herrmann, Ed Hofstetter presentó un algoritmo que diseñó filtros FIR con tantas ondas como fuera posible. Esto se conoce como el algoritmo Maximal Ripple. El algoritmo Maximal Ripple impuso una condición de error alterno mediante interpolación y luego resolvió un conjunto de ecuaciones que la solución alterna tenía que satisfacer. [1] Una limitación notable del algoritmo Maximal Ripple fue que los bordes de la banda no se especificaron como entradas para el procedimiento de diseño. Más bien, el conjunto de frecuencias inicial { ω i } y la función deseada D ( ω i ) definieron implícitamente la banda de paso y parada. A diferencia de los intentos anteriores de diseñar un filtro óptimo, el algoritmo Maximal Ripple utilizó 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 Maximal Ripple no fue un diseño de filtro óptimo, pero tuvo un impacto significativo en cómo se formularía el algoritmo de Parks-McClellan.
Historia
En agosto de 1970, James McClellan ingresó a la escuela de posgrado en la Universidad de Rice con una concentración en modelos matemáticos de diseño de filtros analógicos y se inscribió 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, DSP era un campo emergente y, como resultado, las conferencias 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 del semestre, Parks condujo desde Houston a 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 Maximal Ripple). Trajo 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 "Teoría de la señal" debían realizar un proyecto y, dado que la aproximación de Chebyshev era un tema importante en el 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 involucró la teoría de la aproximación óptima de Chebyshev y una implementación eficiente. Al final del semestre de primavera, McClellan y Parks intentaban escribir una variación del algoritmo de intercambio de Remez para filtros FIR. El desarrollo tardó unas seis semanas y, a finales de mayo, se habían diseñado con éxito algunos filtros óptimos.
James McClellan y Thomas Parks
James McClellan nació el 5 de octubre de 1947 en Guam . Recibió su Licenciatura en Ciencias en Ingeniería Eléctrica (1969) de la Universidad Estatal de Louisiana . [2] Después de recibir sus títulos de Maestría en Ciencias (1972) y Doctorado (1973) de la Universidad de Rice , el Dr. McClellan trabajó en el Laboratorio Lincoln del MIT de 1973 a 1975. [2] Se convirtió en profesor en Ingeniería Eléctrica y Computación del MIT Departamento de Ciencias en 1975. [2] Después de trabajar en la universidad durante siete años, el Dr. McClellan se incorporó a Schlumberger en 1982, donde trabajó durante cinco años. [2] Desde 1987, el Dr. McClellan ha sido profesor de ingeniería eléctrica en el Instituto de Tecnología de Georgia . [2] El Dr. McClellan ha recibido numerosos premios por su trabajo en el procesamiento de señales digitales y su aplicación al procesamiento de matrices de sensores: Premio IEEE Signal Processing Technical Achievement Award (1987), IEEE Signal Processing Society Award (1996) e IEEE Jack S. Kilby Medalla de procesamiento de señales (2004). [1] Además de los premios que ha recibido, el Dr. McClellan ha publicado una serie de obras importantes de literatura: Ejercicios basados en computadora para el procesamiento de señales usando MATLAB 5 (1994), DSP First (1997), Signal Processing First (2003) ) y Teoría de números en DSP (1979). [1]
Thomas Parks nació el 16 de marzo de 1939 en Buffalo, Nueva York. Recibió su licenciatura (1961), maestría en ciencias (1964) y doctorado (1967) en ingeniería eléctrica de la Universidad de Cornell . [3] Después de graduarse con su doctorado, el Dr. Parks se unió a la facultad de Rice University. Fue miembro de la facultad de 1967 a 1986, cuando se unió a la facultad de la Universidad de Cornell. [3] El Dr. Parks ha recibido múltiples premios basados en su investigación centrada en el procesamiento de señales digitales con su aplicación a la teoría de señales , sistemas multivelocidad, interpolación y diseño de filtros: Premio al Logro Técnico de la Sociedad IEEE ASSP (1981), Sociedad IEEE ASSP Award (1988), Rice University President's Award (1999), IEEE Third Millennium Medal (2000) y IEEE Jack S. Kilby Signal Processing Medal (2004). [1] Además de los premios que ha recibido, el Dr. Parks ha publicado numerosas contribuciones al campo de la ingeniería eléctrica: DFT / FFT Convolution Algorithms (1985), Digital Filter Design (1987), A Digital Signal Processing Laboratory Using the TMS 32010 (1988), A Digital Signal Processing Laboratory Using the TMS 320C25 (1990), Ejercicios basados en computadora para el procesamiento de señales (1994) y Ejercicios basados en computadora para el procesamiento de señales usando MATLAB 5 (1994). [1]
El algoritmo
El algoritmo Parks-McClellan se implementa siguiendo los siguientes pasos: [1]
- Inicialización: elija un conjunto de frecuencias extremas {ω i (0) }.
- Aproximación de conjunto finito: Calcule la mejor aproximación de Chebyshev en el conjunto extremo actual, dando un valor δ (m) para el error mínimo-máximo en el conjunto extremo actual.
- Interpolación: Calcule la función de error E (ω) sobre el conjunto completo de frecuencias Ω usando (2).
- Busque los máximos locales de | E (m) (ω) | en el conjunto Ω.
- Si max (ωεΩ) | E (m) (ω) | > δ (m) , luego actualice el conjunto extremo a { ω i (m + 1) } seleccionando nuevas frecuencias donde | E (m) (ω) | tiene sus máximos locales. Asegúrese de que el error se alterne en el conjunto ordenado de frecuencias como se describe en (4) y (5). Regrese al paso 2 y repita.
- 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 de Fourier discreta inversa para obtener los coeficientes de filtro.
El algoritmo Parks-McClellan puede reformularse como los siguientes pasos: [4]
- Haga una suposición inicial de las frecuencias extremas L + 2.
- Calcule δ usando la ecuación dada.
- Usando la interpolación de Lagrange, calculamos el conjunto denso de muestras de A (ω) sobre la banda de paso y la banda de supresión.
- Determine los nuevos extremos más grandes de L + 2.
- Si no se satisface el teorema de la alternancia, volvemos a (2) e iteramos hasta que se satisfaga el teorema de la alternancia.
- Si se satisface el teorema de la alternancia, calculamos h (n) y terminamos.
Para obtener una comprensión básica del algoritmo de Parks-McClellan mencionado anteriormente, podemos reescribir el algoritmo anterior en una forma más simple como:
- Supongo que las posiciones de los extremos están espaciadas uniformemente en la banda de paso y parada.
- Realice una interpolación polinómica y vuelva a estimar las posiciones de los extremos locales.
- Mueva los extremos a nuevas posiciones e itere hasta que los extremos dejen de moverse.
Explicación
La imagen de arriba a la derecha muestra las diversas frecuencias extremas para el gráfico mostrado. Las frecuencias extremas son los puntos máximo y mínimo en las bandas de paso y parada. La ondulación de la banda de parada es la parte inferior de las ondulaciones en la parte inferior derecha del gráfico y la ondulación de la banda de paso es la parte superior de las ondulaciones en la parte superior izquierda del gráfico. Las líneas punteadas que atraviesan el gráfico indican el δ o error máximo. Dadas las posiciones de las frecuencias extremas, existe una fórmula para el δ óptimo o el error óptimo. Dado que no conocemos el δ óptimo o las posiciones exactas de los extremos en el primer intento, iteramos. Efectivamente, asumimos inicialmente las posiciones de los extremos y calculamos δ. Luego re-estimamos y movemos los extremos y recalculamos δ, o el error. Repetimos este proceso hasta que δ deje de cambiar. El algoritmo hará que el error δ converja, generalmente dentro de diez a doce iteraciones. [5]
Notas adicionales
Antes de aplicar la aproximación de Chebyshev, era necesario un conjunto de pasos:
- Defina el conjunto de función base para la aproximación, y
- Aproveche el hecho de que las bandas de paso y parada de los filtros de paso de banda siempre estarán separadas por regiones de transición. [1]
Dado que los filtros FIR podrían reducirse al caso de la suma de cosenos, el mismo programa central podría usarse para realizar todos los filtros FIR de fase lineal posibles. En contraste con el enfoque de Rizado máximo, los bordes de la banda ahora podrían especificarse con anticipación.
Para lograr una implementación eficiente del diseño de filtro óptimo utilizando el algoritmo de Parks-McClellan, se deben superar dos dificultades:
- Definir una estrategia de intercambio flexible y
- 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 caras de la estrategia de intercambio para hacer más eficiente el programa:
- Asignar las frecuencias extremas entre las bandas de paso y parada, y
- Habilitando 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 la banda de paso y parada podría asignarse utilizando la relación de los tamaños de las bandas. Además, el borde de la banda de paso y parada siempre se colocaría en el conjunto extremo, y la lógica del programa mantuvo esas frecuencias de borde en el conjunto extremo. El movimiento entre bandas se controló comparando el tamaño de los errores en todas las frecuencias extremas candidatas y tomando la mayor. El segundo elemento del algoritmo fue el paso de interpolación necesario para evaluar la función de error. Utilizaron un método llamado forma baricéntrica de interpolación de Lagrange, que era muy robusto.
Todas las condiciones del algoritmo de Parks-McClellan se basan en el teorema de alternancia de Chebyshev. El teorema de la 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 ondulación. [5] Los extremos deben ocurrir en los bordes de la banda de paso y parada y en ω = 0 o ω = π o en ambos. La derivada de un polinomio de grado L es un polinomio de grado L-1, que puede ser cero como máximo en los lugares L-1. [5] Entonces, el número máximo de extremos locales es el extremo local L-1 más los 4 bordes de la banda, lo que da un total de L + 3 extremos.
Referencias
- ^ a b c d e f g h i j k l m n o p q McClellan, JH; Parques, TW (2005). "Una historia personal del algoritmo de Parks-Mc Clellan ". Revista de procesamiento de señales IEEE . 22 (2): 82–86. Código Bibliográfico : 2005ISPM ... 22 ... 82M . doi : 10.1109 / MSP.2005.1406492 .
- ^ a b c d e McClellan, James (1997), James McClellan Profile , consultado el 28 de marzo de 2009
- ^ a b Parks, Thomas (2006), Escuela de Ingeniería Eléctrica e Informática, Universidad de Cornell , consultado el 28 de marzo de 2009
- ^ Jones, Douglas (2007), Parks – McClellan FIR Filter Design , consultado el 29 de marzo de 2009
- ^ a b c Lovell, Brian (2003), Parks-McClellan Method (PDF) , consultado el 30 de marzo de 2009
Referencias adicionales
Los siguientes enlaces adicionales proporcionan información sobre el algoritmo Parks-McClellan, así como sobre otras investigaciones y artículos escritos por James McClellan y Thomas Parks:
- Aproximación de Chebyshev para filtros digitales no recursivos con fase lineal
- Breve ayuda sobre el diseño de Parks-McClellan de filtros de paso bajo FIR con MATLAB
- Introducción a DSP
- La documentación de MathWorks MATLAB
- Notas de la conferencia ELEC4600
- Implementación del código C (licencia LGPL) - Por Jake Janovetz
- Software de Iowa Hills. "Ejemplo de código C" . Consultado el 3 de mayo de 2014 .
- Algoritmo revisado y ampliado McClellan, Parks y Rabiner, 1975; Código de Fortran.