Fast fourier transform

Procesamiento de señales digitales

Profesor Gabriel Ordóñez Plata gaby@uis.edu.co Escuela de Ingenierías Eléctrica, Electrónica y de Telecomunicaciones.

Cómputo eficiente de la Transformada Discreta de Fourier DFT
Ecuación de Análisis

X k  



N 1 n0

x[ n ] W Nkn

Ecuación de Síntesis

1 x[ n ]  N

 X k W
k 0

N 1

k kn N

Procesamiento de señalesdigitales

Cómputo eficiente de la Transformada Discreta de Fourier DFT
kn kn  Re x[ n ]Re W Nk  Im x[ n ]Im W Nk   X k      kn kn e  Im x[ n ]Re W N  e n  0  j Re x [ n ]Im W N   N 1















  

Para obtener uno de los armónicos X[k] se requieren:  4N multiplicaciones reales  4N-2 Sumas reales 4N 2 La obtención de los N armónicos dex[n] requiere de:  4N2 multiplicaciones reales  N(4N-2) Sumas reales

Procesamiento de señales digitales

Cómputo eficiente de la Transformada Discreta de Fourier DFT La mayoría de los procedimientos para mejorar la eficiencia en los cálculos de la DFT tienen en cuenta las propiedades de periodicidad y simetría de W Nkn  W
k  N n N

W

kn N

W

 

kn * N

(complejaconjugada simétrica)

kn k n  WN  WN nN   WN k N 

(periodicidad en n y k)

Procesamiento de señales digitales

Cómputo eficiente de la Transformada Discreta de Fourier DFT

Algoritmo de Goertzel
FILTRO RESONANTE F0 X[0]

x[n]

FILTRO RESONANTE F1

X[1]

FILTRO RESONANTE F2

X[2]

FILTRO RESONANTE Fn

X[n]

ALGORITMO GOERTZEL

Procesamiento de señales digitalesCómputo eficiente de la Transformada Discreta de Fourier DFT

Algoritmo de Goertzel

W

kN N

e
 kN N

j  2 / N  Nk
km N

e

j 2k

1

X [k ]  W

m 0

 x[m]W

N 1

   x[m]WN k ( N  m ) m 0

N 1

yk [ n] 

X [k ]  yk n  n  N
hk [n]  W
 kn N

m  

 xmW



k ( nm) N

un  m

u[n]

Procesamiento de señalesdigitales

Cómputo eficiente de la Transformada Discreta de Fourier DFT

Algoritmo de Goertzel
H k [ z ]  Z {W
 kn N

1 un}  1  1 WN k Z 1

Y [z ] [z H k [ z]   Y [ z]  H k [ z]X [ z] X [ z]

1W z H k ( z)  1 2 1  2 cos(2k / N ) z  z
k N

1

Procesamiento de señales digitales

Cómputo eficiente de la Transformada Discreta de Fourier DFT

Algoritmo de Goertzelx[n]

+
Z-1 2cos(2k/N) k -WN

+

yk[n]

+
Z-1 -1

Procesamiento de señales digitales

Cómputo eficiente de la Transformada Discreta de Fourier DFT Algoritmos de FFT mediante diezmado en el tiempo
X k  
X k  
X [k ] 



N 1 n0

x[ n ] W Nkn

n par
N / 2 1



x[ n ] W Nkn 
x[2r ]W
2 rk N

n impar



x[ n ] W Nkn


r 0



N / 2 1 r 0 x[2r  1]WN2 r 1k 
2 WN  WN / 2

X [k ] 

N / 2 1


r 0

kr k x[2r ]WN / 2  WN

N / 2 1 r 0

kr x[2r  1]WN / 2 

X [ k ]  F1[ k ]  W F2 [ k ]
k N

Procesamiento de señales digitales

Cómputo eficiente de la Transformada Discreta de Fourier DFT Algoritmos de FFT mediante diezmado en el tiempo
k X [k ]  F1[k ]  WN F2 [k ]
k X [ k  N / 2]  F1[ k ]  WN F2 [k ]

k  0,1,...,

N 1 2

Se requieren (N/2)2 multiplicaciones complejas para calcular F1[k] y otro tanto el cálculo de F2[k] La multiplicación del factor de fase agrega otras N/2 multiplicaciones m ltiplicaciones Para el cálculo total de X[k] se requieren 2(N/2)2 + N/2 multiplicaciones complejas En el primer paso del paso del algoritmo se pasa de N2 multiplicaciones complejas a N2/2 + N/2.Procesamiento de señales digitales

Cómputo eficiente de la Transformada Discreta de Fourier DFT Algoritmos de FFT mediante diezmado en el tiempo

v11[n]  f1[2n] v12[n]  f1[2n 1] v21[n]  f2[2n] v22[n]  f2[2n 1] N n  0,1,...., 1 4

k F [k] V11[k] WNV12[k] 1 k F [k  N / 4] V11[k] WNV12[k] 1

F [k] V21[k] W V [k] 1
k N / 2 22

F [k  N / 4] V11[k] W V [k] 1
k N /...