1

LA TRANSFORMADA RPIDA DE FOURIER (FFT)

La principal ventaja de la base Fourier F , estudiada en la seccin anterior, consiste en que
todas las transformaciones lineales invariantes por traslacin son diagonalizadas por F .
En esta seccin se estudiara otra ventaja clave de F : La DFT puede calcularse mediante
un algoritmo rpido conocido como la transformada rpida de Fourier FFT. Sin este
algoritmo el uso de la DFT seria muy limitado especialmente en anlisis de seal de video o
en seales reales de voz.
Consideremos la cantidad de clculo requerido para un cambio de base. Sea z l 2 (
B es una base de l 2 (

) . S

) , se pueden calcular las componentes [ z ]B de z con respecto a la

base B a partir del producto de las componentes euclidianas z [ z ]E por la matriz cambio
de base de E a B notada como A . Es decir,
[ z ]B A [ z ]E Az .
N 1

Como la m-sima componente del vector Az es

a
n 0

m ,n

z (n) , entonces se requieren de N

multiplicaciones complejas para calcular cada componente de Az . Ahora bien, como Az

tiene N componentes, entonces se requieren de N 2 multiplicaciones para calcular
completamente el vector Az [ z ]B .
Para la base Fourier, la situacin no es diferente: sabemos que z [ z ]F WN z donde WN es
la matriz de Fourier. As el clculo directo de z requiere de N 2 multiplicaciones complejas
Por multiplicacin compleja, se entiende la multiplicacin de dos complejos que requiere
de solo 3 multiplicaciones reales. Pues basta ver que:
(a ib)(c id ) (ac bd ) (ad bc) (ac ad ad bd ) (ad bd bc bd )i
(c d )a (a b)d [(a b)d (c d )b]i

donde las 3 multiplicaciones reales son: (c d )a , (a b)d , (c d )b . En el anlisis de esta

seccin se consideraran solo multiplicaciones complejas ya que hacen que la velocidad del
computador sea ms lenta que cuando se realizan sumas.
En el procesamiento de seales e imgenes, los vectores bajo consideracin son en general
de gran longitud. Una seal de televisin, por ejemplo, requiere aproximadamente de 10
millones de valores en pixeles por segundo para preservar toda la informacin relevante
(Proakis y Manolakis, 1996, pp. 29-30). As un segundo de la seal muestreada es un
vector de longitud 10.000.000 . Una imagen de la huella digital (tal como la del prologo) se
representa digitalmente particionando cada pulgada cuadrada de la imagen en una malla de

500 por 500 pixeles (250000 pixeles) cada uno de los cuales tiene asignado un valor de
intensidad en escala de grises y donde estos valores constituyen un vector de gran longitud.
Para una imagen de video, se pueden tener de 20 a 30 vectores de similar tamao por
segundo. El clculo de las DFT de estos vectores en tiempo real puede llegar a sobrepasar
la capacidad de un hardware computacional lo que hace necesario un algoritmo rpido.
El lema a continuacin es una versin simple de FFT, en la que la longitud N es par. Este
lema exhibe la idea bsica detrs de FFT.
Lema 2.37

Supngase M

, y N 2M . Sea z l 2 (

). Se define u, v l 2 (

mediante
u(k ) z(2k ) para k 0,1,.., M 1, y v(k ) z(2k 1) para k 0,1,.., M 1.

En otras palabras,
u ( z(0), z(2), z(4),..., z(n 4), z( N 2)) y v ( z(1), z(3), z(5),..., z (n 3), z ( N 1)).

Si z denota la DFT de z definido sobre N puntos, esto es, z WN z . Si u, v denotan las

DFT de u y v respectivamente, definidas sobre M

N
puntos, esto es, u WM u , y
2

v WM v . Entonces para m 0,1, 2,..., M 1,

z(m) u (m) e

i 2 m

v(m)

(1)

Tambin, para m M , M 1, M 2,..., N 1, sea

mM .
correspondientes valores de son 0,1, 2,.., M 1 . Entonces

z(m) z( M ) u ( ) e

i 2
N

v( ).

Ntese

que

los

(2)

Demostracin: Para m 0,1, 2,.., N 1 , por definicin

N 1

z(m) z (n)e

i 2 mn

n 0

M 1

z (2k )e

M 1

i 2 m (2 k )
N

k 0

z (2k 1)e

i 2 m (2 k 1)
N

k 0

descomponiendo la suma en la suma sobre valores pares ms la suma sobre valores

N
impares. Reemplazando z (2k ) u(k ) y z(2k 1) v( k) y M
se tiene
2
M 1

z(m) u (k )e
k 0

M 1

i 2 m (2 k )
N

v(k )e
k 0

M 1

i 2 m (2 k 1)
N

u (k )e
k 0

i 2 m ( k )
N

M 1

i 2 m (1)
N

v(k )e
k 0

i 2 m ( k )
N

3
M 1

z(m) u (k )e

i 2 m ( k )

i 2 m

M 1
N

k 0

v(k )e

i 2 m ( k )

M 1

i 2 m ( k )

k 0

Para m 0,1, 2,..., M 1 ,

M 1

z(m) u (k )e

i 2 m ( k )

i 2 m

k 0

v(k )e

u (m) e

i 2 m

v(m)

k 0

As, z(m) u (m) e

i 2 m

v(m)

ecuacin (1)

Para la ecuacin (2), suponiendo m M , M 1,..., N 1 y por el enunciado m M

reemplazando en,
M 1

z(m) u (k )e

i 2 m ( k )

i 2 m

M 1
N

k 0

M 1

u (k )e

v(k )e

u (k )e

k 0

i 2 ( M )( k )
M

M 1

i 2 ( M )
N

k 0

M 1

i 2 m ( k )

v(k )e

u (k )e

i 2 ( )( k )
M

e i 2 k e

i 2 ( )

v(k )e

i 2 ( )( k )
M

e i 2 k

M 1

i 2 ( )
N

v(k )e

i 2 ( M )

i 2 ( )( k )
M

pues e

1 , N 2M

k 0

i 2 ( )

z(m) u ( ) e

M 1

i 2 ( M )
N

k 0

i 2 ( )( k )

k 0

u ( ) e

k 0

k 0

M 1

i 2 ( M )( k )

v( )

i 2 ( )
N

v( )

ecuacin (2)

Ejemplo 1. Sea z (1,1,1, i,1, 1,1, i) l 2 (

) . Encontrar z

Solucin: Siguiendo el mismo procedimiento del lema 2.37, donde N 8 2M M 4

u (1,1,1,1)

v (1, i, 1, i)

1 i 2 (0) n 4
F0 (n) e
, n 0,1, 2,3
4 F0 (1,1,1,1) u
4
Ntese que,
1 i 2 (1) n 4
F1 (n) e
, n 0,1, 2,3
4 F1 (1, i, 1, i) v
4

Calculando u W4u (4,0,0,0) ,y, v W4v (0, 4,0,0)

Entonces por la ecuacin (1) para m 0,1, 2,3
z(0) u(0) 1v(0) 4 0 4 ,

z(1) u (1) e

i 2 (1)

v(1) 0 4e

z(2) u (2) e

z(3) u (3) e

i 2 (2)

2 2 2 2i ,

v(2) 0 0 0 ,

i 2 (3)

v(3) 0 0 0

Luego por la ecuacin (2) para m 4,5,6,7

z(4) u(0) 1v(0) 4 0 4 ,

z(5) u (1) e

i 2 (1)
8

z(6) u (2) e
z(7) u (3) e

v(1) 0 4e

i 2 (2)

2 2 2 2i ,

v(2) 0 0 0 ,

v(3) 0 0 0 .

i 2 (3)

Por lo tanto, z (4, 2 2 2 2i,0,0, 4, 2 2 2 2i,0,0)

El paso bsico del procedimiento anterior inicia con los valores u (m) , v(m) que producen

u (m)

v(m)

i 2 m

(1)

z(m) u (m) e

i 2 m

z(m M ) u (m) e

v(m)

i 2 m

v(m)

Figura 1. Diagrama Mariposa.

z(m) y z(m M ) de acuerdo con el diagrama de la figura 1. El clculo es tan bsico que

alguna veces se evala cuantos diagramas mariposa son realizados por segundo.
Ntese que los valores usados en la ecuacin (1) son los mismos de la ecuacin (2), es
decir, u (m) y v(m) para 0 m M 1. Para aplicar las ecuaciones (1) y (2), primero se
calculan u y v . Como cada uno de estos vectores son de longitud M

N
, cada uno puede
2

ser calculado directamente con M 2 multiplicaciones complejas. Luego se calculan los

i 2 m

N
productos e
v(m) para m 0,1, 2,.., M 1 . Estos requieren M multiplicaciones
complejas adicionales. El resto consiste de solo sumas y restas de estas cantidades, que no
se cuentan. Por lo tanto, el nmero total de multiplicaciones complejas requerido para
calcular z mediante las ecuaciones (1) y (2) es a lo ms
2

N N 1
2M M 2 ( N 2 N )
2 2
2
2

N2
, mientras que el nmero de
2
multiplicaciones complejas que se requieren para calcular z directamente es N 2 . Por lo
tanto el lema 2.37 recorta nuestro tiempo de clculo casi a la mitad.
Para un N suficientemente grande, esto es esencialmente

S N es divisible por 4 en lugar de 2, se puede ir ms all. Como u y v tiene orden par,

entonces se puede aplicar el mismo mtodo para reducir el tiempo requerido para el clculo
de ellos. S N es divisible por 8, es posible realizar un paso ms y as sucesivamente. Una
forma ms general de describir esto es definiendo N , para cualquier entero positivo N
como el nmero mnimo de multiplicaciones complejas que se requieren para calcular la
DFT de un vector de longitud N . Si N 2M entonces las ecuaciones (1) y (2) reducen el
clculo de z al clculo de dos DFT de tamao M , ms M multiplicaciones adicionales
complejas. Por lo tanto,

N 2( M ) M .

(3)

El caso mas favorable es cuando N es una potencia de 2 como en el lema que sigue.
Lema 2.39 Supngase N 2n para algn n . Entonces
N

1
N log 2 ( N )
2

Demostracin: La demostracin se hace por induccin sobre n . Cuando n 1 , un vector

a b
de longitud 21 es de la forma z (a, b) . Entonces z W2 z
clculo que no
a b
1
as que 2 0 1 (2) log 2 (2) . Luego el
2
resultado se cumple para este caso. Ahora supngase el resultado vlido para n k 1 (es
1
decir que se cumple que para N 2k 1
2k 1 (2k 1 ) log 2 (2k 1 ) ) y tratemos de ver
2
k
que se cumple para n k (es decir cuando N 2 ).

requiere ninguna multiplicacin compleja,

2k 2( 2k 1 ) 2k 1 2 (2k 1 ) log 2 (2k 1 ) 2k 1 2k 1 (k 1) 2k 1 2k 1 k

2

Es decir, 2k 2k 1 k

2k
N
k log 2 ( N ) puesto que k log 2 ( N ) y N 2k
2
2

As la desigualdad sigue siendo vlida para n k . Por lo tanto, si n

1
N 2n es verdadero que N N log 2 ( N )
2

entonces para

Como ejemplo, para un vector de longitud 218 262144 , la FFT reduce el nmero de
multiplicaciones complejas necesarias para calcular la DFT

de (218 )2 6.87 1010 a

9 218 2.359296 10 6 haciendo los clculos ms de 29000 veces mas rpido!. As si se

tomaran 8 horas para hacer la DFT de forma directa, por la va de la FFT el mismo clculo
tomara cerca de 1 segundo. Esta relacin se hace ms extrema en la medida que N se
incrementa, al punto tal que clculos que pueden hacerse por FFT en un tiempo razonable
por el clculo directo podra gastarse toda una vida o quizs ms. Esta diferencia radical en
la velocidad de clculo ha sido esencial para el procesamiento de seales digitales hoy en
da.

Lema

2.40.

p, q

Supngase

w0 , w1 ,..., wp 1 l 2 (

N pq .

Sea

z l2 (

).

Definir

) mediante
w (k ) z (kp )

Para b 0,1,..., q 1, definir vb l 2 (

vb ( ) e
Entonces para a 0,1,..., p 1 y

, k 0,1,..., q 1.

) mediante

i 2 b
N

w (b) , 0,1,..., p 1.

b 0,1,..., q 1,

z(aq b) vb (a)

(4)

Ntese que por el algoritmo de la divisin, todo m 0,1,..., N 1 es de la forma aq b

para algn a 0,1, 2,..., p 1 y b 0,1, 2,..., q 1 , por lo tanto, la ecuacin (4) da
como resultado el vector completo de la DFT de z.
Demostracin. Cada n 0,1,..., N 1 se puede escribir de manera nica en la forma kp
para algn k 0,1,.., q 1 y

0,1,.., p 1. Por consiguiente,

7
N 1

z(aq b) z (n)e

p 1 q 1

i 2 ( aq b ) n

z (kp )e

n 0

i 2 ( aq b )( kp )
pq

0 k 0

Simplificando,
i 2 ( aq b )( kp )

pq

p 1

z(aq b) e

ei 2 ak e
i 2 ( a )
p

i 2 ( a )

i 2 ( bk )
p

q 1

i 2 ( b )
N

i 2 ( b )
q

pq

w ( k )e

i 2 ( a )

i 2 ( bk )

i 2 ( bk )
p

i 2 ( b )

se tiene que

ya que w (k ) z (kp )

k 0

w ( b )
p 1

z(aq b) e

i 2 ( a )
p

p 1

i 2 ( b )

w (b) e

vb ( )

i 2 ( a )

vb ( ) vb (a) . Lo que se quera probar.

La prueba anterior muestra el principio bsico detrs de la FFT. En el clculo de z(aq b),
para cada valor de a surgen las mismas cantidades vb ( ), 0 p 1 . El algoritmo FFT
reconoce esto y calcula estos valores solo una vez. El clculo directo de z implcitamente
recalcula estos valores intermedios cada vez que ellos aparecen.
Considrese el nmero de multiplicaciones requeridas para el algoritmo en el lema 2.40.
Primero se calculan los vectores w , para 0,1,..., p 1. Cada uno de estos es un vector
de longitud q , por lo tanto para calcular cada w se requieren q multiplicaciones
complejas. As que este paso requiere un total de p( q ) multiplicaciones complejas. El
siguiente paso es multiplicar cada w (b) por e

i 2 ( b )
N

para obtener los vectores vb ( ) .

Esto requiere un total de pq multiplicaciones complejas, una para cada una de los q
valores de b y p valores de

. Finalmente se calculan los vectores vb para b 0,1,..., q 1.

Cada vb es un vector de longitud p , as que cada uno de los q vectores vb requiere de # p

multiplicaciones complejas, para un total de q( p ) multiplicaciones. Sumando, se tiene un
estimado del nmero de multiplicaciones requeridas para calcular una DFT de tamao
N pq ,
# pq p(#q ) q(# p ) pq.

(5)

Este estimado se puede usar inductivamente para hacer varios clculos sobre el tiempo
requerido para calcular la FFT (ver los ejercicios 2.3.7 y 2.3.8).
La ventaja de usar la FFT es mayor cuando ms compuesto es N . En muchas aplicaciones
se segmentan flujos de datos en piezas de tamao elegido. En este caso se suele tomar N
como una potencia de 2 y as aplicar el lema 2.39. S no es posible tener la longitud para

aplicar el teorema entonces se rellena con ceros hasta que se tenga una longitud altamente
compuesta.
Aunque las ecuaciones (3) y (5) se pueden usar para calcular el nmero total de
multiplicaciones complejas necesarias para calcular z , stas no muestran como configurar
o desarrollar el clculo completo. Los lemas 2.37 y 2.40 muestran como hacer cada paso
pero no muestran como organizarlos iterativamente.
A continuacin se analiza el algoritmo FFT para mostrar como el clculo puede ser
arreglado. Por simplicidad, nos restringiremos al caso donde N es una potencia de 2, es
decir, N 2n . Entonces se puede expandir cualquier m 0,1,..., N 1 en base 2 en la
forma
m m0 2m1 22 m2 ... 2n1 mn1 ,

donde m0 , m1 ,..., mn1 0,1. Para z l 2 (

) , se denota

z (m) z (mn1 , mn2 ,..., m1 , m0 ).

Para cualquier k k0 2k1 22 k2 ..., 2n1 kn1 con k0 , k1 ,.., kn1 0,1 ,
N 1

z(k ) z (m)e

i 2 km

m 0

m0 0 m1 0

i 2 ( k0 2 k1 22 k2 ..., 2n1 kn1 )( m0 2 m1 22 m2 ... 2n1 mn1 )

mn1 0

2n

z (mn 1 , mn 2 ,..., m1 , m0 )e

Ntese que en cada exponente aquellos productos que dan un mltiplo entero de i 2 2n en
el numerador despus de su divisin por 2n el resultado es i 2 en cuyo caso ei 2 1
i 2 ( k0 2 k1 22 k2 ..., 2n1 kn1 )( m0 2 m1 22 m2 ... 2n1 mn1 )
2n

e
i 2 ( k0 2 k1 2 k2 ..., 2
2

e
e

n1

kn1 )(2

n1

i 2 ( k0 2 k1 22 k2 ..., 2n1 kn1 )(2 m1 )

mn1 )

2n

2n

i 2 ( k0 )(2n1 mn1 )

i 2 ( k0 2 k1 )(2n2 mn2 )

i 2 ( k0 2 k1 2 2 k2 )(2 n3 mn3 )

2n

2n

2n

i 2 ( k0 2 k1 22 k 2 ..., 2n1 k n1 )( m0 )
2n

i 2 ( k0 2 k1 2 2 k2 ..., 2 n1 kn1 )( m0 )
2n

Reemplazando arriba se tiene la ecuacin (6),

z(k )

...

m0 0 m1 0

mn1 0

z (mn 1 ,.., m1 , m0 )e

i 2 ( k0 )(2n1 mn1 )

i 2 ( k0 2 k1 )(2n2 mn2 )

i 2 ( k0 2 k1 2 2 k2 ..., 2n1 kn1 )( m0 )

...e

2n

Ntese que la primera suma interna depende de las variables m0 , m1 ,..., mn2 de las sumas
externas y sobre k0 pero no sobre k1 , k2 ,.., kn1. Por tanto, se define
y1 (k0 , mn 2 , mn 3 ,..., m0 )

i 2 ( k0 )(2n1 mn1 )

mn1 0

z (mn 1 , mn 2 ,..., m1 , m0 ) e

2n

z (0, mn 2 , mn 3 ,..., m0 )(1) z (1, mn 2 , mn 3 ,..., m0 )e

i 2 ( k0 )(2n1 )
2n

Calcular y1 (k0 , mn2 , mn3 ,..., m0 ) requiere de solo una multiplicacin compleja para cada
una de las 2n selecciones de k0 , mn2 , mn3 ,..., m0 0,1 , para un total de 2n multiplicaciones complejas que dan todos los 2n valores posibles de y1 . En el siguiente paso, se
define
y2 (k0 , k1 , mn 3 ,..., m0 )

i 2 ( k0 2 k1 )(2n2 mn2 )

mn2 0

y1 (k0 , mn 2 , mn 3 ,..., m0 ) e

2n

z (k0 , 0, mn 3 ,..., m0 )(1) z (k0 ,1, mn 3 ,..., m0 )e

i 2 ( k0 2 k1 )(2n1 )
2n

Solo se requiere de una multiplicacin compleja para calcular cada una de las 2n
selecciones de k0 , mn2 , mn3 ,..., m0 0,1 , para un total de 2n multiplicaciones complejas
que dan todos los 2n valores posibles de y2 . Continuando con este proceso, cada vez se
reemplaza el ndice m restante ms alto por el siguiente k ndice. As el esquema realiza la
secuencia de las transformaciones

z (mn 1 , mn 2 ,..., m1 , m0 )
y1 (k0 , mn 2 , mn 3 ,..., m0 ),
y1 (k0 , mn 2 , mn 3 ,..., m0 )
y2 (k0 , k1 , mn 3 ,..., m0 ),
yn 1 (k0 , k1 , k2 ,...kn 2 , m0 )
yn (k0 , k1 , k2 ,...k n 2 , k n 1 )
Por la ecuacin (6), el vector final yn (k0 , k1 , k2 ,...kn2 , kn1 ) es z(k ) . En cada paso se calcula
el siguiente vector y j en todas las 2n posibles escogencias (o elecciones) de su variable.
Por lo tanto cada paso requiere a lo ms 2n multiplicaciones complejas, y como hay un
total de n pasos entonces se tendr a lo ms n2n N log 2 ( N ) multiplicaciones complejas.
Ntese que una vez que el vector y j ha sido calculado, y j 1 ya no es necesario, y por tanto
puede ser descartado. As, en cada etapa los datos previos pueden reemplazarse por nuevos
datos. Esto reduce la cantidad de memoria necesaria al realizarse el clculo.

10

Hay muchas variaciones del algoritmo FFT, algunas veces con ligeras ventajas que el
algoritmo bsico estudiado en esta seccin. El punto clave es que la DFT de un vector de
longitud N 2n puede ser calculado con a lo ms n2n1 ( N ) log 2 ( N ) multiplicaciones
2
complejas a mientras que con clculo directo se requieren N 2 22n multiplicaciones
complejas.
El algoritmo de la transformada rpida de Fourier puede tambin usarse para la calcular
rpidamente la inversa de la DFT mediante
( w)(n) =

1
w ( N n)
N

En a lo ms ( N ) log 2 ( N ) pasos si N es una potencia de 2 (no se cuenta la divisin por N

2
ya que la divisin entera es relativamente rpida).
Dado que la DFT y la IDFT pueden calcularse rpidamente, entonces tambin es posible
calcular rpidamente las convoluciones. Es decir, basta usar el lema 2.30 de convolucin y
aplicar su inversa a ambos lados as:
)
z w ( zw

Si z, w l 2 (

) , para N 2n , el algoritmo realiza a lo mas N log 2 N multiplicaciones

para calcular z y w , N multiplicaciones para calcular zw (el producto componente a

( N ) log 2 ( N ) multiplicaciones para

2
calcular la IDFT de zw . As en resumen, el algoritmo no toma ms que N (3N ) log 2 N
2
multiplicaciones para calcular z w .
componente de estos dos vectores), y a lo ms

Por la seccin anterior se sabe que todas las transformaciones lineales invariantes por
traslacin definidas sobre l 2 ( N ) pueden verse como un operador de convolucin (teorema
2.19) y donde tambin se afirma la equivalencia con la matrices circulantes. As, el
producto de una matriz N N circulante por un vector de longitud N puede calcularse
usando a lo ms N (3N ) log 2 N , a cambio del producto usual que requiere de N 2
2
multiplicaciones. En otras palabras, cuando T es una transformacin invariante por
traslacin, la DFT no solo diagonaliza T , sino que tambin da una forma prctica y rpida
para calcular T (va FFT). A continuacin una ilustracin grafica que relaciona
N (3N ) log2 N con N 2 .
2

11

Figura 1. Comparacin de N 2 con N (3N ) log 2 N para el caso de la convolucin.

2
Ntese que entre ms largo es el vector z - (eje x) se requieren ms operaciones por el
mtodo directo (en este caso N 2 ) para calcular z w que cuando se usa la FFT donde se
requiere a lo mas de N (3N ) log 2 N operaciones complejas.
2

Figura 2. Comparacin de N 2 con ( N ) log 2 N para el caso de vectores de longitud 2n .

2

12

Ntese que entre ms largo es el vector z de longitud 2n , se requieren ms operaciones por

el mtodo directo (en este caso N 2 ) para calcular z que cuando se usa la FFT donde se
requiere a lo ms de ( N ) log 2 N operaciones complejas.
2