TR10: Una transformada de Fourier más rápida

Un avance matemático promete un mundo digital más veloz.
 

 

En enero de este año, cuatro investigadores del Instituto Tecnológico de Massachusetts (MIT, en Estados Unidos) presentaron un sustituto para uno de los algoritmos más importantes de la informática. Dina Katabi, Haitham Hassanieh, Piotr Indyk y Eric Price han creado una forma más rápida de llevar a cabo la transformada de Fourier, una técnica matemática que sirve para procesar los flujos de datos que subyacen en el funcionamiento de cosas como las resonancias magnéticas, los routers wifi y las redes móviles 4G.

El principio de la transformada de Fourier, desarrollada por primera vez en el siglo XIX, es que cualquier señal, como por ejemplo una grabación de sonido, se puede representar como la suma de una serie de sinusoides o cosinusoides con distintas frecuencias y amplitudes. Así, esta serie de ondas se puede manipular con relativa facilidad. Esto permite, por ejemplo, que una grabación de audio se comprima o se pueda eliminar el ‘ruido’. A mediados de la década de 1960 se creó un algoritmo para la computación denominado ‘transformada rápida de Fourier’ (FFT en sus siglas en inglés). Cualquiera que se haya quedado maravillado ante el diminuto tamaño de un archivo MP3 en comparación con la misma grabación en su estado sin comprimir conoce la potencia de la FFT en acción.

Gracias al nuevo algoritmo, denominado transformada dispersa de Fourier (SFT, por sus siglas en inglés), los flujos de datos se pueden procesar de 10 a 100 veces más rápido que lo que permitía la FFT. Esta velocidad es posible porque la información que más nos importa es muy estructurada: la música no es un ruido aleatorio. Las señales con sentido suelen tener solo una fracción de los posibles valores que podría tener una señal. El término técnico para esto es que la información es “dispersa”. Puesto que el algoritmo SFT no está diseñado para  funcionar con cualquier flujo de datos, puede tomar determinados atajos que de otra forma no estarían disponibles. En teoría, un algoritmo capaz de manejar solo señales dispersas es mucho más limitado que la FFT. Pero “la dispersión está en todas partes”, señala el coinventor Katabi, profesor de ingeniería eléctrica e informática. “Está en la naturaleza, en las señales de vídeo, en las señales de audio”, afirma Katabi.

Una transformada más rápida implica que se necesita menos potencia computacional para procesar una cantidad dada de información, una bendición para los aparatos multimedia que miden el gasto energético al milímetro, como los teléfonos inteligentes. O, con la misma potencia computacional, los ingenieros pueden contemplar la posibilidad de hacer cosas que debido a las necesidades computacionales de la FFT no eran prácticas. Por ejemplo, las conexiones troncales de Internet y los routers actuales solo son capaces de leer o procesar una ínfima parte del río de datos que se pasan entre ellos. La SFT podría permitir a los investigadores estudiar el flujo de este tráfico con mucho más detalle mientras los bits pasan a una velocidad de miles de millones por segundo.

 
Fuente: technologyreview.es