3.1 DFT - Transformada de Fourier Discreta -

1. Transformada de Fourier Discreta

Referencia: Chapra 19.5 p556

Una función representada por valores muestra o discretos se puede dividir en intervalos de 0 a t en N sub-intervalos de igual tamaño Δt=T/N.

La transformada discreta de Fourier se escribe como:

F_k = \sum_{n=0}^{N-1} f_n e^{-i \omega_0 n}

k = 0 a N-1

y la transformada inversa como:

f_n = \frac{1}{N}\sum_{k=0}^{N-1} F_k e^{i \omega_0 n}

n = 0 a N-1

donde ω₀= 2π/N

Muestras de f(t) como f[n] en un periodo T

La DTF requiere N² operaciones complejas. Observe que el factor 1/N es un factor de escala que se puede incluir en una ecuación pero No en ambas.

2. Ejercicio para DTF

Para las muestras de la función coseno, realizar la transformada discreta de Fourier.

f_n = cos(2 \pi 12.5 t)

considere f₀=12.5, Δt=0.01, N=16.

3. Algoritmo

El algoritmo calcula las muestras para f(t) que se usan en el procedimiento de la transformada según la fórmula dada.

El factor 1/N se usará en la primer expresión, para que el primer coeficiente F0 sea igual a la media aritmética de las muestras.

El resultado a mostrar para el ejemplo es:

[[ k, fi[k], k_real, k_imag ]]
[[ 0.          1.          0.          0.        ]
 [ 1.          0.70710678  0.          0.        ]
 [ 2.          0.          0.5         0.        ]
 [ 3.         -0.70710678  0.          0.        ]
 [ 4.         -1.          0.          0.        ]
 [ 5.         -0.70710678  0.          0.        ]
 [ 6.          0.          0.          0.        ]
 [ 7.          0.70710678  0.          0.        ]
 [ 8.          1.          0.          0.        ]
 [ 9.          0.70710678  0.          0.        ]
 [10.          0.          0.          0.        ]
 [11.         -0.70710678  0.          0.        ]
 [12.         -1.          0.          0.        ]
 [13.         -0.70710678  0.          0.        ]
 [14.          0.          0.5         0.        ]
 [15.          0.70710678  0.          0.        ]]

Las instrucciones en Python son:

 DFT Transformada Discreta de Fourier
# Ref. Chapra 5ed 19.5 p556
import sympy as sym
import numpy as np
 
# INGRESO
N = 16
f0 = 12.5
fx = lambda t: np.cos(2*np.pi*f0*t)
dt = 0.01

# fx Discreta, N muestras, tramos dt
ti = np.arange(0,N*dt,dt)
fi = fx(ti)

# PROCEDIMIENTO
casicero = 1e-14 # valores son cero
verdigitos = 4 # ver digitos en la tabla
#np.set_printoptions(4,legacy="1.25") # no muestra tipo datos

w0 = 2*np.pi/N
tabla = []
for k in range(0,N,1): # [0,N)=[0,N-1]
    k_real = 0
    k_imag = 0
    for n in range(0,N,1): # [0,N)=[0,N-1]
        angulo = k*w0*n
        k_real = k_real + fi[n]*np.cos(angulo)/N
        k_imag = k_imag + fi[n]*np.sin(angulo)/N
    tabla.append([k,fi[k],k_real,k_imag])

tabla = np.array(tabla,dtype=float)
# revisa casicero
tabla = np.where(abs(tabla) < casicero, 0, tabla)

# SALIDA
print("[[ k, fi[k], k_real, k_imag ]]")
print(tabla)

4. Gráfica

# GRAFICA ---------
import matplotlib.pyplot as plt
fs_veces = 10 # suavizar x(t), sobremuestreo
# muestreo x(t)
dtc = dt/fs_veces # sobremuestreo para x(t)
tj = np.arange(0,N*dt + dtc, dtc)
fj = fx(tj)

plt.subplot(211)
plt.plot(tj,fj,color="gray",label='f(t)')
plt.stem(ti,fi,linefmt = 'C0:', label='f[n]')
plt.xlabel('t')
plt.legend()

plt.subplot(212)
plt.stem(tabla[:,2], linefmt = 'C1:',label='k_real')
plt.stem(tabla[:,3], linefmt = 'C2:',label='k_imag')
plt.xlabel('n')
plt.ylabel('|k|')
plt.legend()

El Algoritmo Más Importante De Todos Los Tiempos. Veritasium. 21 enero 2023.

Algoritmos101