¿Qué tan importante es usar la potencia de 2 cuando se usa FFT?

8

Aquí está el problema. Tengo una matriz de datos 2D, la primera columna representa los datos de tiempo y la segunda columna representa los datos de respuesta sinusoidal, basados ​​en los datos de tiempo. Aplico fft y obtengo mi frecuencia (con la que comencé) en un contenedor específico como esperaba y encuentro la amplitud y el ángulo de fase de ese contenedor. Ahora el problema es que tengo la misma configuración pero con más puntos de datos, aplico el fft nuevamente y el número de bin cambia (lo cual es normal y es donde espero que esté), la amplitud es la misma pero el ángulo de fase es diferente) primero es esto normal? segundo, ¿qué enfoque debo tomar? Gracias

PD: ninguna de las configuraciones (mencionadas anteriormente) da datos de longitud de potencia de 2, digamos que el primero da 1620 puntos de datos y el segundo da 1745 puntos de datos, por lo que debería tomar la próxima potencia de 2 para ambos del ¿comenzando?

lamia
fuente

Respuestas:

5

Las bibliotecas FFT modernas, como FFTW y el marco Accelerate de Apple, pueden hacer FFT sin potencia de 2 de manera muy eficiente, siempre que todos los divisores primos de la longitud compuesta sean bastante pequeños (2,3,5, etc.)

Una potencia de 2 hace que sea más simple (aproximadamente 1 página de código fuente) si tiene que codificar su propia FFT por alguna razón, o si tiene alguna restricción en cuanto a la longitud máxima del programa (o puertas FPGA, etc.)

Para la medición de fase, podría ser más fácil hacer un desplazamiento hacia delante (girar previamente los datos en N / 2) para hacer referencia a la fase FFT al centro de la ventana de datos, donde la relación de uniformidad / rareza y, por lo tanto, la fase no cambiará o alternar con el número de contenedor (para la fase que es la misma en el centro de esa ventana de datos) incluso para señales que no son periódicas en la longitud FFT, ya que varía la longitud.

hotpaw2
fuente
Hola hotpaw2, lo siento, olvidé mencionar que estoy usando matlab FFT, ¿eso hace alguna diferencia? gracias de nuevo.
lamia
Matlab puede usar una biblioteca moderna de FFT, como FFTW, internamente. Consulte la documentación de matlab para su versión.
hotpaw2
Además, @ hotpaw2, ya estoy usando fftshift ...
lamia
Con fftshift, coloque el centro de ventanas de datos donde desea medir la fase. O calcule la fase desde el centro hacia atrás en el tiempo usando una buena estimación de frecuencia.
hotpaw2
5

No hay nada intrínsecamente 'mágico' sobre realizar una potencia de 2 DFT, aparte del hecho de que realizar una potencia de 2 DFT le permite a uno realizar la DFT en O(nortelosol(norte)) en vez de O(norte2). Por lo tanto, la potencia de 2 DFT (el algoritmo que hace esto se conoce como FFT) le permite simplemente acelerar su cálculo de DFT en un factor enorme.

Aplico el fft nuevamente y el número de bin cambia (lo cual es normal y es donde espero que esté), la amplitud es la misma pero el ángulo de fase es diferente) primero, ¿es esto normal?

Si hace un DFT más grande que su vector de datos, esencialmente va a interpolar en el dominio de la frecuencia. Por lo tanto, su nuevo pico podría no ser el viejo pico equivalente que detectó por primera vez, antes de tomar un DFT más grande. Y dado que no es lo mismo, esencialmente está eligiendo una base exponencial compleja diferente (seno más coseno) esta vez, lo que significa que probablemente tendría un valor de fase diferente, sí.

PD: ninguna de las configuraciones (mencionadas anteriormente) da datos de longitud de potencia de 2, digamos que el primero da 1620 puntos de datos y el segundo da 1745 puntos de datos, por lo que debería tomar la próxima potencia de 2 para ambos del ¿comenzando?

Sí, si desea tomar una potencia de 2 FFT, entonces simplemente elegiría la siguiente potencia de 2 FFT de longitud que es mayor que la longitud de su registro de datos.

no necesariamente quiero o no quiero tomar el poder de 2 FFT (el rendimiento del tiempo no es mi problema en absoluto), más bien, ¿necesito hacerlo?

Nunca debe tomar una FFT de longitud menor que la longitud de su registro, a menos que desee descartar datos. La pregunta "¿Qué tan grande debe ser mi FFT?", Suponiendo que la longitud de la FFT es mayor que la longitud de su registro de datos, se vuelve rápidamente dependiente de la aplicación. Por lo general, puede salirse con una longitud FFT igual a la longitud de su registro. Sin embargo, a veces desea elegir un pico de una FFT 'más suave'. En este caso, puede tomar una mayor longitud de FFT (2 veces más, 3 veces más, 10 veces más, etc.), y habría interpolado su pico en el dominio de la frecuencia. Sin embargo, no hay un número mágico. Recuerde que la granularidad de su resultado FFT es siempreFsnorte.

Tarin Ziyaee
fuente
Gracias user4619 por las respuestas, no necesariamente quiero o no quiero tomar el poder de 2 FFT (el rendimiento del tiempo no es mi problema en absoluto), más bien, ¿necesito hacerlo?
lamia
Además, @ user4619, ya que usted mencionó que sí, el ángulo de fase podría cambiar, ¿en cuál debería confiar que me está dando la respuesta correcta? (No sé el ángulo de fase de antemano o la amplitud, solo sé la frecuencia de antemano) ... gracias
lamia
@lamia Power-of-2 es solo para problemas de velocidad. Eso es. No hay nada mágico al respecto de lo contrario. Acerca del ángulo de fase: recuerde que aunque su ángulo de fase cambie, también lo hace su frecuencia pico. Si realiza una FFT de 1000 puntos, elige el bin de frecuencia 100 como el pico y encuentra su ángulo de fase. Eso es correcto. Luego realiza una FFT de 343212 puntos, y elige una frecuencia 34321 como pico, y tiene un ángulo de fase diferente. Eso sigue siendo correcto. "Fase" es una función de frecuencia. (Si lo encontró útil, no dude en votar)
Tarin Ziyaee
@lamia También vea mis ediciones.
Tarin Ziyaee
Muchas gracias por las explicaciones que ha proporcionado :)
lamia
3

Mostrando la respuesta de @ user4619:

Usando IPython, que es similar a Matlab

In[1]: fft(arange(2**22))
1 loops, best of 3: 354 ms per loop

In[2]: fft(arange(4*1000*90*12)) # close to 2**22
# equal to 2*2 * 2*5*2*5*2*5 * 3*3*2*5 * 2*2*3
1 loops, best of 3: 295 ms per loop

In[2]: fft(arange(2**22+1))
1 loops, best of 3: 14 s per loop

Si usa números primos realmente importantes, bastante importante (¡un factor de 50!). Si usa números que tienen factores bajos, no es importante. Pero hacerlo solo con números primos solo lo hace más rápido: no cambia la respuesta en absoluto.

Scott
fuente