Phase 01: Math Foundations

A Transformação de Fourier

Type: Build

Languages: Python, TypeScript

Prerequisites: Phase 1, Lessons 01-04, 19 (complex numbers)

Time: ~90 minutes

Objetivos de aprendizagem

• Implementar o DFT a partir do zero e verificá-lo em relação ao $O(N \log N)$Cooley-Tukey FFT
• Interpreta os coeficientes de frequência: extrair amplitude, fase e espectro de potência de um sinal
• Aplicar o teorema de convolução para realizar convolução através da multiplicação FFT
• Conectar a decomposição de frequência de Fourier para transformar codificadores posicionais e camadas de convolução CNN

O problema

Uma gravação de áudio é uma sequência de medições de pressão ao longo do tempo. Um preço de ação é uma sequência de valores ao longo de dias. Uma imagem é uma grade de intensidades de pixels sobre o espaço. Todos estes são dados no domínio do tempo (ou domínio do espaço). Você vê valores mudando em algum índice.

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

A transformação de Fourier converte dados do domínio do tempo para o domínio da frequência. Ele pega um sinal e o decompõe em ondas sinusais de diferentes frequências. Cada onda sinusa tem uma amplitude (quão forte é) e uma fase (onde começa).

Isto é importante para a ML porque o pensamento do domínio de frequência aparece em todos os lugares. As redes neurais convolucionais executam convolução, que é multiplicação no domínio de frequência. Os codificadores posicionais transformadores usam a decomposição de frequência para representar a posição. Os modelos de áudio (reconhecimento de fala, geração de música) operam em espectrogramas - representações de frequência do som. Os modelos de séries temporais procuram padrões periódicos. Entender a transformação de Fourier dá-lhe o vocabulário para trabalhar com todos estes.

O conceito

A definição de DFT

Dado$N$amostras x[0], x[1], \ldots, x[N-1], a Transformação de Fourier Discreta produz $N$coeficientes de frequência X[0], X[1], \ldots, X[N-1]- Não .

Cada um .X[k]É um número complexo.\lvert X[k] \rverté proporcional à amplitude de frequência $k$Sem normalização, um sino real de amplitude.$A$Que cai exactamente no bin .$k$dá\lvert X[k] \rvert = AN/2, então divide por $N/2$Para ler a amplitude.$\angle X[k]$Diz-lhe a fase de compensação dessa frequência.

A principal ideia:e^{-2\pi i k n/N}é um fator rotativo em frequência $k$O DFT calcula a correlação entre o sinal e cada um dos $N$Se o sinal contém energia em frequência$k$Se não, é quase zero.

O que significa cada coeficiente

X[0]: the DC component.Esta é a soma de todas as amostras -- proporcional à média. Representa a constante (frequência zero) de compensação do sinal.

X[k] for 1 \le k \le N/2: positive frequencies. $X[k]$representa frequência $k$Ciclos por $N$amostras.$k$significa uma frequência mais elevada (oscillação mais rápida).

X[N/2]: the Nyquist frequency.A maior frequência que pode representar com $N$Por cima disso, temos alias -- frequências altas mascaradas como baixas.

X[k] for N/2 < k < N: negative frequencies.Para sinais de valor real,$X[N-k] = \overline{X[k]}$As frequências negativas são imagens espelhadas das positivas.N/2 + 1- os coeficientes.

DFT inverso

O DFT inverso reconstitui o sinal original a partir dos seus coeficientes de frequência:

As únicas diferenças do DFT de futuro: o sinal no exponente é positivo (não negativo), e há um $1/N$fator de normalização.

O DFT inverso é uma reconstrução perfeita. Não há informação perdida. Você pode ir de domínio de tempo para domínio de frequência e de volta sem qualquer erro. O DFT é uma mudança de base - ele reexprime a mesma informação em um sistema de coordenadas diferente.

A FFT: a acelerar

O DFT tal como definido acima é O(N^2): para cada um $N$Os coeficientes de saída são somados.$N$amostras de entrada.N= 1 milhão, isto é $10^{12}$Operações.

A Transformação de Fourier Rápida (FFT) calcula o mesmo resultado em O(N \log N)- Para o ...N= 1 milhão, que é cerca de 20 milhões de operações em vez de um trilhão.

O algoritmo Cooley-Tukey (o FFT mais comum) funciona dividindo e conquistando:

1. Dividir o sinal em amostras indexadas e paradas.
2. Calcule o DFT de cada metade de forma recorrente.
3. Combine as duas DFTs de meia dimensão usando "fatores de bico" e^{-2\pi i k/N}- Não .

A simetria significa que cada nível de recursão faz$O(N)Trabalho, e há\log_2(N)$Níveis.O(N \log N)- Não .

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

O radix-2 FFT construído aqui é mais rápido quando o comprimento do sinal é um poder de 2. Sempre que um sub-problema tem comprimento ímpar, ele cai de volta à planície dft, por isso os sinais são muitas vezes empurrados a zero para a próxima potência de 2 para a velocidade.numpy.fftOs algoritmos de radix mistos são mais rápidos em longitudes com pequenos fatores primos.

Análise espectral

O power spectrumÉ o que é\lvert X[k] \rvert^2- a magnitude quadrada de cada coeficiente de frequência.

O phase spectrumÉ o que é$\angle X[k]$Para a maioria das tarefas de análise, você se importa com o espectro de potência e ignora a fase.

Resolução de frequência

A resolução de frequência do DFT depende do número de amostras $N$e a taxa de amostragem f_s- Não .

Para resolver duas frequências próximas, é preciso mais amostras. Para capturar frequências altas, é preciso uma taxa de amostragem mais alta.

O teorema da convolução

Este é um dos resultados mais importantes no processamento de sinais e diretamente relevante para as emissoras de televisão.

Convolution in the time domain equals pointwise multiplication in the frequency domain.

Por que isso importa:

• Convolução direta de dois sinais de comprimento $N$E ...M- Toma .$O(NM)$Operações.
• Convolução baseada em FFT $O(N \log N)$Transformar ambos, multiplicar, transformar de volta.
• Para núcleos grandes, a convolução FFT é dramaticamente mais rápida.
• É exatamente o que acontece nas camadas convolucionais com grandes campos receptivos.

Nota: o DFT calcula a convulsão circular (o sinal envolve-se). Para a convulsão linear (sem envolvimento), pad zero para ambos os sinais de comprimento $N + M - 1$antes da computação.

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

Janela

O DFT assume que o sinal é periódico - trata o $N$A diferença entre a frequência de um sinal e a frequência de um sinal é que o sinal não começa e termina no mesmo valor, o que cria uma discontinuidade na fronteira, que aparece como um conteúdo de alta frequência falso.

A janela reduz a fuga diminuindo o sinal para zero em ambas as extremidades antes de calcular o DFT.

Janela comum:

Aplicar a janela multiplicando-a por elemento com o sinal antes do DFT: X = DFT(x * w)- Não .

Propriedades DFT

O teorema de Parseval diz que a energia total é a mesma em ambos os domínios.

Conexão a codificações posicionais

O Transformer original usa codificações posicionais sinusoidais:

Cada par de dimensões .$(2i, 2i+1)$Oscila em uma frequência diferente. As frequências são espaçadas geométricamente de alta (dimensão 0,1) para baixa (última dimensão). Isso dá a cada posição um padrão único em todas as bandas de frequência - semelhante à forma como os coeficientes de Fourier identificam um sinal de forma única.

As principais propriedades que isto fornece:

• Uniqueness:Não há duas posições com a mesma codificação.
• Bounded values:O pecado e o cos estão sempre dentro.[-1, 1]- Não .
• Relative position:A codificação da posição $p+k$pode ser expressa como uma função linear da codificação em posição $p$O modelo pode aprender a atender a posições relativas.

Conexão com as CNNs

Uma camada de convolução aplica um filtro aprendido (núcleo) à entrada deslizando-o através do sinal ou imagem.

Pelo teorema da convolução, isto é equivalente a:

1. FFT a entrada
2. FFT o núcleo
3. Multiplicar no domínio de frequência
4. Se o resultado for

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

Espectogramas e a Transforma Fourier de Curto Tempo

Um único FFT dá-lhe o conteúdo de frequência de todo o sinal, mas não lhe diz nada sobre quando essas frequências ocorrem.

A Transformação de Fourier de Tempo Curto (STFT) resolve isso computação de FFTs em janelas sobrepostas do sinal. O resultado é um espectrograma: uma representação 2D com tempo em um eixo e frequência no outro. A intensidade em cada ponto mostra a energia na frequência naquele momento.

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

Os espectrogramas são a representação padrão de entrada para modelos de áudio ML. Os modelos de reconhecimento de fala (Whisper, DeepSpeech) operam em espectrogramas mel - espectrogramas com frequências mapeadas na escala mel, que melhor se encaixa na percepção de pitch humana.

Aliasing

Se um sinal contém frequências acima f_s/2(a frequência de Nyquist), amostragem a taxa $f_s$O sinal de 90 Hz amostragado a 100 Hz parece idêntico ao sinal de 10 Hz. Não há forma de distinguir-los das amostras sozinhas.

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 isso que os conversores analógicos para digitais incluem filtros anti-aliasing que removem as frequências acima de Nyquist antes da amostragem.

A colcha zero não aumenta a resolução

Um equívoco comum: empolgar um sinal antes de FFT melhora a resolução de frequência. Não. O empolgar zero interpola entre os recipientes de frequência existentes, dando-lhe um espectro mais liso. Mas não pode revelar detalhes de frequência que não estavam presentes nas amostras originais.

A verdadeira resolução de frequência depende apenas do tempo de observação $T = N / f_s$Para resolver duas frequências separadas por$\Delta f$, você precisa pelo menos$T = 1 / \Delta f$Nenhuma quantidade de empolgação de zero altera este limite fundamental.

Construí-lo

Passo 1: DFT a partir do zero

O $O(N^2)$A DFT segue diretamente a partir 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 inverso

A mesma estrutura, exponente positivo, dividido por N- Não .

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)

O FFT recorrente requer poder de 2 comprimento. Dividido em par e ímpar, recorrente, combinar com fatores de torcida.

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

Usá-lo

Para o trabalho real, use o FFT da numpy, que é apoiado 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 análise espectral mais avançada e para análise de janelas:

from scipy.signal import windows, stft

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

Para convulsão:

from scipy.signal import fftconvolve

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

Para os 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 forma (n_frequências, n_time_frames). Cada coluna é o espectro de potência em uma janela de tempo.

Envia-o

Corra .code/fourier.pypara gerar outputs/prompt-spectral-analyzer.mdA versão do TypeScript,code/fourier.ts, escreve o mesmo ficheiro.

Exercícios

1. Pure tone identification.Crie um sinal com uma única onda sinusal em uma freqüência desconhecida (entre 1 e 50 Hz), amostragem a 128 Hz por 1 segundo. Use o seu DFT para identificar a frequência. Verifique as correspondências da resposta. Agora adicione ruído gaussiano com desvio padrão 0,5 e repita. Como o ruído afeta o espectro?

2. FFT vs DFT verification.Gerenar um sinal aleatório de comprimento 64.$O(N^2){}$Verifique se todos os coeficientes correspondem a dentro de 1e-10. Tempo funciona em ambos os sinais de comprimento 256, 512, 1024, e 2048.

3. Convolution theorem proof by example.Crie o sinal x = [1, 2, 3, 4, 0, 0, 0, 0] e filtre h = [1, 1, 1, 0, 0, 0, 0, 0]. Calcule sua convolução circular diretamente (loop aninhado). Em seguida, compute-o através de FFT (transformação, multiplicação, transformação inversa). Verifique a correspondência dos resultados. Agora, faça a convolução linear com pad zero apropriadamente.

4. Windowing effects.Crie um sinal que seja a soma de duas ondas sinusais a 10 Hz e 12 Hz (muito perto). Mostre a 128 Hz por 1 segundo. Calcule o espectro de potência sem janela, janela Hann e janela Hamming. Qual janela torna mais fácil distinguir os dois picos? Por quê?

5. Positional encoding analysis.Gerar as codificações posicionais sinusoidais para d_modelo = 128 e max_pos = 512. Para cada par de posições (p_1, p_2), calcular o produto de pontos de suas codificações. Mostrar que o produto de pontos depende apenas de$\lvert p_1 - p_2 \rvert$O que acontece com o produto de pontos à medida que a distância aumenta?

Indicios

Exercise 1.Com 128 amostras em 1 segundo, bin kÉ o que é$k$Hz, então para uma frequência inteira o índice do maior valor em canhões 1 a 63 é a frequência.generate_signalE ...magnitude_spectrumDepois de adicionar ruído, verifique se o pico está no mesmo lixo enquanto os outros sacos subem.

Exercise 2.Use uma potência de dois comprimentos, porque fftDivide o sinal em duas partes.max(abs(a - b))A taxa de tempo deve aumentar aproximadamente a$N / \log_2 N$- Não .

Exercise 3.Para a convolução circular, calcular y[n] = \sum_k h[k] x[(n-k) \bmod 8]- por mão$n$= 0, 1 e 2, e comparar os três primeiros valores de convolve_directE ...convolve_fftA convulsão linear tem comprimento 4 + 3 - 1 = 6, por isso verifique primeiro se o comprimento 8 já é longo o suficiente.

Exercise 4.Utilizaçãohann_window- Não .hamming_window- Não .apply_window, e power_spectrum, e contar os picos separados entre 9 e 13 Hz. Tanto 10 Hz quanto 12 Hz completam ciclos inteiros em 1 segundo, de modo que nenhuma janela pode parecer melhor. Repita com 10,5 Hz e 12,5 Hz para ver o vazamento que as janelas reduzem.

Exercise 5.Calcule cada codificação com positional_encoding(pos, 128). Compare o produto ponto para posições (0, 10) com o produto ponto para (100, 110): os dois valores devem corresponder a cerca de 1e-10.$\lvert p_1 - p_2 \rvert$Para um fixo$p_1$- Não .

Termos-chave

Mais leitura

• Cooley & Tukey: An Algorithm for the Machine Calculation of Complex Fourier Series (1965)- o papel original da FFT que mudou a computação
• 3Blue1Brown: But what is the Fourier Transform?- a melhor introdução visual às transformações de Fourier
• Lee-Thorp et al.: FNet: Mixing Tokens with Fourier Transforms (2021)- substitui a auto-atenção pela FFT nos transformadores
• Smith: The Scientist and Engineer's Guide to Digital Signal Processing- livro de texto online gratuito que abrange em profundidade a FFT, a análise das janelas e os espectros
• Vaswani et al.: Attention Is All You Need (2017)- codificadores posicionais sinusoidais derivados da decomposição de frequência de Fourier
• Radford et al.: Whisper (2022)- reconhecimento de voz utilizando espectrogramas mel como representação de entrada

This free lesson is part of the AI Engineering from Scratch curriculum. Read the full explanation, run the lesson code, and verify the result in the interactive reader or from the repository source.

Browse the complete course catalog or open this lesson on GitHub.