Contexte et définition

Dans le traitement numérique, on travaille souvent avec un vecteur fini x[n] de longueur N. En supposant que ces N échantillons représentent une période unique d’un signal périodique, on peut appliquer la série de Fourier discrète (DTFS). Le Discrete Fourier Transform (DFT) est défini par la formule X[k] = \sum_{n=0}^{N-1} x[n] \exp(-2\pi i k n / N) pour k = 0 … N-1. Cette expression fournit N coefficients complexes qui décrivent les composantes fréquentielles du signal. Le DFT peut être vu comme un échantillonnage régulier du DTFT, chaque valeur X[k] correspondant à une fréquence k/N du domaine continu.

Implémentation directe en Python

Le code suivant calcule le DFT de façon naïve, en suivant exactement la formule mathématique :

def dft(x):
    """Return X[k] = sum_n x[n] exp(-2 pi i k n / N)."""
    N = len(x)
    n = np.arange(N)
    X = np.empty(N, dtype=complex)
    for k in range(N):
        weights = np.exp(-2j * np.pi * k * n / N)
        X[k] = np.sum(x * weights)
    return X

Chaque itération crée un tableau weights contenant les facteurs d’exponentielle pour tous les indices n. La multiplication point‑wise x * weights reproduit le produit x[n]·e^{-2πikn/N}, puis la somme réalise la sommation sur n. Cette version a une complexité O(N²), ce qui devient prohibitif pour de grands N.

Matrice de Fourier et racines de l’unité

Les racines N‑ièmes de l’unité W_N = exp(-2π i / N) forment une base orthogonale dans ℂᴺ. En élevant W_N à la puissance k·n on obtient la matrice de Fourier F[k,n] = W_N^{k n}. Multiplication de F par le vecteur colonne x reproduit exactement le DFT :

def dft_matrix(N):
    """Construct F[k, n] = W_N**(k*n), where W_N = exp(-2 pi i / N)."""
    root = np.exp(-2j * np.pi / N)
    indices = np.arange(N)
    exponents = np.outer(indices, indices)
    return root**exponents

def dft_via_matrix(x):
    """Compute the DFT as F @ x with the Fourier matrix"""
    return dft_matrix(len(x)) @ x

Cette représentation met en évidence la nature linéaire du DFT et explique pourquoi la matrice F est unitaires : F·F⁺ = N·I, où F⁺ désigne la matrice conjuguée‑transposée. Le facteur N apparaît parce que chaque vecteur de la base possède une norme √N.

Transformée inverse et reconstruction

L’inverse du DFT s’obtient en utilisant la matrice conjuguée de F. La formule inverse est x[n] = (1/N) \sum_{k=0}^{N-1} X[k] \exp(2π i k n / N). En notation matricielle, F^{-1} = (1/N)·F⁺, ce qui conduit à la reconstruction suivante :

def idft(X):
    N = len(X)
    n = np.arange(N)
    x = np.empty(N, dtype=complex)
    for n_idx in range(N):
        weights = np.exp(2j * np.pi * n_idx * np.arange(N) / N)
        x[n_idx] = np.sum(X * weights) / N
    return x

Le même résultat peut être obtenu en multipliant le vecteur X par (1/N)·F⁺. Cette double démonstration – via la série DTFS et via l’algèbre linéaire – confirme que le DFT est une transformation bijective sur l’espace fini des signaux de longueur N. La propriété d’inversibilité garantit que toute information contenue dans les coefficients fréquentiels peut être récupérée sans perte.