TRANSFORMADA RAPIDA DE FOURIER (FAST FOURIER TRANSFORM)

 

Recordemos que la Transformada Discreta de Fourier (DFT del inglés Discrete Fourier Transform) es el equivalente discreto de la Transformada de Fourier donde se ha transformado la variable continua ‘t’ por la variable discreta ‘nTs’ siendo ‘Ts’ el periodo de muestreo. Sin embargo, Hay dos situaciones a considerar en cuanto al uso de la Transformada Discreta de Fourier: Sólo sirve para señales potencia del tipo periódico y la mayoría de las señales a estudiar no son periódicas.

 No obstante, la DFT es una operación ampliamente empleada en tratamiento de señales y en campos afines para analizar las frecuencias presentes en una señal muestreada, resolver  ecuaciones diferenciales parciales y realizar otras operaciones, como: convoluciones y correlaciones y  puede calcularse de modo muy eficiente mediante el algoritmo FFT. Por lo que, ha causado un gran impacto en la comunidad científica el hecho de que se haya desarrollado en MIT, un algoritmo capaz de acelerar sustancialmente el cálculo de la FFT como se anunció el pasado enero durante el Simposio ACM-SIAM en algoritmos discretos.

Cito textualmente a Gilbert Strang, autor del libro de texto de álgebra lineal y sus aplicaciones, quien  se refirió a la transformada rápida de Fourier o FFT, como "el algoritmo numérico más importante en nuestra vida." No es extraño, ya que la FFT se utiliza para procesar los datos en el mundo digital altamente interconectado de hoy.

Algunas aplicaciones que definen a la FFT son: compresión de imagen y audio, filtrado digital, reducción de ruido en señales: como el ruido blanco, resolución de ecuaciones diferenciales parciales, análisis en frecuencia de cualquier señal discreta, ya sea periódicas o aperiódicas.

análisis de materiales y estadística, síntesis, mediante la transformada inversa IFFT, los ya mencionados algoritmos rápidos de convolución, correlación y detección de movimiento, por solo mencionar algunas.

 Aunque la mayoría de los ingenieros asocian la FFT con el procedimiento James Cooley de IBM y John Tukey de Princeton descrito en 1965, los especialistas reconocen que tiene raíces mucho más profundas. Aunque nunca lo publicó, el famoso matemático alemán Carl Friedrich Gauss había elaborado el enfoque básico, probablemente ya en 1805, precediendo, muy poco, incluso el propio trabajo de Fourier sobre el tema, quien quizás no pudo establecer el alcance de su trabajo en aquel momento.

La razón fundamental  de estos avances, es que los nuevos métodos están diseñados para correr rápido sólo para algunas señales-ondas que se denominan "escasas",  es decir, contienen un número relativamente pequeño de componentes de frecuencia de tamaño significativo. Estas señales, se encuentran abundantemente en la naturaleza, ya sean imágenes astronómicas o gorjeos de aves, tiende a concentrarse en las frecuencias más bajas. La FFT tradicional toma la misma cantidad de tiempo de cálculo para cualquier señal.

El nuevo algoritmo de MIT, que se describe en el “paper”  que pronto será publicado, es mejor que la tradicional FFT siempre y cuando el número de componentes de frecuencia presente un porcentaje de un dígito del número de muestras que toma de la señal. Funciona para cualquier señal, pero funciona más rápido que el FFT solamente bajo esas condiciones.

El mejor tiempo que tarda en ejecutar el mejor algoritmo FFT aumenta en proporción a la cuarta potencia del logaritmo del número de muestras, mientras que el más reciente algoritmo de MIT tiene un tiempo de ejecución que es proporcional a sólo la primera potencia de ese número. Lo cual constituye un gran avance.

¿Que es Twiddle Factor?

TWIDDLE FACTOR

Para comprender la importancia del Twiddle Factor y su importancia en el cálculo de la FFT (es decir, Fast Fourier Transform, en inglés), es vital recordar que es la FFT, donde radica su importancia, cuales son las características del algoritmo para su evaluación, entre otros detalles que se mencionarán a continuación:

FFT (Fast Fourier Transform) es la abreviatura usual 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 en derivadas parciales o los algoritmos de multiplicación rápida de grandes enteros. 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.

Brevemente se revisará en qué consiste el algoritmo para determinar la DFT (del Inglés Discrete Fourier Transform). Sean x₀, ...., x_n-1 números complejos. La transformada discreta de Fourier (DFT) se define como:

La evaluación directa de esa fórmula requiere O(n²) operaciones aritméticas. Mediante un algoritmo la FFT se puede obtener el mismo resultado con sólo O(n log n) operaciones reduciendo su tiempo de ejecución. 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 (Ver Diagrama de Mariposa). 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 (es lo que hace el algoritmo de Cooley- Tukey).

Históricamente, el desarrollo de la FFT, se remonta a la guerra fría, periodo durante el cual EEUU buscaba obtener información acerca de las pruebas nucleares  realizadas en la  extinta Unión Soviética, y de los cuales uno de los desarrollos obtenidos fue Twiddle Factor, lo cual permitió optimizar el cálculo de la FFT, al combinarlo con el algoritmo de Cooley-Tukey. Al parecer, a Tukey, se le ocurrió la idea durante una reunión de un comité asesor presidencial de EE.UU. discutiendo  maneras de detectar ensayos de armas nucleares en la Unión Soviética. Otro de los participantes en esa reunión, Richard Garwin de IBM, reconoció el potencial del  método de Tukey y lo puso en contacto con Cooley, quien implementó un método diferente (y menos-clasificado): análisis de los datos cristalográficos 3D (algo así como: FFT Multidimensional). Cooley y Tukey posteriormente publicaron su documento conjunto, y fue aceptado rápidamente.
El algoritmo para el cálculo de la FFT no es reciente, data de 1805 y  fue inventado por Carl Friedrich Gauss, quien lo usó para interpolar la trayectoria de los asteroides Pallas y Juno, sin embargo su trabajo no fue reconocido hasta después de su muerte. La FFT se hizo popular después de que J. Cooley y J. Tukey publicaran su trabajo en el cual reinventaron el algoritmo describiendo como desarrollarlo convenientemente en una computadora. El hecho de que Gauss haya descrito el mismo algoritmo (aunque sin analizar su costo asintótico) no se realizó sino hasta varios años después en 1965.

Ampliando un poco, El algoritmo de Cooley-Tukey, debe su nombre a: J.W. Cooley de IBM y John Tukey de Princenton, y es el algoritmo más común para calcular la transformada rápida de Fourier (FFT). El cual, re-expresa la transformada discreta de Fourier (DFT) de un tamaño arbitrario compuesto N = n₁n₂ en términos de DFT más pequeñas de tamaños N₁ y N₂, de forma alternativa, con el fin de reducir el tiempo de cálculo a O (N log N). Debido a la importancia del algoritmo, el cual es considerado la piedra angular de la informática;  las variantes específicas y formas de ejecución lo ha dado a conocer por el nombre de  sus creadores.
Debido a que el algoritmo de Cooley-Tukey fragmenta la DFT en DFT más pequeñas, se puede combinar arbitrariamente con cualquier otro algoritmo para la DFT. Por ejemplo, el algoritmo de Rader o Bluestein que se puede utilizar para manejar grandes factores primos que no pueden ser descompuestos por el algoritmo: Cooley-Tukey.

Ahora si responderemos a la pregunta: ¿Qué es el Twiddle Factor? El Twiddle Factor, es un coeficiente trigonométrico que se multiplica con los datos durante la FFT (Fast Fourier Transform) y que fue estandarizado por Gentleman &  Sandle en 1966.

El Twiddle Factor, puede entenderse como un vector que gira en forma circular a través del plano complejo S y el cual tiene un valor para cada una de las muestras usadas para calcular la transformada de Fourier, los cuales están separados por un ángulo definido  también por un numero de muestras.

Gráficamente,  puede describirse por la siguiente imagen:

 

Figura 1. El Twiddle Factor, W, describe un "vector giratorio", que gira en incrementos de acuerdo con el número de muestras, N.

Figura 2. El mismo conjunto de valores de W, se repite una y otra vez para diferentes valores de n.  También los que están en 180° aparte de los valores negativos.  Estos valores son usados en el cálculo de la DFT y hacen posible como ya se dijo la FFT.

Como se muestra en la figura anterior, el Twiddle Factor es redundante  en los valores, como el vector rota alrededor. Por ejemplo W para N = 2, es la misma para n = 0, 2, 4, 6, etc, y W para N = 8 es la misma para n = 3, 11, 19, 27, etc.
Además, es simétrico por  el hecho de que los valores que están 180 grados fuera de fase son el negativo de uno al otro. Así, por ejemplo, W para N = 4 muestras, siendo n = 0, 4,8, etc., son el negativo de n = 2, 6,10, etc.
El diagrama de la mariposa se ​​aprovecha de esta redundancia y la simetría, que es parte de lo que hace la FFT posible.
El diagrama de la mariposa se ​​basa en la expresión Danielson-Lanczos y el factor twiddle para crear un algoritmo eficiente. El diagrama de la mariposa, corresponde a una representación gráfica del algoritmo FFT.
A continuación, se muestra el diagrama de una mariposa simple. Es una  unidad básica, que consiste en sólo dos entradas y dos salidas.

 Figura 3. Este esquema es el bloque fundamental en la construcción del digrama de mariposa. Este, tiene dos valores de entrada o N=2 muestras, x (0) y x (1), y resultados en dos valores de salida F (0) y F (1).
A continuación se muestra paso a paso como se construye un diagrama de mariposa de 4-entradas.

Luego se hace la conexión entre ambas.

A continuación se explica eso del “binario inverso” mencionado en la figura anterior:

Para 4 entradas:

Contando desde 0 a 3 en binario 00, 01, 10, 11. Ahora el inverso los bits de cada número obtenida: 00, 10, 01,11. En decimal esto es 0, 2, 1, y 3.

El algoritmo de Cooley- Tukey ilustrado por el diagrama de Mariposa. Se puede ilustrar mediante el siguiente ejemplo, calculando la TFR de un conjunto de cuatro muestras de datos utilizando el algoritmo. Definiendo 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:

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 sub-señ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, 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:

A estos números marcados como W se conocen como “Twiddle Factors” y como se mencionó, sirven para facilitar el cálculo de la FFT cuyas utilidades disfrutamos hoy, como son:

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

BIBLIOGRAFIA:

http://electronictoolsbga.blogspot.com/p/blog-page_23.html

http://www.dsprelated.com/showarticle/107.php

http://www.alwayslearn.com/dft%20and%20fft%20tutorial/DFTandFFT_BasicIdea.html

http://es.wikipedia.org/wiki/Transformada_r%C3%A1pida_de_Fourier

Wikipedia, the free encyclopedia

CONDICIONES DE DIRICHLET

CONDICIONES DE DIRICHLET¹

Se denomina así, al conjunto de condiciones que debe cumplir una función f(x) para que pueda representarse como una serie de Fourier. Para que una función  f(x) sea susceptible de ser expandida como una serie de Fourier, esta debe cumplir con las condiciones presentadas en el siguiente esquema:

• Debe ser periódica.

• Univaluada y continua a trozos (continua menos en un numero finito de puntos) con un numero finito de máximos y mínimos.

• La integral 

debe ser convergente. Donde [-T/2, T/2] indica el intervalo de definición de una función con periodo T.

Para que las series de Fourier existan, los coeficientes de Fourier deben ser finitos, esta condición garantiza su existencia. Esencialmente dice que el integral del valor absoluto de la señal debe ser finito. Los límites de integración son diferentes para el caso de las series de Fourier y de los del caso de las trasformada de Fourier. Este es el resultado que proviene directamente de las diferencias en las definiciones de las dos.

Las series de Fourier existen (los coeficientes son finitas) si

Condición 1 Las Condiciones Débiles para las Series de Fourier

Esto se puede probar usando la condición inicial de los coeficientes iniciales de las series de Fourier que pueden ser finitas

⃒

Dado que: 

entonces:

Condición 2   La transformada de Fourier existe si las condiciones débiles para la trasformada de Fourier 

Esto se puede derivar de la misma manera en la que se derivó las condiciones débiles de Dirichlet para las series de Fourier, se empieza con la definición y se demuestra que la transformada de Fourier debe de ser menor que infinito en todas partes.

LAS CONDICIONES FUERTES DE DIRICHLET

La transformada de Fourier existe si la señal tiene un número finito de discontinuidades y un número finito de máximos y mínimos. Para que las series de Fourier existan las siguientes dos condiciones se deben de satisfacer (junto con la condición débil de Dirichlet):

En un periodo,

§  f(t) tiene solo un número finito de mínimos y máximos. En un periodo,

§  f(t) tiene un numero finito de discontinuidades y cada una es finita.

Esto es lo que se conoce como las condiciones fuertes de Dirichlet. En teoría se puede pensar en señales que violan estas condiciones por ejemplo sin (log t), Sin embargo, no es posible crear esta señal en un laboratorio. Por eso, cualquier señal en el mundo real tendrá una representación de Fourier.

¹ Johann Peter Gustav Lejeune Dirichlet 1805 – 1859 Matemático alemán con importantes contribuciones en teorías de números algebreicas, series y aproximaciones de funciones diferenciales parciales.

Señales: Descripción

Definición de Señal:

 Las señales están ligadas a las comunicaciones y su procesamiento es de vital importancia en la era de la información. Así pues, no son de gran interés si no es posible transmitirlas y recibirlas.

Se considera una señal, todo aquello que contiene información acerca de la naturaleza o el comportamiento de algún fenómeno físico (electromagnético, acústico, mecánico, biológico, etcétera). Una señal, se representa matemáticamente por medio de una función que depende de una o más variables independientes.

 Tipos de señales

 Se tratarán cuatro tipos de señales:

• Analógicas, x(t): Amplitud y tiempo continuos. Las cuales se mencionarán más adelante.
•  Muestreadas, x_s[n]: tiempo discreto, amplitud continua.
•  Cuantizadas x_Q(t): tiempo continuo, amplitud discreta.
•  Digital, x_Q[n]: tiempo y amplitud discreto.

 Señales Discretas y Continuas:

Señales discretas	Señales continuas
Las variables independientes sólo pueden tomar conjuntos restringidos de valores.	Las variables independientes son continuas (pueden tomar cualquier valor real).
Las funciones representativas sólo están definidas para los valores posibles de las variables.	Las funciones representativas están definidas para sucesiones continuas de las variables independientes.
f(n)=ksen(), n= 0,±1,±2, K= ,N=4	f(x)=ax+b a=-1, b=1

Una señal análoga, se representa por una función matemática continua; donde varía el período y la amplitud en función del tiempo. Generalmente la intensidad, la temperatura, la presión, la tensión y  la potencia son portadoras de este tipo de señal.

Las señales análogas se pueden percibir en todos los lugares, por ejemplo, la naturaleza posee un conjunto de estas señales como es la luz, la energía, el sonido, etc., estas son señales que varían constantemente.

Cuando los valores del voltaje o la tensión tienden a variar en forma de corriente alterna se produce una señal eléctrica analógica. En este caso, se incrementa durante medio ciclo el valor de la señal con signo eléctrico positivo; y durante el siguiente medio ciclo, va disminuyendo con signo eléctrico negativo. Es desde este momento que, se produce un trazado en forma de onda senoidal, ya que este da a lugar a partir del cambio constante de polaridad de positivo a negativo. Las señales de cualquier comunicación electrónica o de cualquier ruido, puede presentar algunas complicaciones; por ejemplo, estas pueden ser modificadas a través del ruido de forma no deseada. Es por estas razonas que se recomienda que la señal antes de ser procesada se acondicione; de este modo no generará estas modificaciones imprevistas. Si se presenta este problema; se debe capturar las ondas de sonido analógicas con un micrófono, y luego se deben convertir en una señal de audio (pequeña variación analógica de tensión).

Ahora bien, a medida que cambia la frecuencia del sonido y el volumen va a ir variando la tensión de forma continua; en estos momentos se destina a la entrada de un amplificador lineal.

La tensión de entrada amplificada, o sea, la salida del amplificador se deberá de introducir en el altavoz; el cual convertirá la señal de audio ya amplificada en ondas sonoras; las cuales poseen un mayor y mejor sonido que el sonido que había capturado el micrófono. Son muchos los sistemas que eran analógicos y que hoy en día se han convertido en digitales; como son las grabaciones de video, las grabaciones de audio y las fotografías. También hay sistemas, que en la actualidad usan los dos tipos de métodos, o sea, el analógico y el digital; como es el reproductor de disco compacto.

El muestreo consiste en tomar valores de la señal cada cierto tiempo, es decir, no considerar todo el tiempo de forma continua sino solamente unas muestras equiespaciadas, con lo que el resultado es un conjunto finito de valores. Para hacernos a una idea, repasemos dos ejemplos reales de muestreos de señales que nos darán información de cómo funcionan diferentes sistemas conocidos por todos:

1. CD de audio: f_s = 44.100 Hz para garantizar que f_s ³ f_N donde f_N = 2f y se considera f = 20.000 Hz para abarcar todo el rango de frecuencias que el oído humano es capaz de percibir. Por lo tanto, estamos conservando todo lo que en teoría es audible y por esto hablamos de un sistema de alta calidad.

2. Canal telefónico: f_s = 8.000 Hz para garantizar que f_s ³ f_N donde f_N = 2f y se considera f = 3.400 Hz para abarcar el rango de frecuencias donde se encuentra la voz.

La cuantificación se refiere a asignar a la amplitud de estos instantes de tiempo escogidos (es decir, al valor que toma la señal en estos instantes) un valor concreto de entre un conjunto finito de posibles valores, que son los que vendrán determinados por el número de bits N considerados en este proceso. Dado que para N bits este conjunto es de 2^N valores, cuantos más bits, más posibles valores y por lo tanto mayor precisión (menor error) en esta etapa de cuantificación.

Entre las aplicaciones actuales de señales codificadas podemos mencionar específicamente las siguientes:

• Lectores y grabadores de DVD, (Digital Versátil Disc)
• Receptores y adaptadores de DTV y HDTV, (Digital TV, High Definition TV)
• Canales codificados en la televisión por Cable
• Grabadores digitales de video DV, (Digital Video)
• Procesadores para video-teléfono tipo ISDN, (Integrated Services Digital Network: Red Digital de Servicios Integrados)
• Procesadores de video en PC (Personal Computer) 

Bibliografia:

http://www.investigacionyciencia.es/blogs/tecnologia/20/posts/muestreando-seales-primera-parte-10461

http://www.investigacionyciencia.es/blogs/tecnologia/20/posts/muestreando-seales-segunda-parte-10776

http://www.webelectronica.com.ar/news27/nota10.htm

Dpto. Teoría de la Señal y Comunicaciones. Escuela Técnica Superior de Ing. Telecomunicación. UNIVERSIDAD DE VIGO

http://es.wikipedia.org/wiki/Muestreo_digital