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
- Notions de probabilités discrètes et continues.
- Entropie, information mutuelle
- Premiers théorèmes de Shannon
- Séries de Fourier
- Théorème d'échantillonnage
Horaire des cours
Le cours aura lieu du 12 septembre au 5 décembre 2019 :
Examen de seconde session : mardi 19 juin, de 9h30 à 12h30, bâtiment Sophie Germain, salle 0014.
Bibliographie
- T. Cover, J. Thomas, Elements of Information Theory, Wiley & Sons, 2e édition, 2006
- H. Dym, H. P. McKean, Fourier series and integrals, Academic Press, 1972
- J.-P. Kahane, P.-G. Lemarié-Rieusset, Séries de Fourier et Ondelettes, coll. Nouvelle bibliothèque mathématique, Cassini, 2017
- C. Shannon, La théorie mathématique de la communication, coll. Le sel et le fer, Cassini, 2018. Traduction de « A mathematical theory of communication », The Bell System Technical Journal, vol. 27, p. 379–423, 623–656, 1948.
- C. Shannon, « Communication in the presence of noise », Proc. of the IRE, vol. 37, p. 10–21, 1949. Réimprimé dans Proc. of the IEEE, vol. 86, p. 447--458, 1998.
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).
- 7 novembre
-
Démonstration du théorème de Shannon.
- 14 novembre
-
Échantillonnage.
Discussion de la problématique du traitement numérique
de l'information, échantillonnage, quantification.
Énoncé vague du théorème d'échantillonnage.
Séries de Fourier (définitions).
- 21 novembre
-
Séries de Fourier (suite), théorème de Dirichlet.
Transformation de Fourier.
- 28 novembre
-
Transformation de Fourier, énoncé des théorèmes. Théorème d'échantillonnage.
- 5 décembre
-
Théorème d'échantillonnage. Lien avec la formule de Poisson.
Suréchantillonnage.
Antoine Chambert-Loir—
Dernière mise à jour :