Transformada rápida de fourier

Transformada rápida de Fourier (TRF)
Jean Baptiste Joseph, Baron de Fourier para el año de 1822 publicó un magnifico estudio concerniente al flujo calorífico en el cual desarrolló las series de Fourier, desde ese momento las series de Fourier fueron aplicadas a una gran variedad de ramas de la ciencia, la física, la teoría de los números, la combinatoria, el procesamiento de señales,la teoría de la probabilidad, la estadística, la óptica, la propagación de ondas  entre otras.
Las series de Fourier básicas se aplican a las señales periódicas, es decir, señales que son repetitivas y la transformada de Fourier o integral de Fourier a las señales que son aperiódicas, es decir, que no son repetitivas, ambas tienen un papel de suma importancia en el análisis de señales.
Para el caso dela transformada de Fourier discreta nos permite hacer una aproximación de coeficientes de Fourier, sumas parciales de la serie de Fourier y transformada de Fourier, sin embargo resulta muy laborioso realizar los cálculos ya que para llevar a cabo una transformada de Fourier se es necesario de una gran numero de cálculos, no obstante entra un procedimiento matemático llamado Transformada Rápidade Fourier (TRF).
Este procedimiento fue presentado por James W. Cooley y John W. Tukey en 1965 en un artículo titulado "Un algoritmo de las series complejas de Fourier para máquinas computadoras", reduce de forma impresionante el número de multiplicaciones requeridas para el cálculo, la TRF representó todo un avance en el desarrollo del procesamiento digital de señales.
En la actualidad estealgoritmo es una herramienta muy poderosa para cierto software ya que su principal sistema de análisis de datos esta basado en la TRF por ejemplo Matlab.
Veamos el gran avance que se realizó con este procedimiento con un ejemplo “se puede demostrar que, si N es una potencia entera de 2, entonces f(k/L) dada por la ecuación 3.24, se puede calcular con no más de 4N log2N operaciones aritméticas.Si se calcula son simplemente todas las sumas y productos que intervienen en el cálculo de f(k/L), se deben realizar N-1 sumas y N+1 multiplicaciones, cada una multiplicada N veces para obtener las aproximaciones en N puntos. Esto es un total de
N(N-1)+ N(N-1)=2N2
Operaciones. Suponga, para ser específicos N=2 20= 1 048 576. Ahora 2N 2=2.1990(10 12). Si la computadora que seutiliza realiza un millón de operaciones por segundo, este cálculo requeriría alrededor de 2 199 023 segundos, o casi 25.45 días de tiempo de computadora.
Puesto que en un proyecto dado podría requerir de la transformada de Fourier de muchas funciones, esto es intolerable en términos de tiempo y dinero.
En contraste si N=2n entonces
4N log2N=2n+2 log22n=n2n+2
Con n=20 resultan 83 886 080operaciones. A un millones de operaciones por segundo esto, tomará un poco menos de 84 segundos, una mejora muy sustancial sobre los 25.45 días.” [1]
Como se es patente resulta bastante tedioso aplicar directamente la transformada discreta de Fourier y ni que hablar del verdadero costo monetario que produciría aplicarla directamente, es así que la TRF pasa a colocarse en un punto de partidaextremadamente crucial, porque como ya se analizó resulta viable económicamente como en cuestión de tiempo aplicar la TRF.
Como se sabe la transformada de Fourier de una función no sólo permite hacer una descomposición espectral de una onda, sino que además con el espectro que se genera al realizar el análisis de Fourier se logra reconstruir la función original, esta reconstrucción se lleva acabomediante la transformada inversa. Dado que la transformada no solo contiene información sobre la intensidad de determinada frecuencia, sino también sobre su fase, la información de esta se puede representar como un vector bidimensional o en su defecto como un número complejo, frecuentemente sólo se representa el módulo al cuadrado de este número en las gráficas, este se conoce como densidad...