lundi 16 septembre 2013

La formule de Shannon

Voici une formule très utilisée par les spécialistes du traitement du signal et qui  est un  concentré des  résultats d'analyse de Fourier :
Théorème de Shannon Soit $\omega_0>0$  et $E=\left\{f\in{\mathbb L}^2({\mathbb R})\vert {\rm supp} \widehat{f}\subset [-\omega_0,\omega_0]\right\}$ alors pour tout $f\in E$  et $T\leq \pi/\omega_0$ on a :
$$f(x)=\sum_{n\in{\mathbb Z}} f(nT) {\sin(\pi(x/T-n))\over \pi(x/T-n)}$$
Ce résultat à des applications pratiques très importantes car il permet de reconstruire une fonction à partir d'un simple échantillonnage (la donnée des $(f(nT))_{n\in{\mathbb Z}} $  ) pourvu que la cadence $T$ de l'échantillonnage soit suffisamment rapide comparée à l'étalement du spectre de $f$ dans $[-\omega_0,\omega_0]$. En images voilà ce que ça donne :


Quand la cadence n'est pas suffisante la série  convergence mais pas vers $f$ !! On parle alors de recouvrement (repliement) du spectre (ou plus souvent  d'aliasing en anglais) effet qu'on retrouve souvent en imagerie numérique.
1. Démonstration du cas $T=1$ et $\omega_0=\pi$
On va d'abord démontrer le théorème dans le cas ou $\omega_0=\pi$. La Démonstration ressemble beaucoup à celle de la formule sommatoire de Poisson et démarre en posant:
$$F(\xi)=\sum_{k\in{\mathbb Z}} \widehat{f}(\xi+2k\pi)$$
Comme $\widehat{f}$ est à support compact (dans $[-\pi,\pi]$) la série converge et c'est évidement une fonction $2\pi$  périodique. En fait $F$  est une périodisation de  $\widehat{f}$  mais cela ne marche que si $\widehat{f}$ est à support dans $[-\pi,\pi]$ (comme on le voit sur la figure ci-dessous) car sinon les différents motifs se superposeraient et c'est la cause de l'aliasing évoqué dans l'animation plus haut:


Si on remarque en plus que  $F\in {\mathbb L}^2([-\pi,\pi])$  on peut la décomposer en séries de Fourier $F(\xi)= \sum_{n\in{\mathbb Z}} c_n(F) e^{i\xi n}$ avec
$$\begin{eqnarray*}
c_n(F)&=&\int_{-\pi}^\pi F(\xi) e^{-i\xi n} {d\xi \over 2\pi}
=\int_{-\pi}^\pi \sum_{k\in{\mathbb Z}} \widehat{f}(\xi+2k\pi) e^{-i\xi n} {d\xi \over 2\pi}\\
&=&\sum_{k\in{\mathbb Z}} \int_{-\pi}^\pi  \widehat{f}(\xi+2k\pi) e^{-i\xi n} {d\xi \over 2\pi}~~~\text{Théorème de Fubini }\\
&=&\sum_{k\in{\mathbb Z}} \int_{(2k-1)\pi}^{(2k+1)\pi}  \widehat{f}(t) e^{-it n} {dt \over 2\pi}~~~\text{changement de variable $t=\xi+2k\pi$}\\
&=& \int_{-\infty}^\infty  \widehat{f}(t) e^{-it n} {dt \over 2\pi}~~~\text{relation de Chasles}\\
&=&   {f}(-n) ~~~\text{Formule d'inversion de Fourier}
\end{eqnarray*}$$
On obtient alors que
$$ \widehat{f}(\xi)=F(\xi)\times {\bf 1}_{[-\pi,\pi]}(\xi)
=\sum_{n\in{\mathbb Z}} {f}(-n) e^{i\xi n}\times {\bf 1}_{[-\pi,\pi]}(\xi)
=\sum_{n\in{\mathbb Z}} {f}(n) e^{-i\xi n}\times {\bf 1}_{[-\pi,\pi]}(\xi) $$
il ne reste plus qu'à appliquer la formule d'inversion de Fourier pour obtenir une expression de $f$ sous forme d'une somme :
$$f(x)={1\over 2\pi}{\widehat{\widehat{f}}}(-x)
=\sum_{n\in{\mathbb Z}} {f}(n) {1\over 2\pi}  \widehat{\bf 1}_{[-\pi,\pi]}(-(x-n) )
=\sum_{n\in{\mathbb Z}} {f}(n) {\not2\over \not2\pi}{\sin( \pi(x-n))\over (x-n) }$$
car la transformée de Fourier de la fonction porte fait apparaître un "sinus cardinal" translaté :
 $$\widehat{\bf 1}_{[-\pi,\pi]}(\xi)
=\int_{-\pi}^\pi  e^{-i\xi x} {dx}={e^{-i\xi \pi}-e^{-i\xi \pi}\over -i\xi}
= 2{\sin(\xi \pi)\over \xi}$$

2 Le cas général 
Pour passer  au cas général d'une fonction dont la transformée de Fourier est à support compact, il faut poser $f(x)=g(x/T)$ car alors :
$$ f(x)=g(x/T)=\sum_{n\in{\mathbb Z}} {g}(n){\sin( \pi(x/T-n))\over \pi (x/T-n) }
=\sum_{n\in{\mathbb Z}} {f}(nT){\sin( \pi(x/T-n))\over \pi (x/T-n) } $$
reste à ajuster la valeur de $T$ pour que le support de $\widehat{g}$  (à laquelle on applique la formule de Shannon déjà démontrée) soit bien dans $[-\pi,\pi]$. Pour cela on remarque que :
$${\rm supp}\, \widehat{g} \subset [-\pi,\pi] \Leftrightarrow \widehat{g}(\xi)=0,~~ \forall \vert \xi\vert >\pi $$
sachant que $\widehat{g}(\xi)=T\widehat{f}(T\xi)$ on a donc
$$ \widehat{f}(T\xi)=0 ,~~\forall \vert T\xi\vert >\pi\Leftrightarrow {\rm supp} \widehat{f} \subset [-\pi/T,\pi/T]$$
donc si ${\rm supp}\, \widehat{f} = [-\omega_0,\omega_0]$ il suffit de prendre $T$ tel que $\pi/T\geq \omega_0$ pour que ${\rm supp}\,\widehat{g} \subset [-\pi,\pi]$ ce qui donne la condition $T\leq \pi/\omega_0$

3 Quelques remarques 
 Il peut paraître étonnant qu'on puisse reconstruire une fonction à partir d'un simple échantillonnage, cependant si on regarde les hypothèses du théorème  une fonction ayant une transformée de Fourier à support compact  est forcément de classe $C^\infty $  et même analytique ...  la reconstruction de la fonction à partir de l’échantillonnage est donc à rapprocher du principe des zéros isolés pour les fonctions analytiques. 

Cette hypothèse que $\hat{f}$ soit à support compact n'est pas contraignante dans les applications au traitement des signaux sonores puisque l'on coupe naturellement les fréquences supérieures à 20000Hz qui sont inaudibles pour l'oreille humaine. Un autre intérêt à noter pour les applications pratiques : même si la convergence de la série n'est pas très rapide (à cause du "sinus cardinal") il n'y a pas besoin de calculs complexes pour obtenir les coefficients des fonctions "sinus cardinal" puisqu'il s'agit directement des valeurs d’échantillonnage!

1 commentaire:

Pour écrire des formules mathématiques vous pouvez utiliser la syntaxe latex en mettant vos formules entre des "dollars" $ \$....\$ $ par exemple :
- $\sum_{n=1}^\infty {1\over n^2}={\pi^2\over 6}$ s'obtient avec \sum_{n=1}^\infty {1\over n^2}={\pi^2\over 6}
- $\mathbb R$ s'obtient avec {\mathbb R} et $\mathcal D$ s'obtient avec {\mathcal D}
- pour les crochets $\langle .,. \rangle$ dans les commentaires utilisez \langle .,. \rangle
vous pouvez écrire du html dans les commentaires :
- italique <i> ... </i> gras <b> ... </b>
- lien <a href="http://adresse "> .... </a>