El algoritmo de Goertzel es una técnica en el procesamiento de señales digitales (DSP) para la evaluación eficiente de los términos individuales de la transformada discreta de Fourier (DFT). Es útil en ciertas aplicaciones prácticas, como el reconocimiento de tonos de señalización multifrecuencia de tono dual (DTMF) producidos por los botones del teclado de un teléfono analógico tradicional . El algoritmo fue descrito por primera vez por Gerald Goertzel en 1958. [1]
Al igual que el DFT, el algoritmo de Goertzel analiza un componente de frecuencia seleccionable de una señal discreta . [2] [3] [4] A diferencia de los cálculos directos de DFT, el algoritmo de Goertzel aplica un único coeficiente de valor real en cada iteración, utilizando aritmética de valor real para secuencias de entrada de valor real. Para cubrir un espectro completo, el algoritmo de Goertzel tiene un orden de complejidad más alto que los algoritmos de transformada rápida de Fourier (FFT), pero para calcular una pequeña cantidad de componentes de frecuencia seleccionados, es numéricamente más eficiente. La estructura simple del algoritmo de Goertzel lo hace muy adecuado para procesadores pequeños y aplicaciones integradas.
El algoritmo de Goertzel también se puede utilizar "a la inversa" como una función de síntesis sinusoide, que requiere solo 1 multiplicación y 1 resta por muestra generada. [5]
El algoritmo
El cálculo principal en el algoritmo de Goertzel tiene la forma de un filtro digital y, por esta razón, el algoritmo a menudo se denomina filtro de Goertzel . El filtro opera en una secuencia de entrada en cascada de dos etapas con un parámetro , dando la frecuencia a analizar, normalizada en radianes por muestra.
La primera etapa calcula una secuencia intermedia, :
(1)
La segunda etapa aplica el siguiente filtro a , produciendo secuencia de salida :
(2)
Se puede observar que la primera etapa de filtrado es un filtro IIR de segundo orden con una estructura de forma directa . Esta estructura en particular tiene la propiedad de que sus variables de estado internas son iguales a los valores de salida pasados de esa etapa. Valores de entrada por se presume que todos son iguales a 0. Para establecer el estado del filtro inicial para que la evaluación pueda comenzar en la muestra , a los estados de filtro se les asignan valores iniciales . Para evitar peligros de aliasing , la frecuenciaa menudo se restringe al rango de 0 a π (consulte el teorema de muestreo de Nyquist-Shannon ); usar un valor fuera de este rango no tiene sentido, pero es equivalente a usar una frecuencia con alias dentro de este rango, ya que la función exponencial es periódica con un período de 2π en.
Se puede observar que el filtro de la segunda etapa es un filtro FIR , ya que sus cálculos no utilizan ninguna de sus salidas pasadas.
Se pueden aplicar métodos de transformación Z para estudiar las propiedades de la cascada de filtros. La transformada Z de la primera etapa de filtrado dada en la ecuación (1) es
(3)
La transformada Z de la segunda etapa de filtrado dada en la ecuación (2) es
(4)
La función de transferencia combinada de la cascada de las dos etapas de filtrado es entonces
(5)
Esto se puede transformar de nuevo a una secuencia equivalente en el dominio del tiempo, y los términos se pueden desenrollar de nuevo al primer término de entrada en el índice. : [ cita requerida ]
(6)
Estabilidad numérica
Se puede observar que los polos de la transformada Z del filtro se ubican en y , en un círculo de radio unitario centrado en el origen del plano de la transformada Z compleja. Esta propiedad indica que el proceso de filtrado es marginalmente estable y vulnerable a la acumulación de errores numéricos cuando se calcula utilizando aritmética de baja precisión y secuencias de entrada largas. [6] Christian Reinsch propuso una versión numéricamente estable. [7]
Cálculos DFT
Para el caso importante de calcular un término DFT, se aplican las siguientes restricciones especiales.
- El filtrado termina en el índice , dónde es el número de términos en la secuencia de entrada de la DFT.
- Las frecuencias elegidas para el análisis de Goertzel están restringidas a la forma especial
(7)
- El número de índice que indica que el "intervalo de frecuencia" de la DFT se selecciona del conjunto de números de índice
(8)
Haciendo estas sustituciones en la ecuación (6) y observando que el término , la ecuación (6) toma la siguiente forma:
(9)
Podemos observar que el lado derecho de la ecuación (9) es extremadamente similar a la fórmula que define para el término DFT , el término DFT para el número de índice , pero no exactamente lo mismo. La suma que se muestra en la ecuación (9) requiere términos de entrada, pero solo Los términos de entrada están disponibles al evaluar una DFT. Un recurso simple pero poco elegante es extender la secuencia de entrada con un valor artificial más . [8] Podemos ver en la ecuación (9) que el efecto matemático en el resultado final es el mismo que eliminar el término de la suma, entregando así el valor DFT previsto.
Sin embargo, existe un enfoque más elegante que evita el paso de filtro adicional. De la ecuación (1), podemos observar que cuando el término de entrada extendido se utiliza en el paso final,
(10)
Por lo tanto, el algoritmo se puede completar de la siguiente manera:
- terminar el filtro IIR después de procesar el término de entrada ,
- aplicar la ecuación (10) para construir de las salidas anteriores y ,
- aplicar la ecuación (2) con el calculado valor y con producido por el cálculo directo final del filtro.
Las dos últimas operaciones matemáticas se simplifican combinándolas algebraicamente:
(11)
Tenga en cuenta que detener las actualizaciones del filtro a término y la aplicación inmediata de la ecuación (2) en lugar de la ecuación (11) pierde las actualizaciones del estado del filtro final, lo que produce un resultado con fase incorrecta. [9]
La estructura de filtrado particular elegida para el algoritmo de Goertzel es la clave para sus cálculos eficaces de DFT. Podemos observar que solo un valor de salidase utiliza para calcular la DFT, por lo que se omiten los cálculos para todos los demás términos de salida. Dado que el filtro FIR no se calcula, los cálculos de la etapa IIR, etc. se pueden descartar inmediatamente después de actualizar el estado interno de la primera etapa.
Esto parece dejar una paradoja: para completar el algoritmo, la etapa del filtro FIR debe evaluarse una vez usando las dos salidas finales de la etapa del filtro IIR, mientras que para la eficiencia computacional, la iteración del filtro IIR descarta sus valores de salida. Aquí es donde se aplican las propiedades de la estructura del filtro de forma directa. Las dos variables de estado internas del filtro IIR proporcionan los dos últimos valores de la salida del filtro IIR, que son los términos necesarios para evaluar la etapa del filtro FIR.
Aplicaciones
Términos del espectro de potencia
Examinando la ecuación (6), una pasada de filtro IIR final para calcular el término usando un valor de entrada suplementario aplica un multiplicador complejo de magnitud 1 al término anterior . Como consecuencia, y representan potencia de señal equivalente. Es igualmente válido aplicar la ecuación (11) y calcular la potencia de la señal a partir del término o aplicar la ecuación (2) y calcular la potencia de la señal a partir del término . Ambos casos conducen a la siguiente expresión para la potencia de la señal representada por el término DFT:
(12)
En el pseudocódigo a continuación, las variables sprev
y sprev2
temporalmente historia de salida tienda desde el filtro IIR, mientras que x[n]
es un elemento indexado de la matriz x
, que almacena la entrada.
Ntérminos definidos aquíKterm seleccionado aquíω = 2 × π × Kterm / Nterms;cr: = cos (ω)ci: = pecado (ω)coef: = 2 × crsprev: = 0sprev2: = 0para cada índice n en el rango 0 a Nterms-1 hacer s: = x [n] + coeff × sprev - sprev2 sprev2: = sprev sprev: = sfinalpotencia: = sprev2 × sprev2 + sprev × sprev - coeff × sprev × sprev2
Es posible [10] organizar los cálculos de modo que las muestras entrantes se envíen individualmente a un objeto de software que mantenga el estado del filtro entre actualizaciones, y se acceda al resultado final de energía después de que se haya realizado el otro procesamiento.
Término DFT único con aritmética de valor real
El caso de los datos de entrada de valor real surge con frecuencia, especialmente en sistemas integrados donde los flujos de entrada son el resultado de mediciones directas de procesos físicos. En comparación con la ilustración de la sección anterior, cuando los datos de entrada son valores reales, las variables de estado internas del filtro sprev
y sprev2
pueden observarse también como valores reales, en consecuencia, no se requiere aritmética compleja en la primera etapa IIR. La optimización para la aritmética con valores reales suele ser tan simple como aplicar los tipos de datos con valores reales adecuados para las variables.
Después de los cálculos usando el término de entrada , y se terminan las iteraciones del filtro, se debe aplicar la ecuación (11) para evaluar el término DFT. El cálculo final utiliza aritmética de valor complejo, pero esto se puede convertir en aritmética de valor real separando términos reales e imaginarios:
(13)
En comparación con la aplicación del espectro de potencia, la única diferencia es el cálculo utilizado para finalizar:
(Los mismos cálculos de filtro IIR que en la implementación de potencia de señal)XKreal = sprev * cr - sprev2;XKimag = sprev * ci;
Detección de fase
Esta aplicación requiere la misma evaluación del término DFT , como se discutió en la sección anterior, usando un flujo de entrada de valor real o de valor complejo. Entonces la fase de la señal se puede evaluar como
(14)
tomar las precauciones adecuadas para singularidades, cuadrantes, etc. al calcular la función de tangente inversa.
Señales complejas en aritmética real
Dado que las señales complejas se descomponen linealmente en partes reales e imaginarias, el algoritmo de Goertzel se puede calcular en aritmética real por separado sobre la secuencia de partes reales, dando como resultado , y sobre la secuencia de partes imaginarias, produciendo . Después de eso, los dos resultados parciales de valor complejo se pueden recombinar:
(15)
Complejidad computacional
- Según la teoría de la complejidad computacional , calcular un conjunto de Términos de DFT usando aplicaciones del algoritmo de Goertzel en un conjunto de datos con valores con un "costo por operación" de tiene complejidad .
- Para calcular una sola bandeja DFT para una secuencia de entrada compleja de longitud , el algoritmo de Goertzel requiere multiplicaciones y sumas / restas dentro del ciclo, así como 4 multiplicaciones y 4 sumas / restas finales, para un total de multiplicaciones y sumas / restas. Esto se repite para cada uno de los frecuencias.
- Por el contrario, el uso de una FFT en un conjunto de datos con los valores tiene complejidad .
- Esto es más difícil de aplicar directamente porque depende del algoritmo FFT utilizado, pero un ejemplo típico es un FFT radix-2, que requiere multiplicaciones y adiciones / restas por contenedor DFT , para cada uno de los contenedores.
En las expresiones de orden de complejidad, cuando el número de términos calculados es más pequeña que , la ventaja del algoritmo de Goertzel es clara. Pero debido a que el código FFT es comparativamente complejo, el factor "costo por unidad de trabajo" es a menudo más grande para una FFT, y la ventaja práctica favorece al algoritmo de Goertzel incluso para varias veces más grande que .
Como regla general para determinar si una FFT de radix-2 o un algoritmo de Goertzel es más eficiente, ajuste el número de términos en los datos establecidos hacia arriba a la potencia exacta más cercana de 2, llamando a esto , y es probable que el algoritmo de Goertzel sea más rápido si
Las implementaciones de FFT y las plataformas de procesamiento tienen un impacto significativo en el rendimiento relativo. Algunas implementaciones de FFT [11] realizan cálculos internos de números complejos para generar coeficientes sobre la marcha, lo que aumenta significativamente su "costo K por unidad de trabajo". Los algoritmos FFT y DFT pueden usar tablas de valores de coeficientes precalculados para una mejor eficiencia numérica, pero esto requiere más accesos a valores de coeficientes almacenados en memoria externa, lo que puede conducir a una mayor contención de caché que contrarresta algunas de las ventajas numéricas.
Ambos algoritmos obtienen aproximadamente un factor de eficiencia 2 cuando se utilizan datos de entrada de valor real en lugar de valores complejos. Sin embargo, estas ganancias son naturales para el algoritmo de Goertzel, pero no se lograrán para la FFT sin usar ciertas variantes del algoritmo [ ¿cuál? ] especializado en la transformación de datos de valor real .
Ver también
Referencias
- ^ Goertzel, G. (enero de 1958), "Un algoritmo para la evaluación de series trigonométricas finitas", American Mathematical Monthly , 65 (1): 34-35, doi : 10.2307 / 2310304 , JSTOR 2310304
- ^ Mock, P. (21 de marzo de 1985), "Agregar generación y decodificación DTMF a diseños DSP-μP" (PDF) , EDN , ISSN 0012-7515; también se encuentra en Aplicaciones DSP con la familia TMS320, vol. 1, Texas Instruments, 1989.
- ^ Chen, Chiouguey J. (junio de 1996), algoritmo de Goertzel modificado en la detección de DTMF mediante el DSP TMS320C80 (PDF) , Informe de aplicación, Texas Instruments, SPRA066
- ^ Schmer, Gunter (mayo de 2000), Generación y detección de tonos DTMF: una implementación utilizando el TMS320C54x (PDF) , Informe de aplicación, Texas Instruments, SPRA096a
- ^ Cheng, Eric; Hudak, Paul (enero de 2009), Procesamiento de audio y síntesis de sonido en Haskell (PDF) , archivado desde el original (PDF) el 28 de marzo de 2017
- ^ Gentleman, WM (1 de febrero de 1969). "Un análisis de error del método de Goertzel (Watt) para calcular los coeficientes de Fourier" . The Computer Journal . 12 (2): 160-164. doi : 10.1093 / comjnl / 12.2.160 .
- ^ Stoer, J .; Bulirsch, R. (2002), Introducción al análisis numérico , Springer, ISBN 9780387954523
- ^ "Algoritmo de Goertzel" . Cnx.org. 2006-09-12 . Consultado el 3 de febrero de 2014 .
- ^ "Tiempos de ingeniería electrónica | Conectando la comunidad electrónica global" . EE Times . Consultado el 3 de febrero de 2014 .
- ^ Elmenreich, Wilfried (25 de agosto de 2011). "Detectar una frecuencia de forma eficiente mediante un filtro Goertzel" . Consultado el 16 de septiembre de 2014 .
- ^ Prensa; Flannery; Teukolsky; Vetterling (2007), "Capítulo 12", Recetas numéricas, El arte de la informática científica , Cambridge University Press
Otras lecturas
- Proakis, JG; Manolakis, DG (1996), Procesamiento de señales digitales: principios, algoritmos y aplicaciones , Upper Saddle River, Nueva Jersey: Prentice Hall, págs. 480–481, Bibcode : 1996dspp.book ..... P
enlaces externos
- Algoritmo de Goertzel en la Wayback Machine (archivado el 28 de junio de 2018)
- Un algoritmo DSP para análisis de frecuencia
- El algoritmo de Goertzel de Kevin Banks