Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Théorie de l’Information Année 2016 - 2017 L1 Semestre 2 TD 1 : Codes et Codage

Théorie de l’Information Année 2016 - 2017 L1 Semestre 2 TD 1 : Codes et Codage de caractères 1 Codage de caractères Exercice 1 Convertissez — les nombres (17)10, (42)10, (555)10 en base 16 et 2 — les nombres (3A)16 et (DEC)16 en base 10 et 2 BEGIN SOLUTION — les nombres (17)10 = (11)16, (42)10 = (2A)16, (555)10 = (22B)16 en base 16 et 2 — les nombres (3A)16 = 58 et (DEC)16 = 3564 END SOLUTION Exercice 2 Quelle partie de l’espace de code est utilisée par UTF-32 ? BEGIN SOLUTION L’espace de alphabet représentable en Unicode est U+0 . . .U+(10FFFF)16, il y a donc (11.0000)16 caractères dans l’alphabet. Un mot 32 bit permet de représenter (1.0000.0000)16 valeurs. La fraction utilisée est donc ( 11 10000)16 ≈( 1 3855)10. END SOLUTION Exercice 3 Quelle est la taille (en octets) d’un texte avec n caractères ASCII codé en format 1. UTF-8 2. UTF-16 3. UTF-32 BEGIN SOLUTION 1. n 2. 2n 3. 4n END SOLUTION Exercice 4 Voici des extraits de la table de codage Unicode pour l’alphabet hébreu, japonais et phéni- cien. (a) Hebrew (b) Katakana (c) Phoenician Codez les caractères Alef, Bet et Nun (05D0, 05D1, 05E0), les caractères Gu et We (30B0, 30F1) et Alf, Bet (10900, 10901) en UTF-8, UTF-16, UTF-32. Théorie de l’Information 2016 - 2017 1 TD 1 BEGIN SOLUTION — unicode 0x5D0 : U+05D0 HEBREW LETTER ALEF, UTF-8 : d7 90 UTF-16BE : 05d0 — unicode 0x5D1 : U+05D1 HEBREW LETTER BET, UTF-8 : d7 91 UTF-16BE : 05d1 — unicode 0x5E0 : U+05E0 HEBREW LETTER NUN, UTF-8 : d7 a0 UTF-16BE : 05e0 — unicode 0x30B0 : U+30B0 KATAKANA LETTER GU, UTF-8 : e3 82 b0 UTF-16BE : 30b0 — unicode 0x30F1 : U+30F1 KATAKANA LETTER WE, UTF-8 : e3 83 b1 UTF-16BE : 30f1 — unicode 0x10900 : U+10900 PHOENICIAN LETTER ALF, UTF-8 : f0 90 a4 80 UTF-16BE : d802dd00 — unicode 0x10901 : U+10901 PHOENICIAN LETTER BET, UTF-8 : f0 90 a4 81 UTF-16BE : d802dd01 END SOLUTION 2 Codes et codages Exercice 5 Cochez les cases où m1 ⪯m2 : m1 / m2 01 010 110 01 101 10 11 Exercice 6 On dit qu’une relation R est un ordre si elle est — réﬂexive : ∀x.R(x, x) — antisymétrique : ∀xy.R(x, y) ∧R(y, x) →x = y — transitive : ∀xy.R(x, y) ∧R(y, z) →R(x, z) Pour la relation ⪯, on utilise une notation inﬁxe, c.à.d. on écrit x ⪯y au lieu de ⪯(x, y). Montrez que la relation ⪯déﬁnie par m ⪯m′ =def ∃r.m′ = m · r est un ordre. Exercice 7 On déﬁnit trois codes c1, c2, c3 pour un alphabet A = {a, b, c, d} selon le tableau suivant : x c1(x) c2(x) c3(x) a 0 10 0 b 010 00 10 c 01 11 110 d 10 110 111 Montrez que : — c1 est injectif, mais son extension homomorphe c∗ 1 n’est pas unique — c2 n’est pas un code préﬁxe, mais son extension homomorphe c∗ 2 est unique — c3 est un code préﬁxe BEGIN SOLUTION — Non-unicité de c1 : c1(ca) = c1(b) — Unicité de c2 : Uniquement c2(c) et c2(d) n’ont pas la propriété préﬁxe. Pour toute chaîne 110..., on a besoin d’un lookahead arbitrairement long. Si 11 est suivi d’un nombre pair de 0, on a la séquence cb.... Si 11 est suivi d’un nombre impair de 0, on a la séquence db.... END SOLUTION Exercice 8 Montrez formellement que tout codage unique est un codage injectif. Remarque : L’exercice 7 montre que cette inclusion est stricte. Théorie de l’Information 2016 - 2017 2 TD 1 BEGIN SOLUTION Soit c un codage unique. Il existe donc un d tel que pour tout message m, d(c(m)) = m. Soient m1, m2 messages avec m1 ̸= m2. Supposons c(m1) = c(m2). Par unicité de c, on a m1 = d(c(m1)) = d(c(m2)) = m2, une contradiction. END SOLUTION Exercice 9 Montrez formellement que tout codage c∗qui est l’extension homomorphe d’un code préﬁxe c est injectif. BEGIN SOLUTION Soit c∗un code préﬁxe homomorphe. On montre qu’il est injectif : Si c∗(m1) = c∗(m2), alors m1 = m2. Par induction sur la taille (= nombre de caractères) de m1. — Si |m1| = 0, donc m1 = [], alors c∗(m1) = c∗(m2) = [], donc forcément m2 = []. — Soit |m1| = n + 1, donc m1 = a · m′ 1. On voit que m2 ne peut pas être vide. Il est donc de la forme b · m′ 2. Alors, c∗(m1) = c∗(a · m′ 1) = c(a) · c∗(m′ 1) = c∗(m2) = c(b) · c∗(m′ 2). On voit c(a) ⪯c(b), donc a = b à cause de c code préﬁxe, donc c(a) = c(b), donc c(m′ 1) = c(m′ 2), donc m′ 1 = m′ 2 par hypothèse d’induction. END SOLUTION Exercice 10 Est-ce que le code Morse est unique / injectif / un code préﬁxe ? BEGIN SOLUTION Réponse : il n’est pas injectif (par example code(ATT) = code(J)) et par conséquent pas unique. END SOLUTION Exercice 11 Appliquez l’algorithme arbre_dec aux codages c1 et c2 de la table suivante. x c1(x) c2(x) c3(x) a 00 01 0 b 01 11 10 c 10 00 110 d 11 001 1110 Si la construction de l’arbre échoue, identiﬁez les causes. Est-ce que vous pouvez proposer des codages qui évitent le problème ? BEGIN SOLUTION 1. c2 est “l’inverse” du code c2 de l’exercice 7, donc pas un code préﬁxe. Irréparable. 2. c3 ne permet pas la construction d’un arbre binaire complet (voir exercice 14). On peut trouver le code plus court 0, 10, 110, 111 END SOLUTION Exercice 12 Appliquez l’algorithme tab_cod aux arbres de décodage obtenus dans l’exercice 11 et vé- riﬁez que vous obtenez bien les tables d’origine. Exercice 13 Pourquoi est-ce que l’algorithme tab_cod termine ? Théorie de l’Information 2016 - 2017 3 TD 1 BEGIN SOLUTION Récursion structurelle sur l’arbre. END SOLUTION Exercice 14 (Devoir maison) Analyse de l’algorithme arbre_dec : 1. Quels problèmes se poseraient pour un algorithme de décodage si l’arbre n’était pas un arbre binaire (mais si un noeud intérieur pouvait avoir un seul successeur) ? 2. Un invariant de arbre_dec est qu’il prend la représentation d’une table tab d’un codage préﬁxe. Démontrez que cet invariant est maintenu par les appels récursifs, donc, que {(c, m)|(c, 0 · m) ∈tab} représente bien une table d’un codage préﬁxe (et pareil pour 1 · m). 3. Démontrez que si (c, []) ∈tab, alors il n’est pas possible d’avoir un (d, m) ∈tab, pour un c ̸= d. 4. Démontrez que l’algorithme termine. BEGIN SOLUTION 1. Arbre binaire incomplet : certains codes ne seraient pas un codage correct d’un code source, par exemple 1111. Mais c’est aussi un problème pour des arbres complets, si le message est tronqué. 2. Supposons qu’il existent m1, m2 avec (c, 0 · m1) ∈tab et (c, 0 · m2) ∈tab et m1 ⪯m2. Alors, aussi 0 · m1 ⪯0 · m2. Contradiction avec codage préﬁxe de tab. 3. Si (c, []) ∈tab et (d, m) ∈tab, puisque [] ⪯m, on a une contradiction avec codage préﬁxe de tab. 4. Terminaison : dans chaque appel récursiv, pour chaque (c, m), la taille de m décroit, jusqu’à ce que tab contient uniquement des éléments avec m = []. Selon (3), il peut seulement y avoir un seul (c, []) ∈tab, on termine donc avec la clause (2). END SOLUTION Exercice 15 1. Utilisez l’inégalité de Kraft pour déterminer s’il est possible de construire un code préﬁxe pour les caractères a . . . d avec les longueurs de code suivants : caractère a b c d longueur 1 2 2 3 2. Quelle serait votre réponse si on admet un code de longueur 3 pour le caractère b ? Proposez eﬀectivement un code. BEGIN SOLUTION 1. 2−1 + 2 ∗2−2 + 2−3 = 9 8 > 1, un code n’est pas possible. 2. 2−1 + 2−2 + 2 ∗2−3 = 1, un code est possible, par exemple a 7→0, c 7→10, b 7→110, d 7→111 END SOLUTION Exercice 16 1. Une entreprise veut installer un système téléphonique interne où les 5 membres du directoire ont un numéro à un seul chiﬀre (de 0 à 9) et les 80 autres employés un nombre à deux chiﬀres. Est-ce possible ? 2. Serait-il possible d’avoir des numéros à deux chiﬀres pour les membres du directoire et de trois chiﬀres pour les autres employés ? Faites une proposition concrète. Théorie de l’Information 2016 - 2017 4 TD 1 A noter : L’inégalité de Kraft se généralise d’un code binaire à un code n-aire (alphabet à n chiﬀres) comme suit : Il existe un code préﬁxe n-aire avec k codes u1 . . . uk si et seulement si k X i=1 n−|ui| ≤1 où |ui| est la longeur du code ui. BEGIN SOLUTION 1. 5 ∗10−1 + 80 uploads/S4/ td1-corrige 24 .pdf