Cómo calcular el factor de rotación de la operación mariposa

Cálculo del factor de rotación de la operación mariposa: el factor de rotación es WnkN (nk es un superíndice, N es un subíndice), n es un punto determinado en la secuencia original y k es la secuencia después de DFT (o FFT) En un punto determinado, N es el número de puntos transformados. WnkN=e^[-j*2pi*n*k/N], este es un término exponencial complejo.

Función do_fft:

Si la longitud de la secuencia a calcular es 2, las dos posiciones se escriben como x[0] x[1] y x[0]-x [1] Luego regresa.

Llame a la función do_fft en la primera mitad de la secuencia que debe calcularse.

Llame a la función do_fft en la segunda mitad de la copia de la secuencia que debe calcularse.

for (int i=0; ilt; longitud/2; i).

x[i length/2] *= Wi; tenga en cuenta que debe determinar qué W necesita primero.

x[i] y x[i longitud/2] se reescriben como x[i] x[i longitud/2] y x[i]-x[i longitud/2] respectivamente.

El término nudo de mariposa

todavía se usa con mayor frecuencia en el algoritmo de transformada rápida de Fourier de Cooley-Tukey, que utiliza un método recursivo para convertir n puntos en operaciones de Fourier discretas de n puntos. la entrada se descompone en n=r*m, y la señal de entrada se convierte en m conjuntos de señales en el punto r y cada uno se somete a operaciones de Fourier discretas de r puntos (en otras palabras, la DFT de r puntos se realiza m veces) .

La operación de Fourier discreta en el punto r es básicamente la señal de entrada convertida multiplicada por el factor de rotación y la operación de suma se realiza en una estructura de nudo de mariposa. (Lo anterior es el método de operación del método de extracción en el dominio del tiempo. La operación inversa primero realiza la operación de suma en la estructura del nudo de mariposa y luego multiplica el factor de rotación, que es el método de operación del método de extracción en el dominio de la frecuencia).