Transformada Rápida de Fourier

En 1965, Kuhler y Taki propusieron un nuevo algoritmo para calcular la DFT. Para datos con N puntos de muestreo, este algoritmo reduce las N2 operaciones de números complejos originales a Nlog2N veces, lo que ahorra en gran medida tiempo de computación de la máquina. Este algoritmo se conoce comúnmente como Transformada Rápida de Fourier, abreviado como FFT. Debido a la aparición de FFT, se han producido muchos cambios importantes en el procesamiento de señales digitales, por lo que es de considerable importancia. En esta sección, presentaremos en detalle el principio y la fórmula de cálculo de FFT y brindaremos un diagrama de flujo para implementarlo.

1. Pregunta

Para una secuencia finita x(n), n=0, 1,...,N-1, su DFT es

Tecnología de procesamiento y análisis de señales digitales de prospección geofísica

La ecuación (7-1-1) representa N ecuaciones, escritas en su totalidad

Tecnología de procesamiento y análisis de señales digitales de prospección geofísica

Debido a que x(n) puede ser una secuencia compleja, al calcular cada componente del espectro X(m) en (7-1-2), se requieren N veces de multiplicación compleja y (N-1) veces de suma compleja . Si se calculan todos los N componentes espectrales, es necesario realizar N2 multiplicaciones complejas y N(N-1) sumas complejas. Dado que la multiplicación de dos números complejos es igual a la multiplicación de 4 números reales, N2 multiplicaciones de números complejos equivalen a la multiplicación de 4N2 números reales. Cuando N es grande, la carga de trabajo de cálculo directo de (7-1-2) es muy grande. Por ejemplo, cuando N = 1000, es necesario calcular 4 millones de multiplicaciones de números reales; cuando N = 5000, es necesario calcular 100 millones de veces; Calculado. Multiplicación subreal. Una carga de trabajo de cálculo tan grande requiere un tiempo de cálculo de máquina prolongado, incluso con una computadora de alta velocidad, lo que afecta seriamente la amplia aplicación de DFT en diversos campos. Por lo tanto, la gente ha propuesto si se puede encontrar un algoritmo para reducir el tiempo de cálculo de DFT.

2. Idea básica del algoritmo FFT

En 1965, Kuhler y Taki propusieron un nuevo algoritmo para reducir el tiempo de cálculo de DFT. Tomamos el caso de N = 4 en (7-1-2) como ejemplo para ilustrar la idea básica de este algoritmo.

Para N=4=22, obtenga de (7-1-2)

Tecnología de procesamiento y análisis de señales digitales geofísicas

Convierta (7-1- 3) Escrito en forma matricial

Tecnología de procesamiento y análisis de señales digitales geofísicas

Si en (7-1-4), la matriz que contiene Wi se puede descomponer en dos matrices, y Por Al hacer que solo dos elementos en cada fila de estas dos matrices sean distintos de cero, se puede reducir el número de operaciones de multiplicación. Dado que el tiempo para calcular DFT depende principalmente del número de operaciones de multiplicación, reducir la multiplicación puede mejorar la eficiencia del cálculo. El algoritmo anterior se explica en detalle a continuación.

Primero, reorganice el orden de X(m) en (7-1-4) de la siguiente manera

Tecnología de procesamiento y análisis de señales digitales geofísicas

Porque

Entonces, (7-1-5) puede escribirse como

Tecnología de procesamiento y análisis de señales digitales geofísicas

En segundo lugar, (7-1-6) La La matriz que contiene Wi se descompone en dos matrices con solo dos elementos en cada fila distintos de cero, por lo que obtenemos

Tecnología de procesamiento y análisis de señales digitales geofísicas

En tercer lugar, de (7 - 1-7) Fórmula chelín:

Tecnología de procesamiento y análisis de señales digitales geofísicas

Tecnología de procesamiento y análisis de señales digitales geofísicas

De (7-1-8) Observa que en este paso de la operación, solo se requieren 2 multiplicaciones complejas y 4 sumas complejas.

Cuarto, sustituya (7-1-8) en (7-1-7) para obtener

Tecnología de procesamiento y análisis de señales digitales geofísicas

De ( 7-1-9), podemos ver que en esta operación sólo se necesitan 2 multiplicaciones complejas y 4 sumas complejas. Se puede observar que al calcular el espectro Al calcular (7-1-3) directamente, la operación total requiere 16 multiplicaciones complejas y 12 sumas complejas.

Consideremos el caso en el que el número de puntos de muestreo es N=8. A partir de la fórmula (7-1-2), se puede obtener un sistema de ocho ecuaciones. Escribirlas en forma matricial es

Tecnología de procesamiento y análisis de señales digitales geofísicas

con N=4. La situación es la misma. Primero, reorganice el orden de >

Tecnología de procesamiento y análisis de señales digitales de prospección geofísica

Tecnología de procesamiento y análisis de señales digitales de prospección geofísica

Señal digital de prospección geofísica. tecnología de análisis y procesamiento

Will (7- La matriz que contiene Wi en 1-11) se descompone en tres matrices con solo dos elementos distintos de cero en cada fila, que se obtiene de (7-1-11 )

Tecnología de procesamiento y análisis de señales digitales geofísicas

De (7-1-12)

Tecnología de procesamiento y análisis de señales digitales geofísicas

De (7-1-13) podemos ver que en este paso de cálculo, solo necesitas hacer 4 multiplicaciones complejas y 8 sumas complejas. Según (7-1-13), se obtiene de (7-1-12)

Tecnología de procesamiento y análisis de señales digitales geofísicas

Se puede observar en (7- 1-14), en la segunda operación, sólo es necesario realizar 4 multiplicaciones complejas y 8 sumas complejas. Según (7-1-14), se puede obtener de (7-1-12)

Tecnología de procesamiento y análisis de señales digitales geofísicas

Se puede ver en (7 -1-15), la operación del tercer paso solo requiere 4 multiplicaciones complejas y 8 sumas complejas.

Se puede observar que al calcular el espectro X(m) de N=8, debido a la descomposición matricial e introducir ceros en las tres matrices descompuestas, el número total de operaciones se reduce a solo 12 multiplicaciones complejas. y 24 adiciones complejas. Al calcular (7-1-11) directamente, la operación total requiere 64 multiplicaciones complejas y 56 sumas complejas. En resumen, podemos ver:

Primero, la clave para que el algoritmo FFT sea más rápido que el algoritmo directo es que descompone la matriz original que contiene Wi en el producto de solo dos elementos distintos de cero en cada fila. . Cuando N = 4, se descompone en 2 matrices; cuando N = 8, se descompone en 3 matrices; cuando N = 2n, se descompone en n matrices.

En segundo lugar, para el número total de operaciones del algoritmo FFT:

Cuando N = 4, la multiplicación es (4/2)log24=2 veces y la suma es 4log24. =8 veces;

Cuando N=8, la multiplicación es (8/2)log28=12 veces y la suma es 8log28=24 veces;...;

Cuando N = 2n, la multiplicación es por veces, la suma es Nlog2N.

Para obtener la regla general, Wi también se utiliza para la multiplicación. Si se consideran 1 varios términos Wi y se aprovecha la simetría de DFT, la multiplicación compleja real se puede reducir aún más. A modo de comparación con los cálculos directos, y tomando el peor de los casos, se considera que el algoritmo FFT contiene operaciones de números complejos Nlog2N. El algoritmo directo requiere N2 operaciones. Cuando N es muy grande, la cantidad de operaciones guardadas por el algoritmo FFT es bastante sorprendente.

En tercer lugar, de las fórmulas (7-1-9) y (7-1-15), también podemos ver una situación importante, es decir, el resultado final xi(r) es diferente al requerido espectro X( También hay diferencias entre m). Este fenómeno es causado por la reordenación del orden del espectro x(m). Para resolver esta contradicción, sólo necesitamos expresar r en xi(r) en binario e invertirlo para obtener el resultado deseado.

Por ejemplo, cuando N=4, exprese xi(r) en (7-1-9) como

Tecnología de procesamiento y análisis de señales digitales geofísicas

Invierta la ecuación anterior. Entonces puede obtenga el resultado deseado

Tecnología de procesamiento y análisis de señales digitales geofísicas

Cuando N=8, exprese xi(r) en (7-1-15) en binario como

Tecnología de procesamiento y análisis de señales digitales de prospección geofísica

Obtenga el resultado deseado invirtiendo el bit binario

Tecnología de procesamiento y análisis de señales digitales de prospección geofísica

Geofísica prospección Tecnología de procesamiento y análisis de señales digitales

Generalmente, si r se puede expresar como un número binario de n bits (N = 2n) como

Tecnología de procesamiento y análisis de señales digitales geofísicas

Entonces el orden inverso de los bits binarios de r es

Tecnología de procesamiento y análisis de señales digitales geofísicas

Entonces obtenemos,

Señal digital geofísica Tecnología de análisis y procesamiento