Aproximación trigonométrica y transformada rápida de Fourier: algoritmo de Cooley-Tukey

Abstract

El objetivo principal de este trabajo es presentar, analizar, implementar y comparar el algoritmo de Cooley-Tukey para el cálculo de la Transformada Rápida de Fourier conocida por sus siglas en inglés: FFT (Fast Fourier Transform). Esto se hace en los Capítulos 5 y 6, mientras que los otros cuatro capítulos están dedicados a motivar y justificar la necesidad de la Transformada Rápida de Fourier como algoritmo del cálculo de la Transformada de Fourier Discreta (en inglés, DFT, Discret Fourier Transform) que es introducida desde cuatro puntos de vista distintos. El el primer capítulo se introduce la DFT como una aproximación discreta de la Transformada de Fourier Continua mediante fórmulas de cuadratura para aproximar la integral que la define. En el Capítulo 2 planteamos la aproximación de una función en el sentido de mínimos cuadrados por un polinomio trigonométrico de Fourier de grado m. Cuando m tiende a 1 tendremos la conocida serie de Fourier de la función. La serie de Fourier es una potente herramienta de aproximación de funciones. Mostraremos su relación con la Transformada Discreta de Fourier a través del cálculo efectivo de los coeficientes de dicha serie utilizando fórmulas de cuadratura para el cálculo aproximado de las integrales que las definen. La interpolación trigonométrica será el objeto de estudio del Capítulo 3. En él plantearemos la interpolación con polinomios trigonométricos y polinomios de fase. En ambas situaciones se expondrá la estrecha relación del cálculo de los coeficientes del polinomio con la Transformada de Fourier Discreta. En el Capítulo 4 introducimos la DFT a través del cálculo efectivo de los coeficientes del polinomio trigonométrico de ajuste en el sentido de mínimos cuadrados discretos. El Capítulo 5 llegamos a la parte central del trabajo, donde se expone un método efectivo para el cálculo de la Transformada Discreta: la Transformada Rápida de Fourier y, en particular, el algoritmo de Cooley-Tukey. Por último, ocupamos el último capítulo con una recopilación de varios ejemplos de las situaciones expuestas en el trabajo poniendo en práctica el algoritmo desarrollado y mostrando sus beneficios frente a un cálculo directo de la Transformada de Fourier Discreta. El trabajo termina con un anexo donde se recogen los códigos del algoritmo programado en Matlab.The main objective of this project is to present, analyze, implement and compare CooleyTukey's algorithm in order to calculate the Fast Fourier Transform (FFT), known in Spanish as Transformada Rápida de Fourier. This is calculated in chapters 5 and 6, while the other four chapters are dedicated to promote and justify the need of Fast Fourier Transform as the algorithm to calculate the Discrete Fourier Transform (DFT) (in Spanish: Transformada de Fourier Discreta) that is presented in four different points of view. In the first chapter DFT is introduced as a discrete approximation of Continuous Fourier Transform with the use of quadrature formulas to approximate the integral that defines it. In the Chapter 2 we propose the approximation of a function in the way of leastsquares with grade m Fourier's trigonometric polynomial. When m tends to 1 we obtain the known Fourier's series of the function. Fourier's series is a potent tool to approximate functions. We will show how it relates to the Discrete Fourier Transform with the effective calculation of the coeficients of the referred series by using quadrature formulas that define the approximated calculation of the integrals. Trigonometric interpolation is the main object of study in Chapter 3, in which we will present the interpolation of trigonometric polynomial and phase polynomial. For both cases we will prove how the coeficients' calculation of the polynomial is strongly related to the Discrete Fourier Transformation. In the Chapter 4 we introduce the DFT by the effective calculation of the coeficients of the trigonometrical polynomial fit in the way of discrete least-squares. In the Chapter 5 we reach the main part of the project, where the effective method for the calculation of the Discrete Transform is exposed: the Fast Fourier Transform and, in particular, the Cooley-Tukey's algorithm. In the end, we use the last chapter as a recompilation of different examples of the situations exposed in the project using the developed algorithm and showing its benefits in opposition to the direct calculation of the Discrete Fourier Transform. The project concludes with an annex where the programmed Matlab codes of the algorithm are collected.