Aller au contenu
ELECTRONICS ENGINEERINGelectronics-engineering.com
Recommandée par l'auteur Analyse numérique Traitement numérique du signal Théorie du signal

La transformée de Fourier discrète (DFT) : de la DTFT à l'inverse, propriétés et convolution circulaire démontrées

La DFT comme échantillonnage de la DTFT et repliement temporel, inverse par orthogonalité, Parseval, décalage circulaire, symétrie hermitienne, convolution circulaire et linéaire, noyau de Dirichlet, complétion par des zéros, vérifiée en Python.

https://www.electronics-engineering.com/fr/dft-transformee-de-fourier-discrete-demonstrations-convolution-circulaire/

Cette page vous a-t-elle été utile ? Notez-la :
moyenne 4,0 sur 1 vote

La transformée de Fourier discrète (DFT) est la transformée qu’un ordinateur peut vraiment calculer : elle prend N nombres et en renvoie N. Tout analyseur de spectre numérique, tout égaliseur, tout modem OFDM (Wi-Fi, 4G, 5G) et tout filtre rapide l’utilise, presque toujours à travers l’algorithme FFT. Cet approfondissement dérive la DFT de la transformée de Fourier à temps discret (DTFT) et en démontre les formules et les propriétés : transformée inverse, Parseval, décalage circulaire, symétrie hermitienne, convolution circulaire et comment en tirer la convolution linéaire. Les leçons liées expliquent l’algorithme FFT et l’usage pratique dans l’analyse spectrale (fuite spectrale, fenêtres, méthode de Welch). Le parcours suit les sujets des notes de Sandro Petrizzelli dont cette page est issue.

De la DTFT à la DFT

Une suite x[n] a pour DTFT

    \[ X(e^{j\omega}) = \sum_{n=-\infty}^{\infty} x[n]\,e^{-j\omega n} \]

une fonction continue, périodique de période 2\pi en pulsation normalisée \omega. Un ordinateur ne peut pas mémoriser une fonction continue : il en prend N échantillons équidistants, \omega_k = \frac{2\pi k}{N}, k = 0, \dots, N - 1. Si x[n] n’est non nulle que pour 0 \le n \le N - 1, ces échantillons sont

    \[ X[k] = X(e^{j2\pi k/N}) = \sum_{n=0}^{N-1} x[n]\,W_N^{kn},\qquad W_N = e^{-j2\pi/N} \]

C’est la DFT à N points. Le nombre W_N est une racine N-ième de l’unité : W_N^N = 1, et ses puissances sont N points équidistants sur le cercle unité.

La DFT échantillonne la DTFT
La courbe grise en pointillés est le module de la DTFT d’une impulsion rectangulaire de 4 échantillons ; les points rouges sont la DFT à 8 points, les bleus la DFT à 16 points de la même impulsion complétée par des zéros : ils échantillonnent la même courbe de façon plus dense.

Théorème (échantillonner en fréquence, c’est répéter dans le temps). Si x[n] est plus longue que N, les échantillons X(e^{j2\pi k/N}) de sa DTFT coïncident avec la DFT de la suite \tilde x[n] = \sum_{r} x[n - rN], 0 \le n \le N - 1 : les parties de x au-delà de N se superposent (repliement temporel).

Démonstration. On découpe la somme de la DTFT en blocs de N échantillons, n = m + rN avec 0 \le m \le N - 1 : X(e^{j2\pi k/N}) = \sum_r\sum_{m=0}^{N-1} x[m + rN]\,W_N^{k(m + rN)}. Comme W_N^{krN} = 1, il reste \sum_{m=0}^{N-1}\big(\sum_r x[m + rN]\big)W_N^{km}, la DFT de \tilde x. ∎

C’est le dual du théorème d’échantillonnage : échantillonner dans le temps rend le spectre périodique, échantillonner le spectre rend le signal périodique. C’est pourquoi la DFT traite toujours le bloc de N échantillons comme s’il était une période d’un signal périodique : toutes les propriétés qui suivent sont « circulaires ».

La transformée inverse

Théorème. x[n] = \dfrac{1}{N}\displaystyle\sum_{k=0}^{N-1} X[k]\,W_N^{-kn}.

Démonstration. Il faut un lemme, l’orthogonalité des exponentielles discrètes : \sum_{k=0}^{N-1} W_N^{k\ell} = N si \ell est un multiple de N, sinon 0. En effet dans le premier cas chaque terme vaut 1 ; dans le second W_N^\ell \ne 1 et la somme géométrique vaut \frac{1 - W_N^{N\ell}}{1 - W_N^\ell} = \frac{1 - 1}{1 - W_N^\ell} = 0. On substitue maintenant la définition :

    \[ \frac{1}{N}\sum_{k=0}^{N-1}\Big(\sum_{m=0}^{N-1} x[m]W_N^{km}\Big)W_N^{-kn} = \frac{1}{N}\sum_{m=0}^{N-1} x[m]\sum_{k=0}^{N-1} W_N^{k(m - n)} \]

La somme intérieure vaut N seulement pour m = n (avec m, n entre 0 et N - 1, m - n est un multiple de N seulement s’il est nul) : il reste x[n]. ∎

Sous forme matricielle X = F_N x avec (F_N)_{kn} = W_N^{kn}, et le théorème dit que F_N^{-1} = \frac{1}{N}F_N^* : la matrice \frac{1}{\sqrt N}F_N est unitaire. Le théorème de Parseval en découle immédiatement :

    \[ \sum_{n=0}^{N-1}|x[n]|^2 = \frac{1}{N}\sum_{k=0}^{N-1}|X[k]|^2 \]

parce qu’une matrice unitaire conserve la norme : \|x\|^2 = \|\tfrac{1}{\sqrt N}X\|^2. L’énergie peut se mesurer indifféremment dans le temps ou en fréquence.

Les propriétés, démontrées

Dans tout ce qui suit les indices sont pris modulo N : (n)_N est le reste de la division de n par N.

Linéarité. a\,x[n] + b\,y[n] \leftrightarrow a\,X[k] + b\,Y[k] : la définition est une somme.

Décalage temporel circulaire. x[(n - m)_N] \leftrightarrow W_N^{km}X[k].

Démonstration. \sum_n x[(n - m)_N]W_N^{kn} ; avec p = (n - m)_N, quand n parcourt 0, \dots, N - 1 p aussi (dans un autre ordre), et W_N^{kn} = W_N^{k(p + m)} parce que W_N^{kN} = 1. La somme devient W_N^{km}\sum_p x[p]W_N^{kp} = W_N^{km}X[k]. ∎

Le retard ne change que la phase des coefficients, pas le module. Mais c’est un retard circulaire : les échantillons qui sortent à droite rentrent à gauche.

Décalage circulaire de 3 échantillons sur 8
Les trois derniers échantillons de la suite bleue, en orange, sortent à droite et rentrent au début : c’est le retard qui correspond à la multiplication de la DFT par W puissance 3k.

Décalage en fréquence (modulation). W_N^{-k_0n}x[n] \leftrightarrow X[(k - k_0)_N] : même démonstration avec les rôles échangés. Multiplier par une exponentielle complexe décale le spectre : c’est le principe de la conversion de fréquence dans les récepteurs numériques.

Symétrie hermitienne. Si x[n] est réelle, X[N - k] = X^*[k].

Démonstration. X[N - k] = \sum_n x[n]W_N^{(N - k)n} = \sum_n x[n]W_N^{-kn}, parce que W_N^{Nn} = 1. Pour x réelle, la conjugaison ne change que le signe de l’exposant : X^*[k] = \sum_n x[n]W_N^{-kn}. ∎

Donc la partie réelle et le module sont symétriques par rapport à k = N/2, la partie imaginaire et la phase antisymétriques : pour un signal réel les coefficients de 0 à N/2 suffisent, et la FFT « réelle » fait la moitié du calcul. Le coefficient X[N/2] (avec N pair) est la fréquence de Nyquist et il est réel.

Symétrie de la DFT d'un signal réel
La DFT à 8 points de la suite réelle 3, 1, −1, 2, 0, 1, 0, −2 : la partie réelle, en bleu, est symétrique par rapport à N/2 ; la partie imaginaire, en rouge, est antisymétrique.

Symétrie circulaire. Si de plus x[(-n)_N] = x[n] (paire au sens circulaire, c’est-à-dire x[N - n] = x[n]), la DFT est réelle ; si elle est impaire, imaginaire pure. Cela découle de la propriété précédente : pour x paire, X^*[k] = X[N - k] = X[k].

La convolution circulaire

Théorème. Le produit des DFT correspond à la convolution circulaire :

    \[ Y[k] = X[k]H[k] \;\leftrightarrow\; y[n] = \sum_{m=0}^{N-1} x[m]\,h[(n - m)_N] = (x \circledast h)[n] \]

Démonstration. On calcule la DFT de y et on utilise le décalage circulaire : \sum_n\sum_m x[m]h[(n - m)_N]W_N^{kn} = \sum_m x[m]\Big(\sum_n h[(n - m)_N]W_N^{kn}\Big) = \sum_m x[m]W_N^{km}H[k] = X[k]H[k]. ∎

Filtrer un signal est au contraire une convolution linéaire, y[n] = \sum_m x[m]h[n - m], de longueur L + M - 1 si x et h ont pour longueurs L et M. La convolution circulaire sur N points est la linéaire « enroulée » : les échantillons au-delà de N - 1 sont ajoutés au début (le théorème d’échantillonnage en fréquence appliqué à y).

Exemple. x = (1, 2, 3), h = (1, 1). La convolution linéaire est (1, 3, 5, 3). Avec une DFT à N = 3 points le dernier 3 s’enroule sur n = 0 : (1 + 3, 3, 5) = (4, 3, 5), un résultat faux pour un filtre. Avec N = 4 \ge L + M - 1 il n’y a pas de chevauchement et on retrouve (1, 3, 5, 3).

Convolution linéaire et circulaire
À gauche la convolution linéaire de (1, 2, 3) avec (1, 1), longue de 4 échantillons ; avec N = 3 le dernier échantillon, en orange, s’enroule sur le premier et la convolution circulaire, en rouge, vaut 4, 3, 5.

Règle pratique : pour filtrer avec la FFT, on complète x et h par des zéros jusqu’à N \ge L + M - 1. Pour les longs signaux on découpe le signal en blocs et on utilise les méthodes overlap-add et overlap-save, qui recomposent les blocs sans erreurs ; avec un grand N le coût, O(N\log N) au lieu de O(LM), est bien inférieur à celui de la convolution directe.

Deux DFT à connaître par cœur

Impulsion rectangulaire de L échantillons sur N points : avec la somme géométrique

    \[ X[k] = \sum_{n=0}^{L-1} W_N^{kn} = \frac{1 - W_N^{kL}}{1 - W_N^k} = e^{-j\pi k(L - 1)/N}\,\frac{\sin(\pi kL/N)}{\sin(\pi k/N)} \]

(en mettant en facteur e^{-j\pi kL/N} au numérateur et e^{-j\pi k/N} au dénominateur). Le module est le noyau de Dirichlet, la version discrète du sinus cardinal : pour L = 4, N = 8 il vaut 4, 2.613, 0, 1.082, 0, 1.082, 0, 2.613. C’est aussi la réponse de la fenêtre rectangulaire, l’origine de la fuite spectrale.

Cosinus sur une case. x[n] = \cos\frac{2\pi k_0n}{N} = \frac{1}{2}\big(W_N^{-k_0n} + W_N^{k_0n}\big) : par orthogonalité la DFT vaut \frac{N}{2} en k = k_0 et en k = N - k_0, zéro ailleurs. Si la fréquence ne tombe pas exactement sur une case la DFT a des valeurs pour tout k : c’est la fuite spectrale, traitée dans la leçon sur l’analyse spectrale.

Complétion par des zéros

Compléter par des zéros un bloc de L échantillons jusqu’à N \gt  L n’ajoute pas d’information : d’après le premier théorème, la DFT à N points échantillonne la même DTFT de façon plus dense (figure en haut, 8 et 16 points). Cela aide à mieux lire la position des pics et à atteindre une puissance de 2 pour la FFT, mais la capacité de séparer deux fréquences proches ne dépend que de la durée L du signal observé : environ \Delta\omega \approx 2\pi/L.

Vérification en Python

import numpy as np

def dft(x):
    """DFT from the definition: X[k] = sum x[n] e^{-j 2 pi k n / N}."""
    N = len(x)
    n = np.arange(N)
    W = np.exp(-2j * np.pi * np.outer(n, n) / N)     # Fourier matrix
    return W @ x

def idft(X):
    N = len(X)
    n = np.arange(N)
    return np.exp(2j * np.pi * np.outer(n, n) / N) @ X / N

rng = np.random.default_rng(1)
x = rng.standard_normal(8)
X = dft(x)
print("equal to np.fft.fft:", np.allclose(X, np.fft.fft(x)))
print("exact inverse:", np.allclose(idft(X), x))
print("Parseval:", np.isclose(np.sum(x**2), np.sum(abs(X)**2) / 8))
print("Hermitian symmetry X[N-k] = X*[k]:", np.allclose(X[1:][::-1], np.conj(X[1:])))
m = 3
print("circular shift:", np.allclose(dft(np.roll(x, m)), np.exp(-2j * np.pi * np.arange(8) * m / 8) * X))

# circular versus linear convolution
a, h = np.array([1.0, 2, 3]), np.array([1.0, 1])
lin = np.convolve(a, h)
circ3 = np.real(idft(dft(a) * dft(np.r_[h, 0])))
circ4 = np.real(idft(dft(np.r_[a, 0]) * dft(np.r_[h, 0, 0])))
print("linear:", lin, " circular N=3:", np.round(circ3, 6), " circular N=4:", np.round(circ4, 6))

# DFT of a rectangular pulse of L = 4 samples on N = 8 points: Dirichlet kernel
L, N = 4, 8
r = np.r_[np.ones(L), np.zeros(N - L)]
k = np.arange(1, N)
dirichlet = np.exp(-1j * np.pi * k * (L - 1) / N) * np.sin(np.pi * k * L / N) / np.sin(np.pi * k / N)
print("rectangle, Dirichlet formula:", np.allclose(dft(r)[1:], dirichlet), " |X| =", np.round(abs(dft(r)), 3))

# cosine falling exactly on bin 2
c = np.cos(2 * np.pi * 2 * np.arange(N) / N)
print("cosine on bin 2:", np.round(abs(dft(c)), 6))

Toutes les vérifications affichent True ; la convolution circulaire à 3 points donne (4, 3, 5) et celle à 4 points (1, 3, 5, 3), égale à la linéaire ; le module du rectangle et le cosinus sur la case 2 (valeur 4 en k = 2 et k = 6) correspondent aux formules. La DFT à partir de la définition coûte N^2 multiplications : pour N = 8 cela n’a pas d’importance, pour N = 10^6 si, et c’est la raison de l’algorithme FFT, expliqué dans la leçon liée.

S’abonner
Notifier de
guest
1 commentaire
Le plus ancien
Plus récent Les plus votés
1
0
Vous avez apprécié cet article ? Merci de laisser un commentaire.x