École polytechnique Informatique Introduction à la théorie de l'information Nic
École polytechnique Informatique Introduction à la théorie de l'information Nicolas Sendrier août 2007 Promotion 2005, Majeure 1 d'informatique Chapitre 1 Systèmes de communication 1.1 Introduction La théorie des communications s'intéresse aux moyens de transmettre une information depuis une source jusqu'à un utilisateur (cf. Figure 1.1). La nature de la source peut-être très variée. Il peut s'agir par exemple d'une voix, d'un signal électromagnétique ou d'une séquence de symboles binaires. Le canal peut être une ligne téléphonique, une liaison radio ou encore un support ma- gnétique ou optique : bande magnétique ou disque compact. Le canal sera généralement perturbé par un bruit qui dépendra de l'environnement et de la nature canal : perturbations électriques, rayures, . . . . Le codeur représente l'ensemble des opérations eectuées sur la sortie de la source avant la transmission. Ces opérations peuvent être, par exemple, la modulation, la compression ou encore l'ajout d'une redondance pour combattre les eets du bruit. Elles ont pour but de rendre la sortie de la source compatible avec le canal. En n, le décodeur devra être capable, à partir de la sortie du canal de restituer de façon acceptable l'information fournie par la source. Source Codeur Canal Décodeur Utilisateur - - - - ? Bruit Fig. 1.1 Schéma d'un système de communication. Dans les années 40, C. E. Shannon a développé une théorie mathématique appelée théorie de l'information qui décrit les aspects les plus fondamentaux des systèmes de communication. Cette théorie s'intéresse à la construction et à l'étude de modèles mathématiques à l'aide essentiellement de la théorie des probabilités. Depuis ce premier exposé publié en 19481, la théorie de l'information s'est faite de plus en plus précise et est devenue aujourd'hui incontournable dans la conception tout système de communication, au sens le plus large de ce terme. Dans ce cours, nous étudierons certains de ces modèles mathématiques, qui, bien que considé- rablement plus simple que les sources et les canaux physiques, permettent de donner une bonne intuition de leur comportement. Dans le but de simpli er l'étude des systèmes de communication, nous étudierons séparément les modèles de sources et les modèles de canaux. Ceci peut se schématiser en séparant le codeur et le décodeur de la Figure 1.2 en deux parties. Le but du codeur de source est de représenter la sortie de la source, ou information, en une séquence binaire, et cela de la façon la plus économique possible. Le but du codeur de canal et de son décodeur est de reproduire le plus dèlement possible cette séquence binaire malgré le passage à travers le canal bruité. 1C. E. Shannon, A Mathematical Theory of Communication, Bell System Technical Journal, vol. 27, pages 379423 et 623656, 1948 3 4 CHAPITRE 1. SYSTÈMES DE COMMUNICATION ? - - Utilisateur Décodeur de source Décodeur de canal Canal Codeur de canal Codeur de source Source Bruit Fig. 1.2 Système de communication avec codeurs de source et de canal séparés. Cette séparation rendra notre étude commode, car nous pourrons traiter indépendemment la source et le canal. De plus cette séparation n'implique aucune limitation sur les performances du système. Nous poursuivrons donc ce chapitre d'introduction par une brève description des diérentes classes de modèles de sources et de canaux. 1.2 Sources et codage de source 1.2.1 Sources discrètes sans mémoire Parmi les classes possibles de modèles de sources, nous nous intéresserons plus particulièrement aux sources discrètes sans mémoire. La sortie d'une telle source est une séquence de lettres tirées dans un alphabet ni2 {a1, . . . , aK}. Chaque lettre de la séquence est statistiquement indépendante des autre et obtenue d'après une loi de probabilité xe P(a1), . . . , P(aK). Pour toute lettre ak, 1 ≤k ≤K, de la source, P(aK) est la probabilité pour que cette lettre soit produite, nous aurons donc PK k=1 P(ak) = 1. Il peut sembler étonnant de modéliser une source d'information à l'aide d'un processus aléatoire. L'exemple suivant nous montre toutefois que l'utilisation des probabilités est indispensable pour coder une information de façon compacte. Exemple: Soit une source d'information qui fournit comme information l'une des quatre lettres a1, a2, a3 et a4. Supposons que le codage transforme cette information en symboles binaires. Dans la Table 1.1, nous donnons deux codages diérents de cette source. Dans la première Méthode 1 Méthode 2 a1 →00 a1 →0 a2 →01 a2 →10 a3 →10 a3 →110 a4 →11 a4 →111 Tab. 1.1 Deux codages d'un alphabet de quatre lettres. méthode, deux symboles binaires sont générés pour chaque lettre émise, alors que dans la seconde le nombre de symboles est variable. Si les quatre lettres sont équiprobables, alors la première méthode est la meilleure : 2 symboles par lettre en moyenne au lieu de 2,25. En revanche si l'on a P(a1) = 1 2, P(a2) = 1 4, P(a3) = P(a4) = 1 8, 2Nous réserverons la dénomination de sources discrètes aux alphabets nis. Lorsque l'alphabet est in ni et dénombrable nous parlerons de source discrète in nie. 1.3. CANAUX ET CODAGE DE CANAL 5 alors la méthode 1 nécessite toujours 2 symboles binaires par lettre en moyenne alors que la méthode 2 qui n'en nécessite que 1,75. Elle est dans ce cas la plus économique. Il est donc important pour coder correctement une source de connaître son comportement statistique. 1.2.2 Entropie d'une source discrète sans mémoire Il apparaît qu'il existe un lien entre l'information fournie par une source et la distribution de probabilité de la sortie de cette source. Plus l'événement donné par la source est probable, moins la quantité d'information correspondante est grande. Plus précisément, si une lettre ak a une probabilité P(ak) d'être produite par la source, son information propre sera I(ak) = −log2 P(ak). Cette dé nition parait conforme à l'idée intuitive que l'on peut se faire de l'information, et en particulier on a I(ak) = 0 si P(ak) = 1, c'est-à-dire que l'occurrence d'un événement certain ne peut fournir aucune information. La valeur moyenne de l'information propre calculée sur l'ensemble de l'alphabet revêt une grande importance. Elle est appelée entropie de la source et vaut K X k=1 −P(ak) log2 P(ak). L'entropie d'une source est le nombre moyen minimal de symboles binaires par lettre nécessaires pour représenter la source. Par exemple, si un alphabet contient 2L lettres équiprobables, il est immédiat que l'entropie de la source correspondante vaut L. Or il est bien clair que pour représenter 2L lettres distinctes, L symboles binaires sont nécessaires. L'entropie d'une source est parfois donnée en bits par seconde, si l'entropie d'une source discrète est H, et si les lettres sont émises toutes les τs secondes, son entropie en bits/s sera H/τs. 1.2.3 Autres modèles de sources On peut citer également parmi les classes de modèles de source, les sources discrètes station- naires, pour lesquelles une entropie peut être dé nie de façon analogue. En n, les sources non discrètes, ou sources continues, ont une grande importance pour les applications. La sortie d'une telle source sera une fonction continue du temps, par exemple une tension, qu'il faut coder en une séquence binaire. La fonction continue devra être décrite le plus dèlement possible par la séquence binaire générée par le codeur de source. Le problème essentiel dans ce cas consiste à minimiser le nombre de symboles transmis pour un niveau de distorsion donné. 1.3 Canaux et codage de canal 1.3.1 Canaux discrets Pour modéliser correctement un canal de transmission il est nécessaire de spéci er l'ensemble des entrées et l'ensemble des sorties possibles. Le cas le plus simple est celui du canal discret sans mémoire : l'entrée est une lettre d'un alphabet ni {a1, . . . , aK}, et la sortie est une lettre d'un autre alphabet ni, éventuellement identique, {b1, . . . , bJ}. Ces lettres sont émises en séquence, et pour que le canal soit sans mémoire, il faut que chaque lettre de la séquence reçue ne dépende statistiquement que de la lettre émise de même position. Ainsi un canal discret sans mémoire est entièrement décrit par la donnée des probabilités conditionnelles P(bj | ak), pour tout ak dans l'alphabet d'entrée et tout bj dans l'alphabet de sortie. Par exemple le canal binaire symétrique, représenté dans la Figure 1.3, est un canal discret sans mémoire, dont l'alphabet d'entrée et l'alphabet de sortie sont égaux tous deux à {0, 1}. La 6 CHAPITRE 1. SYSTÈMES DE COMMUNICATION probabilité pour qu'un symbole soit inchangé est 1 −ϵ, et la probabilité pour qu'il soit transformé en son opposé est ϵ. PPPPPPPPPPPPPPPPP P 0 1 0 1 ϵ ϵ 1 −ϵ 1 −ϵ Alphabet d'entrée Alphabet de sortie Fig. 1.3 Canal binaire symétrique. On peut également considérer des canaux discrets à mémoire dans lesquels chaque lettre de la séquence de sortie peut dépendre de plusieurs lettres de la séquence d'entrée. 1.3.2 Canaux continus Il existe une classe de modèles de canaux, appelé canaux continus, beaucoup plus proche des canaux physiques, dans lesquels l'entrée et la sortie sont des uploads/S4/ theorie-de-l-x27-information.pdf
Documents similaires
-
23
-
0
-
0
Licence et utilisation
Gratuit pour un usage personnel Attribution requise- Détails
- Publié le Jui 08, 2022
- Catégorie Law / Droit
- Langue French
- Taille du fichier 0.5633MB