FFT por transformada rápida de Fourier

Fast Fourier Transform es un término general para métodos de cálculo rápidos y eficientes que utilizan computadoras para calcular transformadas discretas de Fourier (DFT). La Transformada Rápida de Fourier fue propuesta por J.W Cooley y T.W. El uso de este algoritmo puede reducir en gran medida la cantidad de multiplicaciones requeridas por la computadora para calcular la transformada de Fourier discreta. En particular, cuantas más N muestras se transformen, más significativos serán los ahorros computacionales del algoritmo FFT. Información ampliada

La idea básica de FFT es descomponer la secuencia original de N puntos en una serie de secuencias "cortas" en secuencia. Aproveche al máximo la simetría y periodicidad de los factores exponenciales en la fórmula de cálculo de DFT para encontrar la DFT correspondiente a estas secuencias cortas y combínelas adecuadamente para lograr el propósito de eliminar cálculos repetidos, reducir la multiplicación y simplificar la estructura. Desde entonces, se han desarrollado algoritmos rápidos como la base alta y la base dividida basados ​​en esta idea. Con el rápido desarrollo de la tecnología digital, en 1976 apareció la transformada de Vinograd Fourier basada en la teoría de números y la teoría polinomial (WFTA) y el factor primo. Algoritmo de transformada de Fourier. Su gran similitud es que cuando N es un número primo, el cálculo DFT se puede convertir para resolver la convolución circular, reduciendo así aún más el número de multiplicaciones y aumentando la velocidad.