La transformada Z chirp ( CZT ) es una generalización de la transformada discreta de Fourier (DFT). Mientras que las muestras DFT el plano Z en puntos espaciados uniformemente a lo largo del círculo unidad, el chirp Z-transformar las muestras a lo largo de arcos de espiral en el plano Z, que corresponden a líneas rectas en el plano S . [1] [2] El DFT, el DFT real y el DFT con zoom se pueden calcular como casos especiales de CZT.
Específicamente, la transformada chirp Z calcula la transformada Z en un número finito de puntos z k a lo largo de un contorno de espiral logarítmico , definido como: [1] [3]
donde A es el punto de partida complejo, W es la relación compleja entre puntos y M es el número de puntos a calcular.
Al igual que la DFT, la transformación Z de chirp se puede calcular en operaciones O ( n log n ) donde. Un algoritmo O ( N log N ) para la transformada Z de chirp inverso (ICZT) se describió en 2003, [4] [5] y en 2019. [6]
Algoritmo de Bluestein
El algoritmo de Bluestein [7] [8] expresa el CZT como una convolución y lo implementa de manera eficiente usando FFT / IFFT.
Como la DFT es un caso especial de la CZT, esto permite el cálculo eficiente de la transformada discreta de Fourier (DFT) de tamaños arbitrarios, incluidos los tamaños primos . (El otro algoritmo para FFT de tamaños primos, el algoritmo de Rader , también funciona reescribiendo el DFT como una convolución). Fue concebido en 1968 por Leo Bluestein . [9] El algoritmo de Bluestein se puede utilizar para calcular transformaciones más generales que la DFT, basándose en la transformada z (unilateral) (Rabiner et al. , 1969).
Recuerde que la DFT está definida por la fórmula
Si reemplazamos el producto nk en el exponente por la identidad
obtenemos así:
Esta suma es precisamente una convolución de las dos secuencias a n y b n definidas por:
con la salida de la convolución multiplicada por N factores de fase b k * . Es decir:
Esta convolución, a su vez, se puede realizar con un par de FFT (más la FFT precalculada de chirp b n complejo ) mediante el teorema de convolución . El punto clave es que estas FFT no tienen la misma longitud N : tal convolución se puede calcular exactamente a partir de las FFT sólo rellenándola con ceros a una longitud mayor o igual a 2 N –1. En particular, se puede rellenar a una potencia de dos o algún otro tamaño altamente compuesto , para lo cual la FFT se puede realizar de manera eficiente, por ejemplo, mediante el algoritmo de Cooley-Tukey en tiempo O ( N log N ). Por lo tanto, el algoritmo de Bluestein proporciona una forma O ( N log N ) de calcular las DFT de tamaño principal, aunque varias veces más lento que el algoritmo de Cooley-Tukey para tamaños compuestos.
El uso de relleno de ceros para la convolución en el algoritmo de Bluestein merece un comentario adicional. Suponga que ponemos cero a una longitud M ≥ 2 N –1. Esto significa que a n se extiende a una matriz A n de longitud M , donde A n = a n para 0 ≤ n < N y A n = 0 en caso contrario, el significado habitual de "relleno de ceros". Sin embargo, debido al término b k - n en la convolución, se requieren valores positivos y negativos de n para b n (teniendo en cuenta que b - n = b n ). Los límites periódicos implícitos en la DFT de la matriz con relleno de ceros significan que - n es equivalente a M - n . Por lo tanto, b n se extiende a una matriz B n de longitud M , donde B 0 = b 0 , B n = B M - n = b n para 0 < n < N , y B n = 0 en caso contrario. A y B son entonces FFTed, puntual multiplicado, y inversa FFTed para obtener la convolución de una y b , de acuerdo con el teorema de convolución usual.
También seamos más precisos sobre qué tipo de convolución se requiere en el algoritmo de Bluestein para la DFT. Si la secuencia b n fuera periódica en n con período N , entonces sería una convolución cíclica de longitud N , y el relleno de ceros sería solo por conveniencia computacional. Sin embargo, este no suele ser el caso:
Por lo tanto, para N incluso la convolución es cíclica, pero en este caso N es compuesto y normalmente se usaría un algoritmo FFT más eficiente como Cooley-Tukey. Para N impar, sin embargo, a continuación, b n es antiperiodic y técnicamente tener una convolución negacyclic de longitud N . Sin embargo, tales distinciones desaparecen cuando un cero rellena un n hasta una longitud de al menos 2 N −1 como se describió anteriormente. Por lo tanto, quizás sea más fácil pensar en él como un subconjunto de las salidas de una convolución lineal simple (es decir, sin "extensiones" conceptuales de los datos, periódicos o de otro tipo).
transformaciones z
El algoritmo de Bluestein también se puede utilizar para calcular una transformada más general basada en la transformada z (unilateral) (Rabiner et al. , 1969). En particular, puede calcular cualquier transformación de la forma:
para un número complejo arbitrario z y para diferentes números N y M de entradas y salidas. Dado el algoritmo de Bluestein, dicha transformación se puede utilizar, por ejemplo, para obtener una interpolación más finamente espaciada de alguna porción del espectro (aunque la resolución de frecuencia todavía está limitada por el tiempo de muestreo total, similar a un Zoom FFT), mejorar arbitrariamente polos en análisis de función de transferencia, etc.
El algoritmo se denominó algoritmo de transformada z chirp porque, para el caso de la transformada de Fourier (| z | = 1), la secuencia b n de arriba es una sinusoide compleja de frecuencia linealmente creciente, que se denomina chirp (lineal) en sistemas de radar .
Ver también
Referencias
- ^ a b Un estudio de la transformada Z de Chirp y sus aplicaciones - Shilling, Steve Alan
- ^ "Transformada Z de Chirp - MATLAB czt" . www.mathworks.com . Consultado el 22 de septiembre de 2016 .
- ^ Martin, Grant D. (noviembre de 2005). "Optimización del zoom espectral de transformación Z de Chirp con MATLAB®" (PDF) .
- ^ Bostan, Alin (2003). Algorithmique eficace pour des operations de base en Calcul formel (PDF) (PhD). Ecole polytechnique.
- ^ Bostan, Alin; Schost, Éric (2005). "Evaluación e interpolación de polinomios en conjuntos especiales de puntos". Revista de complejidad . 21 (4): 420–446. doi : 10.1016 / j.jco.2004.09.009 .
- ^ Los ingenieros resuelven un rompecabezas de 50 años en el procesamiento de señales: transformación Z de chirp inverso , por IOWA STATE UNIVERSITY, 10 de octubre de 2019
- ^ Bluestein, L. (1 de diciembre de 1970). "Un enfoque de filtrado lineal para el cálculo de la transformada de Fourier discreta". Transacciones IEEE sobre audio y electroacústica . 18 (4): 451–455. doi : 10.1109 / TAU.1970.1162132 . ISSN 0018-9278 .
- ^ "Algoritmo FFT de Bluestein" . DSPRelated.com.
- ^ Bluestein, L. (1970). "Un enfoque de filtrado lineal para el cálculo de la transformada de Fourier discreta". Transacciones IEEE sobre audio y electroacústica . 18 (4): 451–455. doi : 10.1109 / TAU.1970.1162132 .
General
- Leo I. Bluestein, "Un enfoque de filtrado lineal para el cálculo de la transformada discreta de Fourier", Northeast Electronics Research and Engineering Meeting Record 10 , 218-219 (1968).
- Lawrence R. Rabiner, Ronald W. Schafer y Charles M. Rader, " El algoritmo de transformación z de chirp y su aplicación ", Bell Syst. Tech. J. 48 , 1249 - 1292 (1969). También publicado en: Rabiner, Shafer y Rader, " El algoritmo chirp z-transform ", IEEE Trans. Audio Electroacústica 17 (2), 86–92 (1969).
- DH Bailey y PN Swarztrauber, "La transformada fraccional de Fourier y sus aplicaciones", SIAM Review 33 , 389-404 (1991). (Tenga en cuenta que esta terminología para la transformada z no es estándar: una transformada fraccional de Fourier se refiere convencionalmente a una transformada continua completamente diferente).
- Lawrence Rabiner, "El algoritmo de transformación z de chirp: una lección de serendipia", IEEE Signal Processing Magazine 21 , 118-119 (marzo de 2004). (Comentario histórico.)
- Vladimir Sukhoy y Alexander Stoytchev: "Generalización de la FFT inversa fuera del círculo unitario" , (octubre de 2019). # Acceso abierto.
- Vladimir Sukhoy y Alexander Stoytchev: "Análisis de error numérico del algoritmo ICZT para contornos de chirp en el círculo unitario" , Sci Rep 10, 4852 (2020).
enlaces externos
- Un algoritmo DSP para análisis de frecuencia : la Transformada Chirp-Z (CZT)
- Resolviendo un rompecabezas de 50 años en el procesamiento de señales, segunda parte