Théorème d'échantillonnage
Le théorème d'échantillonnage, dit aussi théorème de Shannon ou théorème de Nyquist-Shannon, établit les conditions qui permettent l'échantillonnage d'un signal de largeur spectrale et d'amplitude limitées.
La connaissance de plus de caractéristiques du signal permet sa description par un nombre inférieur d'échantillons, par un processus d'acquisition comprimée.
Définition
modifierDans le cas général, le théorème d'échantillonnage énonce que l’échantillonnage d'un signal exige un nombre d'échantillons par unité de temps supérieur 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 négligeable par rapport à la fréquence maximale et le théorème affirme simplement :
La représentation discrète d'un signal exige des échantillons régulièrement espacés à une fréquence d'échantillonnage supérieure au double de la fréquence maximale présente dans ce signal.
Réciproquement, l'échantillonnage avec des échantillons régulièrement espacés peut décrire un signal à condition qu'il ne contienne aucune fréquence supérieure à la moitié de la fréquence d'échantillonnage, dite fréquence de Nyquist.
Le théorème inclut des possibilités moins souvent mises en pratique, comme l'échantillonnage d'un signal à bande de fréquences étroite à 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À 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 publié 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 Union soviétique (Kotelnikov, 1933), en Allemagne (Raabe, 1939) et au Japon (Someya, 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 quelques 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 aux démonstrations basées sur la distribution de Dirac.
Considérations préliminaires
modifierLe théorème d'échantillonnage donne la réponse mathématique à la question « combien d'échantillons faut-il pour représenter exactement un signal ? ». Le signal échantillonné représente correctement le signal continu si on peut le reconstituer sans ambiguïté. Il faut pour cela que deux signaux différents ne fournissent pas les mêmes échantillons. Nous allons d'abord déterminer les conditions nécessaires, liant la fréquence d’échantillonnage et les fréquences qui composent le signal, pour atteindre cet objectif.
Montrons que deux sinusoïdes dont la fréquence a le même écart à un multiple quelconque de la fréquence d'échantillonnage peuvent produire les mêmes échantillons.
Démonstration
- Soit une sinusoïde d'amplitude unitaire, de fréquence et de phase à l'origine :
- .
- En l'échantillonnant à une fréquence , on prend une valeur avec un pas , donc pour chaque où est un nombre entier quelconque, on obtient la suite d'échantillons :
- .
- Considérons maintenant les sinusoïdes d'amplitude unitaire, de fréquence , où est un nombre entier, et de phase à l'origine telles que :
- et .
- L'échantillonnage à la même fréquence donne la suite de nombres et :
- ,
- .
- Les échantillons tirés de ces deux sinusoïdes de fréquence et sont identiques. On en tire la conclusion qui suit.
Des sinusoïdes dont les fréquences ont le même écart à un multiple quelconque de la fréquence d'échantillonnage peuvent produire les mêmes échantillons.
Nous déduisons de cette observation qu'il faut que le signal d'origine ne puisse contenir qu'une seule des sinusoïdes de fréquence . Cette condition n'est remplie que si l'on sait par avance que le signal d’origine ne présente des fréquences que dans un intervalle situé entre deux multiples entiers de . Dans tous les autres cas, une même suite d'échantillons peut renvoyer à plusieurs signaux différents. Dans la plupart des applications, la fréquence du signal d'origine est comprise entre 0 et une fréquence maximale. Si cette fréquence maximale est supérieure à , il existe alors au moins une sinusoïde de fréquence plus basse qui présente les mêmes échantillons : on parle de repliement du spectre. Cependant, montrer qu'un échantillonnage à une fréquence 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
modifierLa démonstration qui suit reprend celle de Shannon formulée en 1949[8].
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 d'une fonction
la décrit par les fréquences qu'elle contient, exprimées dans ces équations par l'intermédiaire de la pulsation . La transformée de Fourier inverse donne la valeur de en fonction de [7] :
- .
Le signal dont s'occupe le théorème est limité en fréquence. Au-delà de , correspondant à une pulsation , les coefficients fréquentiels sont négligeables. Par conséquent,
- .
Recherchons la valeur des échantillons régulièrement espacés prenant les valeurs de pour multiple de la demi-période correspondant à ; où est un nombre entier :
- .
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 , en prenant l'intervalle comme période :
La reconstitution de la fonction est donnée par :
La valeur des échantillons prélevés à déterminent donc les coefficients du développement en série de Fourier de dans l'intervalle de fréquences . Les valeurs des échantillons déterminent donc entièrement . Puisque la transformée de Fourier d'une fonction la définit entièrement, déterminer , c'est déterminer . Ainsi, 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 en exprimant directement la fonction en fonction de son échantillonnage.
Reconstitution du signal : formule de Shannon
modifierSoit une liste d'échantillons .
Si l'on reprend l'expression de à partir de ,
en y remplaçant cette fonction par son développement en série de Fourier,
et par la valeur du coefficient déjà calculée, on obtient :
On peut calculer l'intégrale
- ,
ce qui conduit à :
- .
La fonction sinus cardinal vaut 1 pour et 0 pour tous les autres multiples de . Dans le cas présent, elle vaut 1 pour l'échantillon , c'est-à-dire pour , 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
modifierLe développement du traitement du signal dans les années suivant la publication de Shannon[9] 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 qu'à la transformation de Fourier par voie de conséquence, 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[10].
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 par un peigne de Dirac , somme d'impulsions de Dirac d'énergie et espacés de , la période d'échantillonnage.
- .
La transformée de Fourier de est la convolution de la transformée de Fourier de par celle du peigne de Dirac :
- ,
- .
L'impulsion de Dirac étant l'élément neutre de la convolution, on obtient :
- .
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 . 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 à condition que les parties de spectre qui se recouvrent aient une énergie négligeable par rapport au bruit de fond ou à la résolution du système.
Reconstitution avec la fonction sinc
modifierPuisque la transformée du signal correctement échantillonné contient, dans l'intervalle , la transformée du signal d'origine s(t), on obtient cette dernière transformée en multipliant par une fonction porte valant sur l'intervalle et 0 ailleurs :
- .
Il suffit ensuite de prendre la transformée de Fourier inverse pour reconstituer . 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. La fonction s'obtient alors comme le produit de convolution de l'échantillonnage par un sinus cardinal. Le calcul conduit alors à la formule :
- .
On a ainsi obtenu le signal initial 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
modifierComme indiqué précédemment, 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, c'est-à dire la fréquence d'échantillonnage. Lorsque la condition d'échantillonnage est satisfaite elle équivaut à une succession de copies de la transformée du signal initial.
Le spectre incluant la fréquence nulle, et ne dépassant pas la moitié de la fréquence d'échantillonnage, se désigne comme bande de base. Des copies de ce spectre autour d'une fréquence multiple de la fréquence d'échantillonnage fournissent tous la même information.
Si le spectre d'un signal à haute fréquence est inclus dans un de ces intervalles, l'échantillonnage à la fréquence d'échantillonnage de la bande de base suffit pour le décrire parfaitement.
Annexes
modifierBibliographie
modifier- Publications historiques
- (en) Claude E. Shannon, « Communication in the presence of noise », Proceedings of the Institute of Radio Engineers, vol. 37, no 1, , p. 10–21 (lire en ligne, consulté le )réédité comme classique dans Proceedings of the IEEE, vol. 86, no 2, (févr. 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, , p. 442-446 (lire en ligne, consulté le )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, Édimbourg, vol. 35, , p. 181–194 ; (en) Edmund Taylor Whittaker, « Interpolation function theory », Cambridge Tracts in Mathematics and Mathematical Physics, Cambridge, Royaume-Uni, Cambridge University Press, .
- « 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, (lire en ligne)réédité comme classique dans Proceedings of the IEEE, vol. 90, no 2, (févr. 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, (lire en ligne, consulté le )
— (en) W.R. Bennett, « Time division multiplex systems », Bell Systems Technical Journal, vol. 20,
— (en) Dennis Gabor, « Theory of communication : Part 1: The analysis of information », Journal of the Institute of Electrical Engineering, Londres, vol. 93-3, no 26, , p. 429-457 (lire en ligne, consulté le ).
- Vladimir Alexandrovitch Kotelnikov (1908-2005) était parvenu au même résultat :
- (en) C. Bissel, « The Sampling Theorem », Communications Engineer, UK, IET, (ISSN 1479-8352)
- (en) Kotelnikov VA, « On the transmission capacity of “ether” and wire in electrocommunications », Izd. Red. Upr. Svyazzi RKKA, 1933, republié en traduction anglaise dans Modern Sampling Theory: Mathematics and Applications, éditeurs J. J. Benedetto und PJSG Ferreira, Birkhauser (Boston) 2000, (ISBN 0-8176-4023-1)
- Publications modernes
- Jean-François Bercher, TF, Dirac, convolution, et tutti quanti, École Supérieure d’Ingénieurs en Électrotechnique et Électronique, (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, , p. 1565-1596 (lire en ligne, consulté le ).
- 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, , p. 569-587 (lire en ligne, consulté le )
- (en) Martin Vetterli, Pina Marziliano et Thierry Blu, « Sampling signals with finite rate of innovation », IEEE Transactions on Signal Processing, vol. 50, no 6, (bigwww.epfl.ch/publications/vetterli0201.pdf)
Articles connexes
modifier- Échantillonnage (signal)
- Fréquence d'échantillonnage
- Repliement de spectre
- échantillonnage non uniforme
- Acquisition comprimée
Notes et références
modifier- Shannon 1949, p. 449
- (en) Hans Dieter Lüke, « The Origins of the Sampling Theorem », IEEE Communications Magazine, , p. 106–108 (lire en ligne, consulté le ) ; Jerri 1977, p. 1566
- Whittaker 1915
- Unser 2000, p. 569.
- (en) John J. Benedetto, « Prologue », dans J.J. Benedetto, Ahmed I. Sayed, Sampling, Wavelets, and Tomography, Boston, Birkhäuser, (lire en ligne), xv-xvi
- Bernard Lacaze, « La formule d'échantillonnage et A. L. Cauchy », Traitement du Signal, vol. 15, no 4, (lire en ligne, consulté le )
- Pour toute la démonstration, on adopte la notation exponentielle issue de la Formule d'Euler : . 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.
- Shannon 1949, p. 448
- Shannon 1949. Les articles et livre qu'il a publié ensuite renvoient à cet article pour la démonstration.
- Bercher 2001 donne, en plus des explications courantes, une présentation de ce développement théorique.