Master MIC, 1re année

Université Paris Diderot

Résumé

Le cours s'articule autour de trois théorèmes de Claude Shannon. Ce sont trois théorèmes mathématiques avec des problématiques différentes autour de la numérisation optimale et la transmission de l'information.

Le premier théorème s'intéresse à la compression des données : si on veut numériser un document, il est intuitivement clair qu'on va gagner en espace de stockage en codant de façon plus courte les caractères les plus fréquents et de façon plus longue les moins fréquents. Cette fréquence des caractères nous fera introduire le language des probabilités et d'entropie de Shannon.

Le deuxième théorème s'intéresse à la transmission (ou stockage) sans pertes des données. On démontre qu'en introduisant un peu de redondance dans un document numérisé, on peut le retrouver malgré la perte aléatoire d'une partie de l'information. C'est encore ici le language des probabilités qui est utilisé. En plus de l'entropie, apparaît ici la notion de capacité d'un canal de transmission.

Le troisième est le théorème d'échantillonnage. Une information peut être une fonction d'une variable réelle. Le théorème d'échantillonnage nous explique comment, en prenant la valeur de cette fonction en un nombre fini de points, on peut reconstruire l'information. On tient compte pour cela des fréquences de notre fonction. L'analyse faite ici est basée sur la théorie des séries de Fourier.

Contenu

  1. Notions de probabilités discrètes et continues.
  2. Entropie, information mutuelle
  3. Premiers théorèmes de Shannon
  4. Séries de Fourier
  5. Théorème d'échantillonnage

Horaire des cours

Le cours aura lieu du 12 septembre au 5 décembre 2019 :
Attention ! Le cours du 10 octobre aura lieu au bâtiment Lavoisier, salle 130.

Bibliographie

Documents disponibles

Résumé des séances

12 septembre
Introduction : le modèle de Shannon de la communication. Entropie. Entropie d'une variable aléatoire discrète, exemples d'un tirage de dés, d'une loi uniforme et d'une loi de Bernoulli. Entropie conditionnelle. Divergence d'une loi par rapport à une autre et information mutuelle de deux variables aléatoires ; positivité de l'information mutuelle, lien avec l'entropie.
19 septembre
Information mutuelle conditionnelle, indépendance conditionnelle de deux variables aléatoires relative à une variable aléatoire. Taux d'entropie d'un processus stochastique. Cas d'un processus iid, d'un processus stationnaire. Processus markoviens homogènes : entropie dans le cas stationnaire.
26 septembre
Reprise du cours sur le taux d'entropie d'un processus stochastique. Processus markoviens homogènes : existence et calcul de l'entropie dans le cas stationnaire, puis dans le cas primitif (= irréductible apériodique, le théorème de convergence vers la loi stationnaire a été admis). Codage. Alphabet, mots, longueur, concaténation des mots (structure de monoïde). Code, code uniquement décodable, code préfixe.
3 octobre
Inégalité de Kraft–McMillan. Minoration de la longueur moyenne d'un mot de code par l'entropie de la source. Inversement, construction de codes permettant une compression assez efficace (Shannon).
10 octobre
Codes optimaux : codage de Huffman. Inégalité de Markov, inégalité de Bienaymé–Tchebitcheff, loi faible des grands nombres.
17 octobre
Interprétation statistique de l'entropie. Modèle de communication avec bruit, définition d'un canal sans mémoire. Capacité de transmission d'un tel canal, exemples.
24 octobre
Reprise du calcul de la capacité de transmission d'un canal avec bruit. Code adapté à un canal avec bruit, taux de transmission, probabilités d'erreur maximale et moyenne ; ratio atteignable. Énoncé du théorème de Shannon. Démonstration d'une inégalité : un ratio atteignable est au plus égal à la capacité de transmission, inégalité de Fano. Discussion orale de l'inégalité inverse : existence de codes efficaces (de ratio proche de la capacité, de grande longueur et probabilité d'erreur maximale petite) ; comment passer d'un code de probabilité d'erreur moyenne petite à un code de probabilité d'erreur maximale petite ; argument de moyenne sur tous les codes possibles. Discussion orale des codes correcteurs existants (des codes linéaires aux turbocodes).
Powered by MathJax Valid CSS! Valid XHTML 1.1! Antoine Chambert-LoirDernière mise à jour :