## 2.1.3 LA TRANSFORMADA RÁPIDA DE FOURIER

La transformada de Fourier tiene amplias aplicaciones en ingeniería, física y matemáticas. Su versión discreta se usa en problemas de interpolación, en la obtención de soluciones para ecuaciones diferenciales parciales, en el diseño de circuitos, en cristalografía y, muy extensamente, en el procesamiento de señales. Éste fue uno de los primeros problemas con los que se usó la estrategia de divide y vencerás para desarrollar un algoritmo con orden asintótico más bajo que el cálculo directo.

El algoritmo mejorado se denomina transformada rápida de Fourier. Este algoritmo tuvo un impacto considerable porque muchos otros cálculos matemáticos se pueden expresar en términos de transformadas de Fourier. En algunos casos resulta más fácil convertir el problema natural en un problema de transformadas de Fourier, y efectuar dos transformadas de Fourier, que calcular una solución del problema original directamente. La convolución es un ejemplo.

El problema de calcular la convolución de dos vectores surge de manera natural y frecuente en problemas de probabilidad, ingeniería y otras áreas. La multiplicación simbólica de polinomios, es un cálculo de convolución.

La transformada discreta de Fourier de un n-vector y la convolución de dos n-vectores se pueden calcular de manera directa realizando n2 multiplicaciones y menos de n2 sumas. El algoritmo de divide y vencerás para calcular la transformada discreta de Fourier ejecuta Θ(n log n) operaciones aritméticas. Este algoritmo se conoce como transformada rápida de Fourier, o FFT (por sus siglas en inglés). Luego usamos la FFT para calcular convoluciones en tiempo Θ(n log n). Este ahorro de tiempo es muy valioso en las aplicaciones.

La transformada rápida de Fourier y la matriz Fn

La transformada discreta de Fourier transforma un n-vector complejo (es decir, un n-vector con componentes complejos) en otro n-vector complejo. Para transformar un n-vector real, basta con tratarlo como un n-vector complejo en el que todas las partes imaginarias son cero.

Para n >= 1, sea w una raíz n-ésima primitiva de 1, y sea Fn la matriz de n x n con elementos fij = wij, donde 0 <=i, j<= n - 1. La transformada discreta de Fourier del n-vector P = (p0, p1, . . . , pn-1) es el producto FnP.

La estrategia de divide y vencerás consiste en dividir el problema en ejemplares más pequeños, resolverlos, y utilizar las soluciones para obtener la solución del ejemplar actual. Aquí, para evaluar p en n puntos, evaluamos dos polinomios más pequeños en un subconjunto de los puntos y luego combinamos los resultados de forma apropiada. Recordemos que wn/2 = -1 y por tanto, para 0 <=j <=(n/2) - 1, w(n/2)+j = wj.

Transformada rápida de Fourier (versión recursiva)

Entradas: El vector P = (p0, p1, . . . , pn-1), como arreglo Complex con n elementos, donde n = 2k; un entero k> 0; y un entero m > 0. (Para procesar un vector de float, se le copia en la parte real del arreglo Complex P y se ponen en 0 todas las partes imaginarias.)

Salidas: La transformada discreta de Fourier de P almacenada en el arreglo Complex transformada. Este arreglo (con índices 0, . . . , 2k - 1) se pasa como parámetro y el algoritmo lo llena.

Comentario: Suponemos que las raíces 2k-ésimas de 1: w0, w, . . . , w2k-1, están almacenadas en el arreglo global omega en el orden en que se dan aquí. Usamos m para seleccionar raíces de este arreglo. El procedimiento FFTrecursiva se invocaría inicialmente con m = 1. En general, el conjunto que consiste en cada m-ésimo elemento, es decir, w0, wm, w2m, . . . , es el conjunto de raíces (2k/m)- ésimas de 1.

    void FFTrecursiva(Complex[] P, int k, int m, Complex[] transformada)
       if (k==0)
           transformada[0] = P[0];
       else
           int n = 2k;
           Complex[] pares = nComplex[n/2];
           Complex[] pares =  Complex[n/2];
           Complex xPImpares;
           int j;
           // Evaluar ppares en las raíces 2k-1-ésimas de 1.
           FFTrecursiva((p0, p2, . . . , p2k-2), k-1, 2m, pares);
           // Evaluar pimpares en las raíces 2k-1-ésimas de 1.
           FFTrecursiva((p0, p3, . . . , p2k-1), k-1, 2m, impares);
           for (j=0; j<=2k-1;j++)
       		   // Evaluar p(wj) y p(w2k-1+j).
               xPImpares = omega[m*j] * impares[j];
               // Calcular p(wj).
              transformada[j] = impares[j] + xPImpares;
              // Calcular p(w2k-1+j).
              transformada[2k-1 + j] = impares[j] - xPImpares;

La naturaleza recursiva del algoritmo facilita hallar una ecuación de recurrencia para el número de operaciones efectuadas. Contamos las operaciones aritméticas efectuadas con componentes de P y raíces de 1. Sean M(k), S(k) y R(k) el número de multiplicaciones, sumas y restas, respectivamente, efectuadas por FFTrecursiva para calcular la transformada directa de Fourier de un 2k-vector. Las tres operaciones se efectúan, una de cada una, en el cuerpo del ciclo for, así que M(k) = S(k) = R(k). Obtendremos M(k):

M(0) = 0
M(k) = 2k-1 + 2M(k - 1),

donde el primer término del miembro derecho, es decir, 2k-1, cuenta las multiplicaciones que se efectúan en el ciclo for, y el segundo término, 2M(k - 1), las efectuadas por las invocaciones recursivas de FFTrecursiva para calcular los valores de los arreglos pares e impares. Es fácil ver que M(k) = 2k-1k. Por tanto, M(k) = S(k) = R(k) = 2k-1k = (n/2) lg n. Puesto que las operaciones se efectúan con números complejos, este resultado deberá multiplicarse por una constante pequeña para reflejar el hecho de que cada operación con complejos requiere varias operaciones ordinarias.

###