FFT es un algoritmo eficiente para DFT, llamado transformada rápida de Fourier. Se basa en las características impares, pares, imaginarias, reales y otras de la transformada de Fourier discreta. El algoritmo FFT se puede dividir en algoritmo de extracción basado en el tiempo y algoritmo de extracción basado en frecuencia. Primero, presentamos brevemente los principios básicos de FFT. A partir de la operación DFT, se explican los principios básicos de FFT.
La operación de DFT es:
Donde
Calcular DFT para cada valor K mediante este método requiere 4N veces de multiplicación y suma de números reales (4N-2 ) sumas Para N k valores, se requieren 4N*4N multiplicaciones de números reales y (4N-2)(4N-2) sumas de números reales. Mejorar el algoritmo DFT, reducir su complejidad computacional y utilizar la periodicidad y simetría en DFT para convertir todo el cálculo DFT en una serie de operaciones iterativas, lo que puede mejorar en gran medida el proceso computacional y la complejidad computacional. FFT.
FFT no tiene nuevos descubrimientos en la teoría de la transformada de Fourier, pero se puede decir que es un gran paso adelante en la aplicación de la transformada de Fourier discreta en sistemas informáticos o sistemas digitales.
Supongamos que x(n) es una secuencia compleja de N elementos. Según la transformación DFT, el cálculo de cualquier X(m) requiere N multiplicaciones complejas y N-1 sumas complejas, y una multiplicación compleja es igual. a Cuatro multiplicaciones de números reales y dos sumas de números reales, una suma de números complejos equivale a dos sumas de números reales, incluso si una multiplicación de números complejos y una suma de números complejos se definen como una "operación" (cuatro multiplicaciones de números reales y cuatro sumas de números reales) , entonces N X (m) de una secuencia de números complejos, es decir, la transformación DFT de N puntos requiere aproximadamente N ^ 2 operaciones. Cuando N = 1024 puntos o más, se requieren N2 = 1048576 operaciones en FFT, utilizando la periodicidad y simetría de WN, una secuencia de N elementos (suponiendo que N = 2k, k es un entero positivo) se divide en dos subsecuencias de. N/2 elementos, cada transformación DFT de N/2 puntos requiere (N/2) 2 operaciones, y luego se utilizan N operaciones para combinar las dos transformaciones DFT de N/2 puntos en una transformación DFT de N puntos. Después de esta transformación, el número total de operaciones se convierte en N+2*(N/2)^2=N+(N^2)/2. Continuando con el ejemplo anterior, cuando N=1024, el número total de operaciones pasa a ser 525312, lo que ahorra aproximadamente el 50% de los cálculos. Y si continuamos con esta idea de "dividirlo en dos" hasta dividirlo en dos grupos de unidades de operación DFT, entonces la transformación DFT de N puntos solo requiere operaciones Nlog2N. Cuando N es 1024 puntos, la operación El número de. Los cálculos son solo 10240 veces, que es el 1% del algoritmo directo anterior. Cuantos más puntos, mayor será el ahorro en los cálculos. Esta es la superioridad de FFT.