Módulo 2.
1: Transformada discreta de Fourier (DFT)
Juan P. Ugarte Macías
Objetivos
— Introducir la definición de transformada discreta de Fourier y sus
propiedades
— Entender el concepto de zero-padding y su utilidad
— Introducir el concepto de FFT
— Introducir el concepto de windowing
— Introducir otras transformadas discretas
Juan P. Ugarte Macías Módulo 2.1: DFT 1 / 74
Transformada discreta de Fourier
Definición
La transformada discreta de Fourier (DFT) se define como:
N→1
!
DFT {x(n)} = X (k) = x(n)e →j2ωkn/N
n=0
para k = 0, 1, 2, . . . , N → 1
x(n) = 0 para n ↑
/ 0↓n ↓N →1
!ω = 2ε/N
Existen N muestras de frecuencia en el periodo →ε ↓ ω ↓ ε
Juan P. Ugarte Macías Módulo 2.1: DFT 2 / 74
Transformada discreta de Fourier
¿Cuál es el efecto de discretizar (muestrear) el dominio de la
frecuencia?
Sea xp una extensión periódica de la señal original x(n):
Juan P. Ugarte Macías Módulo 2.1: DFT 3 / 74
Transformada discreta de Fourier
¿Cuál es el efecto de discretizar (muestrear) el dominio de la
frecuencia?
xp tiene un periodo T = N!t. Los coeficientes de la serie de Fourier
son: "
1 T
Xk = xp (t)e →j2ωkt/T dt
T 0
Entonces:
N→1
1 !
Xk = x(n!t)e →j2ωkn!t/T !t
T
n=0
Haciendo T /!t = N, x(n!t)!t = x(n):
N→1
1 !
Xk = x(n)e →j2ωkn/N
T
n=0
Por lo tanto: X (k) = TXk
Juan P. Ugarte Macías Módulo 2.1: DFT 4 / 74
Transformada discreta de Fourier
Transformada inversa discreta de Fourier (IDFT)
La IDFT se define como:
N→1
1 !
IDFT {X (k)} = x(n) = X (k)e j2ωnk/N
N
k=0
para 0 ↓ n ↓ N → 1
Por definición el resultado de la IDFT cumple:
N→1
1 !
x(n + N) = X (k)e j2ω(n+N)k/N = x(n)
N
k=0
Juan P. Ugarte Macías Módulo 2.1: DFT 5 / 74
Transformada discreta de Fourier
Ejemplos
Si x(n) = 2 cos(2εn/8) para 0 ↓ n ↓ 7 y x(n) = 2 cos(2εn/16) para
0 ↓ n ↓ 7, graficar las correspondientes señales periódicas
IDFT {DFT {x(n)}} con N = 8 sin calcular las DFT.
Para una señal x(n) = [1, 1/2, →1, 1/2], calcular la DFT con N = 4.
¿Cuál es la IDFT para n = →2?
Juan P. Ugarte Macías Módulo 2.1: DFT 6 / 74
Transformada discreta de Fourier
Forma matricial de la DFT
X (0) 1 1 ··· 1 x(0)
X (1) 1 e →j
2ω
··· e →j
2ω(N→1)
x(1)
N N
.. = . .. .. .. ..
.
.. . . .
.
2ω(N→1) 2ω(N→1)(N→1)
X (N → 1) 1 e →j N ··· e →j N x(N → 1)
X = Wx
con:
1 1 ··· 1
1
WN1 ··· WNN→1
W = .. .. .. ..
. . . .
(N→1) (N→1)(N→1)
1 WN ··· WN
donde:
WNk = e →j2ωk/N
Juan P. Ugarte Macías Módulo 2.1: DFT 7 / 74
Transformada discreta de Fourier
Forma matricial de la DFT
X (0) 1 1 ··· 1 x(0)
X (1) 1 e →j N
2ω
··· e →j
2ω(N→1)
x(1)
N
.. = .. .. .. .. ..
. . . . . .
2ω(N→1) 2ω(N→1)(N→1)
X (N → 1) 1 e →j N ··· e →j N x(N → 1)
X = Wx
Número de adiciones: N(N → 1)
Número de multiplicaciones (N → 1)2
El orden del número de multiplicaciones y adiciones: N 2
La IDFT:
1
x = W →1 X , W →1 = W̄
N
Juan P. Ugarte Macías Módulo 2.1: DFT 8 / 74
Propiedades de la DFT
Propiedades de la DFT I
Desplazamiento en tiempo:
DFT {x(n → n0 )} = X (k)e →j2ωkn0 /N
donde el periodo básico de la señal origina x(n) es
n0 ↓ n ↓ N → n0 → 1
Señal modulada:
DFT {x(n)e j2ωnk0 /N } = X {k → k0 }
Si x(n) es real entonces: X̄ (k) = X (N → k)
Si la DFT es real entonces: x̄(n) = x(N → n)
Juan P. Ugarte Macías Módulo 2.1: DFT 9 / 74
Propiedades de la DFT
Propiedades de la DFT II
Teorema de Parseval, para señales periódicas relaciona la energía en
los dominios del tiempo y la frecuencia:
N→1
! N→1
1 !
|x(n)|2 = |X (k)|2
N
n=0 k=0
Convolución de dos señales periódicas x(n) y h(n):
N→1
!
y (n) = x(m)h(n → m)
m=0
entonces la convolución circular:
Y (k) = DFT {y (n)} = X (k)H(k)
Juan P. Ugarte Macías Módulo 2.1: DFT 10 / 74
Propiedades de la DFT
Ejemplo
Sea la señal discreta x(n) = u(n) → u(n → 5). Calcular x(n) ↔ x(n).
Extender la señal con periodo N = 7. Calcular la convolución circular.
Comparar los resultados. ¿Cuánto debe ser el periodo N para que
ambos cálculos coincidan?
Juan P. Ugarte Macías Módulo 2.1: DFT 11 / 74
Propiedades de la DFT
Ejemplo
Juan P. Ugarte Macías Módulo 2.1: DFT 12 / 74
Propiedades de la DFT
Cálculo de la convolución por DFT I
Sea x(n) de longitud M y h(n) de longitud L. Entonces
y (n) = x(n) ↔ h(n) tiene longitud M + L → 1
Para el cálculo de la convolución circular, las longitudes de cada señal
N ↗M +L→1
Caso contrario ocurre aliasing
Juan P. Ugarte Macías Módulo 2.1: DFT 13 / 74
Propiedades de la DFT
Cálculo de la convolución por DFT II
Sea x(n) de longitud M y h(n) de longitud L. Si M >> L, la
convolución directa después de L → 1 muestras:
n
!
y (n) = x(m)h(n → m)
m=n→L+1
Para convolución circular, la señal x(n) se parte en secuencias de
longitud N que no se superponen:
K
! →1
x(n) = xk (n)
k=0
donde xk (n) = x(n)[u(n → kN) → u(n → (k + 1)N))]
Juan P. Ugarte Macías Módulo 2.1: DFT 14 / 74
Propiedades de la DFT
Cálculo de la convolución por DFT II
Juan P. Ugarte Macías Módulo 2.1: DFT 15 / 74
Propiedades de la DFT
Cálculo de la convolución por DFT III
Juan P. Ugarte Macías Módulo 2.1: DFT 16 / 74