Transformada Rápida de Fourier (FFT) de secuencias de números complejos unidimensionales
Supongamos que x (N) es una secuencia discreta de longitud finita de N puntos, sustitúyala en la ecuación (8-3) y en la ecuación (8-4), y sea su transformada de Fourier (DFT)
Conceptos básicos del procesamiento de datos geofísicos
La transformación inversa (IDFT) es
Conceptos básicos del procesamiento de datos geofísicos
La única diferencia entre los dos es el signo exponente de W es diferente, y la diferencia es una constante 1/N, por lo que a continuación solo analizamos las operaciones de la ecuación de transformación directa DFT (8-5), y las operaciones de su ecuación de transformación inversa (8-6) son exactamente lo mismo.
En términos generales, W es un número complejo, por lo tanto, X(j) también es un número complejo. Para la transformada de Fourier (DFT) de la ecuación (8-5), se necesitan N veces para calcular un. Valor X(j) Multiplicación compleja y sumas complejas N-1. Y X (j) tiene N valores (j = 0, 1,..., N-1), por lo que para completar toda la operación DFT, requiere N2 multiplicaciones complejas y N (N-1) sumas complejas.
Para calcular directamente la DFT, el número de multiplicaciones y sumas es proporcional a N2. Cuando N es grande, la cantidad de cálculo será muy grande. Por ejemplo, cuando N = 8, la DFT requiere 64 multiplicaciones complejas. ;Y cuando N = 1024, la multiplicación requerida por DFT es 1048576 veces, es decir, más de un millón de operaciones de multiplicación complejas, lo que requiere una alta velocidad de operación. Por tanto, es necesario mejorar el método de cálculo de DFT para reducir el número de operaciones.
Analizando Wjk, hay N2 valores en la superficie. Debido a su periodicidad, en realidad solo hay N valores diferentes W0, W1,..., WN-1. Para N=2m, debido a su simetría, solo hay N/2 valores diferentes W0, W1,...,
Conceptos básicos del procesamiento de datos geofísicos Por lo tanto, la secuencia larga DFT se puede descomponer. En una secuencia corta DFT. Se ha analizado anteriormente que DFT es proporcional a N2, por lo que cuanto más pequeño es N, más ventajoso es. Al mismo tiempo, utilizando la ley de combinación de ab + ac = a (b + c), puede sumar los coeficientes x (k) correspondientes al mismo Wr y luego multiplicarlos por Wr, lo que puede reducir en gran medida el número. de operaciones. Esta es la idea del algoritmo de la Transformada Rápida de Fourier (FFT).
A continuación, analicemos el algoritmo FFT bajo la condición de N=2m.
1. Algoritmo FFT para N=4
Para m=2, N=4, la transformada de Fourier de la ecuación (8-5) es
La Tierra Conceptos básicos del procesamiento de datos físicos
Escriba la ecuación (8-7) en forma matricial
Conceptos básicos del procesamiento de datos geofísicos
Para facilitar el análisis, j en el En la fórmula anterior, k se escribe en forma binaria, es decir,
Fundamentos del procesamiento de datos geofísicos
Sustituyendo en la ecuación (8-7), obtenemos
Geofísico Fundamentos de procesamiento de datos
Analizar la periodicidad de Wjk para reducir el número de multiplicaciones
Fundamentos del procesamiento de datos geofísicos
Entonces la ecuación de sustitución (8-9) es compilado
Conceptos básicos del procesamiento de datos geofísicos
La fórmula anterior se puede calcular en capas. La capa interna se calcula primero y luego los resultados del cálculo de la capa interna se utilizan al calcular. Capa exterior, que puede evitar cálculos repetidos. Escrito en forma jerárquica
Conceptos básicos del procesamiento de datos geofísicos
Entonces X (j1 j0) = X2 (j1 j0).
La fórmula anterior muestra que para N=4 FFT, la relación periódica de Wr se puede dividir en m=2 pasos para el cálculo. De hecho, utilizando la simetría de Wr, la fórmula (8-11) aún se puede simplificar y calcular. Considerando
Conceptos básicos del procesamiento de datos geofísicos
La ecuación (8-11) se puede simplificar a
Conceptos básicos del procesamiento de datos geofísicos
Como j=j0; k=k0, y expresamos la fórmula anterior en sistema decimal, obtenemos
Conceptos básicos del procesamiento de datos geofísicos
Como puede ver, complete el cálculo FFT de N= 4 en la fórmula anterior (Tabla 8-1) requiere N·(m-1)/2=2 multiplicaciones complejas y N·m=8 sumas complejas, que es N2=16 multiplicaciones complejas y N·(N- 1) = 12 adiciones complejas es mucho menos.
Tabla 8-1 Proceso de cálculo del algoritmo FFT para N=4
Nota: W0=1;
[Ejemplo 1] Encuentre el espectro de N=4 secuencia de muestra 1, 3, 3, 1 (Tabla 8-2).
Tabla 8-2 Secuencia de muestra N=4
2 Algoritmo FFT de N=8
Similar al caso de N=4, expresado en binario formulario, Sí
Conceptos básicos del procesamiento de datos geofísicos
Escrito en forma de cálculo jerárquico:
Conceptos básicos del procesamiento de datos geofísicos
Entonces X(j2 j1 j0)=X3(j2 j1 j0).
Ampliar k=2k1+k0, es decir, k=0, 1, 2, 3, hay
Conceptos básicos del procesamiento de datos geofísicos
Uso un método similar para calcular X2 (k0) de la Ecuación (8-14) j1 j0), Cuando X3(j)=X(j)(j=0,1,…,7), el cálculo FFT de N=23= 8 se completa. El proceso detallado se muestra en la Tabla 8-3.
Tabla 8-3 Proceso de cálculo del algoritmo FFT para N=8
Nota: para transformación directa y transformación inversa
[Ejemplo 2] Encuentre N=8 Espectro de secuencia de muestra (Tabla 8-4) x (k) = 1, 2, 1, 1, 3, 2, 1, 2.
Tabla 8-4 Secuencia de muestra N=8
3. Cualquier algoritmo FFT de N=2m
Enumere la FFT de N=4 y N=8. Fórmulas de cálculo para comparar
Conceptos básicos del procesamiento de datos geofísicos
Observando las fórmulas (8-18) y las fórmulas (8-19), no es difícil ver que siguen las siguientes reglas :
(1) El subíndice en el lado izquierdo de la ecuación aumenta de 1 a m, y puede reemplazarse por q=1, 2,...,m, luego el lado derecho de la ecuación es q-1;
(2) El límite superior de k es un número impar y disminuye con el aumento de q. Es 0 cuando q=m, por lo que su rango de valores es k=0, 1. , 2,..., (2m-q-1);
(3) El límite superior de j es un número impar y aumenta con el aumento de q, y es 0 cuando q=1 , y su rango de valores es j=0, 1, 2,..., (2q-1- 1);
(4) El coeficiente de k es 2q en el lado izquierdo de la ecuación y 2q-1 en el lado derecho de la ecuación (incluido el exponente de potencia de W);
(5), etc. La constante en el número de serie en el lado izquierdo de la ecuación es una potencia de 2, y el exponente de potencia es 1 menor que el subíndice q, es decir, 2q-1 la constante m en el número de serie en el lado derecho de la ecuación es un valor fijo 2m-1;
Resuma las reglas anteriores y escriba el algoritmo FFT para cualquier entero positivo m, N = 2m de la siguiente manera:
De X0 (p) = x (p) (p = 0, 1 ,...,N-1) Inicio:
(1) Para q=1,2,...,m, ejecute los pasos (2)~(3);
(2) Para k=0, 1, 2,..., (2m-q-1) y j=0, 1, 2,..., (2q-1-1), ejecute
Conceptos básicos del procesamiento de datos geofísicos
(3) j, k finaliza el ciclo
(4) q finaliza el ciclo es de Xm (p) (p); = 0, 1,..., N-1) Espectro X(p) de la secuencia x(p).
El programa de algoritmo FFT anterior es fácil de implementar en una computadora. Solo se necesitan tres matrices complejas. Los pasos de programación son los siguientes:
(1) Establezca las matrices complejas X1 (. N-1), X2 (N-1) y (el límite inferior de la matriz comienza desde 0);
(2) Asigne la secuencia de muestra x a X1, es decir, X1 (k) = x (k) (k = 0, 1, ..., N-1);
(3) Calcular W, es decir, transformación directa y transformación inversa
(4 ) q=1, 2,..., m, si q es un número par, Ejecute (6), en caso contrario ejecute el paso (5);
(5)k=0,1,2, …, (2m-q-1) y j=0,1,2,… , (2q-1-1) ciclo, como
X2 (2qk+j) = X1 (2q-1k+ j) + =[X1(2q-1k+j)-X1(2q-1k+j+2m-1)]W(2q-1k)
Para k, j termina el ciclo;
(6)k＝ 0, 1, 2,..., (2m-q-1) y j=0, 1, 2,..., (2q-1-1) ciclo, como
X1 (2qk+j)=X2 ( 2q－1k＋j）+X2（2q－1k＋j+2m－1）
/p>
El bucle termina en k y j ;
(7) El ciclo q finaliza. Si m es un número par, genera X1(j); de lo contrario, genera X2(j) (j=0,1,...,N-1). , eso es lo que se requiere.