Phase 01: Math Foundations

La transformation de Fourier

Type: Build

Language:Python

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

Time: ~90 minutes

Objectifs d'apprentissage

• Mettre en œuvre la FFT à partir de zéro et la vérifier contre la FFT O(N log N) Cooley-Tukey
• Interpréter les coefficients de fréquence: extraire l'amplitude, la phase et le spectre de puissance d'un signal
• Appliquer le théorème de la convolutions pour effectuer la convolutions par la multiplication FFT
• Connectez la décomposition de fréquence Fourier aux couches de codage positionnel et de convolutions de CNN transformateurs

Le problème

Une enregistrement audio est une séquence de mesures de pression au fil du temps. Un prix d'action est une séquence de valeurs sur plusieurs jours. Une image est une grille d'intensités de pixels sur l'espace. Toutes ces données sont dans le domaine du temps (ou domaine de l'espace). Vous voyez des valeurs en changement sur un certain indice.

Mais de nombreux modèles sont invisibles dans le domaine temporel. Ce signal audio est-il un ton pur ou un accord? Le prix de l'action a-t-il un cycle hebdomadaire? Cette image a-t-elle une texture répétée? Ces questions concernent le contenu de la fréquence, et le domaine temporel le cache.

La transformation de Fourier convertit les données du domaine temporel au domaine de fréquence. Elle prend un signal et le décompose en ondes sinusales de différentes fréquences. Chaque onde sinusale a une amplitude (la force de son amplitude) et une phase (où elle démarre).

Cela importe pour ML parce que la pensée du domaine de fréquence apparaît partout. Les réseaux neuronaux convolutifs effectuent une convolutions, qui est la multiplication dans le domaine de fréquence. Les encodements positionnels des transformateurs utilisent la décomposition de fréquence pour représenter la position. Les modèles audio (reconnaissance de la parole, génération de musique) fonctionnent sur des spectrogrammes - représentations de fréquence du son. Les modèles de séries temporelles recherchent des modèles périodiques. Comprendre la transformation de Fourier vous donne le vocabulaire pour travailler avec tout cela.

Le concept

La définition de la DFT

Compte tenu des échantillons N x[0], x[1], ..., x[N-1], la Transformation Fourier discrète produit des coefficients de fréquence N X[0], X[1], ..., X[N-1]:

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

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

Chaque X [k] est un nombre complexe. Sa magnitude. X [k] détecte l'amplitude de la fréquence k. Son angle de phase ((X [k]) vous indique le décalage de phase de cette fréquence.

Le point de vue clé: e^(-2piikn/N)est un phasor rotatif à la fréquence k. Le DFT calcule la corrélation entre le signal et chacune des fréquences N à espace égal. Si le signal contient de l'énergie à la fréquence k, la corrélation est grande.

Ce que chaque coefficient signifie

X[0]: the DC component.C'est la somme de tous les échantillons, proportionnelle à la moyenne.

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

X[k] for 1 <= k <= N/2: positive frequencies.X[k] représente les cycles de fréquence k par échantillon N. Un k plus élevé signifie une fréquence plus élevée (oscillation plus rapide).

X[N/2]: the Nyquist frequency.La fréquence la plus élevée que vous pouvez représenter avec des échantillons N. Au-dessus de cela, vous obtenez un aliasing -- des fréquences élevées masquant comme des fréquences basses.

X[k] for N/2 < k < N: negative frequencies.Pour les signaux à valeur réelle, X[N-k] = conj(X[k]). Les fréquences négatives sont des images miroir des signaux positifs. C'est pourquoi les informations utiles sont dans les premiers coefficients N/2 + 1.

DFT inversé

Le DFT inverse reconstruit le signal d'origine à partir de ses coefficients de fréquence:

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

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

Les seules différences du DFT avant: le signe dans l'exponent est positif (pas négatif), et il y a un facteur de normalisation 1/N.

Le DFT inverse est une reconstruction parfaite. Aucune information n'est perdue. Vous pouvez passer du domaine temporel au domaine de fréquence et retourner sans aucune erreur. Le DFT est un changement de base - il réexprime les mêmes informations dans un système de coordonnées différent.

Le FFT: le rendre rapide

Le DFT tel que défini ci-dessus est O(N^2): pour chacun des coefficients de sortie N, vous sumez sur N échantillons d'entrée.

La transformation rapide de Fourier (FFT) calcule le même résultat en O(N log N. Pour N = 1 million, c'est environ 20 millions d'opérations au lieu d'un trillion.

L'algorithme Cooley-Tukey (le FFT le plus courant) fonctionne par division et conquête:

1. Divisez le signal en échantillons indexés par et par.
2. Calculer le DFT de chaque moitié de manière récursive.
3. Combinez les deux DFT de taille moyenne en utilisant des "facteurs à double" e^(-2pii*k/N).

CopyX[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 symétrie signifie que chaque niveau de récursion fonctionne O(N), et il y a des niveaux log2(N. 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 exige que la longueur du signal soit de puissance 2.

Analyse spectrale

Le power spectrumest X [k] squares - la magnitude carrée de chaque coefficient de fréquence.

Le phase spectrumest angle ((X[k]) -- le décalage de phase de chaque fréquence. Pour la plupart des tâches d'analyse, vous vous souciez du spectre de puissance et ignorez la phase.

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

Résolution de fréquence

La résolution de fréquence du DFT dépend du nombre d'échantillons N et du taux d'échantillonnage fs.

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

Pour résoudre deux fréquences proches, il faut plus d'échantillons.

Le théorème de la convolutions

C'est l'un des résultats les plus importants dans le traitement des signaux et directement pertinent pour les CNN.

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

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

where * is convolution and . is element-wise multiplication

Pourquoi cela importe ?

• La convolutions directes de deux signaux de longueur N et M effectuent des opérations O(N*M).
• La convolutions basées sur FFT prennent O(N log N): transformer les deux, multiplier, transformer en arrière.
• Pour les grands noyaux, la convolutions FFT sont considérablement plus rapides.
• C'est exactement ce qui se passe dans les couches convolutives avec de grands champs réceptifs.

Note: le DFT calcule la convulsion circulaire (le signal se retourne). Pour la convulsion linéaire (pas de contour), les deux signaux sont à zéro avant le calcul.

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

Les fenêtres

Le DFT suppose que le signal est périodique - il traite les échantillons N comme une période d'un signal infiniment répétitif. Si le signal ne commence pas et ne se termine pas à la même valeur, cela crée une discontinuité à la limite, qui apparaît comme un contenu à haute fréquence faux. Cela s'appelle fuite spectrale.

Le débit de la fenêtre réduit la fuite en réduisant le signal à zéro à chaque extrémité avant de calculer le DFT.

Les fenêtres communes:

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

Appliquer la fenêtre en la multipliant par élément avec le signal avant le DFT: X = DFT(x * w)- Je suis désolé .

Propriétés de DFT

Le théorème de Parseval dit que l'énergie totale est la même dans les deux domaines.

Connexion à des encodements positionnels

Le Transformer original utilise des codes positionnels sinusoïdes:

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

Chaque paire de dimensions (2i, 2i+1) oscille à une fréquence différente. Les fréquences sont géométriquement séparées de haute (dimension 0,1) à basse (dernières dimensions). Cela donne à chaque position un motif unique dans toutes les bandes de fréquences - similaire à la façon dont les coefficients de Fourier identifient uniquement un signal.

Les propriétés clés que cela fournit:

• Uniqueness:Aucune position n'a le même code.
• Bounded values:Le péché et le cos sont toujours dans [-1, 1].
• Relative position:Le codage de la position p+k peut être exprimé comme une fonction linéaire du codage à la position p. Le modèle peut apprendre à attirer les positions relatives.

Connexion à la CNN

Une couche de convolutions applique un filtre (nucle) appris à l'entrée en le faisant glisser à travers le signal ou l'image.

Selon le théorème de la convolutions, cela équivaut à:

1. FFT l'entrée
2. FFT le noyau
3. Multipliez dans le domaine de fréquence
4. Si le résultat est

Les implémentations standard de CNN utilisent la convulsion directe (plus rapide pour les petits noyaux 3x3). Mais pour les grands noyaux ou la convulsion globale, les approches basées sur FFT sont nettement plus rapides. Certaines architectures (comme FNet) remplacent entièrement l'attention par FFT, atteignant une précision concurrentielle avec O(N log N) au lieu de la complexité O(N^2).

Les spectrogrammes et la transformation Fourier à court terme

Un FFT unique vous donne le contenu de fréquence de l'ensemble du signal, mais ne vous dit rien sur quand ces fréquences se produisent.

La transformation Fourier à court temps (STFT) résout cette question en calculant des FFT sur des fenêtres de signal qui se chevauchent. Le résultat est un spectrogramme: une représentation 2D avec le temps sur un axe et la fréquence sur l'autre. L'intensité à chaque point montre l'énergie à cette fréquence à ce moment-là.

CopySTFT 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

Les spectrogrammes sont la représentation standard des entrées pour les modèles audio ML. Les modèles de reconnaissance de la parole (Whisper, DeepSpeech) fonctionnent sur des spectrogrammes mel - des spectrogrammes avec des fréquences mappées à l'échelle mel, ce qui correspond mieux à la perception du son humain.

Le nom de l'alias

Si un signal contient des fréquences supérieures à fs/2 (la fréquence de Nyquist), l'échantillonnage à la fréquence fs créera des copies alias. Un signal de 90 Hz échantillonné à 100 Hz ressemble à un signal de 10 Hz. Il n'y a aucun moyen de les distinguer des échantillons seuls.

CopyExample:
  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.

C'est pourquoi les convertisseurs analogiques vers numériques incluent des filtres anti-aliasing qui éliminent les fréquences supérieures à Nyquist avant le prélèvement d'échantillons.

Le rembourrage à zéro n'augmente pas la résolution

Un malentendu commun: le remplissage à zéro d'un signal avant FFT améliore la résolution de la fréquence. Ce n'est pas le cas. Le remplissage à zéro interpole entre les poubelles de fréquences existantes, ce qui vous donne un spectre plus lisse. Mais il ne peut pas révéler les détails de fréquence qui n'étaient pas présents dans les échantillons originaux.

La résolution de la fréquence réelle dépend uniquement du temps d'observation T = N / fs. Pour résoudre deux fréquences séparées par delta_f, vous avez besoin d'au moins T = 1 / delta_f secondes de données. Aucune quantité de rembourrage zéro ne modifie cette limite fondamentale.

Faites-le

Étape 1: DFT à partir de zéro

Le DFT O ((N^2) dérive directement de la définition.

pythonCopyimport 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

Étape 2: DFT inversé

La même structure, l'exponent positif, divisé par N.

pythonCopydef 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

Étape 3: FFT (Cooley-Tukey)

La FFT récursive nécessite une puissance de longueur de 2.

pythonCopydef 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

Étape 4: Aide à l'analyse spectrale

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

Utilisez-le

Pour le vrai travail, utilisez le FFT de numpy qui est pris en charge par des bibliothèques C hautement optimisées.

pythonCopyimport 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]

Pour l'analyse des fenêtres et des spectraux plus avancés:

pythonCopyfrom scipy.signal import windows, stft

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

Pour la convolutions:

pythonCopyfrom scipy.signal import fftconvolve

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

Pour les spectrogrammes:

pythonCopyfrom scipy.signal import stft

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

La matrice du spectrogramme a une forme (n_frequences, n_time_frames). Chaque colonne est le spectre de puissance à une fenêtre temporelle.

La faire partir

On court .code/fourier.pypour générer outputs/prompt-spectral-analyzer.md- Je suis désolé .

Exercices

1. Pure tone identification.Créer un signal avec une seule onde sinus à une fréquence inconnue (entre 1 et 50 Hz), échantillonné à 128 Hz pendant 1 seconde. Utilisez votre DFT pour identifier la fréquence. Vérifiez les correspondances de la réponse. Ajoutez maintenant le bruit gaussien avec déviation standard 0.5 et répète. Comment le bruit affecte-t-il le spectre?

1. FFT vs DFT verification.Générer un signal aléatoire de longueur 64. Compute à la fois DFT (O(N^2)) et FFT. Vérifiez que tous les coefficients correspondent à 1e-10. Le temps fonctionne sur les signaux de longueur 256, 512, 1024, et 2048.

1. Convolution theorem proof by example.Créer le signal x = [1, 2, 3, 4, 0, 0, 0, 0] et filtrer h = [1, 1, 1, 0, 0, 0, 0, 0]. Computez leur convolutions circulaires directement (boucle nichée). Computez-le ensuite via FFT (transformation, multiplication, transformation inverse). Vérifiez la correspondance des résultats.

1. Windowing effects.Créer un signal qui est la somme de deux ondes sinusoïdes à 10 Hz et 12 Hz (très proche). échantillonner à 128 Hz pendant 1 seconde. Compute le spectre de puissance sans fenêtre, fenêtre Hann et fenêtre Hamming. Quelle fenêtre rend le plus facile de distinguer les deux sommets? Pourquoi?

1. Positional encoding analysis.Générer les codage positionnaires sinusoïdes pour d_model = 128 et max_pos = 512. Pour chaque paire de positions (p1, p2), calculer le produit des points de leurs codage. Montrez que le produit des points dépend uniquement de p1 - p2 et non des positions absolues. Que se passe-t-il au produit des points à mesure que la distance augmente?

Les termes clés

Pour en savoir plus

• Cooley & Tukey: An Algorithm for the Machine Calculation of Complex Fourier Series (1965)- le papier FFT original qui a changé l'informatique
• 3Blue1Brown: But what is the Fourier Transform?- la meilleure introduction visuelle aux transformations de Fourier
• Lee-Thorp et al.: FNet: Mixing Tokens with Fourier Transforms (2021)- remplace l'auto-attention par la FFT dans les transformateurs
• Smith: The Scientist and Engineer's Guide to Digital Signal Processing- livre en ligne gratuit couvrant en profondeur les FFT, les fenêtres et l'analyse spectrale
• Vaswani et al.: Attention Is All You Need (2017)- les encodements positionnels sinusoïdes dérivés de la décomposition de fréquence Fourier
• Radford et al.: Whisper (2022)- reconnaissance vocale à l'aide de mélespectogrammes comme représentation d'entrée

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.