Efficient Software Implementation of the Nearly Optimal Sparse Fast Fourier Transform for the Noisy Case

Implementación software eficiente de la Transformada de Fourier Escasa casi óptima para el caso con ruido

En este artículo se presenta una implementación software optimizada (sFFT-4.0) del algoritmo Transformada Rápida de Fourier Escasa (sFFT) Casi Óptimo para el caso con ruido. En primer lugar, se desarrolló una versión modificada del algoritmo sFFT Casi Óptimo para el caso con ruido, esta modificación resuelve los problemas de exactitud de la versión origial al modificar la ventana plana y los procedimientos; y en segundo lugar, se implementó el algoritmo modificado en una plataforma multinúcleo compuesta de ocho núcleos. Los resultados experimentales en el agrupamiento de computadores muestran que la implementación desarrollada es más rápida que el cálculo directo usando la biblioteca FFTW bajo ciertas condiciones de escasés y tamaño de señal, y mejora los tiempos de ejecución de implementaciones previas como sFFT-2.0. Al mejor conocimiento de los autores, la implementación desarrollada es la primera del algoritmo sFFT Casi Óptimo para el caso con ruido.

1 INTRODUCCIÓN

El término sFFT hace referencia a una familia de algoritmos que permiten estimar la Transformada Discreta de Fourier (DFT) de una señal dispersa, de forma más rápida que los algoritmos de FFT encontrados en la literatura [1],[2],[3],[4]; en este caso, se asume que la señal es dispersa o aproximadamente dispersa en el dominio de la DFT.

Por un lado, investigadores del Instituto Tecnológico de Massachusetts (MIT) presentaron dos algoritmos sFFT [2] que mejoran el tiempo de ejecución respecto a todos los desarrollos anteriores [1],[5],[6],[7], incluyendo los algoritmos FFT convencionales más optimizados como FFTW [8]; el primer algoritmo está pensado para el caso sin ruido, y el segundo algoritmo para el caso con ruido.

Por otro lado, hasta donde sabemos sólo hay cuatro implementaciones de software de los algoritmos MIT sFFT reportadas en la literatura; la primera fue desarrollada por los autores del algoritmo para la primera versión del algoritmo sFFT [1]; la segunda es una implementación optimizada de la primera versión del algoritmo sFFT [9]; la tercera es una implementación basada en GPU de la primera versión del algoritmo sFFT [10]; y la cuarta es una implementación optimizada del algoritmo sFFT Casi Óptimo para el caso sin ruido [11]. Por lo tanto, no hay ninguna implementación de software en la literatura del algoritmo sFFT Casi Óptimo para el caso ruidoso, que es de interés práctico para los investigadores científicos.

Por lo tanto, teniendo en cuenta lo anterior, la principal contribución de este trabajo es el desarrollo de una versión modificada del algoritmo sFFT Casi Óptimo y su implementación de software optimizada en un entorno multinúcleo proporcionado por un clúster Beowulf.