La transformée de Fourier la plus rapide en Occident

Un aspect intéressant des formes d’onde variant dans le temps est qu’en utilisant une astuce appelée transformée de Fourier (FT), elles peuvent être représentées comme la somme de leurs fréquences sous-jacentes. Cet aperçu mathématique est extrêmement utile lors du traitement numérique des signaux et permet de mettre en œuvre un moyen plus simple de filtrage dépendant de la fréquence dans un système numérique. [klafyvel] avait besoin de cette capacité pour un projet, alors j’ai commencé à rechercher la meilleure méthode qui conviendrait à un Arduino Uno. Dans un effort pour comprendre exactement ce qui se passait, ils ont considérablement amélioré la taille du code, le temps d’exécution et la précision du porteur de couronne précédent.

Une transformée de Fourier complète en temps réel est une opération gourmande en ressources qui nécessite plus que ce qu’un Arduino Uno peut offrir, de sorte que des approximations plus rapides ont été développées au fil des ans qui échangent une précision absolue contre la vitesse et la taille. Celles-ci sont connues sous le nom de transformées de Fourier rapides (FFT). [klafyvel] mis à plonger profondément dans les mathématiques impliquées, ainsi que certaines techniques de programmation de bas niveau pour déterminer si les compromis offerts dans les solutions existantes avaient été optimisés. Les résultats sont impressionnants.

Résultats d'analyse comparative de code FFT les plus rapides en ms
Résultats de l’analyse comparative montrant la vitesse de mise en œuvre par rapport à la concurrence (ApproxFFT)

Non content de produire un nouvel algorithme primé, ce qui est documenté sur le blog est une masterclass pour vraiment comprendre un problème et il n’y a pas moins de quatre algorithmes parmi lesquels choisir en fonction de la façon dont vous classez l’importance de la vitesse d’exécution, de la précision, du code taille ou taille du tableau.

En cours de route, nous avons droit à de grandes distractions sur la façon d’approximer les flottants par leurs exposants (texte français), comment contrôler, programmer et collecter des données à partir d’un Arduino en utilisant Julia, comment améliorer massivement la vitesse du code en utilisant la trigonométrie identités et comment gérer les débordements lorsque les variables deviennent trop grandes. Il y a beaucoup à digérer ici, mais les explications sont très claires et parsemées d’extraits de code pour le rendre plus facile et si vous avez le temps de lire, vous êtes sûr d’apprendre beaucoup ! Le code est sur GitHub ici.

Si vous êtes intéressé par les FFT, nous les avons déjà vues autour de ces parties. Remplissez vos bottes avec ce lien de projets tagués.