Algoritmo de chirrido

El algoritmo Chirp ( algoritmo de Bluestein ) es un algoritmo para el cálculo de la transformada rápida de Fourier , que consiste en reducir el cálculo de la transformada discreta de Fourier al cálculo de la convolución .

Para , , la fórmula del algoritmo se deriva de la fórmula para la transformada discreta de Fourier de una señal a una señal de la siguiente manera [1] : $n\en \mathbb {N}$ ${\displaystyle \omega =e^{-{\frac {2\pi i}{n))))$ $\beta ={\sqrt {\omega ))$ $X$ $X$

X(k)=\sum \limits _{j=0}^{n-1}x(j)\omega ^{kj}=\sum \limits _{j=0}^{n-1 }x(j)\beta ^{2kj}=\beta ^{-k^{2}}\sum \limits _{j=0}^{n-1}\beta ^{(jk)^{2} }{\bigg (}\beta ^{-j^{2}}x(j){\bigg )},\;k=0,\ldots,n-1

Usando la notación , podemos reescribir esta fórmula en una forma más compacta: $a(j)=x(j)\beta ^{-j^{2))$ $b(j)=\beta^{j^{2))$

X(k)=b^{*}(k)\left(a*b\right),\;k=0,\ldots,n-1

Aquí, el superíndice significa conjugación compleja y el símbolo significa convolución. Las cantidades a veces se llaman chirp ( ing. chirp ). ${\ estilo de visualización ^ {*}}$ $*$ ${\ estilo de visualización b (j)}$

El algoritmo contiene convolución de punto, cuyo cálculo requiere operaciones y multiplicaciones adicionales, es decir, el número total de operaciones tiene el orden de , por lo que el algoritmo de Bluestein no es asintóticamente más eficiente que el cálculo directo de la transformada de Fourier. Sin embargo, en algunas aplicaciones, permite una implementación de hardware más simple. Además, el cálculo directo de la convolución puede ser reemplazado por algoritmos rápidos [2] . $norte$ $O(n^{2})$ $2n$ $O(n^{2})$

Por ejemplo, utilizando el teorema de convolución , puede reemplazar el cálculo de la convolución con el cálculo de dos transformadas de Fourier discretas, cada una de las cuales puede calcularse mediante un algoritmo rápido, por ejemplo, el método Cooley-Tukey y, por lo tanto , asegurar la implementación del algoritmo de Bluestein con complejidad computacional . Las cantidades y su transformada de Fourier también se pueden calcular por adelantado y almacenar en la memoria para su posterior reutilización. $O(n\log n)$ ${\ estilo de visualización b (j)}$

Notas

↑ Blahut, 1989 , pág. 147.
↑ Blahut, 1989 , pág. 149.

Literatura

Blahuth, R. Algoritmos rápidos de procesamiento de señales digitales. —M.:Mir, 1989. — 448 p. (Ruso)