Problème — La transformée de Fourier discrète : inversion et égalité de Parseval

1) La somme fondamentale. Notons $S(p)={\sum }_{k=0}^{n-1}{\omega }^{kp}={\sum }_{k=0}^{n-1}{\left({\omega }^p\right)}^k$ : c'est une somme géométrique de raison ${\omega }^p=e^{2i\pi p/n}$. Or $e^{2i\pi p/n}=1$ si et seulement si $\frac{2\pi p}{n}\equiv 0[2\pi ]$, c'est-à-dire si et seulement si $\frac{p}{n}$ est un entier : si et seulement si $p$ est un multiple de $n$.

Si $p$ est un multiple de $n$, tous les termes valent $1$ et $S(p)=n$.

Sinon, ${\omega }^p\ne 1$, et la formule de la somme géométrique s'applique : $$S(p)=\frac{1-{\left({\omega }^p\right)}^n}{1-{\omega }^p}=\frac{1-{\left({\omega }^n\right)}^p}{1-{\omega }^p}=0,$$ puisque ${\omega }^n=1$. En résumé : $$\sum _{k=0}^{n-1}{\omega }^{kp}=\{\begin{array}{ll}n& \text{si }p\text{ est un multiple de }n,\\ 0& \text{sinon.}\end{array}$$ C'est la propriété d'« orthogonalité » des racines de l'unité : tout le problème en découle.

2) Périodicité et formule d'inversion. La périodicité. Pour tous $k$ et $p$, ${\omega }^{-k(p+n)}={\omega }^{-kp}{\left({\omega }^n\right)}^{-k}={\omega }^{-kp}$, d'où $X_{p+n}=X_p$ : la suite $(X_p)$ est $n$-périodique, et $n$ nombres, $X_0,\dots ,X_{n-1}$, la décrivent entièrement.

L'inversion. Soit $m\in \{0,\dots ,n-1\}$. Remplaçons chaque $X_p$ par sa définition — en nommant $k$ l'indice de sommation intérieur — et échangeons l'ordre de sommation, ce qui est licite pour une somme double finie : $$\frac{1}{n}\sum _{p=0}^{n-1}{X}_p{\omega }^{mp}=\frac{1}{n}\sum _{p=0}^{n-1}\sum _{k=0}^{n-1}{x}_k{\omega }^{-kp}{\omega }^{mp}=\frac{1}{n}\sum _{k=0}^{n-1}{x}_k\sum _{p=0}^{n-1}{\omega }^{(m-k)p}=\frac{1}{n}\sum _{k=0}^{n-1}{x}_{k}S(m-k).$$ Pour $k$ et $m$ dans $\{0,\dots ,n-1\}$, l'entier $m-k$ est compris entre $-(n-1)$ et $n-1$ : c'est un multiple de $n$ si et seulement si $m-k=0$. Par le 1), $S(m-k)$ vaut $n$ pour $k=m$ et $0$ pour tous les autres $k$. Il reste un seul terme : $$\frac{1}{n}\sum _{p=0}^{n-1}{X}_p{\omega }^{mp}=\frac{1}{n}{x}_{m}n=x_m.$$

Le point délicat. Après l'échange des sommes, c'est le 1) qui « trie » les termes, n'en gardant qu'un ; encore faut-il que $m-k$ reste dans l'intervalle où le seul multiple de $n$ est $0$ — d'où le choix de $m$ et $k$ entre $0$ et $n-1$.

La lecture. La formule d'inversion s'écrit $x_m={\sum }_{p=0}^{n-1}{c}_p{\omega }^{mp}$ avec $c_p=\frac{X_p}{n}$ : le signal est une superposition de $n$ « fréquences pures » $m\mapsto e^{2i\pi pm/n}$, d'amplitudes complexes $c_p$, et ces amplitudes le déterminent entièrement.

3) L'égalité de Parseval. Comme $|\omega |=1$, on a $\overline{\omega }={\omega }^{-1}$, donc $\overline{{\omega }^{-lp}}={\omega }^{lp}$ et $\overline{X_p}={\sum }_{l=0}^{n-1}\overline{x_l}{\omega }^{lp}$. Le produit de deux sommes finies se développe en somme double : $$|X_p{|}^2=X_p\overline{X_p}=\sum _{k=0}^{n-1}\sum _{l=0}^{n-1}{x}_k\overline{x_l}{\omega }^{(l-k)p}.$$ Sommons sur $p$ de $0$ à $n-1$ et échangeons les sommes : $$\sum _{p=0}^{n-1}|X_p{|}^2=\sum _{k=0}^{n-1}\sum _{l=0}^{n-1}{x}_k\overline{x_l}S(l-k).$$ Comme au 2), $S(l-k)$ vaut $n$ si $l=k$ et $0$ sinon : seuls les termes diagonaux survivent, et $$\sum _{p=0}^{n-1}|X_p{|}^2=n\sum _{k=0}^{n-1}{x}_k\overline{x_k}=n\sum _{k=0}^{n-1}|x_k{|}^2.$$ La traduction. En divisant par $n^2$ : $$\frac{1}{n}\sum _{k=0}^{n-1}|x_k{|}^2=\sum _{p=0}^{n-1}{\left|\frac{X_p}{n}\right|}^2:$$ la moyenne des carrés des échantillons — l'« énergie » moyenne du signal — est la somme des carrés des modules des amplitudes $c_p$, sans terme croisé.

4) Les échantillons d'un cosinus. Par la formule d'Euler, $x_k=\frac{1}{2}\left({\omega }^{mk}+{\omega }^{-mk}\right)$, donc $$X_p=\frac{1}{2}\sum _{k=0}^{n-1}\left({\omega }^{k(m-p)}+{\omega }^{-k(m+p)}\right)=\frac{1}{2}(S(m-p)+S(-(m+p)\left)\right).$$ Pour $0\le p\le n-1$ : l'entier $m-p$ est strictement compris entre $-n$ et $n$, donc c'est un multiple de $n$ si et seulement si $p=m$ ; l'entier $m+p$ est compris entre $1$ et $n-1+m<2n$, donc c'est un multiple de $n$ si et seulement si $m+p=n$, c'est-à-dire $p=n-m$. Ces deux indices sont distincts, puisque $m<\frac{n}{2}$ donne $m<n-m$. Ainsi $$X_m=X_{n-m}=\frac{n}{2},X_p=0\text{ pour tout autre }p\in \{0,\dots ,n-1\}.$$ Le spectre a deux raies, en $p=m$ et en $p=n-m$ ; la seconde correspond à ${\omega }^{(n-m)k}={\omega }^{-mk}$, la « fréquence négative » que la formule d'Euler fait apparaître. Chacune porte l'amplitude $c=\frac{X_p}{n}=\frac{1}{2}$.

Parseval. Le membre de gauche vaut ${\left(\frac{n}{2}\right)}^2+{\left(\frac{n}{2}\right)}^2=\frac{n^2}{2}$ ; l'égalité de Parseval donne donc $n{\sum }_{k=0}^{n-1}{\cos }^2\frac{2\pi mk}{n}=\frac{n^2}{2}$, soit $$\sum _{k=0}^{n-1}{\cos }^2\frac{2\pi mk}{n}=\frac{n}{2}.$$ La moyenne des carrés des échantillons vaut $\frac{1}{2}$ : c'est, en version discrète, le fait que la valeur efficace d'un signal sinusoïdal d'amplitude $1$ vaut $\frac{1}{\sqrt{2}}$.

5) Le repliement. Les échantillons de la fréquence $\nu$ sont $\cos \frac{2\pi \nu k}{f_e}$. Pour la fréquence $\nu +f_e$ : $$\cos \frac{2\pi (\nu +f_e)k}{f_e}=\cos \left(\frac{2\pi \nu k}{f_e}+2\pi k\right)=\cos \frac{2\pi \nu k}{f_e},$$ par $2\pi$-périodicité du cosinus, $k$ étant entier. Pour la fréquence $f_e-\nu$, strictement positive quand $\nu <f_e$ : $$\cos \frac{2\pi (f_e-\nu )k}{f_e}=\cos \left(2\pi k-\frac{2\pi \nu k}{f_e}\right)=\cos \frac{2\pi \nu k}{f_e},$$ par périodicité et parité du cosinus. Dans les deux cas, les échantillons sont identiques : on ne peut pas distinguer $\nu$ de $\nu +f_e$, ni de $f_e-\nu$. En itérant — retrancher des multiples de $f_e$, puis remplacer par $f_e$ moins elle une fréquence qui dépasse $\frac{f_e}{2}$ —, toute fréquence donne les mêmes échantillons qu'une fréquence de $\left[0,\frac{f_e}{2}\right]$, sa fréquence apparente.

6) La condition d'échantillonnage. Soient $\nu \ne {\nu }^{\prime }$ deux fréquences de $\left]0,\frac{f_e}{2}\right[$. À l'instant $t_1=\frac{1}{f_e}$, les échantillons valent $\cos \frac{2\pi \nu }{f_e}$ et $\cos \frac{2\pi {\nu }^{\prime }}{f_e}$. Les angles $\frac{2\pi \nu }{f_e}$ et $\frac{2\pi {\nu }^{\prime }}{f_e}$ sont deux réels distincts de $]0,\pi [$, intervalle sur lequel le cosinus est strictement décroissant, donc injectif : les deux valeurs diffèrent, et les deux suites d'échantillons sont distinctes.

Le choix de $f_e$. Si $\nu <\frac{f_e}{2}$, c'est-à-dire $f_e>2\nu$, les échantillons déterminent $\nu$ parmi toutes les fréquences de $\left]0,\frac{f_e}{2}\right[$. Si au contraire $\frac{f_e}{2}<\nu <f_e$, la fréquence $f_e-\nu$, plus basse, donne les mêmes échantillons : l'appareil « voit » une fréquence qui n'existe pas. C'est le repliement de spectre — l'effet stroboscopique des roues qui semblent tourner à l'envers au cinéma. D'où la règle : on choisit une fréquence d'échantillonnage strictement supérieure au double de la plus grande fréquence présente dans le signal.

Le théorème obtenu — transformée de Fourier discrète. Soient $n\ge 2$, $\omega =e^{2i\pi /n}$ et $(x_0,\dots ,x_{n-1})$ une famille de nombres complexes. Les nombres $X_p={\sum }_{k=0}^{n-1}{x}_k{\omega }^{-kp}$ déterminent la famille par la formule d'inversion $x_m=\frac{1}{n}{\sum }_{p=0}^{n-1}{X}_p{\omega }^{mp}$, et ils vérifient l'égalité de Parseval ${\sum }_{p=0}^{n-1}|X_p{|}^2=n{\sum }_{k=0}^{n-1}|x_k{|}^2$. Corollaire : pour une fréquence d'échantillonnage $f_e$, deux fréquences distinctes de $\left]0,\frac{f_e}{2}\right[$ ont des échantillons distincts, tandis que toute fréquence a les mêmes échantillons qu'une fréquence de $\left[0,\frac{f_e}{2}\right]$ ; pour qu'un signal de fréquence $\nu$ soit lu à sa vraie fréquence, on échantillonne à $f_e>2\nu$ (condition de Shannon).

Contrôle numérique. Pour $n$ de $2$ à $13$ : la somme du 1) pour tous les $p$ entre $-2n$ et $2n$, l'inversion et Parseval sur des familles aléatoires, et les valeurs du 4), à $10^{-9}$ près. Pour $f_e=1000$ et $\nu =130$, les fréquences $1130$ et $870$ donnent les mêmes échantillons sur vingt instants, tandis que $130$ et $310$, toutes deux inférieures à $500$, diffèrent dès l'instant $t_1$.

Ce que le problème installe. Les racines de l'unité forment un système « orthogonal » — la somme du 1) vaut $n$ ou $0$ —, et cette orthogonalité suffit à décomposer un signal, à le reconstruire et à partager son énergie sans terme croisé. L'égalité de Parseval est un théorème de Pythagore : on la retrouvera au chapitre des espaces préhilbertiens, où des familles orthogonales de cosinus et de sinus échantillonnés jouent ce rôle. Et c'est le calcul que fait l'oscilloscope numérique quand, en travaux pratiques de physique, on effectue l'analyse spectrale d'un signal en choisissant de façon cohérente la fréquence d'échantillonnage.