Théorie
de l'information et du codage
Année
académique 2001-2002
Matière pour l'examen
écrit (18 janvier, matin théorie, après-midi exercices)
Exercices
Les exercices porteront
sur la matière des chapitres 3, 4, 5 et 8 des notes.
Un formulaire sera mis à
disposition des étudiants, pour la résolution des exercices.
Théorie
La partie théorie de
l'examen se fera sans l'aide du formulaire. Elle est composée de deux
parties d'importance égale.
QCM : le QCM couvrira la matière des chapitres
3,4,5,8,9,10.1-10.3,et 15.1-15.4, 15.6-15.8.
Outre le QCM, on posera deux questions à développer plus en détails, parmi les
thèmes suivants.
1.
Inégalité
de Gibbs. Enoncé, démonstration. Enoncés et démonstration des conséquences :
H(X) <= log |X|; I(X;Y) >= 0;
D(P||Q) >= 0.
2.
Règles
de chaînage (entropies, entropies conditionnelles, informations mutuelles):
énoncés et démonstrations
3.
Définition
d'un réseau bayésien et sémantique probabiliste, d-séparation et propriété
fondamentale
4.
Algorithmes
d'inférence sur chaînes de Markov cachées: position des problèmes d'inférence,
explication de l'algorithme BCJR
5.
Notion
de taux (ou débit) d'entropie d'une source S. Définitions et conditions
suffisantes d'existence
6.
Inégalité
de Kraft (démonstration), en déduire que s'il existe un code déchiffrable pour
des longueurs de mots données, alors il existe également un code instantané
pour les même longueurs de mots. Discussion des conséquences.
7.
Premier
théorème de Shannon. Enoncé et démonstration.
8.
Algorithme
de codage arithmétique : expliquer le principe
9.
Définition
générale de la capacité en information et cas particulier du canal sans
mémoire. Calcul de la capacité en information de certains canaux. Discussion
intuitive de l'effet de la mémoire sur la capacité.
10.
Canal
Gaussien : définition, calcul de la capacité en information, discussion de la
capacité en fonction du rapport signal bruit et de la bande passante.
11.
2nd
théorème de Shannon pour le canal discret sans mémoire (énoncé et démonstration
dans les grandes lignes)
12.
2nd
théorème de Shannon pour le canal Gaussien (énoncé et démonstration dans les
grandes lignes)
13.
Codage
de canal : discussion des différents modes d'utilisation du canal Gaussien
14.
Codage
algébrique : explication du code de Hamming (7,4). Notion de code linéaire
15.
Codes
convolutionnels : codage et décodage (algorithme de Viterbi), décisions
souples, réseau bayésien correspondant à ce problème
16.
Discussion
de la différence entre décodage par mot de code et décodage par bit source
17.
Explication
du fonctionnement des Turbo-codes.