MÈtodos r·pidos para el c·lculo de la TDF

12
Métodos rápidos para el cálculo de la TDF

12.1.

Introducción

La transformada discreta de Fourier (TDF) tiene un papel muy importante en el diseño,
análisis y realización de sistemas y algoritmos de tratamiento de señales en tiempo discreto1 . Las propiedades básicas de la transformada de Fourier y de la TDF, presentadas
en los Capítulos 3 y 4 respectivamente, hacen que analizar ydiseñar sistemas en el dominio transformado sea conveniente y práctico. Este hecho, junto con la existencia de
algoritmos eficientes para el cálculo explícito de la TDF, la convierten en un componente
importante de muchas aplicaciones prácticas de los sistemas en tiempo discreto.
Como se comentó en el Capítulo 4, la TDF X [k ] de N puntos son las muestras de la transformada de Fourier X (e jω )en N frecuencias equiespaciadas ω k = 2πk/N es decir, en
N puntos de la circunferencia unidad del plano complejo. En este capítulo se presentan varios métodos muy eficientes para calcular la TDF. Estos algoritmos se denominan
colectivamente transformada rápida de Fourier (FFT, “Fast Fourier Transform”), y los dos
más conocidos se estudian en las Secciones 12.4 y 12.5. Estos algoritmos sonaplicables
cuando el orden N de la TDF es potencia entera de 2, N = 2α . Si éste no es el caso, existen
algoritmos un poco más complicados, algunos de los cuales se presentan en la Sección
12.7, tales como el método de las raíces variadas o el de factores primos.
Hay muchas formas de medir la complejidad y la eficiencia de un determinado algoritmo
o realización, y el resultado final depende tanto dela tecnología disponible como de la
aplicación. La medida de la complejidad computacional que se utilizará es el número
de multiplicaciones y sumas aritméticas. Esta medida es simple de aplicar, y el número
de multiplicaciones y sumas está directamente relacionado con la velocidad de cómputo
cuando los algoritmos se ejecutan en computadores digitales de propósito general o en
microprocesadoresdedicados. Sin embargo, en realizaciones VLSI existen otras medidas
que pueden ser más apropiadas, por ejemplo, el área del chip y los requisitos de potencia,
que pueden no estar relacionadas directamente con el número de operaciones aritméticas.
En términos de multiplicaciones y sumas, los algoritmos FFT puede ser varios órdenes
1 Este

capítulo está basado mayormente en el Capítulo 9“Computation of the Discrete Fourier Transform”, de la 2da eidición del libro de Oppenheim, junto con algunos agregados de la 1ra. edición y de los
libros de Ingle y Proakis y de Porat.

1

12. Métodos rápidos para el cálculo de la TDF

2

de magnitud más eficientes que otros algoritmos alternativos, a tal punto que en muchos casos el procedimiento más conveniente para realizar una convoluciónes calcular
la transformada de las sucesiones que se van a convolucionar, multiplicar las transformadas y calcular luego la transformada inversa del producto de dichas transformadas.
Esta forma de implementación se denomina convolución de alta velocidad. Los detalles de
esta técnica se presentaron en el Capítulo 4 (convolución por bloques: métodos overlapadd y overlap-save). En la Sección 12.8se compara el tiempo de cálculo y el número de
operaciones necesarios para calcular una TDF de N puntos utilizando el comando fft
de M ATLAB. Este comando elige el tipo de algoritmo a utilizar según el valor de N, por
lo que su registro en función del largo de la sucesión permite inferir detalles de la implementación. También se comparan los tiempos de cálculo que insume una convolucióntradicional, y una de alta velocidad, y su variación en función del largo de las sucesiones
a convolucionar.
En aparente contradicción, existe una serie de algoritmos para calcular un conjunto más
general de muestras de la TDF, que resultan de reescribirla como una convolución. Son
útiles cuando se requieren sólo algunos valores de la TDF en un del intervalo de frecuencias comprendido en 0 ω <...