Théorème d'échantillonnage de Nyquist-Shannon

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Le théorème d'échantillonnage de Nyquist-Shannon énonce que l'échantillonnage d'un signal, c'est-à-dire sa représentation sous une forme discrète, par une liste de valeurs prélevées régulièrement dans ce signal, exige une fréquence d'échantillonnage supérieure au double de l'écart entre les fréquences minimale et maximale qu'il contient.

Dans le cas le plus courant, la fréquence minimale du signal est petite par rapport à sa fréquence maximale et le théorème affirme plus simplement :

La représentation discrète d'un signal par des échantillons régulièrement espacés exige une fréquence d'échantillonnage supérieure au double de la fréquence maximale présente dans ce signal.

En général, on échantillonne dans l'intervalle compris entre 0 et la fréquence de Nyquist, c'est-à-dire la moitié de la fréquence d'échantillonnage.

Le théorème inclut aussi des possibilités moins souvent mises en pratique, comme l'échantillonnage d'un signal à bande de fréquences étroite (en) à moins du double de la fréquence maximale. Il montre aussi que d'autres types d'échantillonnage, par exemple avec des échantillons groupés par deux, ou un échantillonnage de la valeur et de sa dérivée un point sur deux, peuvent décrire le signal. Dans tous ces cas, le même nombre total d'échantillons est nécessaire[1].

Attribution[modifier | modifier le code]

À partir des années 1960, le théorème d'échantillonnage est souvent appelé théorème de Shannon, du nom de l'ingénieur qui en a donné la démonstration en posant les bases de la théorie de l'information chez Bell Laboratories en 1949. Quelques années plus tard, on joint à ce nom celui de Nyquist, de la même entreprise, qui avait ouvert la voie dès 1928. Ces attributions font l'objet de débats, le problème ayant occupé les mathématiciens, en termes théoriques, depuis le XIXe siècle, et l'industrie des télécommunications depuis le début du XXe siècle. Ces deux auteurs se sont fait connaître d'autre part par d'importantes contributions à la théorie du signal et à l'électronique, mais la recherche liée à la transmission du télégraphe et du téléphone a publié des résultats similaires indépendamment en Russie (Kotelnikov, 1933), en Allemagne (Raabe, 1939) et au Japon (Soreya, 1949)[2]. Au Royaume-Uni Edmund Taylor Whittaker avait donné en 1915 l'essentiel de la démonstration[3]. Tous ces noms peuvent se retrouver dans des dénominations du théorème.

La publication de Shannon expose sous une forme synthétique, rigoureuse et complète le théorème, en l'appliquant à la description du signal, mais il ne s'en attribue pas le mérite[4]. Très concise, elle n'évoque certains aspects qu'en quelque mots ; son objectif principal était de donner une définition rigoureuse de l'information, à partir de l'intervalle de fréquences et du bruit. De très nombreuses publications ont développé depuis, d'une part, les aspects technologiques liés à l'échantillonnage et d'autre part, les mathématiques correspondant à des usages particuliers. Leurs auteurs ont recouru aux ouvrages classiques de mathématiques, et ont rattaché le théorème à des travaux plus anciens, notamment ceux de Cauchy[5], attribution contestée[6].

La théorie des distributions, publiée en 1951, sert aujourd'hui de base à beaucoup de démonstrations.

Considérations élémentaires[modifier | modifier le code]

La transformation du signal en une suite d'échantillons a de nombreux usages (voir Échantillonnage).

Le théorème d'échantillonnage donne la réponse mathématique à la question « combien d'échantillons faut-il pour représenter exactement un signal ? ».

Pour qu'un échantillonnage puisse représenter un signal, il faut

  1. que tout signal ait au moins une représentation, et
  2. que toute représentation corresponde à un signal et un seul.
Avec cette fréquence d'échantillonnage, les signaux en bleu et en rouge ont la même représentation

On montre que deux sinusoïdes dont la fréquence a le même écart à un multiple quelconque de la fréquence d'échantillonnage produisent les mêmes échantillons :

Soit une sinusoïde d'amplitude a et de fréquence f :

y(x) = a \cos(2\pi f x)\,.

En l'échantillonnant à une fréquence f_e, on prend une valeur avec un pas P = \frac{1}{f_e}, donc pour chaque x = n P = \frac{n}{f_e}n est un nombre entier quelconque, on obtient la suite d'échantillons e :

e_n = a \cos(\frac{2\pi n f}{f_e}) \,.

Considérons maintenant une sinusoïde de même amplitude a et de fréquence k f_e \pm fk est un nombre entier :

y'(t) = a \cos(2\pi \left(k f_e \pm f \right) x).

L'échantillonnage à la même fréquence, donne la suite de nombres e’ :

e'_n = a\cos\left(\frac{2\pi n (k f_e \pm f)}{f_e}\right) = a\cos\left(2\pi \frac{n k f_e }{f_e} \pm 2\pi \frac{n f}{f_e}\right) = a\cos\left(2 n k \pi \pm 2\pi \frac{n f}{f_e}\right) = a\cos\left(\frac{2\pi n f}{f_e}\right)\,.

Les échantillons tirés des sinusoïdes de fréquence f et k f_e \pm f sont identiques et on en tire la conclusion suivante.

Toutes les sinusoïdes dont l'écart absolu avec un multiple de la fréquence d'échantillonnage est égal produisent les mêmes échantillons.

Pour que l'échantillonnage puisse représenter le signal, il faut que celui-ci ne puisse contenir qu'une seule des sinusoïdes de fréquence k fe±fk f_e \pm f. Cette condition n'est remplie que dans un intervalle de largeur égale à la moitié de la fréquence d'échantillonnage, commençant par un multiple de la fréquence d'échantillonnage.

On conclut aussi de l'étude que la représentation échantillonnée d'un signal comprend la suite des valeurs des échantillons et la bande de fréquences dans laquelle il doit être reconstitué.

Cependant, montrer qu'un échantillonnage à une fréquence de moins de deux fois ou moins la fréquence maximale d'un signal ne peut pas le représenter ne prouve pas qu'un échantillonnage à une fréquence supérieure puisse le faire. Pour arriver à cette conclusion, il faut mettre en œuvre les concepts et les théorèmes de l'analyse spectrale.

Démonstration de Shannon[modifier | modifier le code]

Spectre d'un signal limité en fréquence de 0 à B[7]

Les théorèmes d'analyse spectrale montrent que tout signal peut se décomposer en une somme de sinusoïdes de fréquences, d'amplitudes et de phases diverses. On considère un signal inscrit entre une fréquence minimale et une fréquence maximale. L'expérience détermine quelle est la plage de fréquence qui intéresse. Même si les coefficients de fréquences hors de cet intervalle ne sont pas nuls, on les néglige dès lors qu'ils ne contribuent pas de façon significative à la valeur moyenne quadratique totale.

La transformée de Fourier \operatorname{\hat{s}}(\omega)=\int_{-\infty}^\infty s(x) e^{-i\omega x}\,dx d'une fonction s(x) la décrit par les fréquences f qu'elle contient, exprimées dans ces équations par la pulsation ω = 2 π f. La transformée de Fourier inverse donne la valeur de s(x) en fonction de \operatorname{\hat{s}}(\omega)[7]

s(x)=\frac1{2\pi}\int_{-\infty}^\infty{\operatorname{\hat{s}}(\omega)e^{i\omega x}\,d\omega}

Le signal dont s'occupe le théorème est limité en fréquence. Au-delà de fmax, correspondant à une pulsation ωmax = 2 π fmax, les coefficients fréquentiels sont négligeables. Par conséquent,

s(x) = \frac1{2 \pi} \int_{-\omega_{max}}^{\omega_{max}}{\operatorname{\hat{s}}(\omega) e^{i \omega x} \, \mathrm{d}\omega}.

Recherchons la valeur de s(x) pour x multiple de la demi-période de fmax ; x=\frac{n}{2f_{max}}n est un nombre entier :

s(\frac{n}{2f_{max}}) = \frac1{2 \pi} \int_{-\omega_{max}}^{\omega_{max}}{\operatorname{\hat{s}}(\omega) e^{i \omega \frac{n}{2 f_{max}}} \, \mathrm{d}\omega}.

On reconnaît dans cette l'intégrale le coefficient du -n-ième terme du développement en série de Fourier de la fonction \operatorname{\hat{s}}(\omega), en prenant l'intervalle [-fmax, +fmax] comme période :

c_{-n} =  \frac{1}{2 \omega_{max}} \int_{-\omega_{max}}^{\omega_{max}}{\operatorname{\hat{s}}(\omega) e^{i \omega \frac{n}{2f_{max}}}} \, \mathrm{d}\omega = \frac{1}{2 f_{max}} s(\frac{n}{2 f_{max}})

La reconstitution de la fonction \operatorname{\hat{s}} est donnée par :

\operatorname{\hat{s}}(\omega) = \sum_{n=-\infty}^{\infty}{c_n e^{i \omega \frac{n}{2f_{max}}}}

La valeur des échantillons en prélevés à x=\frac{n}{2f_{max}} déterminent donc les coefficients du développement en série de Fourier de \operatorname{\hat{s}}(\omega) dans l'intervalle de fréquences [-fmax, fmax]. Les valeurs des échantillons déterminent donc entièrement \operatorname{\hat{s}}(\omega). Puisque la transformée de Fourier d'une fonction la définit entièrement, déterminer \operatorname{\hat{s}}(\omega), c'est déterminer s(x).

Nous avons montré qu'à tout signal de bande de fréquences limitées correspond une et une seule représentation discrète constituée à partir d'échantillons de ce signal pris à intervalles réguliers espacés de la demi période de la fréquence maximale du signal. On peut éviter le passage par la série de Fourier donnant \operatorname{\hat{s}}(\omega) en exprimant directement la fonction s en fonction de son échantillonnage.

Reconstitution du signal : formule de Shannon[modifier | modifier le code]

Soit une liste d'échantillons e_n = s(\frac{n}{2 f_{max}})=2f_{max}c_{-n} = \frac{\omega_{max}}{\pi}c_{-n}.

Si l'on reprend l'expression de s(x) à partir de \operatorname{\hat{s}}(\omega),

s(x)= \frac1{2 \pi} \int_{-\omega_{max}}^{\omega_{max}}{\operatorname{\hat{s}}(\omega) e^{i \omega x} \, \mathrm{d}\omega}

en y remplaçant cette fonction par son développement en série de Fourier,


\begin{align}
  s(x)
& = \frac1{2\pi} 
      \int_{-\omega_{max}}^{\omega_{max}}
        \left(\sum_{n=-\infty}^\infty c_{-n} e^{-i \omega \frac{n\pi}{\omega_{max}}} \right)
          e^{i \omega x} \, \mathrm d\omega \\
& = \frac1{2\pi} 
      \int_{-\omega_{max}}^{\omega_{max}}
       {\left(\sum_{n=-\infty}^\infty{c_{-n} e^{i \omega (x-\frac{n\pi}{\omega_{max}})}} \right) \, \mathrm d\omega} 
\end{align}

et c-n par la valeur du coefficient déjà calculée, on obtient



\begin{align}
  s(x) 
  & = \frac1{2 \pi}
        \int_{-\omega_{max}}^{\omega_{max}}
          \left(\sum_{n=-\infty}^\infty
             \left(\frac\pi{\omega_{max}} e_n\right)
               e^{i \omega (x-\frac{n\pi}{\omega_{max}})} \right) \, \mathrm d\omega \\ 
  & = \frac1{2\omega_{max}}
        \sum_{n=-\infty}^\infty
          e_n \int_{-\omega_{max}}^{\omega_{max}}
            e^{i \omega(x- \frac{n\pi}{\omega_{max}})} \, \mathrm d\omega
\end{align}

On peut calculer l'intégrale

\int_{-\omega_{max}}^{\omega_{max}}e^{i \omega(x- \frac{n \pi}{\omega_{max}})} \, \mathrm{d}\omega

ce qui conduit à :

s(x) = \sum_{n=-\infty}^{\infty}{e_n \frac{\sin (\omega_{max} x - n \pi) }{\omega_{max} x - n \pi} }

La fonction sinus cardinal \frac{\sin x}{x} vaut 1 pour x = 0 et 0 pour tous les autres x multiples de π. Dans le cas présent, elle vaut 1 pour l'échantillon n et 0 pour tous les autres échantillons, tandis que ses autres valeurs participent à l'interpolation entre les échantillons.

Démonstration avec le peigne de Dirac[modifier | modifier le code]

Le développement du traitement du signal dans les années suivant la publication de Shannon[8] va donner lieu à de nombreux raffinements de la théorie mathématique de l'échantillonnage. Le plus radical est l'utilisation de la théorie des distributions pour décrire l'échantillonnage. En fournissant une extension à la notion de fonction, ainsi, par voie de conséquence, qu'à la transformation de Fourier, elle donne une structure mathématique idéale à l'échantillonnage. C'est la description qui prévaut dans la plupart des manuels aujourd'hui. La démonstration de Shannon, en effet, si elle répond aux critères de rigueur d'une philosophie pragmatiste, laisse le mathématicien idéaliste insatisfait. Pour les signaux porteurs d'information, limités a priori en durée et en résolution (par le bruit de fond), la transformation de Fourier fournit une description en fréquences adéquate, et de cette transformée, on peut revenir, par la transformation inverse, à la description temporelle. Mais dans le cas d'une fonction périodique, donc sans limite de durée, la transformation de Fourier aboutit à un spectre de raies, correspondant aux coefficients de la série de Fourier. Ce spectre d'un signal périodique idéal ne répond pas aux conditions de Dirichlet et on ne peut pas lui appliquer la transformation de Fourier inverse, pour retrouver la fonction périodique. La théorie des distributions permet de surmonter cette limitation théorique[9].

Transformée de Fourier d'un signal

Un raisonnement simple reposant sur les propriétés de la transformée de Fourier et de la distribution de Dirac montre que la transformée d'un signal échantillonné est périodique, et identique à la transformée de Fourier du signal lui-même dans la bande de fréquences d'origine.

Considérons la distribution obtenue en multipliant le signal s(t) par un peigne de Dirac, somme de d'impulsions de Dirac \delta_T d'énergie T distants de T.

s^*(t) = T s(t) \cdot \delta_T (t)\,
Transformeé de Fourier d'un signal échantillonné.
L'échantillonnage est correct si le recouvrement entre deux lobes est inférieur à la limite de résolution ou de bruit de fond (trait rouge).

La transformée de Fourier \operatorname{\widehat{s*}}(f) de s*(t) est la convolution de la transformée de Fourier de s(t') par celle du peigne de Dirac :

\operatorname{\widehat{s^*}}(f) = \operatorname{\hat{s}}(f) \ast \sum_{n=-\infty}^{\infty} \delta(f - \frac{n}{T})

Le δ étant l'élément neutre de la convolution, on obtient:

\operatorname{\widehat{s^*}}(f) = \sum_{n=-\infty}^{+\infty} \operatorname{\hat{s}}(f - n/T)

Cette expression donne la somme de la transformée du signal non échantillonné et de toutes les translatées de celle-ci avec un pas égal à la fréquence d'échantillonnage 1/T. Si cette fréquence est supérieure au double de la fréquence maximale du signal, les translatés ne se chevauchent pas et on peut reconstituer de façon exacte la transformée de Fourier du signal et donc le signal lui-même.

Par contre, la transformée de Fourier d'un signal de durée limitée s'étend nécessairement sur toute l'étendue des fréquences. Une partie des spectres translatés se recouvre donc inévitablement. Ce phénomène est appelé « repliement de spectre ». Si on veut éviter le franglais on utilise en général le terme repliement de préférence à aliasing. Toute l'information utile est contenue dans l'intervalle [-1/(2T), 1/(2T)] à condition que les parties de spectre qui se recouvrent aient une énergie négligeable par rapport au bruit de fond où à la résolution du système.

Reconstitution avec la fonction sinc[modifier | modifier le code]

Puisque la transformée \operatorname{\widehat{s^*}}(f) du signal correctement échantillonné contient, dans l'intervalle [-1/(2T), 1/(2T)], la transformée \operatorname{\widehat{s}}(f) du signal d'origine s(t), on obtient cette dernière transformée en multipliant \operatorname{\widehat{s^*}}(f) par une fonction porte p(f) valant 1 sur l'intervalle [-1/(2T), 1/(2T)] et 0 ailleurs :

\operatorname{\widehat{s}}(f) = \operatorname{\widehat{s^*}}(f) \times p(f)

Il suffit ensuite de prendre la transformée de Fourier inverse pour reconstituer f. La transformée de Fourier inverse transforme le produit de fonctions en produit de convolution, et la transformée de Fourier inverse d'une fonction porte est un sinus cardinal sinc, où \operatorname{sinc}(x) = \frac{\sin(x)}{x}. La fonction f s'obtient alors comme convolée de l'échantillonnage par un sinus cardinal. Le calcul conduit alors à la formule :

s(t) = \sum_{n=-\infty}^{+\infty} s(n T) \cdot
\operatorname{sinc}(\frac\pi T(t - nT))

On a ainsi obtenu le signal initial f en filtrant l'échantillonnage de ce signal par un filtre parfait, passe tout de 0 à la moitié de la fréquence d'échantillonnage, et coupe tout ailleurs.

Sous-échantillonnage[modifier | modifier le code]

Cette figure représente les transformées de Fourier de deux signaux avant et après échantillonnage. L'un est un signal basse fréquence et l'autre a le même contenu décalé par un multiple de la fréquence d'échantillonnage. Les transformées sont identiques, la transformée du signal passe-bas nécessitant moins d'échantillons.

D'après ce qui précède la transformée de Fourier d'un signal échantillonné est toujours une fonction périodique de la fréquence sur l'intervalle]-∞, ∞[, la période étant l'inverse de la période d'échantillonnage. Lorsque la condition d'échantillonnage est satisfaite c'est une succession de copies de la transformée du signal initial.

En d'autres termes deux copies d'un spectre basse fréquence situées par rapport à la fréquence nulle à un intervalle multiple de la fréquence d'échantillonnage fournissent la même information que le spectre centré. Si ces deux copies représentent un signal situé dans une haute fréquence on peut leur substituer la copie centrée, ce qui permet de réduire la fréquence d'échantillonnage.

Compléments[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

Publications historiques[modifier | modifier le code]

  • (en) Claude E. Shannon, « Communication in the presence of noise », Proceedings of the Institute of Radio Engineers, vol. 37, no 1,‎ janvier 1949, p. 10–21 (lire en ligne)
    réédité comme classique dans Proceedings of the IEEE, vol. 86, no. 2, (Feb. 1998) précédé de (en) Aaron D. Wyner et Shlomo Shamai (Shitz), « Introduction to “Communication in the Presence of Noise” by C. E. Shannon », Proceedings of the IEEE, vol. 86, no 2,‎ février 1986, p. 442-446 (lire en ligne)
    Shannon écrit « Ce fait est connu dans l'art de la communication. », il en donne la preuve mathématique, et il précise :
    • « Le théorème a été donné auparavant sous une autre forme par des mathématiciens » : (en) Edmund Taylor Whittaker, « On the Functions Which are Represented by the Expansions of the Interpolation Theory », Proceedings of the Royal Society of Edinburgh, Section A, Edinburgh, vol. 35,‎ 1915, p. 181–194 ; (en) Edmund Taylor Whittaker, « Interpolation function theory », Cambridge Tracts in Mathematics and Mathematical Physics, Cambridge, UK, Cambridge University Press,‎ 1935.
    • « mais n'a pas été explicitement publié dans la littérature sur la théorie de la communication, malgré »
      (en) Harry Nyquist, « Certain topics in telegraph transmission theory », AIEE Transactions,‎ avril 1928 (lire en ligne)
      réédité comme classique dans Proceedings of the IEEE, vol. 90, no. 2, (Feb. 1998) précédé de (en) Norman C. Beaulieu, « Introduction to “Certain Topics in Telegraph Transmission Theory” », Proceedings of the IEEE, vol. 90, no 2,‎ février 202 (lire en ligne)

      (en) W.R. Bennett, « Time division multiplex systems », Bell Systems Technical Journal, vol. 20,‎ avril 1941
      (en) Dennis Gabor, « Theory of communication : Part 1: The analysis of information », Journal of the Institute of Electrical Engineering, London, vol. 93-3, no 26,‎ 1946, p. 429-457 (lire en ligne).
  • Vladimir Alexandrovitch Kotelnikov (en) (1908-2005) était parvenu au même résultat :

Publications modernes[modifier | modifier le code]

  • Jean-François Bercher, TF, Dirac, convolution, et tutti quanti, École Supérieure d’Ingénieurs en Électrotechnique et Électronique,‎ 2001 (lire en ligne)
  • (en) Abdul J. Jerri, « The Shannon Sampling Theorem—Its Various Extensions and Applications: A Tutorial Review », Proceedings of the IEEE, vol. 65, no 11,‎ novembre 1977, p. 1565-1596 (lire en ligne).
  • Yue Lu et Minh N. Do, « A geometrical approach to sampling signals with finite rate of innovation », 2004.
  • (en) Michael Unser, « Sampling — 50 Years After Shannon », Proceedings of the IEEE, vol. 88, no 4,‎ avril 2000, p. 569-587 (lire en ligne)
  • (en) Martin Vetterli, Pina Marziliano et Thierry Blu, « Sampling signals with finite rate of innovation », IEEE Transactions on Signal Processing, no 6,‎ 2002 ([bigwww.epfl.ch/publications/vetterli0201.pdf lire en ligne])

Voir aussi[modifier | modifier le code]

Notes et références[modifier | modifier le code]

  1. Shannon 1949, p. 449
  2. (en) Hans Dieter Lüke, « The Origins of the Sampling Theorem », IEEE Communications Magazine,‎ avril 1999, p. 106–108 (lire en ligne) ; Jerri 1977, p. 1566
  3. Whittaker 1915
  4. Unser 2000, p. 569.
  5. (en) John J. Benedetto, « Prologue », dans J.J. Benedetto, Ahmed I. Sayed, Sampling, Wavelets, and Tomography, Boston, Birkhäuser,‎ 2004 (lire en ligne), xv-xvi
  6. Bernard Lacaze, « La formule d'échantillonnage et A. L. Cauchy », Traitement du Signal, vol. 15, no 4,‎ 1998 (lire en ligne)
  7. a et b Pour toute la démonstration, on adopte la notation exponentielle issue de la Formule d'Euler : \mathrm{e}^{\mathrm{i}\,x} = \cos(x) + \mathrm{i}\,\sin(x). Les coefficients en nombres complexes pour chaque fréquence incluent par conséquent la phase, contrairement au graphique, qui ne donne qu'une indication de l'amplitude.
  8. Shannon 1949. Les articles et livre qu'il a publié ensuite renvoient à cet article pour la démonstration.
  9. Bercher 2001 donne, en plus des explications courantes, une présentation de ce développement théorique.