Resolución Ejercicio 1 - Transformada de Fourier Discreta (DFT)

Fundamentos Matemáticos

La Transformada de Fourier Discreta (DFT) es una herramienta matemática fundamental en el análisis numérico y el procesamiento de señales. Mientras que la Serie de Fourier continua se aplica a funciones periódicas en el dominio continuo, la DFT actúa sobre un vector de valores muestreados (discretos), típicamente equiespaciados en el tiempo.

El enunciado nos plantea la siguiente expresión (atención, corrigiendo un leve error tipográfico en los índices del PDF original, donde la sumatoria iteraba sobre $k$ en lugar de $n$):

$$X_k = \sum_{n=0}^{N-1} x_n e^{-i \frac{2\pi k n}{N}}, \quad k = 0, \dots, N-1$$

Donde:

• $N$ es la longitud del vector o cantidad total de muestras.
• $x_n$ es el valor de la señal en la muestra n-ésima (dominio temporal).
• $X_k$ es el coeficiente k-ésimo de la transformada (dominio frecuencial), generalmente un número complejo.
• $e^{-i \frac{2\pi k n}{N}}$ son las funciones de base complejas. Por la fórmula de Euler ($e^{-i\theta} = \cos(\theta) - i\sin(\theta)$), representan armónicos senoidales y cosenoidales a distintas frecuencias.

Cada coeficiente $X_k$ resultante nos cuantifica "cuánto" de la frecuencia $k$ está presente en nuestra señal $x$.

Implementación Numérica

Si bien el cálculo directo iterando con dos bucles for (uno exterior para $k$ y otro interior para $n$) es correcto conceptualmente, acarrea una complejidad algorítmica de $\mathcal{O}(N^2)$. En un lenguaje interpretado como Python, esto sería extremadamente lento para vectores grandes.

Para sortear esto, la convención en Python (utilizando numpy) es vectorizar las operaciones echando mano al álgebra lineal subyacente (rutinas BLAS/LAPACK escritas en C/Fortran). Podemos construir una matriz cuadrada $M$ de dimensiones $N \times N$, donde cada elemento $M_{k,n} = e^{-i \frac{2\pi k n}{N}}$, y luego obtener el vector $X$ sencillamente multiplicando la matriz $M$ por el vector columna $x$.

El código en Python ha sido implementado y guardado en dft.py.

import numpy as np

def calcular_dft(x: np.ndarray) -> np.ndarray:
    """
    Calcula la Transformada de Fourier Discreta (DFT) de manera vectorizada.
    
    Parámetros:
    x (np.ndarray): Señal discreta en el tiempo (array 1D).
    
    Retorna:
    np.ndarray: Espectro de frecuencias (DFT) complejo (array 1D).
    """
    # Nos aseguramos que x sea un array de numpy de tipo float
    x = np.asarray(x, dtype=float)
    N = x.shape[0]
    
    # Generamos los vectores de índices n y k
    n = np.arange(N)
    k = n.reshape((N, 1)) # Lo transformamos a vector columna para hacer broadcasting
    
    # Matriz exponencial de Fourier (NxN)
    M = np.exp(-2j * np.pi * k * n / N)
    
    # Producto matricial: X_k = M * x_n
    return np.dot(M, x)

[!infobox] Ejercicio 1: Implementación de DFT Contexto: Transformada de Fourier Discreta a partir de su definición matemática. Resolución Numérica: Se implementa de forma vectorizada utilizando numpy. En lugar de utilizar bucles anidados, se calcula el producto $X = M \cdot x$, donde $M$ es la matriz que contiene los valores de las exponenciales complejas $M_{k,n} = e^{-i \frac{2\pi k n}{N}}$. Esto acelera exponencialmente la ejecución en un entorno como Python (vectorización), aunque matemáticamente mantengamos una complejidad $\mathcal{O}(N^2)$. Advertencia/Clave: Notar que la fórmula matemática del enunciado tiene un error de índices; el sumatorio se realiza sobre la variable temporal discreta $n$, no sobre $k$. En la vida real e industrial, jamás utilizamos esta DFT "nativa" cuadrática, sino el algoritmo FFT (Fast Fourier Transform) de Cooley-Tukey, cuya complejidad es radicalmente menor: $\mathcal{O}(N \log N)$.