Introducción

La DFT (Discrete Fourier Transform o Transformada Discreta de Fourier), tiene la característica de ser periódica, a pesar de que en algunos casos esta periodicidad no sea evidente, la transformada tiene un periodo igual a la longitud N de la señal usada para la transformación. Para el cálculo de dicha Transformada Discreta de Fourier existen algoritmos muy eficientes que permiten el cálculo de la misma con un número reducido de operaciones, esto ha permitido que la DFT constituya una herramienta básica no solo para el análisis frecuencial si no en numerosas aplicaciones.

Las ventajas que ofrece la DFT, es la existencia de algoritmos de cálculo que permiten realizar este análisis con un número mínimo de operaciones. Estos algoritmos se agrupan bajo la denominación de FFT (Fast Fourier Transform o Transformada Rápida), y optimizan los cálculos necesarios para la DFT, siempre y cuando las señales implicadas cumplan una serie de requisitos, uno de los más importantes es que el número de muestras sea una potencia de 2. Como cultura general la FFT fue publicada en 1964 por Cooley y Tukey, la FFT es un método muy eficiente de cálculo.

Ahora bien, al poder analizar la DFT y FFT en una dimensión consideraremos la Transformada discreta de Fourier de dos dimensiones que está definida como:

y la Transformada Inversa de Fourier de dos dimensiones esta dada por:

La transformada de Fourier bidimensional es una operación separable, quiere decir que se puede hacer como la Transformada de Fourier de una dimensión aplicada a cada una de las columnas y después aplicada a cada uno de los renglones. Puede ser primero los renglones y después a las columnas, obteniendo el mismo resultado. El mismo principio se aplica a la Transformada de Fourier Inversa Bidimensional.

Consideremos ahora que, con el análisis matemático mencionado de la Transformada de Fourier de Dos dimensiones Directa e Inversa es necesario conocer las demás herramientas que lograran la implementación de un programa en C que pueda leer archivos con extensión .csv con el fin de obtener los datos y hacer el proceso matemático. Para ilustrar mejor, un archivo con extensión .csv es un documento de texto sin formato que contiene una lista de datos, estos archivos se utilizan a menudo para intercambiar datos entre diferentes aplicaciones. Un archivo \verb+.csv+ tiene una estructura bastante simple como se ha dicho es una lista de datos separados por comas.

En el desarrollo de este programa se hace uso del algoritmo de diezmado en el tiempo, se basa en descomponer x[n] en subsecuencias recursivamente, calcular las DFTs de cada subsecuencia y combinarlas para componer la DFT de subsecuencias mayores hasta llegar a la secuencia x[n] de N puntos.

Fig. 1. Algoritmo FFT de diezmado en el tiempo, descomposición inicial.

La figura 1 muestra como es el calculo de la DFT para una secuencia de N = 8 muestras. Con la simplificación de la figura 2.

Fig. 2. Algoritmo FFT de diezmado en el tiempo (N=8) simplificado.

Finalmente con la simplificación de la figura 2 se consigue reducir el número de operaciones finales por un factor de 2, ya que el factor de números complejos a realizar se reduce a la mitad. Ahora veamos lo que es el bitreversal, este algoritmo permite que una secuencia ya sea de entrada o salida de la FFT sea reordenada para obtener el resultado deseado, este algoritmo se implementara en el desarrollo del programa en C, con un N = 8 el cual estará representado por 3 bits (2^3). El bit 3 y el bit 1 deben ser intercambiados de sus posiciones, tal como se muestra en la figura 3.

Fig. 3. Resultado del bitreversal para el caso de N=8con tres bits.