Dft-fft 1w1v6a

Transformada Discreta de Fourier (DFT) Señal Real x(n), n=0,1…,N-1

Valores complejos

Señal Discreta 1.5

N 1

X(k )   x (n )e

j

2 kn N

,

k  0,..., N  1, (DFT)

n 0

1

X p (k )

0.5

Procesamiento en Frecuencia

DFT

0

x p (n), n  0,1,..., N  1

IDFT

-0.5

-1

0

2

4

6

8

10

12

14

16

18

n

X(k )  X(k ) e 

Bloque de N=16 muestras

j ( k )  Fase

x p (n )   X p (k )e

j

2 kn N

n  0,....N  1 (IDFT)

,

k 0

Módulo

Región de Interés

Región de Interés

Espectro de Módulo

N 1

Espectro de Fase Espectro de Fase

Espectro de Magnitud

3

4.5 4

2

3.5 3

1 2.5 2

0

1.5

-1

1 0.5

-2 0 -0.5

Centro de antisimetría 0

5

10 k

Centro de simetría

Bloque de N=16 frecuencias

15

0

5

10

15

k

Bloque de N=16 frecuencias

Prof. Dr. Guillermo Kemper

Transformada Discreta de Fourier (DFT) Señal Real x(n), n=0,1…,N-1

Valores complejos

Señal Discreta 1.5

N 1

X(k )   x (n )e

j

2 kn N

,

k  0,..., N  1, (DFT)

n 0

DSP 1

X p (k )

0.5

Procesamiento en Frecuencia

DFT

0

x p (n), n  0,1,..., N  1

IDFT

-0.5

-1

0

2

4

6

8

10

12

14

16

18

X( k )  X R (k )  j X I ( k )   Parte Re al

n

Bloque de N=16 muestras

Parte Im aginaria

Región de Interés

Espectro de la parte Real

N 1

x p (n )   X p (k )e

j

2 kn N

n  0,....N  1 (IDFT)

,

k 0

Región de Interés

Espectro de la parte Imaginaria (antisimétrica)

(simétrica)

Espectro de la Parte Imaginaria

Espectro de la Parte Real 8

8

6

6 4

4 2

2

0

0

-2

-2

-4

-4

-6

Centro de antisimetría

-8

-6

0

0

Centro de simetría

5

10 k

Bloque de N=16 frecuencias

15

5

10

15

k

Bloque de N=16 frecuencias

Prof. Dr. Guillermo Kemper

Transformada Discreta de Fourier (DFT): Algunos comentarios

La transformada de Fourier de un bloque de señal real discreta x(n) de “N” muestras resulta en una función discreta compleja X(k) de N valores (Tamaño de la transformada: N muestras por periodo de espectro). El modulo de X(k) es un función discreta de “N” valores con centro de simetría ( función par). La fase de X(k) es un función discreta de “N” valores con centro de antisimtería (función impar). Si se desdobla X(k) en una función discreta correspondiente a la parte real y una función discreta correspondiente a la parte imaginaria, entonces la parte real presentará centro de simetría (función par) y la parte imaginaria centro de antisimetría (función impar). Si se procesa el espectro X(k) para obtener el espectro procesado Xp(k), este tiene que satisfacer las condiciones anteriores para que al aplicar la transformada inversa se obtenga una señal real discreta xp(n). De lo contrario la señal resultante xp(n) seria también compleja. conjugado

También se verifica que X(k)=X *(N-k) cuando x(n) es real.

El calculo de la DFT desgasta excesiva carga computacional por lo que su implementación es hecha vía la FFT (Fast Fourier Transform) y la IFFT (Inversa). Esto obliga a que el numero de componentes “N” sea potencia de 2.

Prof. Dr. Guillermo Kemper

Transformada Discreta de Fourier (DFT): Resolución

N :Tamaño de la Transformada (muestras por periodo) X(k)

N=8

f 

0

1 2

3 4 5

6

7 8

9 10 11 12 13

k

0

 2 3  5 6 7 2

 (rad)

0

f 2f 3f fs/2 5f 6f 7f

f (Hz)

fs

Región de interés

Numero de muestras en la región de interés (incluyendo “”) : N/2 + 1 Numero de muestras en la región de interés (sin incluir “”) : N/2

=2/N (rad)

f=fs/N (Hz)

Resolución de la transformada Prof. Dr. Guillermo Kemper

Transformada Discreta de Fourier (DFT): Carga Computacional N 1

X(k )   x (n )e

j

2 kn N

,

k  0,..., N  1, (DFT)

n 0

DFT vía “Fuerza Bruta” No. de multiplicaciones complejas: N2 No. de adiciones complejas: N(N-1)

equivalente equivalente

No. de multiplicaciones reales: 4N2 No. de adiciones reales: 2N(N-1)

DFT vía FFT (Fast Fourier Transform) equivalente

No. de multiplicaciones complejas: (N/2)log2N No. de adiciones complejas: Nlog2N

No. de multiplicaciones reales: 2Nlog2N equivalente

No. de adiciones reales: 2Nlog2N

Para que funcione la FFT, el tamaño de la transformada “N” tiene que ser una potencia de 2.

Prof. Dr. Guillermo Kemper

DFT (Fuerza Bruta) vs FFT

Prof. Dr. Guillermo Kemper

Proceso FFT (N=8)

Prof. Dr. Guillermo Kemper

Transformada Discreta de Fourier (DFT): Carga Computacional 1 Nodo

Árbol del Proceso FFT (decimación en el tiempo) : N=8

WN  e W e p N

j

2 N

j

2 p N

No. de Etapas de la FFT  log 2 N Variación del exp onente " p" en cada grupo de una det er min ada etapa: N p  No. de la etapa 2

Etapa 1

Etapa 2

Etapa 3

Prof. Dr. Guillermo Kemper