Transformada rápida de Fourier

Transformada rápida de Fourier
Para otros usos de este término, véase Transformación (desambiguación).

FFT es la abreviatura usual (del inglés Fast Fourier Transform) de un eficiente algoritmo que permite calcular la transformada de Fourier discreta (DFT) y su inversa. La FFT es de gran importancia en una amplia variedad de aplicaciones, desde el tratamiento digital de señales y filtrado digital en general a la resolución de ecuaciones diferenciales parciales o los algoritmos de multiplicación rápida de grandes enteros. El algoritmo pone algunas limitaciones en la señal y en el espectro resultante. Por ejemplo: la señal de la que se tomaron muestras y que se va a transformar debe consistir de un número de muestras igual a una potencia de dos. La mayoría de los analizadores TRF permiten la transformación de 512, 1024, 2048 o 4096 muestras. El rango de frecuencias cubierto por el análisis TRF depende de la cantidad de muestras recogidas y de la proporción de muestreo.

Uno de los algoritmos aritméticos más ampliamente utilizados es la transformada rápida de Fourier, un medio eficaz de ejecutar un cálculo matemático básico y de frecuente empleo. La transformada rápida de Fourier es de importancia fundamental en el análisis matemático y ha sido objeto de numerosos estudios. La aparición de un algoritmo eficaz para esta operación fue una piedra angular en la historia de la informática.

Las aplicaciones de la transformada rápida de Fourier son múltiples. Es la base de muchas operaciones fundamentales del procesamiento de señales, donde tiene amplia utilización. Además, proporciona un medio oportuno para mejorar el rendimiento de los algoritmos para un conjunto de problemas aritméticos comunes.


Contenido

Definición

Sean x0, ...., xn-1 números complejos. La transformada discreta de Fourier (DFT, por sus siglas en inglés) se define como

 f_j =  \sum_{k=0}^{n-1} x_k e^{-{2\pi i \over n} jk }
\qquad
j = 0,\dots,n-1.

La evaluación directa de esa fórmula requiere O(n²) operaciones aritméticas. Mediante un algoritmo FFT se puede obtener el mismo resultado con sólo O(n log n) operaciones. En general, dichos algoritmos dependen de la factorización de n pero, al contrario de lo que frecuentemente se cree, existen FFTs para cualquier n, incluso con n primo.

La idea que permite esta optimización es la descomposición de la transformada a tratar en otras más simples y éstas a su vez hasta llegar a transformadas de 2 elementos donde k puede tomar los valores 0 y 1. Una vez resueltas las transformadas más simples hay que agruparlas en otras de nivel superior que deben resolverse de nuevo y así sucesivamente hasta llegar al nivel más alto. Al final de este proceso, los resultados obtenidos deben reordenarse.

Dado que la transformada discreta de Fourier inversa es análoga a la transformada discreta de Fourier, con distinto signo en el exponente y un factor 1/n, cualquier algoritmo FFT puede ser fácilmente adaptado para el cálculo de la transformada inversa. Por lo general, tenemos que:

x[n] = IDFT\{X[k]\}=\frac{1}{N}\left(DFT\left\{X^*[k]\right\}\right)^*

Un algoritmo que es mucho más eficiente en cuanto al tiempo de cómputo para grandes arreglos de entrada cuya longitud es una potencia entera de dos, recibe el nombre de Transformada de Fourier Rápida (TFR), y dicho algoritmo fue popularizado por Cooley y Tukey en 1965. Se puede ilustrar mediante el siguiente ejemplo, calculando la TFR de un conjunto de cuatro muestras de datos utilizando el algoritmo. Defina el conjunto de muestras de una señal como la señal X₀[n] en TD de forma que los datos de entrada para el algoritmo sea {X₀[0],X₀[1],X₀[2],X₀[3]}. La fórmula de la TFD es la siguiente:

X[k]=\sum_{n=0}^{N_{F-1} }X[n]e^{-j2\pi(kn/N_F)}

Se recomienda usar la notación:

                                        W=e-j(2π/NF)

Para este caso de 4 puntos de datos, es posible escribir la TFR en forma de matriz como:

Imaaaag3.png

Efectuar la multiplicación usual de matrices directa requeriría N² multiplicaciones complejas y N(N-1) adiciones complejas. Por lo tanto puedes escribirse de la siguiente manera:

Imgagen454.png

Debido a que Wn=Wn+mNF , donde m es un entero, es posible factorizar la matriz en el producto de dos matrices;

Immaatrizg6.png

Los elementos “1” y “2” han cambiado de lugar en el vector que se encuentra del lado izquierdo. Cuando se multipliquen las matrices, los renglones 1 y 2, también se intercambiarán. Después se calcula el número de multiplicaciones y adiciones que se requieren. Primero se identifica el resultado de multiplicar la segunda matriz cuadrada por el conjunto de datos de entrada como:

Imagenmatrizg7.png

El primer elemento es:

X1[0]=X0[0]+W0X0[2]

Como una multiplicación para llegar a una conclusión general.De manera similar X1[1] requiere una multiplicación y una adición. Sin embargo,X1[2] requiere sólo una adición debido a que Este cálculo requiere una multiplicación y una adición.Aunque W0 es uno, se dejará esto W0=-W2 y el producto ya se ha obtenido en el cálculo del primer elemento y puede, en consecuencia, sólo almacenarse hasta que se necesite y luego restarse en vez de sumarse. De manera similar,X1[3] sólo requiere una adición más. Hasta ahora se tienen dos multiplicaciones y cuatro sumas. Apelando a condiciones de simetrías similares en la segunda multiplicación de matrices se encuentra que se requieren dos multiplicaciones y cuatro sumas más. Así, en total, se necesitan cuatro multiplicaciones y ocho adiciones. Puesto que, computacionalmente, las multiplicaciones requieren por lo general mucho más tiempo de cómputo que las adiciones, el algoritmo de TFR para cuatro puntos es alrededor de cuatro veces más rápido que la TDF directa.

GraficaTFR.png

Algoritmo de diezmado en el tiempo

Es el algoritmo más famoso para el cálculo de una FFT, diseñado por J.W. Cooley y John Tukey en 1965. Tomando como entrada una señal discreta x[n] con N muestras, se basa en dividir la señal de entrada en otras dos señales de N/2 muestras (por un lado los coeficientes pares y por otro los impares), y se envían cada una de estas subseñales a una FFT de tamaño N/2 puntos. Cada uno de los coeficientes de salida de la FFT de las muestras impares se multiplica por W_N^K=e^{-i\frac{2\pi }{N}k}, donde k es la posición del vector salida, y se suma a las muestras pares. A su vez, las FFT de N/2 puntos se pueden resolver de esta misma manera, realizando esta operación de manera recursiva hasta obtener una FFT de una señal de tamaño 2, cuyo resultado es:

X[0] = x[0] + x[1]
X[1] = x[0] − x[1]


Aplicaciones

  • Tratamiento de imagen (JPEG) y audio (MP3)
  • Reducción de ruido en señales, como el ruido blanco
  • Análisis en frecuencia de cualquier señal discreta
  • Análisis de materiales y estadística
  • Síntesis, mediante la transformada inversa IFFT

Enlaces externos


Wikimedia foundation. 2010.

Игры ⚽ Поможем сделать НИР

Mira otros diccionarios:

  • Transformada de Fourier discreta — Para otros usos de este término, véase Transformación (desambiguación). En matemáticas, la transformada discreta de Fourier o DFT (del inglés, discrete Fourier transform) es un tipo de transformada discreta utilizada en el análisis de Fourier.… …   Wikipedia Español

  • Transformación — El término transformación hace referencia a la acción o procedimiento mediante el cual algo se modifica, altera o cambia de forma manteniendo su identidad. Adjetivo: transformada, transformado En ciencias sociales Transformación social (redirige… …   Wikipedia Español

  • Transformación (desambiguación) — Saltar a navegación, búsqueda El término transformación, algunas veces expresado como transformada, puede hacer referencia a los siguientes elementos: En matemáticas Transformada de Fourier, Transformada de Fourier discreta y Transformada rápida… …   Wikipedia Español

  • GNU Scientific Library — Desarrollador proyecto GNU gnu.org/software/gsl/ Información general Última versión estable 1.14 12 de marzo 2010 …   Wikipedia Español

  • Filtro digital — Saltar a navegación, búsqueda Un filtro digital es un sistema que, dependiendo de las variaciones de las señales de entrada en el tiempo y amplitud, se realiza un procesamiento matemático sobre dicha señal; generalmente mediante el uso de la… …   Wikipedia Español

  • Huella digital acústica — “Acoustic fingerprints” o huellas digitales acústicas, son identificadores para archivos de audio basados en el contenido del archivo. Con ellas podemos identificar un patrón o “firma” de un archivo de audio, para que este pueda ser reconocido… …   Wikipedia Español

  • Volker Strassen — dando la conferencia del premio Knuth en SODA 2009. Volker Strassen es un matemático alemán, profesor emérito del departamento de matemáticas y estadística de la Universidad de Constanza.[1] …   Wikipedia Español

  • COFDM — Saltar a navegación, búsqueda COFDM (Coded Orthogonal Frequency Division Multiplexing) es el sistema de modulación usado en el DAB y en los sistemas de televisión digital. A diferencia de otros sistemas que modulan en una sola frecuencia… …   Wikipedia Español

  • James Cooley — Nombre James Cooley Nacimiento 18 de septiem …   Wikipedia Español

  • Analizador de espectro — Saltar a navegación, búsqueda Un analizador de espectro es un equipo de medición electrónica que permite visualizar en una pantalla las componentes espectrales en un espectro de frecuencias de las señales presentes en la entrada, pudiendo ser… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”