La transformada Z chirp ( CZT ) es una generalización de la transformada discreta de Fourier (DFT). Mientras que la DFT toma muestras del plano Z en puntos uniformemente espaciados a lo largo del círculo unitario, la transformada Z chirp toma muestras a lo largo de arcos espirales en el plano Z, correspondientes 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 del 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 en 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 transformada Z chirp se puede calcular en operaciones O ( n log n ) donde . En 2003, [4] [ 5 ] y en 2019 se describió un algoritmo O ( N log N ) para la transformada Z chirp inversa (ICZT).
El algoritmo de Bluestein [7] [8] expresa el CZT como una convolución y lo implementa eficientemente 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 la DFT como una convolución). Fue concebido en 1968 por Leo Bluestein. [7] 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 * . Eso es:
Esta convolución, a su vez, se puede realizar con un par de FFT (más la FFT precalculada del chirp complejo b n ) 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 FFT solo rellenándola con ceros hasta 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 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 principal, aunque varias veces más lento que el algoritmo de Cooley-Tukey para tamaños compuestos.
El uso de relleno con 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 an se extiende a una matriz An de longitud M , donde An = an para 0 ≤ n < N y An = 0 en caso contrario: el significado habitual de "relleno con 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 rellena 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 0 = b 0 , B n = B M – n = b n para 0 < n < N , y B n = 0 en caso contrario. Luego se aplica FFT a A y B , se multiplica puntualmente y se aplica FFT inversa para obtener la convolución de a y b , de acuerdo con el teorema de convolución habitual.
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 con ceros sería solo por conveniencia computacional. Sin embargo, generalmente este no es 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. Sin embargo, para N impar, entonces b n es antiperiódico y técnicamente tenemos una convolución negacíclica de longitud N. Sin embargo , tales distinciones desaparecen cuando se rellena con ceros una an hasta una longitud de al menos 2 N −1 como se describe anteriormente. Por lo tanto, quizás sea más fácil pensar en ello 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).
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 números diferentes 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 Zoom FFT), mejorar arbitrariamente polos en los análisis de funciones 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 llama chirrido (lineal) en sistemas de radar .
![{\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}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/afd30e17b4a6946de260a729f34452b1ab0bb092)
