transformada rapida de fourier

Capítulo 6

TRANSFORMADA RAPIDA
DE FOURIER (FFT)
Los temas a tratar en el presente capítulo son:

6.1

Algoritmo FFT

6.2

FFT Inversa.

6.3

Implementación

Televisión Digital

6- 2

La implementación de la ec. (4.15) involucra un número de sumas y multiplicaciones complejas que
es proporcional a N2.
Lo anterior se puede apreciar fácilmente ya que para cada uno de los Nvalores de µ, la expansión
− j 2πµx / N
de la sumatoria requiere N multiplicaciones complejas de f(x) por e
y (N-1) sumas de
resultados.
− j 2πµx / N
El término e
puede ser calculado de una vez y almacenado en una tabla para las
aplicaciones subsecuentes; por tal razón, la multiplicación de µ por x en este término no se
contabiliza normalmente como parte de la implementación.

Sedemuestra en lo que sigue que la descomposición de la ec. (4.15) (se reitera para mayor
comodidad):
F (µ ) =

1
N

N −1

∑ f (x ) ⋅ e − j 2πµx / N

((4.15))

x =0

permite reducir el número de sumas y multiplicaciones a un valor proporcional a Nlog2N.
El procedimiento de descomposición se denomina Algoritmo de Transformada Rápida de Fourier
(FFT).
El ahorro o reducción en el número deoperaciones es significativo para valores de N como los que
es doble esperar en imágenes prácticas, por ejemplo, para una imagen de 1024 x 1024 pixels,
N = 1024, se tendría:
N2 = 1.048.576 operaciones complejas,
Con FFT
N2log2N = 10.240 operaciones complejas
Con una reducción de 102.4:1, el tiempo de cómputo, empleando máquinas equivalentes, se
reduce a menos del 1%.
La descripción quesigue se refiere al desarrollo de un algoritmo de FFT para una variable. Tal
como se señala en la ecuación (4.5.1) (“Separabilidad”), una T.F. de dos variables puede ser
calculada por aplicación sucesiva de la T.F. de una variable.
6.1 Algoritmo para FFT.
El algoritmo que se plantea está basado en el método denominado “doblamiento sucesivo”.
Para simplificar las expresiones, la ec. (4.15) sereescribe:
F (µ ) =

1
N

N −1

∑ f (x )W µ
N

x

(6.1)

x =0

donde
Wn = e − j 2π / N

(6.2)

N = 2n

(6.3)

y N se supone de la forma :

Televisión Digital

6- 3

con N entero positivo. Entonces puede expresarse:
N = 2M

(6.4)

con M también entero positivo. Sustituyendo (6.4) en (6.1) se tiene:
F (µ ) =

1
2M

2 M −1

∑ f (x )W µ

x
2M

x =0

11

= 
2 M


M −1

∑ f (x )W

µ (2 x )

2M

x =0

1
+
M

M −1

∑ f (2 x + 1)W






µ (2 x +1) 

2M

x =0

(6.5)

µ
µ
Puesto que, de ec(6.2), W22M x = W Mx , la ec. (6.5) puede expresarse:

F (µ ) =

1 1


2 M


M −1

∑

µ
f (2 x )WM x +

x =0

1
M

M −1

∑ f (2 x + 1)W µ W µ
M

x

x =0

2M





(6.6)

Si se define:
F par (µ ) =

1
M

M −1

∑ f (2 x )W µ
M

x

(6.7)

x =0

para µ = 0, 1, …, M-1 y:
Fimpar (µ ) =

1
M

M −1

∑ f (2 x + 1)W µ
M

x

(6.8)

x =0

para µ = 0, 1, …, M-1, entonces la ec. (6.6) se hace:
F (µ ) =

{

1
F par (µ ) + Fimpar (µ )W2µ
M
2

}

(6.9)

µ
µ
También, dado que W M + M = W M y W2µ + M = −W2µ ,
M
M

F (µ + M )=

{

1
F par (µ ) − Fimpar (µ )W2µ
M
2

}

(6.10)

Un análisis cuidadoso de las ecuaciones (6.7) a (6.10) muestra algunas propiedades
interesantes de dichas expresiones. Nótese que una transformada de N-puntos puede ser
calculada dividiendo la expresión original en dos partes, como se indica en las ecs (6.9) y
(6.10).
El cálculo de la primera mitad de F (µ ) requiere de laevaluación de las dos transformadas de
N/2 puntos según las ecs. (6.7) y (6.8). Los valores resultantes de Fimpar (µ ) y F par (µ ) se
sustituyen en la ecuación (6.9) para obtener F (µ ) para µ = 0, 1, 2, …, (N/2-1). La otra mitad se
obtiene mediante la ecuación (6.10) sin requerir evaluaciones adicionales de la transformada.
Considerando un número de muestras igual a 2n, con n entero positivo,...