Quelle est l'importance d'utiliser la puissance de 2 lors de l'utilisation de la FFT?

8

Voici le problème. J'ai un tableau 2D de données, la première colonne représente les données de temps et la deuxième colonne représente les données de réponse sinusoïdale, basées sur les données de temps. J'applique fft et j'obtiens ma fréquence (avec laquelle j'ai commencé) dans un bin spécifique comme je m'y attendais et je trouve l'amplitude et l'angle de phase de ce bin. Maintenant, le problème est que j'ai la même configuration mais avec plus de points de données, j'applique à nouveau le fft et le numéro de bin change (ce qui est normal et c'est là où je m'attends à ce qu'il soit), l'amplitude est la même mais l'angle de phase est différent) est-ce d'abord normal? deuxièmement, quelle approche dois-je adopter? Je vous remercie

PS: aucune des configurations (mentionnées ci-dessus) ne donne des données de longueur de puissance de 2, disons que la première donne 1620 points de données et la seconde donne 1745 points de données, donc devrait prendre la prochaine puissance de 2 pour les deux de la début?

lamia
la source

Réponses:

5

Les bibliothèques FFT modernes, telles que FFTW et le framework Accelerate d'Apple, peuvent faire des FFT non puissantes de 2 très efficacement, tant que tous les diviseurs premiers de la longueur composite sont assez petits (2,3,5, etc.)

Une puissance de 2 le rend plus simple (environ 1 page de code source) si vous devez coder votre propre FFT pour une raison quelconque, ou si vous êtes autrement contraint quant à la longueur maximale du programme (ou portes FPGA, etc.)

Pour la mesure de phase, il pourrait être plus facile de faire un décalage fft (pré-rotation des données par N / 2) pour référencer la phase FFT au centre de la fenêtre de données, où le rapport de régularité / impair, et donc la phase ne changera pas ou alterner avec le numéro de bin (pour la phase qui est la même au centre de cette fenêtre de données) même pour les signaux qui ne sont pas périodiques dans la longueur FFT, car vous faites varier la longueur.

hotpaw2
la source
Salut hotpaw2, désolé d'avoir oublié de mentionner que j'utilise matlab FFT, cela fait-il une différence? Merci encore.
lamia
Matlab peut utiliser une bibliothèque FFT moderne, telle que FFTW, en interne. Consultez la documentation de matlab pour votre version.
hotpaw2
Aussi, @ hotpaw2, j'utilise déjà fftshift ...
lamia
Avec fftshift, placez le centre de fenêtres de données là où vous voulez mesurer la phase. Ou calculez la phase du centre vers l'arrière dans le temps en utilisant une bonne estimation de fréquence.
hotpaw2
5

Il n'y a rien de intrinsèquement «magique» dans l'exécution d'une puissance de 2 DFT, à part le fait que l'exécution d'une puissance de 2 DFT permet d'effectuer la DFT dans O(Nlog(N)) au lieu de O(N2). Ainsi, la puissance de 2 DFT, (l' algorithme qui fait cela est connu sous le nom de FFT), vous permet d'accélérer simplement votre calcul DFT par un facteur énorme.

J'applique à nouveau le fft et le nombre de bin change (ce qui est normal et c'est là que je m'attends à ce qu'il soit), l'amplitude est la même mais l'angle de phase est différent) est-ce d'abord normal?

Si vous faites une DFT plus grande que votre vecteur de données, vous allez essentiellement interpoler dans le domaine fréquentiel. Ainsi, votre nouveau pic pourrait ne pas être l'ancien pic équivalent que vous avez détecté pour la première fois, avant de prendre un DFT plus grand. Et comme ce n'est pas la même chose, vous choisissez essentiellement une base exponentielle complexe différente (sinus plus cosinus) cette fois-ci, ce qui signifie que vous auriez probablement une valeur de phase différente, oui.

PS: aucune des configurations (mentionnées ci-dessus) ne donne des données de longueur de puissance de 2, disons que la première donne 1620 points de données et la seconde donne 1745 points de données, donc devrait prendre la prochaine puissance de 2 pour les deux de la début?

Oui, si vous souhaitez prendre une puissance de 2 FFT, vous choisirez simplement la puissance suivante de 2 FFT de longueur supérieure à la longueur de votre enregistrement de données.

Je ne veux pas nécessairement ou ne veux pas prendre la puissance de 2 FFT (les performances temporelles ne sont pas du tout mon problème), plus, en ai-je besoin?

Vous ne devez jamais prendre une FFT de longueur inférieure à la longueur de votre enregistrement, sauf si vous souhaitez supprimer les données. La question «Quelle doit être la taille de ma FFT», en supposant que la longueur de la FFT est supérieure à la longueur de votre enregistrement de données, puis devient rapidement dépendante de l'application. Habituellement, vous pouvez vous en tirer avec une longueur FFT identique à la longueur de votre enregistrement. Cependant, parfois, vous souhaitez choisir un pic à partir d'une FFT «plus fluide». Dans ce cas, vous pouvez prendre une longueur FFT plus grande (2 fois plus, 3 fois plus, 10 fois plus, etc.) et vous auriez interpolé votre pic dans le domaine fréquentiel. Il n'y a cependant pas de nombre magique. N'oubliez pas que la granularité de votre résultat FFT est toujoursFsN.

Tarin Ziyaee
la source
Merci user4619 pour les réponses, je ne veux pas nécessairement ou ne veux pas prendre la puissance de 2 FFT (les performances temporelles ne sont pas du tout mon problème), plus, ai-je besoin?
lamia
Aussi, @ user4619, puisque vous avez mentionné que oui, l'angle de phase pouvait changer, lequel dois-je faire confiance qui me donne la bonne réponse? (je ne connais pas l'angle de phase avant main ni l'amplitude, je ne connais que la fréquence avant main) ... merci
lamia
@lamia Power-of-2 est uniquement destiné aux problèmes de vitesse. C'est ça. Sinon, il n'y a rien de magique. À propos de l'angle de phase - n'oubliez pas que même si votre angle de phase change, votre fréquence de crête change également. Si vous effectuez une FFT de 1000 points, vous choisissez la fréquence 100 comme pic et trouvez son angle de phase. C'est exact. Ensuite, vous effectuez une FFT de 343212 points, et choisissez une fréquence 34321 comme pic, et elle a un angle de phase différent. C'est toujours correct. La "phase" est fonction de la fréquence. (Si vous avez trouvé cela utile, n'hésitez pas à voter)
Tarin Ziyaee
@lamia Voir aussi mes modifications.
Tarin Ziyaee
Merci beaucoup pour les explications que vous avez fournies :)
lamia
3

Affichage de la réponse de @ user4619:

Utilisation d'IPython, similaire à 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 vous utilisez des nombres vraiment premiers, plutôt important (un facteur de 50!). Si vous utilisez des chiffres qui ont de faibles facteurs, ce n'est pas important. Mais le faire avec seulement des nombres premiers ne fait que plus rapidement - cela ne change pas du tout la réponse.

Scott
la source