Résumé du cours

La Théorie de l'Information est à l'origine une Théorie de la Communication : elle vise à établir les limites de la transmission fiable et efficace de signaux dans des milieux où les signaux sont soumis à des distorsions plus ou moins aléatoires. Dans ce cours d'introduction, on ne parlera que de signaux discrets, c'est-à-dire de textes.

Codage source

Le problème la plus simple consiste à transmettre fidèlement et efficacement un texte dans un milieu fiable : cela revient à comprimer de manière réversible le texte. La démarche de la Théorie de l'Information postule que les textes sont produits par une source aléatoire (une source n'est qu'une loi de probabilité sur les textes). Ce postulat permet de définir de manière opérationnelle un taux de compression optimal sur une source donnée. Un premier résultat (dû à C.E Shannon, 1948) affirme que ce taux de compression optimal peut être caractérisé par l'entropie de la source (donc par une fonctionnelle de la loi de probabilités qui définit la source). De plus, cette caractérisation est constructive : il existe des algorithmes de compression efficaces et simples (codage de Huffmann, codage arithmétique). Ces algorithmes sont des briques de base dans la construction de techniques de compression utilisées quotidiennement (par exemple jpeg, jpeg2000, gzip).

Le second problème consiste à comprimer fidèlement et efficacement les réalisations d'une source inconnue, c'est le problème du codage universel. Caractériser le coût du codage universel lorsqu'on s'intéresse à une famille de sources donnée revient à résoudre un problème de Statistique. On montre l'intérêt des techniques dites de mélanges à l'aide de quelques arguments d'optimisation, et l'intérêt des mélanges construits à partir des lois de Dirichlet et on passe aux techniques effectivement utilisées : les méthodes de dictionnaires (gzip, zip, compress) et la transformation de Burrows-Wheeler (bzip2). Les vingt-cinq dernières années ont été marquées par des progrès marquants dans la mise en oeuvre et l'analyse du codage universel : celui-ci est utilisé est massivement utilisé par l'Informatique et il posse des questions intéressantes à la théorie des séries chronologiques et à la théorie ergodique.

Plus délicat encore est le problème de la compression respectant un critère de fidélité, c'est-à-dire une contrainte de distorsion. Ce problème conduit à introduire une nouvelle fonctionnelle de la source : la fonction de débit-distorsion. Cette fonctionnelle, contrairement à l'entropie, est définie de manière implicite comme l'objectif d'un problème d'optimisation. Le second grand résultat de Shannon montre que la fonction de débit-distortion caractérise les possibilités de la compression respectant un critère de fidélité sur une source donnée. La preuve s'appuie sur un argument de sélection aléatoire, elle ne débouche pas sur des méthodes pratiques, mais fournit un guide dans la conception de compresseurs de sons et d'images (comme jpeg, mpeg, mp3, rpe-lpc...). Enfin, le calcul de la fonction de débit-distorsion d'une source donnée conduit à analyser un algorithme de minimisation alternée dont le principe est applicable au delà des problèmes de Théorie de l'Information.

Codage canal

Le problème de la transmission sur un milieu qui n'est pas fiable, le codage canal est lui aussi abordé via une modélisation stochastique : un canal définit une probabilité de transition entre un symbole d'entrée et un symbole de sortie. Là encore, il est possible de faire caractériser les limites de la transmission fiables sur un canal donné comme les solutions d'un problème d'optimisation posé à partir de la matrice de transition qui définit le canal. Mais comme dans le cas du codage « source » avec un critère de fidélité, cette caractérisation n'est pas constructive. La Théorie de l'Information a lancé un défi que l'Informatique n'a pas encore complètement relevé.

Le cours s'achèvera par la présentation des deux grandes directions explorées en codage canal :

  • le codage algébrique sera présenté via les codes de Reed-Solomon . Cette méthode illustre l'apport de l'algorithmique des matrices structurées et de l'algèbre en codage. C'est aussi un outil utile en combinatoire, en complexité et en algorithmique.
  • les codes à matrice de parité creuse. Cette approche bouillonne depuis une dizaine d'années, elle reprend de manière subtile l'argument de sélection aléatoire utilisé dans la démonstration du Théorème de Codage Canal et conduit à la construction de codes dotés d'algorithmes simples et très efficaces.

Prérequis

Probabilités élémentaires (ensembles finis)

Horaires

  • Volume : 13 × 3 heures.
  • Lundi de 8 heures 45 à 12 heures à Chevaleret salle 0C02.
  • Premier cours : 3 octobre 2005
  • Pas de cours le 17 octobre

Evaluation

  • 6 ECTS
  • 3 Devoirs.

Public:

Etudiants en Master Mathématiques et/ou Informatique Les versions successives de ce cours ont été données en DEA et DESS d'Ingénieurie Mathématiques à l'Université Paris-Sud de 2000 à 2002, puis en Master Informatique à l'Université Paris VII et à l'ENS CACHAN en 2003 et 2004.

Enseignant

S. Boucheron