Transformada Z de Chirp

La transformada Z de chirp ( CZT ) es una generalización de la transformada de Fourier discreta (DFT). Mientras que la DFT muestrea el plano Z en puntos espaciados uniformemente a lo largo del círculo unitario, la transformada Z de chirp muestrea a lo largo de arcos espirales en el plano Z, correspondientes a líneas rectas en el plano S. [ ^{1] [2]} La DFT, la DFT real y la DFT de zoom se pueden calcular como casos especiales de la CZT.

Específicamente, la transformada Z de chirp calcula la transformada Z en un número finito de puntos z _k a lo largo de un contorno espiral logarítmico , definido como: ^{[1] [3]}

${\displaystyle X_{k}=\sum _{n=0}^{N-1}x(n)z_{k}^{-n}}$

${\displaystyle z_{k}=A\cdot W^{-k},k=0,1,\dots ,M-1}$

donde A es el punto de inicio 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 transformada 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 inversa (ICZT) se describió en 2003, ^{[4] [5]} y en 2019. ^[6] $n=\max(M,N)$

Algoritmo de Bluestein

El algoritmo de Bluestein ^{[7] [8]} expresa la CZT como una convolución y la implementa eficientemente usando FFT /IFFT.

Como la DFT es un caso especial de la CZT, esto permite el cálculo eficiente de la transformada de Fourier discreta (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 la DFT como una convolución). Fue concebido en 1968 por Leo Bluestein. ^[7] El algoritmo de Bluestein se puede utilizar para calcular transformadas más generales que la DFT, basadas en la transformada z (unilateral) (Rabiner et al. , 1969).

Recordemos que la DFT se define mediante la fórmula

${\displaystyle X_{k}=\sum _{n=0}^{N-1}x_{n}e^{-{\frac {2\pi i}{N}}nk}\qquad k=0,\dots ,N-1.}$

Si reemplazamos el producto nk en el exponente por la identidad

${\displaystyle nk={\frac {-(k-n)^{2}}{2}}+{\frac {n^{2}}{2}}+{\frac {k^{2}}{2}}}$

Así obtenemos:

${\displaystyle X_{k}=e^{-{\frac {\pi i}{N}}k^{2}}\sum _{n=0}^{N-1}\left(x_{n}e^{-{\frac {\pi i}{N}}n^{2}}\right)e^{{\frac {\pi i}{N}}(k-n)^{2}}\qquad k=0,\dots ,N-1.}$

Esta suma es precisamente una convolución de las dos secuencias a _n y b _n definidas por:

${\displaystyle a_{n}=x_{n}e^{-{\frac {\pi i}{N}}n^{2}}}$

${\displaystyle b_{n}=e^{{\frac {\pi i}{N}}n^{2}},}$

con la salida de la convolución multiplicada por N factores de fase b _k ^* . Es decir:

${\displaystyle X_{k}=b_{k}^{*}\left(\sum _{n=0}^{N-1}a_{n}b_{k-n}\right)\qquad k=0,\dots ,N-1.}$

Esta convolución, a su vez, se puede realizar con un par de FFT (más la FFT precalculada del chirp complejo b _n ) a través del teorema de convolución . El punto clave es que estas FFT no tienen la misma longitud N : una convolución de este tipo se puede calcular exactamente a partir de las FFT solo rellenándolas con ceros hasta una longitud mayor o igual a 2 N –1. En particular, se puede rellenar hasta una potencia de dos o algún otro tamaño altamente compuesto , para el cual la FFT se puede realizar de manera eficiente mediante, por ejemplo, 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 DFT de tamaño primo, 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 algún comentario adicional. Supongamos que rellenamos con ceros hasta 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 tanto positivos como negativos de n para b _n (observando que b _{– n} = b _n ). Los límites periódicos implícitos en la DFT de la matriz rellenada con 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 ₀ = b ₀ , B _n = B _{M – n} = b _n para 0 < n < N , y B _n = 0 en caso contrario. Luego se aplican FFT a A y B , se multiplican puntualmente y se aplican FFT inversamente para obtener la convolución de a y b , de acuerdo con el teorema de convolución habitual.

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 es generalmente el caso:

${\displaystyle b_{n+N}=e^{{\frac {\pi i}{N}}(n+N)^{2}}=b_{n}\left[e^{{\frac {\pi i}{N}}(2Nn+N^{2})}\right]=(-1)^{N}b_{n}.}$

Por lo tanto, para N pares, la convolución es cíclica, pero en este caso N es compuesta y normalmente se usaría un algoritmo FFT más eficiente, como Cooley–Tukey. Sin embargo, para N impares, entonces b _n es antiperiódica y técnicamente tenemos una convolución negacíclica de longitud N . Sin embargo, tales distinciones desaparecen cuando se rellena con ceros a _n hasta una longitud de al menos 2 N −1 como se describió anteriormente. Por lo tanto, tal vez sea más fácil pensar en ella como un subconjunto de los resultados de una convolución lineal simple (es decir, sin "extensiones" conceptuales de los datos, periódicas o de otro tipo).

transformadas z

El algoritmo de Bluestein también se puede utilizar para calcular una transformación más general basada en la transformada z (unilateral) (Rabiner et al. , 1969). En particular, puede calcular cualquier transformación de la forma:

${\displaystyle X_{k}=\sum _{n=0}^{N-1}x_{n}z^{nk}\qquad k=0,\dots ,M-1,}$

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 total de muestreo, similar a una FFT de Zoom), mejorar polos arbitrarios en análisis de funciones de transferencia, etc.

El algoritmo se denominó algoritmo de transformada z de 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 los sistemas de radar .

Véase también

• Transformada de Fourier fraccionaria

Referencias

1. Un estudio de la transformada Z de Chirp y sus aplicaciones - Shilling, Steve Alan
2. "Transformada Z de Chirp - MATLAB czt". www.mathworks.com . Consultado el 22 de septiembre de 2016 .
3. Martin, Grant D. (noviembre de 2005). "Optimización del zoom espectral mediante transformada Z de Chirp con MATLAB®" (PDF) .
4. Bostan, Alin (2003). Algoritmo eficaz para operaciones de base en cálculo formal (PDF) (Doctor). Escuela Politécnica.
5. Bostan, Alin; Schost, Éric (2005). "Evaluación polinómica e interpolación en conjuntos especiales de puntos". Journal of Complexity . 21 (4): 420–446. doi :10.1016/j.jco.2004.09.009.
6. Ingenieros resuelven un rompecabezas de 50 años en el procesamiento de señales: transformada Z de chirrido inverso, por la UNIVERSIDAD ESTATAL DE IOWA 10 DE OCTUBRE DE 2019
7. Bluestein, L. (1970-12-01). "Un enfoque de filtrado lineal para el cálculo de la transformada de Fourier discreta". IEEE Transactions on Audio and Electroacoustics . 18 (4): 451–455. doi :10.1109/TAU.1970.1162132. ISSN  0018-9278.
8. "Algoritmo FFT de Bluestein". DSPRelated.com.

General

• Leo I. Bluestein, "Un enfoque de filtrado lineal para el cálculo de la transformada de Fourier discreta", Northeast Electronics Research and Engineering Meeting Record 10 , 218-219 (1968).
• Lawrence R. Rabiner, Ronald W. Schafer y Charles M. Rader, "El algoritmo de la transformada 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 de la transformada z de chirp", IEEE Trans. Audio Electroacoustics 17 (2), 86–92 (1969).
• DH Bailey y PN Swarztrauber, "La transformada de Fourier fraccionaria 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 de Fourier fraccionaria se refiere convencionalmente a una transformada continua completamente diferente).
• Lawrence Rabiner, "El algoritmo de transformada 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 a partir 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 chirrido en el círculo unitario", Sci Rep 10, 4852 (2020).

Enlaces externos

• Un algoritmo DSP para el análisis de frecuencia: la transformada Chirp-Z (CZT)
• Resolviendo un rompecabezas de 50 años en el procesamiento de señales, segunda parte