El principio del algoritmo de transformada rápida de Fourier
Categoría: Ciencia e Ingeniería gt; gt; Ingeniería Tecnología Ciencia
Descripción del problema:
¿Quién puede decirme los principios básicos del algoritmo de transformada rápida de Fourier? ¡Cuanto más específico sea, mejor!
¡Gracias de antemano! !
Análisis:
La transformada rápida de Fourier (FFT) es un algoritmo rápido para la transformada de Fourier discreta. Se basa en las características impares, pares, imaginarias, reales y otras de la transformada de Fourier discreta. Se obtiene mejorando el algoritmo de transformada discreta de Fourier. No hace nuevos descubrimientos sobre la teoría de la transformada de Fourier, pero se puede decir que es un gran paso adelante para la aplicación de la transformada discreta de Fourier 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 N2 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 pasa a ser N 2 (N/2) 2 = N N2/2. Continuando con el ejemplo anterior, cuando N = 1024, el número total de operaciones pasa a ser 525312, lo que ahorra aproximadamente 50 operaciones. 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 1 del algoritmo directo anterior. Cuantos más puntos, mayor será el ahorro en los cálculos. Esta es la superioridad de FFT.
zhidao.baidu/q?word=BFECCBD9B8B5C1A2D2B6B1E4BBBBamp;ct=17amp;pn=0amp;tn=ikaslistamp;rn=10
zhidao.baidu/question/872986