NeoFronteras

Nueva transformada rápida de Fourier

Área: Matemáticas — lunes, 23 de enero de 2012

Consiguen mejorar aún más la transformada rápida de Fouier. La nueva versión se mucho más rápida.

Foto

No somos conscientes del gran impacto que tiene las Matemáticas en la vida cotidiana. Son odiadas por muchos e ignoradas por otros y, sin embargo, conforman el mundo moderno. Además de ser usadas por las demás ciencias se emplean directamente en muchos casos.
Un resultado de un abogado francés del siglo XVII (el pequeño teorema de Fermat) es el que ahora nos permite conectarnos de manera segura con nuestro banco. Un concepto como el de autovector usando en Álgebra es el que, en el corazón de Google, nos permite encontrar lo que buscamos en Internet. Esto por citar sólo dos ejemplos.
Una rama matemática importante es el Análisis de Fourier, que permite, entre otras cosas, representar una señal irregular como una combinación de sus frecuencias puras, como pueda ser la fluctuación en el voltaje de la corriente que circula por un cable que conecta su reproductor de MP3 si sus auriculares. El análisis de Fourier se utiliza mucho en el procesamiento de señales o para la compresión de ficheros de imagen o sonido.
Permite además transformar problemas diferenciales en problemas algebraicos que se puedan resolver. Un ejemplo típico es la búsqueda de bolsas de petróleo mediante problemas inversos. Se envían ondas sonoras (mediante explosiones) al terreno y se trata de reconstruir la posible bolsa de petróleo que hay ahí a partir de la señal rebotada. Para este tipo de problema inverso hay que ensayar multitud de posibles configuraciones de la bolsa hasta dar con la correcta. Esto exige resolver el mismo tipo de problema muchas veces cambiando los parámetros que lo determinan. Sólo con el uso de la transformada rápida de Fourier se pudo abordar ese problema. Un problema computacional que no es abordable en un momento sólo se puede abordar si se encuentran algoritmos nuevos más rápidos, no con computadoras más rápidos y potentes. Sin la transformada rápida de Fourier muchos problemas computacionales aún no serían abordables.
La transforma de Fourier es una operación matemática que permite descomponer una función en sus frecuencias constituyentes. Se define como una integral definida y no necesariamente se calcula de manera sencilla si se usan métodos analíticos. El adjetivo de “rápida” que se añade se refiere a una clase especial de transformada de Fourier. La definición de transformada de Fourier habitual es muy difícil y costosa de aplicar computacionalmente hablando. La transformada rápida de Fourier o FFT es una versión numérica, una buena aproximación a la original, y que implementada en un programa se calcula bastante rápido.
Desde que se descubrió la transformada rápida de Fourier en los años sesenta los expertos se han preguntado si habría otras versiones aún más rápidas. Ahora un grupo de investigadores del MIT presentan un nuevo algoritmo que permite hacer que la transformada de Fourier sea más rápida. En algunos casos puede llegar a ser 10 veces más rápida que la antigua versión. El nuevo algoritmo ha sido presentado en el Congreso de Algoritmos Discretos en Kioto (Japón) la semana pasada.
El nuevo algoritmo permitiría un tratamiento de imágenes más rápido o enviar un video desde un teléfono celular a otro sin consumir mucho ancho de banda o batería.
Una señal digital es un muestreado discreto de una señal analógica. La FFT toma una señal digital que contiene un determinado número de muestras y las expresa en función del peso ponderado de su equivalente en número de frecuencias. La ponderación tiene en cuenta que algunas frecuencias son más importantes que otras y las que tienen poco peso pueden ser incluso despreciadas. Por esta razón la FFT es importante en la comprensión. Un bloque 8 por 8 píxeles contiene 64 píxeles en total y puede ser determinado directamente por 64 frecuencias distintas (cada píxel de un determinado valor aparece una sola vez). Pero los estudios experimentales muestran que 57 de esas frecuencias pueden ser descartadas con una pérdida mínima de calidad de imagen.
El nuevo algoritmo determina los pesos de las frecuencias más pesadas de la señal. A esto se le puede denominar “dispersar”. Cuando más rápidamente se determinen estas frecuencias, más rápido será el algoritmo y esto dependerá de lo susceptible que sea la señal a ser “dispersada”. Si la señal es lo suficientemente “dispersa” el algoritmo puede muestrearla aleatoriamente en lugar de leerla completamente.
Pero en la Naturaleza la mayoría de las señales son dispersas. Como analogía podemos tomar una pieza musical de cámara realizadas por instrumentos musicales. En ese caso, una señal podría consistir en unos pocos instrumentos musicales de los que sólo uno toca una nota cada vez. Este tipo de señal se podría “dispersar” fácilmente por este método, sería una señal “dispersa”. Pero, por otro lado, una grabación que registrara todos los posibles instrumentos tocando todas las notas a la vez no sería una señal que se pudiera “dispersar”, pero ese tipo de señales no son interesantes.
El nuevo algoritmo descansa sobre dos ideas. La primera es dividir la señal en secciones más delgadas de ancho de banda, justo a un tamaño en el que la sección considerada generalmente contiene sólo una frecuencia con gran peso. Esto permite determinar la importancia de la frecuencia dentro de cada conjunto. Para conseguir identificar la importancia de la frecuencia dentro de cada conjunto usan un filtro que es una combinación de dos ya existentes.
Además, estos investigadores aplican una segunda idea: usar una técnica que normalmente se emplea para mejorar las comunicaciones inalámbricas. La técnica se basa en que las frecuencias más importantes modulan otras señales en el conjunto. Muestreando rápidamente el conjunto a diferentes momentos se revelan qué frecuencias dominan la señal.
En señales dispersas este nuevo algoritmo es mucho más rápido que al anterior. Estos investigadores trabajan ahora en cómo incorporar el nuevo algoritmo a las técnicas de compresión de video y audio usados en la actualidad.
Así que si el smarphone que le hagan comprar en un futuro tiene unas prestaciones mucho mejores que el actual, estas se deberán en gran parte a este nuevo algoritmo.

Copyleft: atribuir con enlace a http://neofronteras.com/?p=3724

Fuentes y referencias:
Nota de prensa.
Ilustración: csee.umbc.edu

Salvo que se exprese lo contrario esta obra está bajo una licencia Creative Commons.
Compartir »

4 Comentarios

  1. lluís:

    Y esa » eliminación de frecuencias»,Dado que las frecuencias que tienen poco peso(supongo que por «frecuencia» se puede entender «energía») pueden ser despreciadas, parece que, si he entendido bien la analogía de la pieza musical de cámara,la pérdida de calidad de imágen (o sonido)no debería ser lo mínima que dice este estudio.De todos modos quizá no he entendido muy bien todo esto, para empezar me parece que no comprendo demasiado bien el concepto de «frecuencias más importantes que otras».

  2. Patricio López:

    lluís:

    Siempre que pasas del mundo analógico al digital existe una pérdida de información asociada a que es imposible realizar un muestreo con frecuencia infinita, ni con infinitos niveles de bits (esto último es lo conocido como ruido de cuantización).
    Pero, dependiendo de que quieres hacer con la señal, puedes sacrificar una gran cantidad de las frecuencias sin que se note al reconstituir la señal original. Por ejemplo, en los algoritmos tipo JPEG, que comprimen imagenes, se basan en que en general las fotos tienden a tener cambios de color suaves, por lo que puedes sacrificar las frecuencias altas con una pérdida de calidad despreciable (en un cuadro cubista, con muchos y violentos cambios de color, esta pérdida tiende a notarse más).
    En el caso del audio, se parte de la base que puedes sacrificar todas las frecuencias sobre los 20 Khz, pues estas no son audibles para el oído humano. Dado que el muestreo es el doble de la frecuencia máxima a almacenar, por eso el CD se muestrea a 44Khz. Si hilas más fino, el oído tiene una mejor capacidad de respuesta en las frecuencias agudas de su rango que en las graves(por eso en un coro siempre se escuchan más las sopranos que los tenores o los bajos, o bien puedes decir que se escucha mejor la voz de una mujer que un hombre), por lo que puedes sacrificar parte de estas últimas con poca pérdida de calidad. Esto permite que algoritmos como el MP3 puedan reducir el tamaño de los archivo hasta en un 80% del original con poca pérdida de calidad. Pero, siempre existen los puristas que sí notan dicha diferencia. Para ellos la alternativa es el disco de vinilo con amplificadores analógicos basados en MOSFET de potencia (o tubos de vacío para los fanáticos extremos). Para el resto de los mortales, la compresión por eliminación de frecuencias que se basa en la FFT es un gran avance.

  3. lluís:

    Entendido.Muchas gracias, Patricio.

  4. cosme:

    Muy interesante.

RSS feed for comments on this post.

Lo sentimos, esta noticia está ya cerrada a comentarios.