transformada rápida de fourier. - iniciolsb/elo320/clases/c24.pdf · preciso resolver el sistema...

1

Profesor Leopoldo Silva Bijit 20-01-2010

Capítulo 24

Transformada rápida de Fourier.

Es considerado un algoritmo clásico, que permite obtener a partir de una serie de valores

temporales las componentes espectrales en frecuencia, y viceversa con un costo O(n log n).

Como veremos es un caso particular del problema más general de calcular polinomios.

Existen dos formas de cálculo: una es evaluar un polinomio representado por sus coeficientes.

La otra es representar el polinomio por una serie de puntos.

24.1. Representación por n coeficientes.

Sea un polinomio de n coeficientes:

Donde los coeficientes son los n valores de aj.

Si se evalúan las potencias de x a través de multiplicaciones se requieren (n-1) + (n-2) +..+1

multiplicaciones, originando un algoritmo de complejidad O(n2).

La evaluación de polinomios suele efectuarse empleando la regla de Horner:

Que es de complejidad O(n), ya que requiere (n-1) multiplicaciones. La siguiente rutina ilustra

el procedimiento de cálculo.

double Horner(int a[ ], int n, double x)

{ double A=a[n-1];

for( i=n-2; i>=0; i--) A=a[i] +x*A;

return(A);

}

Las operaciones de suma y resta de polinomios expresados por sus coeficientes son de

complejidad O(n), ya que basta sumar o restar los coeficientes.

Sin embargo el producto de polinomios es de complejidad O(n2).

Si A y B son de n coeficientes, el producto C(x) = A(x)B(x) tendrá (2n-1) coeficientes:

1

0

( )n

j

jj

A x a x

0 1 2 2 1( ) ( ( .... ( ( ))....))i i i i n i nA x a x a x a x a x a

2 Estructuras de Datos y Algoritmos


c0 = a0b0

c1 = a0b1 + a1b0

c2 = a0b2 + a1b1 + a2b0

…

Operación que se denomina convolución de los coeficientes.

La evaluación de los coeficientes de C es O(n), y debe repetirse n veces, lo cual implica O(n2),

para el costo de la multiplicación de polinomios.

24.2. Representación por n valores.

Se tienen los valores o muestras: ( )k ky A x con k = 0..n-1

y0

x0

y1

x1

y2

x2

yn-1

xn-1 x

Figura 24.1 Representación por muestras.

Si se conocen los puntos: (xk, yk ), se tienen n ecuaciones con n incógnitas (los coeficientes).

0 1 2 1

0 0 0 1 0 2 0 1 0

0 1 2 1

1 0 1 1 1 2 1 1 1

0 1 2 1

1 0 1 1 1 2 1 1 1

....

....

.....

....

n

n

n

n

n

n n n n n n

y a x a x a x a x

y a x a x a x a x

y a x a x a x a x

Pueden existir diferentes representaciones por puntos, ya que sólo se requiere que los n puntos

xk sean diferentes. Como se verá la elección adecuada de los n puntos permitirá acelerar el

cálculo a O(n log n).

Esta representación puede obtenerse a partir de la representación por coeficientes con un costo

O(n2), ya que debe aplicarse n veces el algoritmo de Horner.

2 2

0

( )n

j

jj

C x c x

0

j

j k j kk

c a b

Transformada rápida de Fourier 3


También es posible pasar de la representación por puntos a la de coeficientes, para esto es

preciso resolver el sistema de ecuaciones planteado antes. Este problema se conoce como

interpolación.

2 1

0 00 0 0

2 11 11 1 1

2 11 11 1 1

1 ...

1 ...

1 ...

n

n

nn nn n n

a yx x x

a yx x x

a yx x x

La matriz tiene inversa si el determinante no es cero. El determinante de la matriz anterior, que

se denomina de Vandermonde, puede calcularse según:

1 0 2 1 1 20 1

det ( ) ( )( )...( )k j n nj k n

x x x x x x x x

El costo de evaluar la matriz inversa es O(n2) y además se debe realizar n multiplicaciones del

vector de los yk por los renglones de la matriz inversa, con lo cual resulta O(n3).

Sin embargo los coeficientes pueden calcularse con costo O(n2) empleando la fórmula de

interpolación de polinomios de Lagrange:

1 2 1 0 2 1 0 1 20 1 1

0 1 0 2 0 1 1 0 1 2 1 1 1 0 1 1 1 2

( )( )...( ) ( )( )...( ) ( )( )...( )( ) ....

( )( )...( ) ( )( )...( ) ( )( )...( )

n n nn

n n n n n n

x x x x x x x x x x x x x x x x x xA x y y y

x x x x x x x x x x x x x x x x x x

Que es un polinomio de n coeficientes que pasa por los n puntos (xk, yk).

O bien tal que A(xk) = yk para k=0..n-1, lo cual puede comprobarse en la fórmula anterior.

La ventaja de representación por puntos es que el cálculo del producto (también la suma y resta)

de polinomios es ahora O(n). Pero en caso de multiplicación, los polinomios deben

representarse con 2n puntos, ya que C, debe ser de 2n puntos.

Si se tienen los polinomios A y B, puede determinarse su producto C, según:

0 0 1 1 2 1 2 1

0 0 1 1 2 1 2 1

0 0 0 1 1 1 2 1 2 1 2 1

( ) ( , ),...( , ),...( , )

( ) ( , ),...( , ),...( , )

( ) ( , ),...( , ),...( , )

A n An n A n

B n Bn n B n

A B n An Bn n A n B n

A x x y x y x y

B x x y x y x y

C x x y y x y y x y y

24.3. Transformada discreta de Fourier.

Se tienen las transformadas de Fourier, directa e inversa, en el dominio de f y t, para la señal s(t)

y su densidad espectral S(f), definidas según:



2

1 2

( ( )) ( ) ( )

( ( )) ( ) ( )

j ft

j ft

s t S f s t e dt

S f s t S f e df

Y las transformadas discretas de Fourier: 1

2 /

0

12 /

0

( ) ( )

1( ) ( )

nj ik n

i

nj ik n

i

S k s i e

s k S i en

Con k=0..n-1

Si se define: wn=e-j2 /n

como la n-ava raíz compleja de la unidad, se tiene que:

e-j2 k/n

= (wn)k

El valor principal suele definirse según: ej2 /n

, en el primer cuadrante.

Reemplazando S(k) por Sk, s(k) por sk, y (wn)k por x se tienen dos polinomios.

Los polinomios se evalúan en las raíces complejas de la unidad. Si se reemplazan las potencias

de x se obtiene la relación que permite obtener el espectro a partir de las muestras temporales:

Las figuras siguientes muestran los polinomios representados por puntos.

1

0

1

0

1

ni

k ii

ni

k iin

S s x

s S x

2 10 00 0 0

2 11 11 1 1

2 11 11 1 1

1 ...

1 ...

1 ...

n

n

nn nn n n

s Sx x x

s Sx x x

s Sx x x

0*1 0*2 0*( 1)0 0

1*1 1*2 1*( 1)1 1

( 1)*1 ( 1)*2 ( 1)*( 1)1 1

1 ...

1 ...

1 ...

n

n n n

n

n n n

n n n nn nn n n

s Sw w w

s Sw w w

s Sw w w



Figura 24.2 Representación de polinomios por puntos.

El elemento (r, c) de la matriz anterior es (wn)r*c

con r y c variando entre 0 y (n-1).

Puede comprobarse que el elemento (r, c) de la matriz inversa es: (1/n)*(wn)-r*c

Que permite obtener las muestras temporales a partir del espectro. Notamos que el problema es

similar al anterior, pero cambiando el signo de las n-avas potencias complejas de la unidad, y un

escalamiento dividiendo por n.

Conocidas las muestras temporales, se requieren n multiplicaciones para obtener una muestra

del espectro, y como se requieren n muestras en frecuencia, se obtiene un algoritmo de costo

cuadrático. Además deben calcularse las potencias complejas de las n-avas raíces de la unidad.

24.4. Desarrollo del algoritmo de transformada rápida de Fourier.

El algoritmo FFT permite calcular la DFT en O( n log n).

El polinomio S(x) puede separarse en dos, uno con las potencias pares de x; el otro, con las

potencias impares:

s0

t0

s1

t1

s2

t2

sn-1

tn-1 t

T=intervalo de muestreo

S0

f0

S1

f1

S2

f2

Sn-1

fn-1 f

fS=1/n T=separación en frecuencia

0*1 0*2 0*( 1)0 0

1*1 1*2 1*( 1)1 1

( 1)*1 ( 1)*2 ( 1)*( 1)1 1

1 ...

1 ...1

1 ...

n

n n n

n

n n n

n n n nn nn n n

S sw w w

S sw w w

n

S sw w w

1

0

( )n

i

k ii

S S x s x

( / 2) 1

0 2 2

( / 2) 1

1 3 1

2 2

( ) ...

( ) ...

( ) ( ) ( )

n

p n

n

i n

k p i

S x s s x s x

S x s s x s x

S S x S x xS x



Los polinomios son de n/2 puntos cada uno. Esto considerando n par y más específicamente una

potencia de dos.

El cálculo de los Sk para n puntos puede descomponerse en dos cálculos de polinomios pero con

la mitad de puntos cada uno. A su vez, cada uno de esos polinomios, puede ser calculado en

términos de dos polinomios con la cuarta parte de los puntos, y así sucesivamente.

Más adelante veremos cómo los Sk pueden calcularse recursivamente, para obtener esa relación

es preciso conocer algunas propiedades de las raíces complejas de la unidad.

24.5. n-avas raíces complejas de la unidad.

Existen n raíces n-avas complejas de la unidad: wn0, wn

1, wn

2,… wn

n-1

Con : (wn)k = e

-j2 k/n

Para n = 2, se tienen

w20=e

-j 0 = cos(0) + j sen(0) = +1

w21=e

-j 1 = cos(- ) + j sen(- ) = -1

Figura 24.3. Raíces complejas cuadradas de la unidad

Para n = 4, se tienen:

(w4) = e-j /2

= -j

w40 = +1

w41 = -j

w42 = -1

w43= +j

Debe notarse que w44 = w4

0

Figura 24.4. Raíces complejas cuartas de la unidad

Algunas propiedades:

Para n>=0, k>=0 y d>0:

w40

w41

w42

w43

w20 w2

1



2 / 2 /

/ 2 2 / / 2

2

/ 2 2 2 2 2

2 / 2 2 / 1/ 2

2

1

0

( ) ( )

( ) 1

( ) ( )

( )

( ) 1 ( ) 1 (1) 1( ) 0

1 1 1

dk j dn dk j n k k

dn n

n j n n j

n

k n k n k n k

n n n n n

j n j n

n n

k n n k kn

k i n nn k k k

in n n

w e e w

w e e w

w w w w w

w e e w

w ww

w w w

La última relación es una serie geométrica, se requiere n>=1, y que k sea positivo no divisible

por n, para que el denominador no sea cero.

Si se efectúa el producto de la matriz de Vandermonde por su inversa, el elemento (r, c) del

producto, puede expresarse según:

1 1

( )

0 0

( / ) ( / )n n

kr kc k c r

n n nk k

n nw w w la cual toma valor 1 para r=c, y cero en caso contrario. Lo

cual origina una matriz unitaria, comprobándose que la expresión para la inversa es correcta. Se

requiere que (c-r) no sea divisible por n, esto se cumple ya que fuera de la diagonal:

-(n-1) < (r-c) < (n-1).

24.6. Series discretas para dos y cuatro puntos.

Se tiene para n = 2:

S0 = s0 + x0s1

S1 = s0 + x1s1

Evaluando en las raíces cuadradas complejas de la unidad:

S0 = s0 + w20s1 = s0 + (+1)s1

S1 = s0 + w21s1 = s0 + (- 1)s1

Resultando:

S0 = s0 + s1

S1 = s0 - s1

Para n = 4:

Evaluando en las raíces cuartas complejas de la unidad, notando que todos los valores no son

diferentes, debido a las propiedades de las raíces cuartas complejas de la unidad, se obtienen:

0 0 0 0

0 4 0 4 1 4 2 4 3

0 1 2 3

1 4 0 4 1 4 2 4 3

0 2 4 6

2 4 0 4 1 4 2 4 3

0 3 6 9

3 4 0 4 1 4 2 4 3

S w s w s w s w s

S w s w s w s w s

S w s w s w s w s

S w s w s w s w s



Reemplazando por los valores numéricos:

Finalmente, se advierte que para cuatro puntos, están incorporados los polinomios asociados a

dos puntos. Donde se ha definido: (S0p, S1p) y (S0i, S1i) como series de dos puntos.

0

0 0 2 1 3 0 4 0

0

2 0 2 1 3 0 4 0

1

1 0 2 1 3 1 4 1

1

3 0 2 1 3 1 4 1

( ) ( )

( ) ( )

( ) ( )

( ) ( )

p i

p i

p i

p i

S s s s s S w S

S s s s s S w S

S s s j s s S w S

S s s j s s S w S

24.7. Relaciones de recurrencia.

De la descomposición en dos polinomios y reemplazando los valores de evaluación con las n-

avas raíces complejas de la unidad, se desprenden dos relaciones de recurrencia para calcular los

Sk.

Una para los valores: S0, S1 , S2,…. , Sn/2 -1, y otra para: Sn/2, Sn/2 +1 , Sn/2 +2,…. , Sn-1

Empleando las propiedades de las raíces complejas, se obtienen:

Donde se han definido los valores de la parte par e impar como una evaluación de un polinomio

de n/2 puntos.

Finalmente se obtienen:

0 0 1 2 3

1 0 1 2 3

2 0 1 2 3

3 0 1 2 3

1

S s s s s

S s js s js

S s s s s

S s js s js

2 2

2 2

2 / 2 2

/ 2

( ) ( )

( ) ( )

( ) ( )

k p i

k k k

k p n n i n

k n k n k n

k n p n n i n

S S x xS x

S S w w S w

S S w w S w

/ 2

/ 2

( )

( )

k

kp p n

k

ki i n

S S w

S S w

2 2

/ 2 / 2

2 / 2 2 2 2

/ 2 / 2 / 2

( ) ( ) ( ) ( )

( ) ( ) ( ) ( ) ( ) ( )

k k k k k k k

k p n n i n p n n i n kp n ki

k n k n k n k k k k k k k

k n p n n i n p n n i n p n n i n kp n ki

S S w w S w S w w S w S w S

S S w w S w S w w S w S w w S w S w S



Con k=0, 1, 2,… (n/2)- 1

Asumiendo operaciones con números complejos, los n valores se calculan de a pares, en

términos de los valores asociados a dos series de n/2 puntos cada una:

for (k=0; k<= (n/2)-1; k++)

{ Sk = Skp + wnk Ski ;

Sk+n/2 = Skp - wnk Ski ;

}

Es usual calcular una sola vez, la expresión común dentro del for.

for (k=0; k<= (n/2)-1; k++)

{ t = wnk Ski ;

Sk = Skp + t ;

Sk+n/2 = Skp - t ;

}

El costo de calcular una potencia puede extraerse, a través de una multiplicación dentro del lazo:

wn = e-j2 /n

;

w = 1;

for (k=0; k<= (n/2)-1; k++)

{ t = w*Ski ;

Sk = Skp + t ; //Operación denominada mariposa. Butterfly.

Sk+n/2 = Skp - t ;

w * = wn ;

}

La codificación puede modificarse para tratar las variables complejas, por sus partes reales e

imaginarias.

Para un polinomio descrito por 8 puntos temporales. El cálculo puede visualizarse mediante la

descomposición en dos polinomios de 4 puntos, con los puntos pares en uno, y los impares en

otro. Un polinomio de 4 puntos, se puede calcular mediante la composición de dos polinomios

de dos puntos, donde nuevamente se separan los ubicados en posiciones pares e impares. No es

necesario descomponer polinomios de dos puntos, ya que su evaluación es sencilla. El siguiente

árbol ilustra la separación entre partes pares e impares.

/ 2

k

k kp n ki

k

k n kp n ki

S S w S

S S w S



Figura 24.5. Descomposición en polinomios pares e impares.

Si cada vez se suprime el bit menos significativo que representa al índice en binario, se tendrá

que la división se efectúa entre pares e impares. Por ejemplo el grupo (0, 2, 4, 6) se transforma

al suprimir el bit menos significativo en (0, 1, 2, 3).

Esta visualización también posibilita un algoritmo iterativo en lugar de recursivo. En el nivel de

las hojas se aplica la operación mariposa a todos los grupos de a dos (pero en el orden que

figuran en las hojas), luego se evalúan polinomios de 4 puntos cada uno, considerando ahora las

raíces cuartas complejas de la unidad, y así sucesivamente ascendiendo de nivel.

24.8. Reordenamiento de los puntos.

Si se observa la siguiente tabla, donde se han colocado los valores de las muestras temporales en

un arreglo, junto a sus índices en binario y el arreglo modificado. Puede notarse que los índices

en binario del arreglo modificado son las imágenes especulares de los índices originales. Puede

también notarse que la última columna se puede visualizar como un contador binario inverso, es

decir los dígitos que primero cambian son los más significativos. En este caso sólo es preciso

intercambiar s1 con s4, y s3 con s6.

Arreglo original Contador binario Arreglo modificado Contador inverso

s0 000 s0 000

s1 001 s4 100

s2 010 s2 010

s3 011 s6 110

s4 100 s1 001

s5 101 s5 101

s6 110 s3 011

s7 111 s7 111

Figura 24.6. Contador binario directo e inverso.

Para 16 puntos, colocando los valores de los contadores binarios directo e inverso, en decimal,

puede notarse que bastaría generar las dos secuencias de valores siguientes:

s0 s1 s2 s3 s4 s5 s6 s7

s0 s2 s4 s6

s1 s3 s5 s7

s2 s6

s0 s4

s1 s5

s3 s7



i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

j 0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15

ig x ig x ig x x x x ig

Figura 24.7. Contador binario inverso con cuentas en decimal.

Y sólo intercambiar cuando j> i. Esto evita los cambios en los casos identificados en el tercer

renglón con ig (por igualdad), y los cambios marcados con x (esto volvería a su lugar a los

elementos del arreglo). Además no es preciso revisar los casos con i= 0 e i=15.

Si el número de muestras es una potencia de dos, se tiene que el primer valor de j, de la

secuencia que debe generarse, será: j=n/2 o la expresión equivalente: j=n>>1.

La siguiente función intercambia los elementos de un arreglo x, generando las secuencias de

valores de i y j.

void bitreverse(int *x, int n)

{ int nmedios=n>>1, i, j, k, tx;

//i contador binario

for (i=1, j=nmedios; i<n-2; i++)

{

//printf("i=%d j=%d\n", i , j);

if (i < j) {

tx = x[i];

x[i] = x[j];

x[j] = tx;

}

//j contador binario inverso. Incrementa en uno la posición más significativa.

//y desplaza a la derecha las reservas.

for(k=nmedios; k <= j; k >>= 1) {j -= k;}

j+=k;

}

}

Ejemplos del contador binario inverso, con operaciones en decimal:

Si k y j tienen valor 8 ( 1000 en binario) se efectúa la resta (queda j=0) y la condición de reinicio

deja k=4 (0100), lo cual termina la iteración. Después del for se setea en uno el bit que marca k,

y deja j=4 (0100).

“Se cambian todos los unos más significativos por ceros, hasta encontrar el primer cero, el

cual se setea a uno”.

Si k=8 y j = 12 ( 1100 en binario) se efectúa la resta (queda j=4) y la condición de reinicio deja

k=4 (0100), se vuelve a iterar, quedando j=0 y k=2. Lo cual termina la iteración. Después del for

se setea en uno el bit que marca k, y deja j=4 (0010).



El siguiente ejemplo, busca el primer cero y lo cambia por uno, poniendo en cero el más

significativo.

Si k=8 y j=10 (1010), la primera iteración deja j=2 (0010) y k = 4 (0100), terminando la

iteración. El nuevo valor de j será 6 (0110)

Otra alternativa de diseño es generando la imagen especular de i para formar j.

“Se detectan los unos de i, y se los copia, mediante la variable m, en la posición especular en

j”.

void contadorinverso(int *x, int n)

{ int nmedios=n>>1, i, j, m ,k ,tx;

for (i=1,j=nmedios; i<n-2; ) //el penúltimo es par

{

printf("i=%d j=%d\n",i,j);

if (i < j) {

tx = x[i];

x[i] = x[j];

x[j] = tx;

}

for(i++, k=nmedios, m=1, j=0; k >=1; k >>= 1, m<<=1)

{

if(i&k) j|=m;

}

}

}

24.9. Operación mariposa.

Para deducir el algoritmo iterativo, veremos algunos casos específicos.

Para una serie de dos puntos, se muestra la serie inicial de puntos temporales en un arreglo.

Luego de aplicar la operación mariposa, y finalmente la reinterpretación de los puntos en

frecuencia.

n=2

for (k=0; k<= (n/2)-1; k++)



}

S0 = S0p + w20 S0i ;

S1 = S0p - w20 S0i ;

Con w20 = 1

La composición de la serie de 4 puntos a partir de las series de dos puntos, se obtiene con:

s0 s1

s0+s1 s0-s1

S0 S1



n=4

for (k=0; k<= (n/2)-1; k++)



}

0

0 0 4 0 0 2 1 3

0

2 0 4 0 0 2 1 3

1

1 1 4 1 0 2 1 3

1

3 1 4 1 0 2 1 3

( ) ( )

( ) ( )

( ) ( )

( ) ( )

p i

p i

p i

p i

S S w S s s s s

S S w S s s s s

S S w S s s j s s

S S w S s s j s s

Con: w40 = 1, w4

1 = - j = (w2

1)

1/2 w4 = 2w

Para una serie de cuatro puntos temporales, se procede al reordenamiento. A éstos se los trata

como series de dos puntos. Se aplica la operación mariposa, con n=2, a todos los pares:

Luego de la operación en los pares:

(0,1)(2,3)

Quedan las series en frecuencia de dos puntos

Se aplica ahora la operación mariposa con n=4. A los pares (0,2) y (1,3).

Lo cual genera los cuatro puntos en frecuencia.

Que puede leerse según:

La composición de la serie de 8 puntos a partir de las series de cuatro puntos, se obtiene con:

n=8

for (k=0; k<= (n/2)-1; k++)



}

Es decir:

S0p+S0i S0p-S0i S1p-jS1i S1p+jS1i

S0 S1 S2 S3

s0 s2 s1 s3

s0+s2 s0 -s2 s1 +s3 s1 -s3

S0p S1p S0i S1i



0

0 0 8 0

0

4 0 8 0

1

1 1 8 1

1

5 1 8 1

2

2 2 8 2

2

6 2 8 2

3

3 3 8 3

3

7 3 8 3

p i

p i

p i

p i

p i

p i

p i

p i

S S w S

S S w S

S S w S

S S w S

S S w S

S S w S

S S w S

S S w S

Con: w80 =1, w8

1 = e

-j /4 =

1(1 )

2j w8 = 4w

En el nivel 0: Se forman series de dos puntos, aplicando la operación mariposa con n=2, a los

pares: (0, 1), (0+2*1, 1+2*1), (0+2*2, 1+2*2), (0+2*3, 1+2*3)

En el nivel uno: Se forman series de 4 puntos. La composición de dos series de 2 puntos se logra

aplicando la operación con n=4, a los pares (0,2) (1,3) y también a los pares (0+4, 2+4) (1+4,

3+4) logrando dos series de cuatro puntos.

En el nivel dos: La composición de dos series de 4 puntos se logra aplicando la operación con

n=8. A los pares (0,4) (1,5) (2,6) (3, 7)

Dos series de 4 puntos

Serie de 8 puntos

Veamos ahora el caso general:

Si n es el número de puntos.

En el nivel 0, se tienen n/2 series de 2 puntos.



En el nivel j, se tienen n/2j+1

series de 2j+1

puntos.

En último nivel, el m-1, la única serie es de n= 2m

puntos.

El algoritmo iterativo debe generar las series asociadas al nivel, y los pares de puntos de cada

serie y luego aplicarles la operación mariposa a cada par.

Es decir, a través de la variable j, se repite para cada grupo formado por nn puntos:

S0p S1p S2p S3p S0i S1i S2i S3i

S0 S1 S2 S3 S4 S5 S6 S7



for(j=0; j<n; j+=nn)

for (k=0; k<= (nn/2)-1; k++)

{ Sk+j = Skp + wnk Ski ;

Sk+j+n/2 = Skp - wnk Ski ;

}

Falta aún una última iteración para procesar cada uno de los niveles.

El siguiente segmento genera los pares a los que debe aplicárseles la operación.

void mariposa(int m)

{ int n, k, j, nn, nivel;

n = 1;

for (k=0; k<m; k++) n *= 2; //n=2^m genera número de puntos

nn=1;

for (nivel=0; nivel<m; nivel++)

{ nn=2*nn; //series de nn puntos. Con nn=2^(nivel+1)

for(j=0; j<n; j=j+nn) //Para todos los n elementos en grupos de nn

{

for (k=0; k< nn/2; k++)//Se aplica mariposa a los pares (k+j, k+j+nn/2)

{ printf("(%d,%d)", k+j, k+j+nn/2); }

putchar('\n');

}

}

}

Para m= 4, se tienen 16 puntos, el programa genera los pares:

(0,1) 8 series de dos puntos

(2,3)

(4,5)

(6,7)

(8,9)

(10,11)

(12,13)

(14,15)

(0,2)(1,3) 4 series de 4 puntos

(4,6)(5,7)

(8,10)(9,11)

(12,14)(13,15)

(0,4)(1,5)(2,6)(3,7) 2 series de 8 puntos

(8,12)(9,13)(10,14)(11,15)

(0,8)(1,9)(2,10)(3,11)(4,12)(5,13)(6,14)(7,15) 1 serie de 16 puntos

La siguiente función resume las principales ideas. Sólo falta definir el tratamiento de los

números complejos y de los arreglos.



void mariposa(double *S, int m)

{ int n, k, j, nn, nivel;

double w, wn, u, t;

for (k=0, n=1; k<m; k++) n *= 2; //n=2^m genera n, el número de puntos a partir de m

nn=1;

wn = w2 ; //Al inicio las series son de dos puntos




{

w = 1;

for (k=0; k< nn/2; k++) //Se aplica mariposa a los pares (k+j, k+j+nn/2)

{

t = w*Sk+j+nn/2 ; //Con los valores de series de nn/2 puntos

u = Sk+j;

Sk+j = u + t ; //Se calculan con la operación mariposa, los

Sk+j+nn/2 = u - t ; //valores de las series de nn puntos.

w * = wn ;

}

}

wn = nw ; //Se duplica el número de puntos.

}

}

Al inicio, en el nivel cero, las series son de dos puntos; al subir de nivel debe calcularse la nueva

raíz compleja. Se ilustra, en el primer cuadrante la nueva raíz, que tiene la mitad del ángulo.

wn

w2n n

n/2

Figura 24.8. Cálculo de la raíz cuadrada.

Para calcular la raíz compleja principal asociada a una serie de 2n puntos a partir de la raíz

compleja principal asociada a una serie de n puntos, pueden efectuarse las siguientes

definiciones:



2 2 2

n n n

n n n

w x jy

w x jy

Del diagrama, aplicando la identidad trigonométrica para la tangente del ángulo medio, se

obtiene una relación entre las coordenadas cartesianas de las raíces; la segunda relación se

cumple debido a que el módulo de las raíces es de magnitud unitaria.

2

2

2 2

2 2

/ 2( )1 cos

1

1

n n

n n

n n

sentg

y y

x x

x y

Despejando, del sistema de ecuaciones, se obtienen las coordenadas cartesianas de w2n en

función de las coordenadas de wn.

2

2

1

2

1

2

nn

nn

xy

xx

El código completo de la función, con: s[i]=x[i] + jy[i], wn=wn1 +jwn2, w=w1 +jw2, además

se definen una serie de variables locales, para intercambios y para extraer constantes dentro de

los lazos. Se eliminan los llamados a función, para disminuir el costo de la creación de frames

en el stack. Se agrega el argumento dir, para obtener la transformada directa e inversa con la

misma función.

void FFT(short int dir, long m, double *x, double *y )

{ int n, nn, nmedios, nivel, i,j,k,i1;

double w1,w2, wn1,wn2,tx,ty,tw,t1,t2;

for (k=0,n=1; k<m; k++) n *= 2; //n=2^m genera número de puntos a partir de m

//void bitreverse(int *x, int n)

nmedios=n>>1;

for (i=1, j=nmedios; i<n-2; i++)

{

//printf("i=%d j=%d\n",i,j);

if (i < j) {

tx = x[i]; ty = y[i];

x[i] = x[j]; y[i] = y[j];

x[j] = tx; y[j] = ty;

}



//j contador binario. Incrementa en uno la posición más significativa.

//y desplaza a la derecha las reservas.

for(k=nmedios; k <= j; k >>= 1) {j -= k;}

j+=k;

}

/* Calcula FFT */

nn=1;

//wn = w2 = -1+j0; En el primer nivel son series de dos puntos

wn1 = -1.0;

wn2 = 0.0;




{

//w = 1+j0;

w1 = 1.0; w2 = 0.0;

for (k=0; k< nn/2; k++) //Se aplica mariposa a los pares (k+j, k+j+nn/2)

{

i=k+j;

i1=i+nn/2;

//t = w*S[k+j+nn/2];

t1 = w1 * x[i1] - w2 * y[i1];

t2 = w1 * y[i1] + w2 * x[i1];

//u = S[k+j];

//S[k+j+nn/2] = u - t;

x[i1] = x[i] - t1;

y[i1] = y[i] - t2;

//S[k+j] = u + t ; //Operación mariposa.

x[i] += t1;

y[i] += t2;

//w * = wn ;

tw = w1 * wn1 - w2 * wn2;

w2 = w1 * wn2 + w2 * wn1;

w1 = tw;

}

}

//wn = sqrt(wn) ; Al subir de nivel se requiere la raíz cuadrada de la anterior.

wn2 = sqrt((1.0 - wn1) / 2.0);

if (dir == 1) wn2 = -wn2;

wn1 = sqrt((1.0 + wn1) / 2.0);

}

/* Escalamiento para transformada inversa */

if (dir == -1) for (i=0; i<n; i++) { x[i] /= n; y[i] /= n; }

}



24.10. Interpretación de la FFT.

24.10.1. Corriente continua.

Para una serie de 16 valores constantes en el tiempo se obtiene un espectro de un solo punto en

el origen.

Figura 24.9. Forma de onda y espectro para señal continua en tiempo.

Nótese el valor 16 en el valor máximo del espectro. En algunas definiciones se plantea la

transformada directa escalada en 1/n. En este caso el máximo valor del espectro será 1. Esto

mejora la interpretación como un impulso de Dirac de fuerza uno, asociado a la corriente

continua.

24.10.2 Primera armónica.

Para 16 muestras de la señal temporal: cos(2 n t/16), con n=0..15 se tiene la gráfica de la

señal, en incrementos de t. Su FFT, graficada como magnitudes de los valores complejos,

está asociada dos puntos diferentes de cero; uno en f=1 f, y otro en f=15 f.

Donde f = 1/ t.

Se toman 16 muestras en un período de la señal temporal. La gráfica temporal está en unidades

de t, que es el intervalo de muestreo. Se dice que es la primera armónica.

El espectro está en unidades de f. El punto espectral en 15 f es una frecuencia espejo relativa

a f=8 f, que se denomina frecuencia de Nyquist, para el caso de 16 muestras.

En el espectro, la más alta muestra en frecuencia (positiva o negativa) se denomina frecuencia

de Nyquist. Es la mayor componente de alta frecuencia que puede existir en la señal temporal.

Dicho de otra forma si la señal no contiene frecuencias superiores a la de Nyquist puede ser

reconstruida exactamente a partir de sus muestras.



Si la señal que se va a muestrear tiene una frecuencia máxima, para poder recuperar dicha señal,

a partir de sus muestras, debe muestreársela con una frecuencia que sea el doble de la frecuencia

máxima. Es decir dos muestras por período a lo menos. Si la señal varía más rápido que la mitad

de la frecuencia de muestreo no puede recuperársela a partir de las muestras.

Figura 24.10. Forma de onda y espectro para Primera armónica.

24.10.3. Segunda armónica.

Para 16 muestras de la señal temporal: cos(2 n t/8), con n=0..15 se tiene la gráfica de la señal,

en incrementos de t. Su FFT está asociada dos puntos diferentes de cero; uno en f=2 f, y otro

en f=14 f. Donde f = 1/ t. Se dice que es la segunda armónica.

El punto espectral en 14 es una frecuencia espejo relativa a la frecuencia de Nyquist.

Se toman ahora 8 muestras por período.

Figura 24.11. Forma de onda y espectro para Segunda armónica.



24.10.4. Tercera armónica.

Se dibuja ahora la señal temporal de tercera armónica junto a la primera o fundamental, en

forma continua. A la derecha se ilustran las 16 muestras de la tercera armónica. Se toman 16/3

muestras por período.

Figura 24.12. Forma de onda y muestras para Tercera armónica.

La trasformada rápida muestra el espectro, donde figura la tercera armónica, y su espejo en 13.

Figura 24.13. Espectro para Tercera armónica.

24.10.5. Séptima armónica.

Nótese que las muestras temporales difícilmente permiten visualizar la figura continua. Se

toman 16/7 muestras por período.



Figura 24.14. Forma de onda y muestras para Séptima armónica.

La transformada rápida permite visualizar el contenido armónico de la séptima. Y el espejo en

9.

Figura 24.15. Espectro para Séptima armónica.

24.10.6 Octava armónica.

Al tomar muestras con la frecuencia de Nyquist, se toman dos muestras por período de la octava

armónica, que tiene período 2 t, ya que la fundamental tiene período 16 t.

Frecuencia de la fundamental = 1/16 t = f/16 = ff.

Frecuencia de la octava armónica es = f/2 = 8 ff .

Período de muestreo = t, frecuencia de muestreo =1/ t = f.

Frecuencia de Nyquist = f/2 = 8 ff .

Las muestras de la octava armónica, dos por período, se ilustran junto a una gráfica continua.



Figura 24.16. Forma de onda y muestras para Octava armónica.

Y el espectro de magnitudes obtenido mediante la FFT:

Figura 24.17. Espectro para Octava armónica.

Para la novena armónica, cuya frecuencia es mayor que la de Nyquist se obtiene un espectro

idéntico al de la séptima armónica. Lo cual no permite reconstruir la señal temporal a través de

su espectro.

24.10.7 Frecuencias no múltiplos enteros de la frecuencia de muestreo.

Los casos anteriores daban un espectro de tonos puros. Sin embargo una frecuencia levemente

diferente hace aparecer varias armónicas. Veamos por ejemplo una señal de 1,2 veces la

frecuencia fundamental (cos(2 n t*1,2/16) )

Se aprecia un valor de componente continua y presencia de segunda tercera y cuarta, en

magnitudes decrecientes. Siendo mayor la presencia de primera armónica.



Figura 24.18. Forma de onda y espectro para no múltiplo de frecuencia de muestreo.

Para una señal con frecuencia 1,5 veces la de primera armónica, aparecen componentes

espectrales en toda la banda (de 0 a 8), siendo más importantes las contribuciones de la primera

y segunda.

Figura 24.19. Espectro para con frecuencia 1,5 veces la de primera armónica.



La mezcla de dos tonos puros: segunda de amplitud uno, y cuarta de amplitud 0,5.

Figura 24.20. Mezcla de frecuencias múltiples de la de muestreo.

La mezcla de un tercio de la 3,2 armónica con un quinto de la 5,5 armónica:

Figura 24.20. Mezcla de frecuencias no múltiplos de la de muestreo.

Se aprecia la dificultad para interpretar el contenido armónico en el espectro. Se detecta con

facilidad la importancia de la tercera, pero no la de la quinta o sexta.

24.11. Derivación de la FFT a partir de la transformada de Fourier.

dfefStsfS

dtetsfSts

ftj

ftj

21

2

)()())((

)()())((



Si se aproxima la primera integral, asumiendo que s(t) es cero fuera del período fundamental

(i=0..n-1), por una sumatoria, considerando el tiempo como una variable discreta t=i t.

s0

t0=0

s1

t1=1 t

s2

t2=2 t

sn-1

tn-1

t

t=intervalo de muestreo

n t=Período fundamental

Figura 24.21. Aproximación de la integral temporal.

Para aproximar la segunda integral, se discretiza la variable f, en los puntos i f. Esto también

considera cero el espectro fuera del intervalo n f. Con i=0..n-1 y k=0..n-1.

Dividiendo la primera por t, y arreglando la segunda sumatoria, se obtiene:

Definiendo, con k=0..n-1:

12

0

2

( ) ( )

( ) ( )

i nj fi t

i

j fk t

S f s i t e t

s k t S f e df

12

0

12

0

( ) ( )

( ) ( )

i nj ki f t

i

i nj ki f t

i

S k f s i t e t

s k t S i f e f

12

0

12

0

( )( )

( )( )

i nj ki f t

i

i nj ki f t

i

S k fs i t e

t

S i fs k t f t e

t



Se obtienen los polinomios:

Referencias.

Thomas H. Cormen, Charles E. Leiserson, y Ronald L. Rivest, "Introduction to Algorithms",

Second Edition, McGraw-Hill, ISBN 0-07-013151-1, 2001.

( )( )

( ) ( )

1

S k fS k

t

s k s k t

fn t

12 /

0

12 /

0

( ) ( )

1( ) ( )

i nj ki n

i

i nj ki n

i

S k s i e

s k S k en



Índice general.

CAPÍTULO 24 ............................................................................................................................................ 1

TRANSFORMADA RÁPIDA DE FOURIER. ......................................................................................... 1

24.1. REPRESENTACIÓN POR N COEFICIENTES. ........................................................................................... 1 24.2. REPRESENTACIÓN POR N VALORES. .................................................................................................. 2 24.3. TRANSFORMADA DISCRETA DE FOURIER. ......................................................................................... 3 24.4. DESARROLLO DEL ALGORITMO DE TRANSFORMADA RÁPIDA DE FOURIER. ....................................... 5 24.5. N-AVAS RAÍCES COMPLEJAS DE LA UNIDAD. ..................................................................................... 6 24.6. SERIES DISCRETAS PARA DOS Y CUATRO PUNTOS. ............................................................................ 7 24.7. RELACIONES DE RECURRENCIA. ....................................................................................................... 8 24.8. REORDENAMIENTO DE LOS PUNTOS. ............................................................................................... 10 24.9. OPERACIÓN MARIPOSA. .................................................................................................................. 12 24.10. INTERPRETACIÓN DE LA FFT. ....................................................................................................... 19

24.10.1. Corriente continua. .............................................................................................................. 19 24.10.2 Primera armónica. ................................................................................................................ 19 24.10.3. Segunda armónica. ............................................................................................................... 20 24.10.4. Tercera armónica. ................................................................................................................ 21 24.10.5. Séptima armónica. ............................................................................................................... 21 24.10.6 Octava armónica. .................................................................................................................. 22 24.10.7 Frecuencias no múltiplos enteros de la frecuencia de muestreo. .......................................... 23

24.11. DERIVACIÓN DE LA FFT A PARTIR DE LA TRANSFORMADA DE FOURIER. ...................................... 25 REFERENCIAS. ......................................................................................................................................... 27 ÍNDICE GENERAL. .................................................................................................................................... 28 ÍNDICE DE FIGURAS. ................................................................................................................................ 29



Índice de figuras.

FIGURA 24.1 REPRESENTACIÓN POR MUESTRAS. .......................................................................................... 2 FIGURA 24.2 REPRESENTACIÓN DE POLINOMIOS POR PUNTOS. ...................................................................... 5 FIGURA 24.3. RAÍCES COMPLEJAS CUADRADAS DE LA UNIDAD ..................................................................... 6 FIGURA 24.4. RAÍCES COMPLEJAS CUARTAS DE LA UNIDAD .......................................................................... 6 FIGURA 24.5. DESCOMPOSICIÓN EN POLINOMIOS PARES E IMPARES. ........................................................... 10 FIGURA 24.6. CONTADOR BINARIO DIRECTO E INVERSO. ............................................................................. 10 FIGURA 24.7. CONTADOR BINARIO INVERSO CON CUENTAS EN DECIMAL. ................................................... 11 FIGURA 24.8. CÁLCULO DE LA RAÍZ CUADRADA. ........................................................................................ 16 FIGURA 24.9. FORMA DE ONDA Y ESPECTRO PARA SEÑAL CONTINUA EN TIEMPO. ....................................... 19 FIGURA 24.10. FORMA DE ONDA Y ESPECTRO PARA PRIMERA ARMÓNICA. ................................................. 20 FIGURA 24.11. FORMA DE ONDA Y ESPECTRO PARA SEGUNDA ARMÓNICA. ................................................ 20 FIGURA 24.12. FORMA DE ONDA Y MUESTRAS PARA TERCERA ARMÓNICA. ................................................ 21 FIGURA 24.13. ESPECTRO PARA TERCERA ARMÓNICA. ............................................................................... 21 FIGURA 24.14. FORMA DE ONDA Y MUESTRAS PARA SÉPTIMA ARMÓNICA. ................................................. 22 FIGURA 24.15. ESPECTRO PARA SÉPTIMA ARMÓNICA. ................................................................................ 22 FIGURA 24.16. FORMA DE ONDA Y MUESTRAS PARA OCTAVA ARMÓNICA. ................................................. 23 FIGURA 24.17. ESPECTRO PARA OCTAVA ARMÓNICA. ................................................................................ 23 FIGURA 24.18. FORMA DE ONDA Y ESPECTRO PARA NO MÚLTIPLO DE FRECUENCIA DE MUESTREO. ............ 24 FIGURA 24.19. ESPECTRO PARA CON FRECUENCIA 1,5 VECES LA DE PRIMERA ARMÓNICA. ......................... 24 FIGURA 24.20. MEZCLA DE FRECUENCIAS MÚLTIPLES DE LA DE MUESTREO. .............................................. 25 FIGURA 24.20. MEZCLA DE FRECUENCIAS NO MÚLTIPLOS DE LA DE MUESTREO. ........................................ 25 FIGURA 24.21. APROXIMACIÓN DE LA INTEGRAL TEMPORAL. ..................................................................... 26

transformada rápida de fourier. - iniciolsb/elo320/clases/c24.pdf · preciso resolver el sistema...

Documents