Phase 01 - Lesson 20

La Transformada de Fourier

This lesson includes a graded coding exercise that runs in your browser, unlocked with lifetime access.

Toda señal es una suma de ondas senoidales. La transformada de Fourier te dice cuáles son.

Tipo: Build Lenguaje: Python Prerrequisitos: Fase 1, Lecciones 01-04, 19 (números complejos) Tiempo: ~90 minutos

Objetivos de Aprendizaje

• Implementar la DFT desde cero y verificarla contra la FFT Cooley-Tukey de O(N log N)
• Interpretar coeficientes de frecuencia: extraer amplitud, fase y espectro de potencia de una señal
• Aplicar el teorema de la convolución para realizar convolución mediante multiplicación por FFT
• Conectar la descomposición de frecuencia de Fourier con las codificaciones posicionales de los transformers y las capas de convolución de las CNN

El Problema

Una grabación de audio es una secuencia de mediciones de presión a lo largo del tiempo. Un precio de una acción es una secuencia de valores a lo largo de los días. Una imagen es una cuadrícula de intensidades de píxel en el espacio. Todos estos son datos en el dominio del tiempo (o dominio del espacio). Ves valores que cambian a lo largo de algún índice.

Pero muchos patrones son invisibles en el dominio del tiempo. ¿Esta señal de audio es un tono puro o un acorde? ¿Tiene este precio de acción un ciclo semanal? ¿Tiene esta imagen una textura repetitiva? Estas preguntas son sobre el contenido de frecuencia, y el dominio del tiempo lo oculta.

La transformada de Fourier convierte datos del dominio del tiempo al dominio de la frecuencia. Toma una señal y la descompone en ondas senoidales de diferentes frecuencias. Cada onda senoidal tiene una amplitud (qué tan fuerte es) y una fase (dónde comienza). La transformada de Fourier te indica ambas.

Esto importa para ML porque el razonamiento en el dominio de la frecuencia aparece en todas partes. Las redes neuronales convolucionales realizan convolución, que es multiplicación en el dominio de la frecuencia. Las codificaciones posicionales de los transformers usan descomposición de frecuencia para representar la posición. Los modelos de audio (reconocimiento de voz, generación de música) operan sobre espectrogramas -- representaciones de frecuencia del sonido. Los modelos de series de tiempo buscan patrones periódicos. Entender la transformada de Fourier te da el vocabulario para trabajar con todos ellos.

El Concepto

La definición de la DFT

Dadas N muestras x[0], x[1], ..., x[N-1], la Transformada Discreta de Fourier produce N coeficientes de frecuencia X[0], X[1], ..., X[N-1]:

X[k] = sum_{n=0}^{N-1} x[n] * e^(-2*pi*i*k*n/N)

for k = 0, 1, ..., N-1

Cada X[k] es un número complejo. Su magnitud |X[k]| te indica la amplitud de la frecuencia k. Su ángulo de fase angle(X[k]) te indica el desplazamiento de fase de esa frecuencia.

La idea clave: e^(-2*pi*i*k*n/N) es un fasor rotatorio en la frecuencia k. La DFT calcula la correlación entre la señal y cada una de las N frecuencias igualmente espaciadas. Si la señal contiene energía en la frecuencia k, la correlación es grande. Si no, es cercana a cero.

Qué significa cada coeficiente

X[0]: la componente DC. Esta es la suma de todas las muestras -- proporcional a la media. Representa el desplazamiento constante (frecuencia cero) de la señal.

X[0] = sum_{n=0}^{N-1} x[n] * e^0 = sum of all samples

X[k] para 1 <= k <= N/2: frecuencias positivas. X[k] representa la frecuencia k ciclos por N muestras. Una k mayor significa una frecuencia mayor (oscilación más rápida).

X[N/2]: la frecuencia de Nyquist. La frecuencia más alta que puedes representar con N muestras. Por encima de esta, obtienes aliasing -- frecuencias altas que se hacen pasar por bajas.

X[k] para N/2 < k < N: frecuencias negativas. Para señales de valor real, X[N-k] = conj(X[k]). Las frecuencias negativas son imágenes especulares de las positivas. Por eso la información útil está en los primeros N/2 + 1 coeficientes.

DFT inversa

La DFT inversa reconstruye la señal original a partir de sus coeficientes de frecuencia:

x[n] = (1/N) * sum_{k=0}^{N-1} X[k] * e^(2*pi*i*k*n/N)

for n = 0, 1, ..., N-1

Las únicas diferencias respecto a la DFT directa: el signo en el exponente es positivo (no negativo), y hay un factor de normalización 1/N.

La DFT inversa es una reconstrucción perfecta. No se pierde información. Puedes ir del dominio del tiempo al dominio de la frecuencia y de vuelta sin ningún error. La DFT es un cambio de base -- reexpresa la misma información en un sistema de coordenadas diferente.

La FFT: hacerla rápida

La DFT definida arriba es O(N^2): para cada uno de los N coeficientes de salida, sumas sobre N muestras de entrada. Para N = 1 millón, eso es 10^12 operaciones.

La Transformada Rápida de Fourier (FFT) calcula el mismo resultado en O(N log N). Para N = 1 millón, eso es alrededor de 20 millones de operaciones en lugar de un billón. Esto es lo que hace que el análisis de frecuencia sea práctico.

El algoritmo de Cooley-Tukey (la FFT más común) funciona por divide y vencerás:

1. Divide la señal en muestras de índice par y de índice impar.
2. Calcula la DFT de cada mitad recursivamente.
3. Combina las dos DFT de medio tamaño usando "factores de giro" (twiddle factors) e^(-2pii*k/N).

X[k] = E[k] + e^(-2*pi*i*k/N) * O[k]          for k = 0, ..., N/2 - 1
X[k + N/2] = E[k] - e^(-2*pi*i*k/N) * O[k]    for k = 0, ..., N/2 - 1

where E = DFT of even-indexed samples
      O = DFT of odd-indexed samples

La simetría implica que cada nivel de recursión hace O(N) trabajo, y hay log2(N) niveles. Total: O(N log N).

graph TD
    subgraph "8-point FFT (Cooley-Tukey)"
        X["x[0..7]<br/>8 samples"] -->|"split even/odd"| E["Even: x[0,2,4,6]"]
        X -->|"split even/odd"| O["Odd: x[1,3,5,7]"]
        E -->|"4-pt FFT"| EK["E[0..3]"]
        O -->|"4-pt FFT"| OK["O[0..3]"]
        EK -->|"combine with twiddle factors"| XK["X[0..7]"]
        OK -->|"combine with twiddle factors"| XK
    end
    subgraph "Complexity"
        C1["DFT: O(N^2) = 64 multiplications"]
        C2["FFT: O(N log N) = 24 multiplications"]
    end

La FFT requiere que la longitud de la señal sea una potencia de 2. En la práctica, las señales se rellenan con ceros (zero-padded) hasta la siguiente potencia de 2.

Análisis espectral

El espectro de potencia es |X[k]|^2 -- la magnitud al cuadrado de cada coeficiente de frecuencia. Muestra cuánta energía hay en cada frecuencia.

El espectro de fase es angle(X[k]) -- el desplazamiento de fase de cada frecuencia. Para la mayoría de las tareas de análisis, te interesa el espectro de potencia e ignoras la fase.

Power at frequency k:  P[k] = |X[k]|^2 = X[k].real^2 + X[k].imag^2
Phase at frequency k:  phi[k] = atan2(X[k].imag, X[k].real)

Resolución de frecuencia

La resolución de frecuencia de la DFT depende del número de muestras N y la tasa de muestreo fs.

Frequency of bin k:      f_k = k * fs / N
Frequency resolution:    delta_f = fs / N
Maximum frequency:       f_max = fs / 2  (Nyquist)

Para resolver dos frecuencias que están cercanas entre sí, necesitas más muestras. Para capturar frecuencias altas, necesitas una tasa de muestreo mayor.

El teorema de la convolución

Este es uno de los resultados más importantes en el procesamiento de señales y directamente relevante para las CNN.

La convolución en el dominio del tiempo equivale a la multiplicación punto a punto en el dominio de la frecuencia.

x * h = IFFT(FFT(x) . FFT(h))

where * is convolution and . is element-wise multiplication

Por qué esto importa:

• La convolución directa de dos señales de longitud N y M toma O(N*M) operaciones.
• La convolución basada en FFT toma O(N log N): transforma ambas, multiplica, transforma de vuelta.
• Para kernels grandes, la convolución por FFT es dramáticamente más rápida.
• Esto es exactamente lo que sucede en las capas convolucionales con campos receptivos grandes.

Nota: la DFT calcula la convolución circular (la señal da la vuelta). Para la convolución lineal (sin dar la vuelta), rellena ambas señales con ceros hasta la longitud N + M - 1 antes de calcular.

graph LR
    subgraph "Time Domain"
        TA["Signal x[n]"] -->|"convolve (slow: O(NM))"| TC["Output y[n]"]
        TB["Filter h[n]"] -->|"convolve"| TC
    end
    subgraph "Frequency Domain"
        FA["FFT(x)"] -->|"multiply (fast: O(N))"| FC["FFT(x) * FFT(h)"]
        FB["FFT(h)"] -->|"multiply"| FC
        FC -->|"IFFT"| FD["y[n]"]
    end
    TA -.->|"FFT"| FA
    TB -.->|"FFT"| FB
    FD -.->|"same result"| TC

Ventaneo

La DFT asume que la señal es periódica -- trata las N muestras como un periodo de una señal que se repite infinitamente. Si la señal no comienza y termina en el mismo valor, esto crea una discontinuidad en el límite, que se manifiesta como contenido espurio de alta frecuencia. Esto se llama fuga espectral (spectral leakage).

El ventaneo reduce la fuga atenuando la señal hasta cero en ambos extremos antes de calcular la DFT.

Ventanas comunes:

Hann window:    w[n] = 0.5 * (1 - cos(2*pi*n / (N-1)))
Hamming window: w[n] = 0.54 - 0.46 * cos(2*pi*n / (N-1))

Aplica la ventana multiplicándola elemento a elemento por la señal antes de la DFT: X = DFT(x * w).

Propiedades de la DFT

El teorema de Parseval dice que la energía total es la misma en ambos dominios. La energía se conserva a través de la transformada.

Conexión con las codificaciones posicionales

El Transformer original usa codificaciones posicionales senoidales:

PE(pos, 2i)   = sin(pos / 10000^(2i/d_model))
PE(pos, 2i+1) = cos(pos / 10000^(2i/d_model))

Cada par de dimensiones (2i, 2i+1) oscila a una frecuencia diferente. Las frecuencias están espaciadas geométricamente desde alta (dimensión 0,1) hasta baja (últimas dimensiones). Esto le da a cada posición un patrón único a través de todas las bandas de frecuencia -- similar a cómo los coeficientes de Fourier identifican una señal de forma única.

Las propiedades clave que esto proporciona:

• Unicidad: No hay dos posiciones que tengan la misma codificación.
• Valores acotados: sin y cos siempre están en [-1, 1].
• Posición relativa: La codificación de la posición p+k puede expresarse como una función lineal de la codificación en la posición p. El modelo puede aprender a atender a posiciones relativas.

Conexión con las CNN

Una capa de convolución aplica un filtro aprendido (kernel) a la entrada deslizándolo a través de la señal o la imagen. Matemáticamente, esto es la operación de convolución.

Por el teorema de la convolución, esto es equivalente a:

1. FFT de la entrada
2. FFT del kernel
3. Multiplicar en el dominio de la frecuencia
4. IFFT del resultado

Las implementaciones estándar de CNN usan convolución directa (más rápida para kernels pequeños de 3x3). Pero para kernels grandes o convolución global, los enfoques basados en FFT son significativamente más rápidos. Algunas arquitecturas (como FNet) reemplazan la atención por completo con FFT, logrando una precisión competitiva con complejidad O(N log N) en lugar de O(N^2).

Espectrogramas y la Transformada de Fourier de Tiempo Corto

Una sola FFT te da el contenido de frecuencia de toda la señal, pero no te dice nada sobre cuándo ocurren esas frecuencias. Un chirp (una señal cuya frecuencia aumenta con el tiempo) y un acorde (todas las frecuencias presentes simultáneamente) pueden tener el mismo espectro de magnitud.

La Transformada de Fourier de Tiempo Corto (STFT) resuelve esto calculando FFT sobre ventanas superpuestas de la señal. El resultado es un espectrograma: una representación 2D con el tiempo en un eje y la frecuencia en el otro. La intensidad en cada punto muestra la energía en esa frecuencia en ese instante.

STFT procedure:
1. Choose a window size (e.g., 1024 samples)
2. Choose a hop size (e.g., 256 samples -- 75% overlap)
3. For each window position:
   a. Extract the windowed segment
   b. Apply a Hann/Hamming window
   c. Compute FFT
   d. Store the magnitude spectrum as one column of the spectrogram

Los espectrogramas son la representación de entrada estándar para los modelos de ML de audio. Los modelos de reconocimiento de voz (Whisper, DeepSpeech) operan sobre mel-espectrogramas -- espectrogramas con frecuencias mapeadas a la escala mel, que se ajusta mejor a la percepción humana del tono.

Aliasing

Si una señal contiene frecuencias por encima de fs/2 (la frecuencia de Nyquist), muestrearla a una tasa fs creará copias con aliasing. Una señal de 90 Hz muestreada a 100 Hz se ve idéntica a una señal de 10 Hz. No hay forma de distinguirlas solo a partir de las muestras.

Example:
  True signal: 90 Hz sine wave
  Sampling rate: 100 Hz
  Apparent frequency: 100 - 90 = 10 Hz

  The samples from the 90 Hz signal at 100 Hz sampling rate
  are identical to the samples from a 10 Hz signal.
  No amount of math can recover the original 90 Hz.

Por eso los convertidores analógico-digital incluyen filtros anti-aliasing que eliminan frecuencias por encima de Nyquist antes del muestreo. En ML, el aliasing aparece al submuestrear (downsampling) mapas de características sin un filtrado pasa-bajos adecuado -- algunas arquitecturas abordan esto con capas de pooling anti-aliasing.

El relleno con ceros no aumenta la resolución

Un error común: rellenar una señal con ceros antes de la FFT mejora la resolución de frecuencia. No lo hace. El relleno con ceros interpola entre los bins de frecuencia existentes, dándote un espectro de aspecto más suave. Pero no puede revelar detalle de frecuencia que no estaba presente en las muestras originales.

La verdadera resolución de frecuencia depende solo del tiempo de observación T = N / fs. Para resolver dos frecuencias separadas por delta_f, necesitas al menos T = 1 / delta_f segundos de datos. Ninguna cantidad de relleno con ceros cambia este límite fundamental.

Build It

Paso 1: DFT desde cero

La DFT O(N^2) se sigue directamente de la definición.

import math

class Complex:
    ...

def dft(x):
    N = len(x)
    result = []
    for k in range(N):
        total = Complex(0, 0)
        for n in range(N):
            angle = -2 * math.pi * k * n / N
            w = Complex(math.cos(angle), math.sin(angle))
            xn = x[n] if isinstance(x[n], Complex) else Complex(x[n])
            total = total + xn * w
        result.append(total)
    return result

Paso 2: DFT inversa

Misma estructura, exponente positivo, división por N.

def idft(X):
    N = len(X)
    result = []
    for n in range(N):
        total = Complex(0, 0)
        for k in range(N):
            angle = 2 * math.pi * k * n / N
            w = Complex(math.cos(angle), math.sin(angle))
            total = total + X[k] * w
        result.append(Complex(total.real / N, total.imag / N))
    return result

Paso 3: FFT (Cooley-Tukey)

La FFT recursiva requiere longitud potencia de 2. Divide en par e impar, recursiona, combina con factores de giro.

def fft(x):
    N = len(x)
    if N <= 1:
        return [x[0] if isinstance(x[0], Complex) else Complex(x[0])]
    if N % 2 != 0:
        return dft(x)

    even = fft([x[i] for i in range(0, N, 2)])
    odd = fft([x[i] for i in range(1, N, 2)])

    result = [Complex(0)] * N
    for k in range(N // 2):
        angle = -2 * math.pi * k / N
        twiddle = Complex(math.cos(angle), math.sin(angle))
        t = twiddle * odd[k]
        result[k] = even[k] + t
        result[k + N // 2] = even[k] - t
    return result

Paso 4: Funciones auxiliares de análisis espectral

def power_spectrum(X):
    return [xk.real ** 2 + xk.imag ** 2 for xk in X]

def convolve_fft(x, h):
    N = len(x) + len(h) - 1
    padded_N = 1
    while padded_N < N:
        padded_N *= 2

    x_padded = x + [0.0] * (padded_N - len(x))
    h_padded = h + [0.0] * (padded_N - len(h))

    X = fft(x_padded)
    H = fft(h_padded)

    Y = [xk * hk for xk, hk in zip(X, H)]

    y = idft(Y)
    return [y[n].real for n in range(N)]

Use It

Para trabajo real, usa la FFT de numpy, que está respaldada por bibliotecas C altamente optimizadas.

import numpy as np

signal = np.sin(2 * np.pi * 5 * np.arange(256) / 256)
spectrum = np.fft.fft(signal)
freqs = np.fft.fftfreq(256, d=1/256)

power = np.abs(spectrum) ** 2

positive_freqs = freqs[:len(freqs)//2]
positive_power = power[:len(power)//2]

Para ventaneo y análisis espectral más avanzado:

from scipy.signal import windows, stft

window = windows.hann(256)
windowed = signal * window
spectrum = np.fft.fft(windowed)

Para convolución:

from scipy.signal import fftconvolve

result = fftconvolve(signal, kernel, mode='full')

Para espectrogramas:

from scipy.signal import stft

frequencies, times, Zxx = stft(signal, fs=sample_rate, nperseg=256)
spectrogram = np.abs(Zxx) ** 2

La matriz del espectrograma tiene forma (n_frequencies, n_time_frames). Cada columna es el espectro de potencia en una ventana de tiempo. Esto es lo que los modelos de ML de audio consumen como entrada.

Ship It

Ejecuta code/fourier.py para generar outputs/prompt-spectral-analyzer.md.

Ejercicios

1. Identificación de tono puro. Crea una señal con una sola onda senoidal en una frecuencia desconocida (entre 1 y 50 Hz), muestreada a 128 Hz durante 1 segundo. Usa tu DFT para identificar la frecuencia. Verifica que la respuesta coincida. Ahora agrega ruido gaussiano con desviación estándar 0,5 y repite. ¿Cómo afecta el ruido al espectro?

2. Verificación FFT vs DFT. Genera una señal aleatoria de longitud 64. Calcula tanto la DFT (O(N^2)) como la FFT. Verifica que todos los coeficientes coincidan con una tolerancia de 1e-10. Cronometra ambas funciones en señales de longitud 256, 512, 1024 y 2048. Grafica la razón entre el tiempo de la DFT y el tiempo de la FFT.

3. Prueba del teorema de la convolución por ejemplo. Crea la señal x = [1, 2, 3, 4, 0, 0, 0, 0] y el filtro h = [1, 1, 1, 0, 0, 0, 0, 0]. Calcula su convolución circular directamente (bucle anidado). Luego calcúlala mediante FFT (transformar, multiplicar, transformar inversamente). Verifica que los resultados coincidan. Ahora haz la convolución lineal rellenando con ceros apropiadamente.

4. Efectos del ventaneo. Crea una señal que sea la suma de dos ondas senoidales en 10 Hz y 12 Hz (muy cercanas). Muestrea a 128 Hz durante 1 segundo. Calcula el espectro de potencia sin ventana, con ventana de Hann y con ventana de Hamming. ¿Qué ventana facilita más distinguir los dos picos? ¿Por qué?

5. Análisis de codificación posicional. Genera las codificaciones posicionales senoidales para d_model = 128 y max_pos = 512. Para cada par de posiciones (p1, p2), calcula el producto escalar de sus codificaciones. Muestra que el producto escalar depende solo de |p1 - p2|, no de las posiciones absolutas. ¿Qué sucede con el producto escalar a medida que aumenta la distancia?

Términos Clave

Lectura Adicional

• Cooley & Tukey: An Algorithm for the Machine Calculation of Complex Fourier Series (1965) - el artículo original de la FFT que cambió la computación
• 3Blue1Brown: But what is the Fourier Transform? - la mejor introducción visual a las transformadas de Fourier
• Lee-Thorp et al.: FNet: Mixing Tokens with Fourier Transforms (2021) - reemplaza la autoatención con FFT en los transformers
• Smith: The Scientist and Engineer's Guide to Digital Signal Processing - libro de texto en línea gratuito que cubre FFT, ventaneo y análisis espectral en profundidad
• Vaswani et al.: Attention Is All You Need (2017) - codificaciones posicionales senoidales derivadas de la descomposición de frecuencia de Fourier
• Radford et al.: Whisper (2022) - reconocimiento de voz usando mel-espectrogramas como representación de entrada