La transformada de Fourier más rápida de Occidente

Un aspecto interesante de las formas de onda que varían en el tiempo es que, utilizando un truco llamado Transformada de Fourier (FT), pueden representarse como la suma de sus frecuencias subyacentes. Esta idea matemática es muy útil a la hora de procesar señales digitalmente y permite una forma más sencilla de implementar el filtrado dependiente de la frecuencia en un sistema digital. [klafyvel] necesitaba esta capacidad para un proyecto, por lo que comenzó a investigar el mejor método que encajara en un Arduino Uno. En un esfuerzo por entender exactamente lo que estaba pasando, han mejorado significativamente el tamaño del código, el tiempo de ejecución y la precisión del anterior portador de la corona.

Una Transformada de Fourier completa en tiempo real es una operación que consume muchos recursos y necesita más de lo que puede ofrecer un Arduino Uno, por lo que a lo largo de los años se han desarrollado aproximaciones más rápidas que intercambian precisión absoluta por velocidad y tamaño. Estas son conocidas como Transformadas Rápidas de Fourier (FFTs). [klafyvel] se dedicó a profundizar en las matemáticas implicadas, así como en algunas técnicas de programación de bajo nivel para averiguar si se habían optimizado las compensaciones ofrecidas en las soluciones existentes. Los resultados son impresionantes.

Resultados de pruebas comparativas que muestran la velocidad de implementación frente a la competencia (ApproxFFT)

No contentos con producir un nuevo algoritmo premiado, lo que se documenta en el blog es una clase magistral para entender realmente un problema y hay nada menos que cuatro algoritmos entre los que elegir dependiendo de cómo se clasifique la importancia de la velocidad de ejecución, la precisión, el tamaño del código o el tamaño del array.

En el camino, nos encontramos con algunas grandes diversiones en cómo aproximar flotadores por sus exponentes (texto en francés), cómo controlar, programar y recoger datos de un Arduino usando Julia, cómo mejorar masivamente la velocidad del código mediante el uso de identidades trigonométricas y cómo lidiar con los desbordamientos cuando las variables se hacen demasiado grandes. Hay mucho que digerir aquí, pero las explicaciones son muy claras y están salpicadas de fragmentos de código para hacerlo más fácil y si tienes el tiempo para leerlo, ¡seguro que aprenderás mucho!  El código está en GitHub aquí.

Si te interesan las FFT, ya las hemos visto antes por estos lares. Llénate las botas con este enlace de proyectos etiquetados.

Alana Herrero
Alana Herrero

Deja una respuesta

Tu dirección de correo electrónico no será publicada.