Transformada Discreta de Fourier II - uv.es · en 4N multiplicaciones reales. N-1 sumas de números complejos. Para calcular los N términos tenemos que hacer N veces las anteriores

Transformada Discreta de Fourier (II)

1

Procesado Digital de Señales, 4º Ingeniería Electrónica. Profesor Emilio Soria. E.T.S.E Universidad de Valencia.

Más problemas...ahora computacionales

!

x(n) "e

# j "2"$ "s"n

N

n= 0

N#1

% =& " X (k) "e

j "2"$ " k#s( )"n

N

n= 0

N#1

%k= 0

N#1

%

!

e

j "2"# " k$s( )"n

N

n= 0

N$1

% =0 k & s

N k = s

' ( )

!

x(n) "e

# j "2"$ "s"n

N

n= 0

N#1

% =& "N " X (s)

!

x(n) =1 0 " n " 4

0 5" n " 9

# $ %

!

X (k) = x(n) "e

# j "2"$ "k"n

N

n= 0

N#1

%

x(n) =1

N" X (k) "e

j "2"$ "k"n

N

k= 0

N#1

%

!

WN = e

" j #2#$

N

!

X (k) = x(n) "WN

k"n

n= 0

N#1

$

x(n) =1

N" X (k) "W

N

#k"n

k= 0

N#1

$

La DFT de orden N de una señal x(n) viene definida por la siguiente expresión

Para cada término de la DFT se necesitan las siguientes operaciones

N multiplicaciones que, en principio, podrían ser complejas depende de x(n). Estas multiplicaciones complejas se transforman

en 4N multiplicaciones reales.

N-1 sumas de números complejos.

Para calcular los N términos tenemos que hacer N veces las anteriores operaciones;

coste computacional proporcional a N2

Este coste computacional es demasiado alto cuando N es alto; hay que buscar alternativas

a la solución directa.

Existen un gran número de variantes rápidas de la DFT conocidas con las siglas FFT

correspondientes a Fast Fourier Transform.

La base de todas ellas radica en las propiedades de simetría de la exponencial compleja que

aparece en la definición de la DFT.

6.2. Algoritmos FFT

Calculo directo de la DFT:

• Si x(n) es compleja =⇒ x(n) = xR(n) + jxI(n) y X(k) =

XR(k) + jXI(k):

XR(k) =N−1∑n=0

[xR(n)cos

(2πkn

N

)+ xI(n)sin

(2πkn

N

)]

XI(k) =N−1∑n=0

[xR(n)sin

(2πkn

N

)− xI(n)cos

(2πkn

N

)]• Esto exige:

1. 2N 2 calculos trigonometricos.

2. 4N 2 multiplicaciones reales.

3. 4N(N − 1) sumas reales.

4. Muchos direccionamientos e indexados.

• En caso de calcularse la DFT de varias secuencias de igual longi-

tud conviene calcular previamente las funciones trigonometricas

y almacenarlas en una “look-up table”, LUT.

• Esto es poco operativo! ¿Como podemos solucionarlo? El meto-

do no explota las propiedades de simetrıa y periodicidad del

factor de fase WN :

◦ Simetrıa: Wk+N/2N = −Wk

N

◦ Periodicidad: Wk+NN = Wk

N

• Si lo aprovecho, obtengo algoritmos rapidos conocidos como

FFTs, Fast Fourier Transforms o Transformadas Rapidas de

Fourier.

154

6.2. Algoritmos FFT

Calculo directo de la DFT:

• Si x(n) es compleja =⇒ x(n) = xR(n) + jxI(n) y X(k) =

XR(k) + jXI(k):

XR(k) =N−1∑n=0

[xR(n)cos

(2πkn

N

)+ xI(n)sin

(2πkn

N

)]

XI(k) =N−1∑n=0

[xR(n)sin

(2πkn

N

)− xI(n)cos

(2πkn

N

)]• Esto exige:

1. 2N 2 calculos trigonometricos.

2. 4N 2 multiplicaciones reales.

3. 4N(N − 1) sumas reales.

4. Muchos direccionamientos e indexados.

• En caso de calcularse la DFT de varias secuencias de igual longi-

tud conviene calcular previamente las funciones trigonometricas

y almacenarlas en una “look-up table”, LUT.

• Esto es poco operativo! ¿Como podemos solucionarlo? El meto-

do no explota las propiedades de simetrıa y periodicidad del

factor de fase WN :

◦ Simetrıa: Wk+N/2N = −Wk

N

◦ Periodicidad: Wk+NN = Wk

N

• Si lo aprovecho, obtengo algoritmos rapidos conocidos como

FFTs, Fast Fourier Transforms o Transformadas Rapidas de

Fourier.

154

!

x(n) "e

# j "2"$ "s"n

N

n= 0

N#1

% =& " X (k) "e

j "2"$ " k#s( )"n

N

n= 0

N#1

%k= 0

N#1

%

!

e

j "2"# " k$s( )"n

N

n= 0

N$1

% =0 k & s

N k = s

' ( )

!

x(n) "e

# j "2"$ "s"n

N

n= 0

N#1

% =& "N " X (s)

!

x(n) =1 0 " n " 4

0 5" n " 9

# $ %

!

X (k) = x(n) "e

# j "2"$ "k"n

N

n= 0

N#1

%

x(n) =1

N" X (k) "e

j "2"$ "k"n

N

k= 0

N#1

%

!

WN = e

" j #2#$

N

!

X (k) = x(n) "WN

k"n

n= 0

N#1

$

x(n) =1

N" X (k) "W

N

#k"n

k= 0

N#1

$

2


4-PointDFT

4-PointDFT

G[0]

G[1]

G[2]

G[3]

H[0]

H[1]

H[2]

H[3]

W 08

W 18

W 28

W 38

W 48

W 58

W 68

W 78

X[0]

X[1]

X[2]

X[3]

X[4]

X[5]

X[6]

X[7]

x[0]

x[1]

x[2]

x[3]

x[4]

x[5]

x[6]

x[7]

EE 102B: The Fast Fourier Transform (FFT) 9-7

FFT. Algoritmo de decimación temporal

Decimation-in-Time Algorithm

• important: now assume that N = 2ν, where ν is an integer, i.e. thenumber of samples in both time and frequency domains is a power of 2

• if the length of our time-domain sequence is not equal to a power of 2,then simply zero-pad it up to the next power of 2 (we already saw thatzero-padding is not a problem because it only increases spectral density

in the frequency domain)

• now, consider the standard DFT formula:

X [k] =N−1∑n=0

x[n]WknN

=N−1∑n=0

n even

x[n]WknN +

N−1∑n=0

n odd

x[n]WknN

=

N/2−1∑r=0

x[2r]W 2rkN

︸︷︷︸n = 2r

+

N/2−1∑r=0

x[2r + 1]W 2rk+kN

︸︷︷︸n = 2r + 1


=

N/2−1∑r=0

x[2r]WrkN/2

︸︷︷︸G[k]

+WkN

N/2−1∑r=0

x[2r + 1]WrkN/2

︸︷︷︸H[k]

WαN = WN/α

= G[k] + WkNH [k]

• we have decomposed an N -point DFT into two (N/2)-point DFTs plusN multiplies

• originally, the DFT required N 2 complex multiplications

• the new procedure requires 2(N/2)2 + N = 0.5N 2 + N complexmultiplications, and we can easily see that 0.5N 2 + N ≤ N 2 for N ≥ 2

• note that X [k] has to be computed for k = 0, 1, . . . , N − 1, butG[k + N/2] = G[k] and H [k + N/2] = H [k] because both G[k] and H [k]are (N/2)-point DFTs

• the resulting computation can be put into a flowgraph

• here is a sample flowgraph for N = 8:


=

N/2−1∑r=0

x[2r]WrkN/2

︸︷︷︸G[k]

+WkN

N/2−1∑r=0

x[2r + 1]WrkN/2

︸︷︷︸H[k]

WαN = WN/α

= G[k] + WkNH [k]

• we have decomposed an N -point DFT into two (N/2)-point DFTs plusN multiplies

• originally, the DFT required N 2 complex multiplications

• the new procedure requires 2(N/2)2 + N = 0.5N 2 + N complexmultiplications, and we can easily see that 0.5N 2 + N ≤ N 2 for N ≥ 2

• note that X [k] has to be computed for k = 0, 1, . . . , N − 1, butG[k + N/2] = G[k] and H [k + N/2] = H [k] because both G[k] and H [k]are (N/2)-point DFTs

• the resulting computation can be put into a flowgraph

• here is a sample flowgraph for N = 8:


Decimation-in-Time Algorithm

• important: now assume that N = 2ν, where ν is an integer, i.e. thenumber of samples in both time and frequency domains is a power of 2

• if the length of our time-domain sequence is not equal to a power of 2,then simply zero-pad it up to the next power of 2 (we already saw thatzero-padding is not a problem because it only increases spectral density

in the frequency domain)

• now, consider the standard DFT formula:

X [k] =N−1∑n=0

x[n]WknN

=N−1∑n=0

n even

x[n]WknN +

N−1∑n=0

n odd

x[n]WknN

=

N/2−1∑r=0

x[2r]W 2rkN

︸︷︷︸n = 2r

+

N/2−1∑r=0

x[2r + 1]W 2rk+kN

︸︷︷︸n = 2r + 1


Se puede dividir este sumatorio en términos

pares e impares.

Se ha dividido la DFT de orden N en dos de orden N/2. El numero de

multiplicaciones queda reducido de N2 a (N/2)2 +N

Si se toma N potencia de 2 podemos aplicar este procedimiento de forma

iterativa hasta la DFT de orden 2

3


FFT.Algoritmo de decimación temporal

-1

W 08

-1

-1

-1

-1

-1

-1

-1

-1

-1

-1

-1

W 08

W 08

W 08

W 08

W 28

W 08

W 28

W 08

W 18

W 28

W 38

x[0]

x[4]

x[2]

x[6]

x[1]

x[5]

x[3]

x[7] X[7]

X[6]

X[5]

X[4]

X[3]

X[2]

X[1]

X[0]


Ejemplo para N=8

Si no se tienen suficientes datos para

tomar N=2k se puede aplicar la técnica del “zero

padding” ; añadir ceros.

4


FFT. Algoritmo de decimación frecuencialSe plantea un procedimiento análogo al anterior pero ahora en el dominio frecuencial. Considerando la DFT de x(n) de orden N

Decimation-in-Frequency Algorithm

• can obtain another FFT algorithm with equivalent computationcomplexity

• first, start with the basic DFT equation:

X [k] =N−1∑n=0

x[n]WknN

• next, consider the computation of just the even DFT samples:

X [2r] =N−1∑n=0

x[n]W 2rnN

=

N/2−1∑n=0

x[n]W 2rnN +

N−1∑n=N/2

x[n]W 2rnN

=

N/2−1∑n=0

x[n]W 2rnN +

N/2−1∑m=0

x[m + N/2]W 2r(m+N/2)N change of variable in second sum





X [k] =N−1∑n=0

x[n]WknN


X [2r] =N−1∑n=0

x[n]W 2rnN

=

N/2−1∑n=0

x[n]W 2rnN +

N−1∑n=N/2

x[n]W 2rnN

=

N/2−1∑n=0

x[n]W 2rnN +

N/2−1∑m=0






X [k] =N−1∑n=0

x[n]WknN


X [2r] =N−1∑n=0

x[n]W 2rnN

=

N/2−1∑n=0

x[n]W 2rnN +

N−1∑n=N/2

x[n]W 2rnN

=

N/2−1∑n=0

x[n]W 2rnN +

N/2−1∑m=0



Los términos pares de X(k) quedan definidos como




X [k] =N−1∑n=0

x[n]WknN


X [2r] =N−1∑n=0

x[n]W 2rnN

=

N/2−1∑n=0

x[n]W 2rnN +

N−1∑n=N/2

x[n]W 2rnN

=

N/2−1∑n=0

x[n]W 2rnN +

N/2−1∑m=0



Si se realiza un cambio de índices n=m+(N/2)

=

N/2−1∑n=0

(x[n] + x[n + N/2])WrnN/2 using W

2rN/2

N = 1 and W2rnN = W

rnN/2

• notice that the last line is an (N/2)-point DFT of the (N/2)-lengthsequence (x[n] + x[n + N/2]) where 0 ≤ n ≤ N/2 − 1

• similarly, can obtain the odd DFT samples as:

X [2r + 1] =

N/2−1∑n=0

WnN(x[n] − x[n + N/2])Wrn

N/2

• same formula as the one for the even DFT samples except the input

samples are subtracted and the difference is multiplied by the twiddlefactors Wn

N

• for N = 8, can draw this first stage of the algorithm in the following

flowgraph:


Aplicando propiedades de simetría y agrupando términos se llega a

=

N/2−1∑n=0

(x[n] + x[n + N/2])WrnN/2 using W

2rN/2

N = 1 and W2rnN = W

rnN/2

• notice that the last line is an (N/2)-point DFT of the (N/2)-lengthsequence (x[n] + x[n + N/2]) where 0 ≤ n ≤ N/2 − 1

• similarly, can obtain the odd DFT samples as:

X [2r + 1] =

N/2−1∑n=0

WnN(x[n] − x[n + N/2])Wrn

N/2

• same formula as the one for the even DFT samples except the input

samples are subtracted and the difference is multiplied by the twiddlefactors Wn

N

• for N = 8, can draw this first stage of the algorithm in the following

flowgraph:


De forma análoga se tiene para los términos impares lo siguiente

HEMOS CONSEGUIDO USAR LA DFT DE ORDEN N/2 PARA CALCULAR LOS

TÉRMINOS DE LA DFT DE ORDEN N5


W 08

W 08

W 08

W 38

W 28

W 18

-1

-1

-1-1

-1

-1

-1

W 08

W 08

W 28

W 08

-1

-1

-1

-1

-1

W 08

W 28

x[6]

x[7]

x[4]

x[5]

x[2]

x[3]

x[0]

x[1]

X[0]

X[4]

X[2]

X[6]

X[1]

X[5]

X[7]

X[3]


FFT. Algoritmo de decimación frecuencialx [0] X [0]

x [1] X [2]

x [2] X [4]

x [3] X [6]

x [4] X [1]

x [5] X [3]

x [6] X [5]

x [7]WNh [3]

h [2]

h [1]

h [0]

g [3]

g [2]

g [1]

g [0]

X [7]

N2

–1

–1

–1

–1

DFT

– point

N2

DFT

– point

3

WN2

WN1

WN0

Figure 9.17 Flow graph ofdecimation-in-frequency decompositionof an N -point DFT computation into two(N /2)-point DFT computations(N = 8).

From Discrete-Time Signal Processing, 2e by Oppenheim, Schafer, and Buck ©1999-2000 Prentice Hall, Inc.

Tanto en la decimacion temporal como en la

frecuencial el coste de la DFT queda reducido de

N2 a N⋅log2(N).

6


Convolución usando la FFT (I)La aplicación más común de la DFT es para implementar de manera óptima la operación básica en procesado de la señal como es la convolución lineal (recordemos que hay una

convolución circular).La manera de hacerlo es muy sencilla; dadas dos secuencias de longitud N1 y N2 la

convolución lineal va a tener de longitud N1+N2-1. Lo que se hace es rellenar con ceros las dos secuencias hasta que las dos tengan N1+N2-1 términos; evidentemente si se van a

usar las FFT comentadas anteriormente se buscará la potencia de 2 más cercana a ese valor N1+N2-1. Seguidamente se calculan las DFT, se multiplican para, posteriormente,

calcular la DFT inversa del producto; el resultado es la convolución lineal de las dos secuencias.

– multiply X1[k] and X2[k] and compute the inverse FFT of theproduct

• computation of each FFT requires (N/2) log2 N multiplications,multiplication of X1[k] and X2[k] requires N multiplications, andcomputation of the inverse FFT requires N +(N/2) log2 N multiplications

• the total number of multiplications using the FFT is then2N + 1.5N log2 N

• this is much faster than performing direct convolution for long

sequences; example:

N1 N2 N N1N2 − min{N1, N2} 2N + 1.5N log2 N

2 5 8 8 5210 15 32 140 30450 80 256 3,950 3,584

50 1000 2048 49,950 37,888512 10000 16384 5,119,488 376,832


7


Convolución usando la FFT (II)Se ha comentado el método a seguir cuando se quiere usar la DFT para determinar la convolución lineal de dos secuencias finitas y, en principio, no muy largas ¿qué ocurre si no se da esta circunstancia?.

Supondremos, para hacerlo más gráfico que se quiere convolucionar una respuesta impulsional

h(n) de un sistema discreto de longitud M con una secuencia de entrada x(n). Empezaremos por el

método de solapamiento y suma

Figura 5.3: Esquematico para Solapamiento y suma

144

Figura 5.3: Esquematico para Solapamiento y suma

144

Los datos de entrada se tomarán en bloques de longitud L. A cada uno de los bloques se añadirán

M-1 ceros.

Se calculan las DFT de orden N de la nueva secuencia y de h(n), evidentemente hay que añadir

L-1 ceros a h(n). Se multiplican y se calcula la DFT inversa del producto.

Finalmente hay que tener en cuenta el efecto de añadir los ceros; los M-1 últimos términos de la salida para cada bloque deben sumarse a los M-1

primeros términos del siguiente bloque.

8


Convolución usando la FFT (III)El método que expondremos en esta diapositiva

es el método de solapamiento y almacenamiento

Aquí la señal de entrada en cada bloque está solapada con el bloque anterior en los M-1 primeros términos. Además los M-1 últimos términos se solapan (añaden) a los del siguiente bloque. En el primer bloque, evidentemente, hay que añadir M-1 ceros.

Se calculan las DFT de orden N de la nueva secuencia y de h(n), evidentemente hay que añadir L-1 ceros a h(n). Se multiplican y se calcula la DFT inversa del producto.

Finalmente hay que tener en cuenta los efectos del aliasing temporal por lo que los primeros M-1 términos de la salida para cada bloque no deben ser tenidos en cuenta.

Figura 5.1: Esquematico para Solapamiento y almacenamiento

x

Rellenar 0

Rellenar 0 DFTN

DFTN

DFTN

-1

h(n)

x(n)

x1(n)*x2(n)

Figura 5.2: Metodo de calculo de la convolucion lineal usando DFT

143

Figura 5.1: Esquematico para Solapamiento y almacenamiento

x

Rellenar 0

Rellenar 0 DFTN

DFTN

DFTN

-1

h(n)

x(n)

x1(n)*x2(n)

Figura 5.2: Metodo de calculo de la convolucion lineal usando DFT

143

9


Algoritmo de Goertzel (I)Este algoritmo es apropiado cuando no se quieren calcular todos los términos de la

DFT de orden N. Una aplicación típica de este caso es la conocida como DTMF

(Dual Tone Multi-Frequency).

Se utiliza cuando se cumple que M≤log2 (N) siendo M el número de términos a determinar y N el

orden de la DFT.

6.3.1. Algoritmo de Goertzel

El algoritmo de Goertzel explota la periodicidad de los factores de

fase {WkN} y nos permite expresar el calculo de la DFT como una

operacion de filtrado lineal.

Tenemos:

X(k) =N−1∑n=0

x(n)WknN

Si multiplicamos por W−kNN = −1:

X(k) = W−kNN

N−1∑m=0

x(m)WkmN =

N−1∑m=0

x(m)W−k(N−m)N

que tiene una forma clara de convolucion.(!)

Si definimos la secuencia:

yk(n) =N−1∑m=0

x(m)W−k(N−m)N

decimos que esta es la salida de una convolucion de la secuencia de

entrada x(n) por un filtro de respuesta impulsional :

hk(n) = W−knN u(n)

La salida de este filtro en n = N da el valor de la DFT en la

frecuencia wk = 2πk/N : X(k) = yk(n)|n=N .

El filtro con resp. impuls. hk(n) tiene por funcion de transferencia:

Hk(z) =1

1−W−kN z−1

que tiene un polo sobre la circunferencia unidad a la frecuencia

(equidistante) wk = 2πk/N .

169





Tenemos:

X(k) =N−1∑n=0

x(n)WknN


X(k) = W−kNN

N−1∑m=0

x(m)WkmN =

N−1∑m=0

x(m)W−k(N−m)N



yk(n) =N−1∑m=0

x(m)W−k(N−m)N







Hk(z) =1

1−W−kN z−1



169

Sólo hemos multiplicado

por 1 !!!!!

si se define la secuencia





Tenemos:

X(k) =N−1∑n=0

x(n)WknN


X(k) = W−kNN

N−1∑m=0

x(m)WkmN =

N−1∑m=0

x(m)W−k(N−m)N



yk(n) =N−1∑m=0

x(m)W−k(N−m)N







Hk(z) =1

1−W−kN z−1



169

Se observa entonces que esta secuencia es la salida de un filtro de entrada x(n) y

respuesta impulsional hk (n) con





Tenemos:

X(k) =N−1∑n=0

x(n)WknN


X(k) = W−kNN

N−1∑m=0

x(m)WkmN =

N−1∑m=0

x(m)W−k(N−m)N



yk(n) =N−1∑m=0

x(m)W−k(N−m)N







Hk(z) =1

1−W−kN z−1



169

Conclusión importante a destacar es que X(k)=yk(N)

Tomando Transformadas Z se llega a





Tenemos:

X(k) =N−1∑n=0

x(n)WknN


X(k) = W−kNN

N−1∑m=0

x(m)WkmN =

N−1∑m=0

x(m)W−k(N−m)N



yk(n) =N−1∑m=0

x(m)W−k(N−m)N







Hk(z) =1

1−W−kN z−1



169

¿dónde tiene los polos/ceros H(z)?

10


Algoritmo de Goertzel (II)

IMPORTANTE: Por tanto, toda la DFT se puede calcular pasando

los datos por un banco de N filtros de un solo polo (resonadores)

en paralelo, donde cada filtro tiene su polo a la frecuencia corres-

pondiente de la DFT.

Los datos se tienen que introducir de forma inversa.

IDEA de la IMPLEMENTACAO: En lugar de calcular la DFT

mediante convolucion, lo hacemos empleando la recurrencia de la

ecuacion en diferencias:

yk(n) = W−kN yk(n− 1) + x(n), yk(−1) = 0

La salida deseada es X(k) = yk(N) para k = 0, 1, . . . , N − 1.

Luego tenemos una estructura anidada repetitiva de la forma Y ←−Ax+B con la ventaja de que los DSPs pueden realizar un producto

y una suma en un solo pulso de reloj.

Hk(z) es una operacion compleja que puede pasar a ser eficiente

combinando pares de resonadores con polos complejos conjugados.

Esto nos lleva a filtros de dos polos con funciones de transferencia

de la forma:

Hk(z) =1−W−k

N z−1

1− 2cos(2πk/N)z−1 + z−2

Las ecuaciones en diferencias son:

vk(n) = 2cos(2πk/N)vk(n− 1)− vk(n− 2) + x(n)

yk(n) = vk(n)−WkNvk(n− 1)

170

Si determinamos la ecuación en diferencias a partir de H(z) llegaríamos a

Esta ecuación en diferencias no es eficiente por 2 razones fundamentales; tenemos que calcular todos los yk(n) ya que nos interesa el último y aparecen multiplicaciones

complejas (donde cada una de ellas equivalen a 4 reales) en todos los paso intermedios









yk(n) = W−kN yk(n− 1) + x(n), yk(−1) = 0







de la forma:

Hk(z) =1−W−k

N z−1

1− 2cos(2πk/N)z−1 + z−2




170









yk(n) = W−kN yk(n− 1) + x(n), yk(−1) = 0







de la forma:

Hk(z) =1−W−k

N z−1

1− 2cos(2πk/N)z−1 + z−2




170

Si se plantea una estructura canónica las ecuaciones en diferencias son:

Donde la última ecuación sólo se calcula para n=N.

x [n]

–1

z–1

z–1

2 cos 2!kN –WN

yk[n]

k

Figure 9.2 Flow graph of second-order recursive computation of X [k](Goertzel algorithm).

From Discrete-Time Signal Processing, 2e by Oppenheim, Schafer, and Buck ©1999-2000 Prentice Hall, Inc.

La solución pasa por multiplicar numerador/denominador de H(z) por

la expresión:









yk(n) = W−kN yk(n− 1) + x(n), yk(−1) = 0







de la forma:

Hk(z) =1−W−k

N z−1

1− 2cos(2πk/N)z−1 + z−2




170









yk(n) = W−kN yk(n− 1) + x(n), yk(−1) = 0







de la forma:

Hk(z) =1−W−k

N z−1

1− 2cos(2πk/N)z−1 + z−2




170

Se llega entonces a la siguiente expresión.

11

Documents

Transformada Discreta de Fourier II - uv.es · en 4N multiplicaciones reales. N-1 sumas de números complejos. Para calcular los N términos tenemos que hacer N veces las anteriores