Phase 01 - Lesson 20

A Transformada de Fourier

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

Todo sinal e uma soma de ondas senoidais. A transformada de Fourier diz quais são elas.

Tipo: Build Linguagem: Python Pré-requisitos: Fase 1, Lições 01-04, 19 (números complexos) Tempo: ~90 minutos

Objetivos de Aprendizagem

• Implementar a DFT do zero e verifica-lá contra a FFT Cooley-Tukey de O(N log N)
• Interpretar coeficientes de frequência: extrair amplitude, fase e espectro de potência de um sinal
• Aplicar o teorema da convolução para realizar convolução via multiplicação por FFT
• Conectar a decomposição de frequência de Fourier as codificações posicionais de transformers e as camadas de convolução de CNNs

O Problema

Uma gravacao de áudio e uma sequência de medicoes de pressao ao longo do tempo. Um preço de ação e uma sequência de valores ao longo dos dias. Uma imagem e uma grade de intensidades de pixel pelo espaço. Tudo isso são dados no domínio do tempo (ou domínio do espaço). Você ve valores mudando ao longo de algum índice.

Mas muitos padrões são invisiveis no domínio do tempo. Este sinal de áudio e um tom puro ou um acorde? Este preço de ação tem um ciclo semanal? Esta imagem tem uma textura repetitiva? Essas perguntas são sobre o conteúdo de frequência, e o domínio do tempo o esconde.

A transformada de Fourier converte dados do domínio do tempo para o domínio da frequência. Ela pega um sinal e o decompõe em ondas senoidais de diferentes frequências. Cada onda senoidal tem uma amplitude (quão forte ela e) e uma fase (onde ela começa). A transformada de Fourier informa ambas.

Isso importa para ML porque o raciocínio no domínio da frequência aparece em todo lugar. Redes neurais convolucionais realizam convolução, que e multiplicação no domínio da frequência. Codificações posicionais de transformers usam decomposição de frequência para representar posição. Modelos de áudio (reconhecimento de fala, geração de música) operam sobre espectrogramas -- representações de frequência do som. Modelos de séries temporais buscam padrões periódicos. Entender a transformada de Fourier lhe da o vocabulário para trabalhar com todos eles.

O Conceito

A definição da DFT

Dadas N amostras x[0], x[1], ..., x[N-1], a Transformada Discreta de Fourier produz N coeficientes de frequência 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] e um número complexo. Sua magnitude |X[k]| informa a amplitude da frequência k. Seu ângulo de fase angle(X[k]) informa o deslocamento de fase dessa frequência.

A ideia central: e^(-2*pi*i*k*n/N) e um fasor rotativo na frequência k. A DFT calcula a correlação entre o sinal e cada uma das N frequências igualmente espaçadas. Se o sinal contém energia na frequência k, a correlação e grande. Se não, ela e próxima de zero.

O que cada coeficiente significa

X[0]: a componente DC. Esta e a soma de todas as amostras -- proporcional a média. Ela representa o deslocamento constante (frequência zero) do sinal.

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

X[k] para 1 <= k <= N/2: frequências positivas. X[k] representa frequência k ciclos por N amostras. k maior significa frequência maior (oscilacao mais rápida).

X[N/2]: a frequência de Nyquist. A maior frequência que você pode representar com N amostras. Acima dela, você obtém aliasing -- frequências altas se disfarcando de baixas.

X[k] para N/2 < k < N: frequências negativas. Para sinais de valor real, X[N-k] = conj(X[k]). As frequências negativas são imagens espelhadas das positivas. E por isso que a informação útil esta nos primeiros N/2 + 1 coeficientes.

DFT inversa

A DFT inversa reconstrói o sinal original a partir de seus coeficientes de frequência:

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

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

As únicas diferenças em relação a DFT direta: o sinal no expoente e positivo (não negativo), e há um fator de normalização 1/N.

A DFT inversa e uma reconstrução perfeita. Nenhuma informação e perdida. Você pode ir do domínio do tempo para o domínio da frequência e voltar sem nenhum erro. A DFT e uma mudanca de base -- ela reexpressa a mesma informação em um sistema de coordenadas diferente.

A FFT: tornando-a rápida

A DFT definida acima e O(N^2): para cada um dos N coeficientes de saída, você soma sobre N amostras de entrada. Para N = 1 milhão, isso da 10^12 operações.

A Transformada Rápida de Fourier (FFT) calcula o mesmo resultado em O(N log N). Para N = 1 milhão, isso da cerca de 20 milhões de operações em vez de um trilhão. E isso que torna a análise de frequência prática.

O algoritmo de Cooley-Tukey (a FFT mais comum) funciona por dividir para conquistar:

1. Separe o sinal em amostras de índice par e de índice impar.
2. Calcule a DFT de cada metade recursivamente.
3. Combine as duas DFTs de meio tamanho usando "fatores de rotação" (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

A simetria significa que cada nível de recursão faz O(N) trabalho, e há log2(N) níveis. 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

A FFT exige que o comprimento do sinal seja uma potência de 2. Na prática, os sinais são preenchidos com zeros (zero-padded) até a próxima potência de 2.

Análise espectral

O espectro de potência e |X[k]|^2 -- a magnitude ao quadrado de cada coeficiente de frequência. Ele mostra quanta energia há em cada frequência.

O espectro de fase e angle(X[k]) -- o deslocamento de fase de cada frequência. Para a maioria das tarefas de análise, você se importa com o espectro de potência e ignora a 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)

Resolução de frequência

A resolução de frequência da DFT depende do número de amostras N e da taxa de amostragem 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 duas frequências que estão próximas uma da outra, você precisa de mais amostras. Para capturar frequências altas, você precisa de uma taxa de amostragem maior.

O teorema da convolução

Este e um dos resultados mais importantes em processamento de sinais e diretamente relevante para CNNs.

Convolução no domínio do tempo equivale a multiplicação ponto a ponto no domínio da frequência.

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

where * is convolution and . is element-wise multiplication

Por que isso importa:

• A convolução direta de dois sinais de comprimento N e M leva O(N*M) operações.
• A convolução baseada em FFT leva O(N log N): transforme ambos, multiplique, transforme de volta.
• Para kernels grandes, a convolução por FFT e drasticamente mais rápida.
• E exatamente isso que acontece em camadas convolucionais com campos receptivos grandes.

Observação: a DFT calcula a convolução circular (o sinal da a volta). Para a convolução linear (sem dar a volta), preencha ambos os sinais com zeros até o comprimento 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

Janelamento

A DFT assume que o sinal e periódico -- ela trata as N amostras como um período de um sinal que se repete infinitamente. Se o sinal não começa e termina no mesmo valor, isso cria uma descontinuidade na fronteira, que aparece como conteúdo espúrio de alta frequência. Isso e chamado de vazamento espectral (spectral leakage).

O janelamento reduz o vazamento ao afunilar o sinal até zero em ambas as extremidades antes de calcular a DFT.

Janelas comuns:

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))

Aplique a janela multiplicando-a elemento a elemento pelo sinal antes da DFT: X = DFT(x * w).

Propriedades da DFT

O teorema de Parseval diz que a energia total e a mesma em ambos os domínios. A energia e conservada através da transformada.

Conexão com codificações posicionais

O Transformer original usa codificações posicionais senoidais:

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

Cada par de dimensões (2i, 2i+1) oscila em uma frequência diferente. As frequências são espaçadas geometricamente de alta (dimensão 0,1) a baixa (últimas dimensões). Isso da a cada posição um padrão único em todas as bandas de frequência -- semelhante a como os coeficientes de Fourier identificam um sinal de forma única.

As propriedades-chave que isso fornece:

• Unicidade: Nenhuma das posições tem a mesma codificação.
• Valores limitados: sin e cos estão sempre em [-1, 1].
• Posição relativa: A codificação da posição p+k pode ser expressa como uma função linear da codificação na posição p. O modelo pode aprender a atender a posições relativas.

Conexão com CNNs

Uma camada de convolução aplica um filtro aprendido (kernel) a entrada deslizando-o pelo sinal ou imagem. Matematicamente, isso e a operação de convolução.

Pelo teorema da convolução, isso e equivalente a:

1. FFT da entrada
2. FFT do kernel
3. Multiplicar no domínio da frequência
4. IFFT do resultado

Implementações padrão de CNN usam convolução direta (mais rápida para kernels pequenos 3x3). Mas para kernels grandes ou convolução global, abordagens baseadas em FFT são significativamente mais rápidas. Algumas arquiteturas (como o FNet) substituem a atenção inteiramente por FFT, alcancando precisão competitiva com complexidade O(N log N) em vez de O(N^2).

Espectrogramas e a Transformada de Fourier de Curto Prazo

Uma única FFT lhe da o conteúdo de frequência do sinal inteiro, mas não diz nada sobre quando essas frequências ocorrem. Um chirp (um sinal cuja frequência aumenta ao longo do tempo) e um acorde (todas as frequências presentes simultaneamente) podem ter o mesmo espectro de magnitude.

A Transformada de Fourier de Curto Prazo (STFT) resolve isso calculando FFTs sobre janelas sobrepostas do sinal. O resultado e um espectrograma: uma representação 2D com o tempo em um eixo e a frequência no outro. A intensidade em cada ponto mostra a energia naquela frequência naquele 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

Espectrogramas são a representação de entrada padrão para modelos de ML de áudio. Modelos de reconhecimento de fala (Whisper, DeepSpeech) operam sobre mel-espectrogramas -- espectrogramas com frequências mapeadas para a escala mel, que se ajusta melhor a percepção humana de tom.

Aliasing

Se um sinal contém frequências acima de fs/2 (a frequência de Nyquist), amostrar a uma taxa fs criara copias com aliasing. Um sinal de 90 Hz amostrado a 100 Hz parece idêntico a um sinal de 10 Hz. Não há como distingui-los apenas a partir das amostras.

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.

E por isso que conversores analógico-digital incluem filtros anti-aliasing que removem frequências acima de Nyquist antes da amostragem. Em ML, o aliasing aparece ao reduzir a amostragem (downsampling) de mapas de características sem filtragem passa-baixa adequada -- algumas arquiteturas tratam isso com camadas de pooling anti-aliasing.

Preenchimento com zeros não aumenta a resolução

Um equívoco comum: preencher um sinal com zeros antes da FFT melhora a resolução de frequência. Não melhora. O preenchimento com zeros interpola entre os bins de frequência existentes, lhe dando um espectro de aparencia mais suave. Mas ele não consegue revelar detalhe de frequência que não estava presente nas amostras originais.

A resolução de frequência verdadeira depende apenas do tempo de observação T = N / fs. Para resolver duas frequências separadas por delta_f, você precisa de pelo menos T = 1 / delta_f segundos de dados. Nenhuma quantidade de preenchimento com zeros muda esse limite fundamental.

Build It

Passo 1: DFT do zero

A DFT O(N^2) segue diretamente da definição.

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

Passo 2: DFT inversa

Mesma estrutura, expoente positivo, divisão 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

Passo 3: FFT (Cooley-Tukey)

A FFT recursiva exige comprimento potência de 2. Separe em par e impar, recursione, combine com fatores de rotação.

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

Passo 4: Funções auxiliares de análise 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 trabalho real, use a FFT do numpy, que e respaldada por bibliotecas C altamente otimizadas.

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 janelamento e análise espectral mais avançada:

from scipy.signal import windows, stft

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

Para convolução:

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

A matriz do espectrograma tem formato (n_frequencies, n_time_frames). Cada coluna e o espectro de potência em uma janela de tempo. E isso que modelos de ML de áudio consomem como entrada.

Ship It

Execute code/fourier.py para gerar outputs/prompt-spectral-analyzer.md.

Exercícios

1. Identificação de tom puro. Crie um sinal com uma única onda senoidal em uma frequência desconhecida (entre 1 e 50 Hz), amostrada a 128 Hz por 1 segundo. Use sua DFT para identificar a frequência. Verifique se a resposta confere. Agora adicione ruído gaussiano com desvio padrão 0,5 e repita. Como o ruído afeta o espectro?

2. Verificação FFT vs DFT. Gere um sinal aleatório de comprimento 64. Calcule tanto a DFT (O(N^2)) quanto a FFT. Verifique se todos os coeficientes coincidem com tolerância de 1e-10. Cronometre ambas as funções em sinais de comprimento 256, 512, 1024 e 2048. Plote a razão entre o tempo da DFT e o tempo da FFT.

3. Prova do teorema da convolução por exemplo. Crie o sinal x = [1, 2, 3, 4, 0, 0, 0, 0] e o filtro h = [1, 1, 1, 0, 0, 0, 0, 0]. Calcule a convolução circular deles diretamente (laço aninhado). Depois calcule-a via FFT (transformar, multiplicar, transformar inversamente). Verifique se os resultados conferem. Agora faça a convolução linear preenchendo com zeros apropriadamente.

4. Efeitos do janelamento. Crie um sinal que seja a soma de duas ondas senoidais em 10 Hz e 12 Hz (muito próximas). Amostre a 128 Hz por 1 segundo. Calcule o espectro de potência sem janela, com janela de Hann e com janela de Hamming. Qual janela torna mais fácil distinguir os dois picos? Por que?

5. Análise de codificação posicional. Gere as codificações posicionais senoidais para d_model = 128 e max_pos = 512. Para cada par de posições (p1, p2), calcule o produto escalar de suas codificações. Mostre que o produto escalar depende apenas de |p1 - p2|, não das posições absolutas. O que acontece com o produto escalar a medida que a distância aumenta?

Termos-Chave

Leitura Adicional

• Cooley & Tukey: An Algorithm for the Machine Calculation of Complex Fourier Séries (1965) - o artigo original da FFT que mudou a computação
• 3Blue1Brown: But what is the Fourier Transform? - a melhor introdução visual as transformadas de Fourier
• Lee-Thorp et al.: FNet: Mixing Tokens with Fourier Transforms (2021) - substitui a auto-atenção por FFT em transformers
• Smith: The Scientist and Engineer's Guide to Digital Signal Processing - livro-texto online gratuito cobrindo FFT, janelamento e análise espectral em profundidade
• Vaswani et al.: Attention Is All You Need (2017) - codificações posicionais senoidais derivadas da decomposição de frequência de Fourier
• Radford et al.: Whisper (2022) - reconhecimento de fala usando mel-espectrogramas como representação de entrada