Calculo Eficiente de La Transformada de Fourier

Clculo eficiente de la transformada de Fourier

Escuela Superior de Ingenieros 6

2.- Clculo eficiente de la Transformada discreta de

Fourier.

La DFT (Transformada Discreta de Fourier) de una secuencia finita de longitud

N es [1] [2]:

1

0

[ ] [ ] , 0,1,..., 1 N

kn

N

n

X k x n W k N

=

= = (2.1)

Siendo -j(2pi/N)N

W =e . La Transformada Discreta de Fourier inversa viene dada

por:

1

0

1[ ] [ ] , 0,1,..., 1

Nkn

N

k

x n X k W n NN

=

= = (2.2)

En las ecuaciones (2.1) y (2.2), tanto x[n] como X[k] pueden ser complejos.

Las expresiones del lado derecho de esas ecuaciones difieren solamente en el signo

de la exponencial WN y en el factor de escala 1/N.

Debido a que x[n] puede ser compleja, si usamos directamente la ecuacin

(2.1) como una frmula para el clculo, necesitaremos N multiplicaciones complejas y

(N-1) sumas complejas para calcular cada valor de la DFT. Para calcular todos los N

valores necesitaremos un total de N2 multiplicaciones complejas y N(N-1) sumas

complejas. Expresando la ecuacin (2.1) en funcin de operaciones con nmeros

reales obtenemos,

{ } { } { } { }( ){ } { } { } { }( )

1

0

Re [ ] Re Im [ ] Im[ ]

Re [ ] Im Im [ ] Re

0,1,... 1

kn knN N N

kn knn

N N

x n W x n WX k

j x n W x n W

k N

=

= + +

=

(2.3)

La ecuacin (2.3) nos muestra que cada multiplicacin compleja requiere

cuatro multiplicaciones reales y dos sumas reales, y que cada suma compleja requiere

dos sumas reales. Por lo tanto, para cada valor de k, el clculo directo de X[k] requiere

4N multiplicaciones reales y (4N-2) sumas reales1. Debido a que X[k] se calcula para N

valores diferentes de k, el clculo directo de la Transformada Directa de Fourier de una

secuencia x[n] requiere 4N2 multiplicaciones reales y N(4N-2) sumas reales. Luego es

aproximadamente proporcional a N2. Es evidente que el nmero de operaciones

aritmticas requeridas para calcular la DFT por el mtodo directo se vuelve cada vez

1 La figura del nmero de operaciones es solo aproximado. Multiplicar por

0

NW , por ejemplo, no

requiere una multiplicacin. Sin embargo, la estimacin de la complejidad operacional obtenida incluyendo tales multiplicaciones es lo suficientemente precisa para comparar entre diferentes clases de algoritmos.



mayor a medida que se incrementa N. Por esta razn, estamos interesados en

mtodos de clculo que reduzcan el nmero de multiplicaciones y sumas.

La mayora de los algoritmos que buscan un cmputo ms eficiente de la DFT

explotan las propiedades de simetra y periodicidad de knN

W ; en concreto,

1. ( )[ ]k N n kn knN N NW W W = = (simetra compleja conjugada).

2. ( ) ( )kn k n N k N nN N N

W W W+ += = (periodicidad en n y en k).

Todos los algoritmos que buscan disminuir el nmero de operaciones se

conocen bajo el nombre de Transformada Rpida de Fourier (FFT). Los algoritmos de

la FFT se basan principalmente en descomponer la Transformada Discreta de Fourier

de una secuencia de longitud N en sucesivas DFT de menor tamao. La manera en la

que se implementa este principio bsico es la que da lugar a los diferentes tipos de

algoritmos. Hay dos clases bsicas de algoritmos:

1. Diezmado en el tiempo.- El nombre proviene de que la secuencia x[n] se

descompone en subsecuencias sucesivamente ms pequeas.

2. Diezmado en frecuencia.- En este caso son los coeficientes de la DFT de la

secuencia X[k] los que se descomponen en subsecuencias menores.

2.1.- Diezmado en el tiempo.

El principio de este algoritmo se ilustra ms convenientemente considerando el

caso especial de que N es una potencia entera de 2, es decir, N=2p. Como N es un

nmero entero par, podemos calcular X[k] separando x[n] en 2 secuencias de (N/2)

puntos, una con los n pares y otra con los n impares. X[k] viene dado por:

1

0

(2 / )

[ ] [ ] , 0,1,..., 1N

nk

Nn

nk j N kn

N

X k x n W k N

W e pi

=

= =

=

(2.4)

Separando x[n] en 2 sumatorios, uno con los n pares y otro con los impares

tenemos:

[ ] [ ] [ ]nk nkN N

n par n impar

X k x n W x nW= + (2.5)

Haciendo el cambio de variables n=2r para el caso par, y n=2r+1 para el caso

impar:

( / 2) 1 ( / 2) 12 (2 1)

0 0

( / 2) 1 ( / 2) 12 2

0 0

[ ] [2 ] [2 1]

[2 ]( ) [2 1]( )

N Nrk r k

N Nr r

N Nrk k rk

N N N

r r

X k x r W x r W

x r W W x r W

+

= =

= =

= + +

= + +

(2.6)

Sabemos que 2/ 2N N

W W= , luego:

2 2 (2 / ) 2 ( / 2)

/ 2

j N j N

N NW e e Wpi pi = = = (2.7)



Finalmente podemos reescribir la ecuacin (2.6):

( / 2) 1 ( / 2) 1

/2 /2

0 0

[ ] [2 ] [2 1]

[ ] [ ], 0,1,..., 1.

N Nrk k rk

N N N

r r

k

N

X k x r W W x r W

G k W H k k N

= =

= + +

= + =

(2.8)

Cada una de las sumas de la ecuacin (2.8) se reorganiza como una DFT de

(N/2) puntos. La primera suma es la DFT de (N/2) puntos de los puntos pares de la

secuencia original, y la segunda suma es la DFT de (N/2) puntos de los puntos

impares de la secuencia original. Aunque el ndice k alcanza N valores, k=0,1,...N-1,

cada una de las sumas se calcula solo para los valores de k entre 0 y (N/2)-1, ya que

tanto G[k] como H[k] son peridicas en k con periodo (N/2). Una vez realizada las dos

DFT, stas se combinan conforme a la ecuacin (2.8).

En la Fig. 2. 1, se calculan dos DFT de 4 puntos, donde G[k] designa la DFT de

4 puntos de los puntos pares y H[k] la de los puntos impares. X[0] se obtiene

multiplicando H[0] por 0N

W , y sumando al producto G[0]. X[1] se obtiene multiplicando

H[1] por 1N

W , y sumando al producto G[1]. La ecuacin (2.8) nos indica que para

obtener X[4], deberamos multiplicar H[4] por 4N

W y sumar el resultado a G[4]. Sin

embargo, tanto G[k] como H[k], son peridicas en k con periodo 4, H[4]=H[0] y

G[4]=G[0]. Por tanto, X[4] se obtiene multiplicando H[0] por 4N

W y sumando al

resultado G[0]. Como se indica en la Fig. 2. 1 los valores X[5], X[6] y X[7] se obtiene de

forma similar.

Si (N/2) es par (esto sucede cuando N es una potencia de 2), podemos calcular

cada una de las DFT de (N/2) puntos, rompindolas en dos sumatorios, cada uno de

los cuales sera una DFT de (N/4) puntos. Reescribiendo G[k] tenemos:

DFT

N/2 puntos

DFT

N/2 puntos

x[0]

x[2]

x[4]

x[6]

x[1]

x[3]

x[5]

x[7]

G[0]

G[1]

G[2]

G[3]

H[0]

H[1]

H[2]

H[3]

X[0]

X[1]

X[2]

X[3]

X[4]

X[5]

X[6]

X[7]

0

NW

1

NW

2

NW

3

NW

4

NW

5

NW

6

NW

7

NW

Fig. 2. 1.- Descomposicin de una DFT de N puntos en dos DFT de (N/2) puntos.



( / 2) 1 ( / 4) 1 ( / 4) 1

2 (2 1)

/ 2 / 2 /2

0 0 0

[ ] [ ] [2 ] [2 1]N N N

rk lk l k

N N N

r l l

G k g r W g l W g l W

+

= = =

= = + + (2.9)

( / 4) 1 ( / 4) 1

/ 4 / 2 / 4

0 0

[ ] [2 ] [2 1]N N

lk k lk

N N N

l l

G k g l W W g l W

= =

= + + (2.10)

Hacindolo de forma similar para H[k]:

( / 4) 1 ( / 4) 1

/ 4 /2 / 4

0 0

[ ] [2 ] [2 1]N N

lk k lk

N N N

l l

H k h l W W h l W

= =

= + + (2.11)

La DFT de (N/2) puntos G[k] puede ser obtenida por la combinacin de dos

DFT de (N/4) puntos, las secuencias g[2l] y g[2l+1]. De igual manera, la DFT de (N/2)

puntos H[k] puede ser obtenida por la combinacin de dos DFT de (N/4) puntos, las

secuencias h[2l] y h[2l+1]. Si insertamos estas modificaciones en la Fig. 2. 1

obtenemos el grfico completo (Fig. 2. 2), donde hemos expresado los coeficientes en

potencias de WN en vez de en potencias de WN/2.

Al final, todo se ha quedado reducido al clculo de 4 DFT de 2 puntos. Si

realizamos dichas DFT obtenemos el grafo completo para una DFT de 8 puntos en el

caso de diezmado en frecuencia (Fig. 2. 3).

x[0]

x[2]

x[4]

x[6]

x[1]

x[3]

x[5]

x[7]

X[0]

X[1]

X[2]

X[3]

X[4]

X[5]

X[6]

X[7]

0

NW

1

NW

2

NW

3

NW

4

NW

5

NW

6

NW

7

NW

DFT

N/4 puntos

DFT

N/4 puntos

DFT

N/4 puntos

DFT

N/4 puntos

0

NW

2

NW

4

NW

6

NW

0

NW

2

NW

4

NW

6

NW

Fig. 2. 2.- Descomposicin de una DFT de 8 puntos en 4 de DFT de 2 puntos.



De la Fig. 2. 3 podemos deducir que cada etapa de la DFT tiene N

multiplicaciones complejas y N sumas complejas. Como hay log2N etapas, tenemos un

total de Nlog2N multiplicaciones complejas y sumas.2

Podemos reducir ms el clculo de la Fig. 2. 3 explotando la simetra y la

periodicidad de los coeficientes rN

W . El clculo bsico es de la forma de la Fig. 2. 4, es

decir, realiza la obtencin de una pareja de valores de una etapa a partir de una pareja

de valores de la etapa anterior. Los coeficientes son siempre potencias de WN y los

exponentes estn separados por N/2. Debido a la geometra del grafo, esta operacin

se le denomina butterfly.

Teniendo en cuenta que:

/ 2 (2 / ) / 2 1N j N N jN

W e epi pi = = = (2.12)

El factor / 2r NN

W + podemos escribirlo:

/ 2 / 2r N N r rN N N N

W W W W+ = = (2.13)

2 Si N=2

10=1024, entonces N

2=2

20=1048576 y NlogN=10240. Conseguimos una reduccin de ms

de dos rdenes de magnitud.

x[0]

x[2]

x[4]

x[6]

x[1]

x[3]

x[5]

x[7]

X[0]

X[1]

X[2]

X[3]

X[4]

X[5]

X[6]

X[7]

0

NW

1

NW

2

NW

3

NW

4

NW

5

NW

6

NW

7

NW

0

NW

2

NW

4

NW

6

NW

0

NW

2

NW

4

NW

6

NW

0

NW

4

NW

0

NW

0

NW

4

NW

4

NW

0

NW

4

NW

Fig. 2. 3.- Grafo completo de la descomposicin de una DFT de 8 puntos.

r

NW

(r+N/2)

NW

Etapa

(m-1)

Etapa

m

Fig. 2. 4.- Diagrama bsico de una butterfly



Si usamos esto, el clculo de la butterfly que se realiza en la Fig. 2. 4 se puede

simplificar como ilustra la Fig. 2. 5. Haciendo esto solo necesitamos una multiplicacin

compleja en vez de dos.

Si usamos el diagrama de la Fig. 2. 5 y lo sustituimos por la butterfly de la Fig.

2. 3, obtenemos la Fig. 2. 6. En este caso en particular, hemos reducido en un factor

de 2 el nmero de multiplicaciones complejas.

2.2.- Diezmado en la frecuencia.

Los algoritmos de FFT mediante diezmado en el tiempo se basan en

estructurar los clculos de la DFT dividiendo la secuencia de entrada x[n] en

subsecuencias cada vez ms pequeas. Tambin podramos dividir la secuencia de

salida X[k] en subsecuencias cada vez ms pequeas de la misma forma que hicimos

antes. Los algoritmos de FFT que se basan en este procedimiento se denominan

algoritmos mediante diezmado en frecuencia.

Etapa

(m-1)

Etapa

mr

NW

-1

Fig. 2. 5.- Diagrama simplificado de una butterfly

x[0]

x[2]

x[4]

x[6]

x[1]

x[3]

x[5]

x[7]

X[0]

X[1]

X[2]

X[3]

X[4]

X[5]

X[6]

X[7]

0

NW

0

NW

0

NW

0

NW

0

NW

2

NW

0

NW

2

NW

0

NW

2

NW

1

NW

3

NW

-1

-1

-1

-1

-1

-1

-1

-1 -1

-1

-1

-1

Fig. 2. 6.- DFT de 8 puntos usando el diagrama de la Fig. 2. 5.



Restringimos de nuevo la discusin al caso en el que N es una potencia de 2

(N=2p) de forma que podemos separar nuevamente el clculo para las muestras pares

e impares.

1

0

[ ] [ ] , 0,1,... 1N

nk

N

n

X k x n W k N

=

= = (2.14)

Las muestras en frecuencia con numeracin par son:

1

(2 )

0

[2 ] [ ] , 0,1,...,( / 2) 1N

n r

N

n

X r x n W r N

=

= = (2.15)

y las podemos expresar como:

( / 2) 1 1

2 2

0 / 2

[2 ] [ ] [ ]N N

nr nr

N N

n n N

X r x nW x nW

= =

= + (2.16)

Si hacemos un cambio de variable en el segundo sumatorio de la ecuacin

(2.16) obtenemos:

( / 2) 1 ( / 2) 1

2 2 [ ( / 2)]

0 0

[2 ] [ ] [ ( / 2)]N N

nr r n N

N N

n n

X r x nW x n N W

+

= =

= + + (2.17)

Finalmente, debido a la periodicidad de 2rnN

W ,

2 [ ( / 2)] 2 2r n N rn rN rnN N N N

W W W W+ = = (2.18)

Y a que 2/ 2N N

W W= , podemos expresar la ecuacin (2.17) como,

( / 2) 1

/ 2

0

[2 ] ( [ ] [ ( / 2)]) , 0,1,...,( / 2) 1N

rn

N

n

X r x n x n N W r N

=

= + + = (2.19)

La ecuacin (2.19) es la DFT de (N/2) puntos, de la secuencia de (N/2) puntos

obtenida sumando la primera mitad y la ltima mitad de la secuencia de entrada.

Podemos repetir el mismo proceso pero para el caso impar. Las muestras

impares son:

1

(2 1)

0

[2 1] [ ] , 0,1,...,( / 2) 1N

n r

N

n

X r x n W r N

+

=

+ = = (2.20)

Reordenando la ecuacin (2.20) tenemos

( / 2) 1 1

(2 1) (2 1)

0 / 2

[2 1] [ ] [ ]N N

n r n r

N N

n n N

X r x n W x nW

+ +

= =

+ = + (2.21)

Una alternativa para el segundo sumatorio de la ecuacin (2.21) es:

( / 2) 11(2 1) [ ( / 2)](2 1)

/ 2 0

( / 2) 1( / 2)(2 1) (2 1)

0

( / 2) 1(2 1)

0

[ ] [ ( / 2)]

[ ( / 2)]

[ ( / 2)]

NNn r n N r

N N

n N n

NN r n r

N N

n

Nn r

Nn

x n W x n N W

W x n N W

x n N W

+ + +

= =

+ +

=

+

=

= +

= +

= +

(2.22)



Para obtener la ecuacin (2.22) hemos usado que ( / 2)2 1N rN

W = y ( / 2) -1NN

W = .

Sustituyendo la ecuacin (2.22) en la ecuacin (2.21) y combinando los dos

sumatorios tenemos:

( / 2) 1

(2 1)

0

[2 1] ( [ ] [ ( / 2)])N

n r

N

n

X r x n x n n W

+

=

+ = + (2.23)

Finalmente, si tenemos en cuenta que 2/ 2N N

W W= , obtenemos:

( / 2) 1

/ 2

0

[2 1] ( [ ] [ ( / 2)]) , 0,1,...,( / 2) 1N

n nr

N N

n

X r x n x n N W W r n

=

+ = + = (2.24)

La ecuacin (2.24) representa la DFT de (N/2) puntos de la secuencia obtenida

restando la segunda mitad de la secuencia de entrada de la primera mitad y

multiplicando la secuencia resultante por nN

W . Si llamamos g[n]=x[n]+x[n+N/2] y

h[n]=x[n]-x[n+N/2], podramos calcular la DFT formando primero las secuencias g[n] y

h[n], luego calculamos h[n] nN

W , y finalmente calculamos la DFT de (N/2) puntos de

esas dos secuencias para obtener las muestras de salida pares e impares

respectivamente. El procedimiento sugerido por la ecuaciones (2.19) y (2.24) se ilustra

en la Fig. 2. 7 para el caso de una DFT de 8 puntos.

Procedemos de forma similar a como obtuvimos el algoritmo de diezmado en el

tiempo. Como N es potencia de 2, (N/2) es par, por lo tanto podemos calcular la DFT

de (N/2) puntos separndola en dos DFT, una para las muestras pares y otra para las

impares. Si seguimos el procedimiento indicado por las ecuaciones (2.19) y (2.24),

combinamos la primera mitad y la ltima mitad de los puntos de entrada para cada

DFT de (N/2) puntos y luego calculamos la DFT de (N/4) puntos. En la Fig. 2. 8 se

ilustra este paso para el caso de 8 puntos.

DFT

N/2 puntos

DFT

N/2 puntos

x[0]

x[1]

x[2]

x[3]

x[4]

x[5]

x[6]

x[7]

X[0]

X[2]

X[4]

X[6]

X[1]

X[3]

X[5]

X[7]

g[0]

g[1]

g[2]

g[3]

h[0]

h[1]

h[2]

h[3]

0

NW

1

NW

2

NW

3

NW

-1

-1

-1

-1

Fig. 2. 7.- Descomposicin de una DFT de N puntos en dos DFT de (N/2) puntos



Para el caso de la DFT de 8 puntos, el sistema ha quedado reducido a calcular

cuatro DFT de 2 puntos, que se realizan sumando y restando los puntos de entrada.

La DFT de 2 puntos de la Fig. 2. 8 podemos sustituirla por la estructura que se

muestra en la Fig. 2. 9, de tal forma que el clculo de la DFT de 8 puntos se realiza

siguiendo el algoritmo mostrado en la Fig. 2. 10.

Contando las operaciones aritmticas de la Fig. 2. 10 y generalizando para

N=2p, vemos como necesitamos (N/2)log2N multiplicaciones complejas y Nlog2N

sumas complejas. Por lo tanto el nmero total de operaciones es el mismo para los

algoritmos de diezmado en el tiempo y diezmado en la frecuencia.

x[0]

x[1]

x[2]

x[3]

x[4]

x[5]

x[6]

x[7]

X[0]

X[4]

X[2]

X[6]

X[1]

X[5]

X[3]

X[7]

DFT

N/4 puntos

DFT

N/4 puntos

DFT

N/4 puntos

DFT

N/4 puntos

0

NW

1

NW

2

NW

3

NW

0

NW

2

NW

0

NW

2

NW

-1

-1

-1

-1

-1

-1

-1

-1

Fig. 2. 8.- Descomposicin de una DFT de 8 puntos en 4 de DFT de 2 puntos

Fig. 2. 9.- DFT de dos puntos.

0

NW

-1X [p]

-1X [q]

X [p]

X [q]-1



2.3.- Algoritmos para valores de N ms grandes.

Aunque el caso especial de N potencia de 2 conduce a algoritmos con

estructuras simples, no es la nica restriccin sobre N que puede producir una

reduccin de los clculos necesarios para obtener la DFT. De hecho, en muchos

casos es deseable evaluar eficientemente la DFT para obtener otros valores de N, y se

pueden emplear los mismos principios aplicados cuando N es potencia de 2 para

obtener los algoritmos de diezmado en el tiempo y en frecuencia al caso de que N sea

un entero compuesto, es decir, el producto de dos o ms factores enteros. Por

ejemplo, si N=RQ es posible expresar una DFT de N puntos como la suma de R DFT

de Q puntos o como la suma de Q DFT de R puntos, y obtener as una reduccin en el

nmero de operaciones. Si N tiene muchos factores, el proceso se puede repetir para

cada uno de los ellos. Los algoritmos para el caso general de N compuesto utilizan un

esquema de indexacin ms complicado que el caso de potencia de 2. Si los factores

de N son primos entre s, el nmero de multiplicaciones se puede reducir a costa de la

indexacin ms complicada de un algoritmo de factor primo.

Por ejemplo, podemos analizar el caso en el que N es una potencia de 4

(N=4v). Obviamente, podramos emplear para este clculo un radix-2, aunque es ms

eficiente computacionalmente usar un radix-4.

Para realizar una FFT radix-4 con diezmado en el tiempo, primero tomamos la

secuencia de entrada y la dividimos en cuatro subsecuencias x(4n), x(4n+1), x(4n+2),

x(4n+3), n=0, 1, , N/4-1. [3]

x[0]

x[1]

x[2]

x[3]

x[4]

x[5]

x[6]

x[7]

X[0]

X[4]

X[2]

X[6]

X[1]

X[5]

X[3]

X[7]

0

NW

1

NW

2

NW

3

NW

0

NW

2

NW

2

NW

0

NW

0

NW

0

NW

0

NW

0

NW

-1

-1

-1

-1

-1

-1

-1

-1

-1

-1

-1

-1

Fig. 2. 10.- DFT de 8 puntos usando DIF.



3

4

0

( / 4) 1

/ 40

( , ) ( , )

( , ) ( , )

0,1,2,3; 0,1,2,3; 0,1,2,..., 1;4

( , ) (4 1)

( , ) ( )4

lq lp

N

l

Nmq

Nm

X p q W F l q W

F l q x l m W

Np l q

x l m x m

NX p q X p q

=

=

=

=

= = =

= +

= +

(2.25)

As, las cuatro DFT de N/4 puntos F(l,q) de la ecuacin (2.25) se combinan

para obtener la DFT de N puntos. La expresin que combina las DFT de n/4 puntos

define una butterfly radix-4 con diezmado en el tiempo.

La butterfly radix-4 se representa en la Fig. 2. 11.a, y de forma ms compacta

en la Fig. 2. 11.b. En la figura se observa como cada butterfly conlleva 3

multiplicaciones complejas y doce sumas complejas.

En la Fig. 2. 12 se muestra la FFT radix-4 de longitud N=16 usando diezmado

en el tiempo.

0

q

2q

3q

-j

-1

j

-1

-1

j

-1

-j

0

NW

q

NW

2q

NW

3q

NW

a) b)

Fig. 2. 11.- Clculo bsico de una butterfly en un algoritmo FFT radix 4.



Como valor ilustrativo, podemos obtener el algoritmo FFT radix-4 con diezmado

en frecuencia fraccionando una DFT de N puntos en cuatro DFT de N/4 puntos.

Tenemos:

1

0

/ 4 1 / 2 1 3 / 4 1 1

0 / 4 / 2 3 / 4

/ 4 1 / 4 1/ 4

0 0

/ 4 1/ 2 3 / 4

0

( ) ( )

( ) ( ) ( ) ( )

( )4

3

2 4

Nkn

Nn

N N N Nkn kn kn kn

N N N N

n n N n N n N

N Nkn Nk kn

N N Nn n

NNk kn Nk

N N N Nn

X k x n W

x n W x n W x n W x n W

Nx n W W x n W

N NW x n W W x n W

=

= = = =

= =

=

=

= + + +

= + + +

+ + +

/ 4 1

0

Nkn

n

=

(2.26)

De la definicin de los twiddle factor, tenemos

/ 4 / 2 3 / 4( ) , ( 1) , ( ) kN k kN k kN kN N N

W j W W j= = = (2.27)

Luego,

/ 4 1

0

3( ) ( ) ( ) ( 1) ( )

4 2 4

Nk k k nk

Nn

N N NX k x n j x n x n j x n W

=

= + + + + + +

(2.28)

La relacin no es una DFT de N/4 puntos porque los twiddle factor dependen

de N y no de N/4. Para convertirla en una DFT de N/4 puntos, subdividimos la

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

2

3

0

2

4

6

0

3

6

9

x(0)

x(1)

x(2)

x(3)

x(4)

x(5)

x(6)

x(7)

x(8)

x(9)

x(10)

x(11)

x(12)

x(13)

x(14)

x(15)

X(0)

X(4)

X(8)

X(12)

X(1)

X(5)

X(9)

X(13)

X(2)

X(6)

X(10)

X(14)

X(3)

X(7)

X(11)

X(15)

Fig. 2. 12.- FFT radix-4 para N=16 usando diezmado en el tiempo.



secuencia en cuatro subsecuencias de N/4 puntos, X(4k), X(4k+1),X(4k+2) y X(4k+3),

k=0, 1, , N/4. As obtenemos la DFT radix-4 con diezmado en frecuencia:

/ 4 10

/ 40

/ 4 1

/ 4

0

3(4 ) ( )

4 2 4

3(4 1) ( )

4 2 4

3(4 2) ( )

4 2 4

Nkn

N Nn

Nn kn

N N

n

N N NX k x n x n x n x n W W

N N NX k x n jx n x n jx n W W

N N NX k x n x n x n x n

=

=

= + + + + + +

+ = + + + +

+ = + + + +

/ 4 1

2

/ 40

/ 4 13

/ 4

0

3(4 3) ( )

4 2 4

Nn kn

N Nn

Nn kn

N N

n

W W

N N NX k x n jx n x n jx n W W

=

=

+ = + + + +

(2.29)

Donde hemos usado la propiedad 4/ 4

kn kn

N NW W= . La entrada de cada DFT de

N/4 puntos es una combinacin lineal de cuatro seales simples escaladas por un

twiddle factor. Este procedimiento se repite v veces, donde v=log4N.

Por ltimo podemos comparar el nmero de multiplicaciones y sumas de los

distintos algoritmos que se usan para calcular una DFT de longitud N. [3] [4]

Multiplicaciones Sumas

N Radix-2 Radix-4 Radix-8 Radix-2 Radix-4 Radix-8

16 24 20 152 148

32 88 408

64 264 208 204 1032 976 972

128 712 2504

256 1800 1392 5896 5488

512 4360 3204 13566 12420

1024 10248 7856 30728 28336

Tabla 2. 1.- Nmero de multiplicaciones y sumas para calcular una DFT de de N puntos.

2.4.- Aplicaciones de la DFT.

Se ha comentado con anterioridad que la DFT es una de las herramientas ms

importantes en el procesamiento digital de seales. Tres formas comunes en las que

se usa son [5]:

1.- Anlisis espectral de la seales.

Es muy comn que la informacin se codifique en sinusoides que es lo que

forma la seal. La forma de la forma de onda en el dominio del tiempo no es

importante en este tipo de seales ya que la clave de la informacin esta en la

amplitud, la frecuencia y la fase de la sinusoide. La DFT se usa para extraer esta

informacin.



2.- Respuesta frecuencial de los sistemas.

Los sistemas se analizan en el dominio del tiempo mediante la convolucin. Un

anlisis similar se puede hacer en el dominio de la frecuencia. Usando la trasformada

de Fourier, cada seal de entrada puede ser representada como un grupo de cosenos,

cada uno con una amplitud y una fase especfica. De la misma manera, la DFT puede

usarse para representar cada seal de salida de una forma similar. Esto significa que

todo sistema lineal puede ser descrito completamente viendo como cambia la fase y la

amplitud de los cosenos cuando pasan a travs de el. Esta informacin se denomina

respuesta frecuencial del sistema. Desde que la respuesta al impulso y la respuesta

frecuencial contienen informacin completa sobre el sistema, debe de haber una

correspondencia unvoca entre ambas. Dada una, puedes calcular la otra. La relacin

entre la respuesta al impulso y la respuesta frecuencial es uno de los fundamentos del

procesamiento de seales: La respuesta frecuencial de un sistema es la Transformada

de Fourier de la respuesta al impulso.

3.- Convolucin va domino de la frecuencia.

Si transformamos dos seales al domino de la frecuencia, las multiplicamos y

transformamos el resultado al dominio del tiempo; obtenemos la convolucin de las

dos seales. Aunque los pasos intermedios son muy diferentes, la salida es idntica a

la convolucin estndar. Se elige este camino para realizar la convolucin debido a

que la convolucin tiene dos problemas principales. El primero es que es

matemticamente difcil de tratar, mientras que el segundo es la velocidad de clculo

(la convolucin es lenta debido al gran numero de sumas y multiplicaciones que hay

que calcular).

Documents

Calculo Eficiente de La Transformada de Fourier