Transformación Z de chirrido

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

Específicamente, la transformada Z 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 partida complejo, W es la razó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 O( n log n ) operaciones donde$n=\max(M,N)$. Un algoritmo O( N log N ) para la transformada Z de chirp inversa (ICZT) fue descrito en 2003, ^{[ 4 ] [ 5 ]} y en 2019. ^{[ 6 ]}

El algoritmo de Bluestein ^{[ 7 ] [ 8 ]} expresa el CZT como una convolución y lo implementa de manera eficiente utilizando 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 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 {-(kn)^{2}}{2}}+{\frac {n^{2}}{2}}+{\frac {k^{2}}{2}}}$

obtenemos así:

${\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}}(kn)^{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_{kn}\right)\qquad k=0,\dots ,N-1.}$

Esta convolución, a su vez, puede realizarse con un par de FFT (más la FFT precalculada de chirp complejo b _n ) mediante el teorema de convolución . El punto clave es que estas FFT no tienen la misma longitud N : dicha convolución solo puede calcularse exactamente a partir de FFT rellenándola 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 compuesto , para lo cual la FFT puede realizarse eficientemente, 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 DFT de tamaño primo, aunque varias veces más lento que el algoritmo de Cooley-Tukey para tamaños compuestos. ^{[ 9 ]}

El uso del relleno de ceros para la convolución en el algoritmo de Bluestein merece un comentario adicional. Supongamos que rellenamos con ceros hasta una longitud M ≥ 2 N – 1. Esto significa que a _n se extiende a un arreglo 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 por la DFT del arreglo con relleno de ceros significan que – n es equivalente a M – n . Por lo tanto, b _n se extiende a un arreglo 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. ^{[ 9 ]} A y B se transforman luego mediante FFT, se multiplican punto por punto y se transforman inversamente mediante FFT para obtener la convolución de a y b , según el teorema de convolución usual. ^{[ 9 ]}

Seamos también 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 periodo 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, este no suele ser 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 par 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ódica y técnicamente tenemos una convolución negacíclica de longitud N. Estas 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, quizás sea más fácil pensar en ella como un subconjunto de las salidas de una convolución lineal simple (es decir, sin "extensiones" conceptuales de los datos, periódicas o de otro tipo). ^{[ 9 ]}

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) ^{[ 9 ]} . 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 ^{[ 9 ]} , dicha transformación puede utilizarse, por ejemplo, para obtener una interpolación más fina de alguna porción del espectro (aunque la resolución de frecuencia sigue estando limitada por el tiempo total de muestreo, similar a una FFT de zoom), realzar polos arbitrarios en análisis de funciones de transferencia, etc.

El algoritmo fue denominado algoritmo de transformada Z de chirrido porque, para el caso de la transformada de Fourier (| z | = 1), la secuencia b _n de arriba es una sinusoide compleja de frecuencia que aumenta linealmente, que se denomina chirrido (lineal) en los sistemas de radar . ^{[ 9 ]}

• Transformada fraccional de Fourier

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