Introducción al Análisis de Fourier

Transformada de Fourier discreta

Dr. Wilfrido Gómez Flores

 Señal discreta

La transformada de Fourier discreta (DFT) trata con señales discretas

compuestas de N puntos separados por un intervalo T .

Consecuentemente, DFT trata con un número nito de frecuencias:

2π
ωu = u, u = 0, 1, . . . , N − 1, (1)
NT
donde u es la variable de frecuencia.

1/32 Transformada Fourier de discreta FIC-05

 Señal discreta

La transformada de Fourier puede ser evaluada sobre un intervalo nito

de tiempo en vez de −∞ a ∞, es decir, para funciones periódicas. De
manera similar, debido a que solo existe un número nito de puntos, la
DFT asume periodicidad de la señal.

2/32 Transformada Fourier de discreta FIC-05

 Denición de DFT
• La DFT se dene en su forma más elemental cuando T = 1.
• De este modo, el par de transformadas de Fourier discretas son:

N −1
X j2πuk
F (u) = f (k)e− N , para u = 0, 1, . . . , N − 1, (2)
k=0

N −1
1 X j2πuk
f (k) = F (u)e N , para k = 0, 1, . . . , N − 1. (3)
N
u=0

• Las expresiones (2) y (3) se pueden representar por los operadores

F[f (k)] y F −1 [F (u)], respectivamente.

3/32 Transformada Fourier de discreta FIC-05

 Denición de DFT
• La DFT y su inversa son periódicas con periodo N, de modo que:

f (k + N ) = f (k) y F (u + N ) = F (u). (4)

• La DFT se puede expresar de forma polar como:

F (u) = |F (u)| ejφ(u) , (5)

donde q
|F (u)| = Re2 [F (u)] + Im2 [F (u)] (6)

y  
−1 Im[F (u)]
φ(u) = tan (7)
Re[F (u)]
son la magnitud y el ángulo de fase, respectivamente.
4/32 Transformada Fourier de discreta FIC-05
 Denición de DFT

(a) Pulso rectangular con N puntos. (b) Espectro de magnitud con N

puntos. (c) Simetría par del espectro de magnitud: |F (u)| = |F (−u)|.
(d) Simetría impar del espectro de fase: −φ(u) = φ(−u)

5/32 Transformada Fourier de discreta FIC-05

 Denición de DFT
• La DFT representa una combinación lineal y puede escribirse en
forma matricial como:

    
1 1 1 1 ··· 1 f (0) F (0)
2 3 N −1
1 WN WN WN ··· WN f (1) F (1)
    
    
 2 4 6 N −2    

 1 WN WN WN ··· WN 
 f (2) =
  F (2) 

. . . . .. . . .
. . . . . . .
    
. . . . . . . .
    
    
N −1 N −2 N −3
1 WN WN WN ··· WN f (N − 1) F (N − 1)
(8)

donde WN = exp(−j2π/N ) y WN = WN2N .

• El par de transformadas DFT se pueden reescribir como:

N −1 N −1
X 1 X
F (u) = f (k)WNuk y f (k) = F (u)WN−uk (9)
N
k=0 u=0

para u = 0, 1, . . . , N − 1 y k = 0, 1, . . . , N − 1, respectivamente.

6/32 Transformada Fourier de discreta FIC-05

 Denición de DFT
0 10 20 30 40 50 60
0
1
10

20

30
10 20 30 40 50 60
40

50

60 -1

0 10 20 30 40 50 60
0
1
10

20

30
10 20 30 40 50 60
40

50

60 -1

En (9), los coecientes DFT son coecientes de proyección de un

vector-señal sobre N señales bases sinusoidales: (a) Re[WNuk ] y
(b) Im[WNuk ], con N = 64 y señal sinusoidal para u = 4.
7/32 Transformada Fourier de discreta FIC-05
 Denición de DFT

DFT de la función f (k) = 5+8
cos 2πk − π2 +4 cos (4πk)+2 cos 8πk − π



2
+
cos (16πk) + 2 cos 32πk − π2 . Solo se muestra la parte real de WN
uk
.○

8/32 Transformada Fourier de discreta FIC-05

 Ejemplo
Considere la señal continua:

π
f (t) = 5 + 2 cos(2πt − )
2
+ 3 cos(4πt)

k
muestreada a fs = 4 Hz en el rango [0, 1], con t = kTs = fs :

 π
5 + 2 cos 2πk −
f (k) = |{z} + 3 cos (4πk),
2 } | {z }
DC | {z 2Hz
1Hz

lo cual genera una señal discreta con N =5 muestras:

f (k) = [8, 4, 8, 0, 8].

9/32 Transformada Fourier de discreta FIC-05

 Ejemplo
A partir de (8) se obtienen los siguientes coecientes de Fourier:

F (u) = [28, 5.23 + j0.89, 0.76 + j9.95, 0.76 − j9.95, 5.23 − j0.89]

Los coecientes son complejos y, a excepción de F (0), cada coeciente posee su

complejo conjugado en el intervalo [0, N − 1]. Asimismo, es común gracar un
periodo del espectro en el intervalo [−N/2, N/2], donde F (0) queda centrado
en el origen. ○

10/32 Transformada Fourier de discreta FIC-05

 Ejemplo

Si la frecuencia de muestreo fs aumenta, también incrementa el número de

puntos, de modo que la señal discreta se aproximará cada vez más a la señal
original y, por tanto, el cálculo de los coecientes de Fourier será cada vez más
exacto. ○

11/32 Transformada Fourier de discreta FIC-05

 Propiedades

Propiedad Función en tiempo Función en frecuencia

Linealidad a1 f1 (k) + a2 f2 (k) a1 F1 (u) + a2 F2 (u)

Periodicidad f (k) = f (k + N ) F (u) = F (u + N )
1 u


Escalamiento f (ak) |a| F a
j2πuk0
Desplazamiento en tiempo f (k − k0 ) F (u)e− N
j2πu0 k
Desplazamiento en frecuencia f (k)e N F (u − u0 )
Desplazamiento al origen f (k)(−1)k F (u − N2 )
Inversión f (−k) F (−u)
dn [f (k)]
Diferenciación n (ju)n F (u)
Pdk
N −1 1 PN −1
Relación de Parseval k=0 |f (k)|2 N u=0 |F (u)|
2

Teorema de convolución f (k) ∗ h(k) F (u)H(u)

12/32 Transformada Fourier de discreta FIC-05

 Funciones de ventana

Topología circular de la DFT: (a) señal periódica f (k) = 2 + sin(2k − π2 ) +

cos( k2 ) − 2 cos2 (2k + π4 ) registrada durante un periodo completo en el rango
[0, 4π], y (b) magnitud del espectro. Cuando la señal es periódica y se registra
durante un número entero de periodos, la DFT representa adecuadamente las
componentes de frecuencia de la señal.

13/32 Transformada Fourier de discreta FIC-05

 Funciones de ventana

(a) Señal periódica f (k) registrada durante una fracción de un periodo, se

genera una señal aperiódica produciendo una discontinuidad entre periodos.
(b) Magnitud del espectro de Fourier, se generan componentes de alta
frecuencia producto de la discontinuidad de f (k).

14/32 Transformada Fourier de discreta FIC-05

 Funciones de ventana

Para reducir los efectos de las discontinuidades, se usan funciones de ventana para
reducir la amplitud de las discontinuidades en los límites de una señal discreta.
(a) Señal original f (k) multiplicada por una función de ventana w(k). (b) Magnitud
del espectro de Fourier donde se observa que la amplitud de componentes de alta
frecuencia es cero.

15/32 Transformada Fourier de discreta FIC-05

 Funciones de ventana
Funciones de ventana típicas w(k) para 0 ≤ n ≤ N − 1:
• Blackman:
   
2πn 4πn
w(k) = 0.42 − 0.5 cos + 0.08 cos .
N N

• Flat Top:

  
2πn 4πn
w(k) = a0 − a1 cos + a2 cos −
N N
   
6πn 8πn
a3 cos + a4 cos ,
N N

donde a0 = 0.21557895, a1 = 0.41663158, a2 = 0.277263158,

a3 = 0.083578947 y a4 = 0.006947368.
16/32 Transformada Fourier de discreta FIC-05
 Funciones de ventana
Funciones de ventana típicas w(k) para 0 ≤ n ≤ N − 1:
• Gaussian: (  )
1 n − N/2 2

w(k) = exp − ,
2 σN/2

donde σ>0 es el ancho de banda.

• Hamming:  
2πn
w(k) = 0.54 − 0.46 cos .
N
• Hann:   
2πn
w(k) = 0.5 1 − cos .
N

17/32 Transformada Fourier de discreta FIC-05

 Funciones de ventana

Blackman Flat top Gaussiano Hamming Hann

Funciones de ventana y su respuesta en frecuencia.

18/32 Transformada Fourier de discreta FIC-05

 DFT de corta duración
• La DFT de corta duración (STFT) es una secuencia de DFTs de

una señal en ventana.

• STFT provee información de frecuencia localizada en el tiempo.

• La STFT está dada por:

M −1
X j2πuk
Fm (u) = f (k) w (k − mR) e− M , para u = 0, 1, . . . , M −1,
k=0
(10)

donde f (k) es una señal y w(k) denota una función de ventana

con M R es el tamaño de salto entre DFT sucesivos tal

puntos,

que el espectro Fm (u) es la DFT de una señal en ventana centrada

en el tiempo mR.

19/32 Transformada Fourier de discreta FIC-05

 DFT de corta duración

20/32 Transformada Fourier de discreta FIC-05

 DFT de corta duración
La magnitud al cuadrado de la STFT produce la representación del

espectrograma de la densidad espectral de potencia de f (k):

espectrograma {f (k)} ≡ |Fm (u)|2 . (11)

Comparación de resolución STFT. La izquierda tiene una mejor resolución

de tiempo y la derecha tiene una mejor resolución de frecuencia.
21/32 Transformada Fourier de discreta FIC-05
 DFT de corta duración

ms

dB/Hz
Hz

-50

-100

ms

dB/Hz
Hz

-50

-100

ms

Espectrogramas de la función chirp para diferentes tamaños de ventana.

22/32 Transformada Fourier de discreta FIC-05
 DFT de corta duración
0.5 4000 20
A 0
-20
0 2000
-40
-60
-0.5 0 -80
0.5 4000 20
E 0
-20
0 2000
-40
-60
-0.5 0 -80
0.5 4000 20
I 0
-20
0 2000
-40
-60
-0.5 0 -80
0.5 4000 20
O 0
-20
0 2000
-40
-60
-0.5 0 -80
0.5 4000 20
U 0
-20
0 2000
-40
-60
-0.5 0 -80
0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.05 0.1 0.15 0.2 0.25 0.3

23/32 Transformada Fourier de discreta FIC-05

 Transformada rápida de Fourier

DFT
FFT
Numero de operaciones

Numero de puntos (N)

La DFT realiza N 2 operaciones, mientras que la transformada rápida de

Fourier (FFT) reduce a N log2 N operaciones.

24/32 Transformada Fourier de discreta FIC-05

 Transformada rápida de Fourier

La FFT aprovecha las propiedades de simetría y periodicidad del

−j2πa
factor WNa = e N para reducir el número de operaciones.

WN6 = WN14 = …
W =W =…
5
N
13
N
WN7 = WN15 = …

WNa+N = WNa WNN =1

a+N/2 WN4 = WN12 = … WN0 = WN8 = …
WN = −WNa WN2 = WN/2
WN3 = WN11 = … WN1 = WN9 = …
WN = WN = …
2 10

Para N = 8

25/32 Transformada Fourier de discreta FIC-05

 Transformada rápida de Fourier
La FFT-DIT (radix-2 decimation in time) divide la señal en dos gru-

pos de índices pares e impares para realizar dos DFTs de tamaño

N/2 y combina sus resultados para formar la DFT de N puntos:

N/2−1 N/2−1
X X
uk
F (u) = f (2k)WN/2 + WNu uk
f (2k + 1)WN/2
k=0 k=0

= E(k) + WNu O(k), (12)

a+N/2
y de acuerdo con la propiedad de simetría WN = −WNa :

F (u + N/2) = E(k) − WNu O(k), (13)

donde E(k) es la DFT para índices pares y O(k) es la DFT para

índices impares.
26/32 Transformada Fourier de discreta FIC-05
 Transformada rápida de Fourier

f(0) + A = f (0) + W20 f (2)

W20
f(2) × −1 + B = f (0) − W20 f (2)

f(1) + C = f (1) + W20 f (3)

W20
f(3) × −1 + D = f (1) − W20 f (3)

Etapa 1

FFT-DIT para N = 4. ○

27/32 Transformada Fourier de discreta FIC-05

 Transformada rápida de Fourier
f(0) + + + F(0)
W20
f(4) × −1 + + + F(1)
0
W4
f(2) + ×−1 + + F(2)
W20 W41
f(6) ×
−1
+ ×−1 + + F(3)
W80
−1
f(1) + + × + F(4)
W20 W81
−1
f(5) × −1 + + × + F(5)
0
W4 W82
−1
f(3) + ×−1 + × + F(6)
W20 W4 1
W83
−1
f(7) × −1 + ×−1 + × + F(7)

FFT-DIT para N = 8.

28/32 Transformada Fourier de discreta FIC-05

 Transformada rápida de Fourier
Input: Array g of size N = 2n
Output: Fourier coecients array g of size N = 2n
1 g
Apply bit-reversal permutation to
2 ∆←1
3 n ← log2 N
4 for pass = 1 . . . n do

5 W ← exp(−j2π/2∆)
6 for (a = 0; a < ∆; a + +) do

7 for (b = 0; b < N ; b += 2∆) do

8 t0 ← g(b + a) + W a g(b + ∆ + a)
9 t1 ← g(b + a) − W a g(b + ∆ + a)
10 g(b + a) ← t0
11 g(b + ∆ + a) ← t1
12 ∆ ← 2∆

Algoritmo FFT-DIT. La longitud de la señal debe ser 2n , n = 0, 1, 2 . . ..

29/32 Transformada Fourier de discreta FIC-05

 Transformada rápida de Fourier
Inversión de bits para N = 8.

Índice Argumento Índice Argumento

original binario ordenado binario

0 0 0 0 0 0 0 0

1 0 0 1 4 1 0 0

2 0 1 0 2 0 1 0

3 0 1 1 6 1 1 0

4 1 0 0 1 0 0 1

5 1 0 1 5 1 0 1

6 1 1 0 3 0 1 1

7 1 1 1 7 1 1 1

30/32 Transformada Fourier de discreta FIC-05

 Transformada rápida de Fourier

Input: Array g of size N = 2n

Output: Reordered array g

1 j←0
2 for (i = 0; i < N ; i + +) do
3 k = N/2
4 if (i < j) then
5 swap g(i) and g(j)
6 while (k ≤ j) do
7 j ←j−k
8 k ← k/2
9 j ←j+k

Algoritmo de Gold-Rader para inversión de bits.

31/32 Transformada Fourier de discreta FIC-05

 Transformada rápida de Fourier
Cuando la señal no es de longitud N = 2n , se debe aplicar un relle-

nado de ceros para agregar ceros al nal de la señal, de tal manera

que se ajuste su longitud a la siguiente potencia entera de dos.

(a) Pulso rectangular original (N = 76). (b) DFT calculada mediante (8). (c) Pulso
rectangular con rellenado de ceros (N = 27 ). (d) DFT calculada mediante FFT-DIT.

32/32 Transformada Fourier de discreta FIC-05