Nueva transformada rápida de Fourier

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

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.

Read more

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.

Fuente  http://neofronteras.com/?p=3724

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

http://www.diac.upm.es/acceso_profesores/asignaturas/tdi/tdi/transformadas/pdf/fourier1.pdf

 

Básicamente la Transformada de Fourier se encarga de transformar una señal del dominio del tiempo, al dominio de la frecuencia, de donde se puede realizar su antitransformada y volver al dominio temporal.

 

En matemática, la transformada de Fourier es una aplicación que hace corresponder a una función f, con valores complejos y definida en la recta, con otra función g definida de la manera siguiente:

g(\xi ) = \frac{1}{\sqrt{2\pi}}\int_{-\infty}^{+\infty} f(x)e^{-i\xi\,x} dx

Donde f es \displaystyle{ L^{1}} , o sea f tiene que ser una función integrable en el sentido de la integral de Lebesgue. El factor, que acompaña la integral en definición facilita el enunciado de algunos de los teoremas referentes a la transformada de Fourier. Aunque esta forma de normalizar la transformada de Fourier es la más comúnmente adoptada, no es universal. En la práctica las variables x y ? suelen estar asociadas a dimensiones (como el espacio -metros-, frecuencia -segundos^-1-,…) y entonces es correcto utilizar la fórmula alternativa:

g(\xi ) = \sqrt{\frac{\beta}{2\pi}} \int_{-\infty}^{+\infty} f(x)e^{-i\beta\xi\,x} dx

de forma que la constante beta cancela la dimensiones asociadas a las variables obteniendo un exponente adimensional.

 
La transformada de Fourier así definida goza de una serie de propiedades de continuidad que garantizan que puede extenderse a espacios de funciones mayores e incluso a espacios de funciones generalizadas.

Además, tiene una multitud de aplicaciones en muchas áreas de la ciencia e ingeniería: la física, la teoría de los números, la combinatoria, el procesamiento de señales (electrónica), la teoría de la probabilidad, la estadística, la óptica, la propagación de ondas y otras áreas. En procesamiento de señales la transformada de Fourier suele considerarse como la decomposición de una señal en componentes de frecuencias diferentes, es decir, g corresponde al espectro de frecuencias de la señal f.

La rama de la matemática que estudia la transformada de Fourier y sus generalizaciones es denominada análisis armónico.

Son varias las notaciones que se utilizan para la transformada de Fourier de f. He aquí algunas de ellas:

\mathcal{F}[f], \hat f, F(f), \mathcal{F} \{ f \}.

 

 

La transformada de Fourier es básicamente el espectro de frecuencias de una función. Un buen ejemplo de eso es lo que hace el oído humano, ya que recibe una onda auditiva y la transforma en una descomposición en distintas frecuencias (que es lo que finalmente se escucha). El oído humano va percibiendo distintas frecuencias a medida que pasa el tiempo, sin embargo, la transformada de Fourier contiene todas las frecuencias contenidas en todos los tiempos en que existió la señal; es decir, en la transformada de Fourier se obtiene un sólo espectro de frecuencias para toda la función.

Definición formal

Sea f una función Lebesgue integrable:

f \in L^1(\mathbb{R}) o f \in L^1(\mathbb{C})

La transformada de Fourier de f es la función

\mathcal{F} \{ f \} \ \ : \xi \mapsto \hat{f}(\xi) := \int_{-\infty}^{\infty} f(x)\ e^{- 2\pi i \xi x}\,dx,

Esta integral tiene sentido, pues el integrando es una función integrable. Una estimativa simple demuestra que la transformada de Fourier F(f) es una función acotada. Además por medio del teorema de convergencia dominada puede demostrarse que F(f) es continua.

La transformada de Fourier inversa de una función integrable f está definida por:

\mathcal{F}^{-1} \{ \hat{f} \} = f(x) = \int_{-\infty}^{\infty} \hat{f}(\xi)\ e^{2 \pi i \xi x}\,d\xi,

Nótese que la única diferencia entre la transformada de Fourier y la transformada de Fourier inversa es el signo negativo en el exponente del integrando. El teorema de inversión de Fourier formulado abajo justifica el nombre de transformada de Fourier inversa dado a esta transformada. El signo negativo en el exponente del integrado indica la traspolación de complementos yuxtapuestos. Estos complementos pueden ser analizados a través de la aplicación de la Varianza para cada función.

 Propiedades básicas

La transformada de Fourier es una aplicación lineal:

\mathcal{F}\{ a\cdot f+b \cdot g \} =a \, \mathcal{F}\{ f \} + b \, \mathcal{F}\{ g \}.

Valen las siguientes propiedades para una función absolutamente integrable f:

  • Cambio de escala:
\mathcal{F} \{ f(at) \}(\xi) = \frac{1}{|a|} \cdot \mathcal{F} \{ f \} \bigg(\frac{\xi}{a}\bigg)
  • Traslación:
\mathcal{F} \{ f(t-a) \} (\xi)=e^{-i\xi a} \cdot \mathcal{F} \{ f \} (\xi)
  • Traslación en la variable transformada:
\mathcal{F}\{ f \} (\xi-a)= \mathcal{F} \{ e^{iat} f(t) \} (\xi)
  • Transformada de la derivada: Si f y su derivada son integrables,
\mathcal F \{ f' \} (\xi) = i\xi \cdot \mathcal{F} \{ f \}(\xi)
  • Derivada de la transformada: Si f y t ? f(t) son integrables, la transformada de Fourier F(f) es diferenciable
\mathcal{F}\{ f \}' (\xi) = \mathcal{F} \{ (-it) \cdot f(t) \}(\xi)

Estas identidades se demuestran por una mudanza de variables o integración por partes.

En lo que sigue, definimos la convolución de dos funciones f, g en la recta se define de la manera siguiente:

(f * g)(x) = \frac{1}{\sqrt{2 \pi}} \int_{-\infty}^{+\infty} f(y) \cdot g(x - y) \, dy.

Nuevamente la presencia del factor delante de la integral simplifica el enunciado de los resultados como el que sigue: Si f y g son funciones absolutamente integrables, la convolución también es integrable, y vale la igualdad:

\mathcal{F}\{ f*g \} = \mathcal{F} \{ f \} \cdot \mathcal{F} \{ g \}

También puede enunciarse un teorema análogo para la convolución en la variable transformada,

\mathcal{F} \{ f \cdot g \} =\mathcal{F}\{ f \}*\mathcal{F}\{ g \}.

pero este exige cierto cuidado con el dominio de definición de la transformada de Fourier.

 Bibliografia Wikipedia.org

Wednesday, January 25th, 2012, by Manuel and is filed under "Ciencia, Fisica, Matematicas, Science | , , , , ". You can leave a response here, or send a Trackback from your own site.

Let us talk about
Name and Mail are required
Join the discuss

« || »