Les codages

Résumé du document

Cours de Mathématiques appliquées à l'informatique se consacrant aux codages. Les notions sont expliquées au cours d'un même cheminement : cours, exemples provenant d'exercices résolus, définitions et propriétés déduites ?

Extraits

[...] - CODAGES & AUTOMATISMES Dans B5 Déterminer le cercle de centre et de rayon 2 (il y aura 10 vecteurs) C ( ; La distance de 2 vecteurs est égale au poids de leur somme + poids 3 Les vecteurs de poids 2 : Pour obtenir le cercle complet, il suffit d'intervertir par bits en changeant 2 éléments à chaque fois. C = { 11000} Sont dans le cercle ce qui est de poids 2 + ne fait pas partie du cercle car de poids 1. [...]

[...] est de rayon 2. C(u ; est constitué de soit 28 vecteurs. C(u ; est constitué de 7 vecteurs. C(u ; est constitué du seul vecteur Définition On va coder de Bk vers Bn avec k [...]

[...] P a ge 9 CODAGES & AUTOMATISMES Codage linéaire d'un bloc k n Soit B et B , deux espaces vectoriels sur B avec k [...]

[...] - 10 ! = k n 10 x 9 x 8 = 3x2 n-k = n 0 n = 1 n 1 n-1 = n = n P a ge = 6 = 120 CODAGES & AUTOMATISMES Propriété : La probabilité qu'il y ait k erreur sur la transmission de n bits est égale à : k n p k q n-k Explication : Envois de 6 bits 2 erreurs p(2 erreurs) = 15 p2 q4 6x Probabilité = = 6 = Exemple 1 : p = 0,002 et on envoi 8 bits p(0 erreur) = 0,998 x 0,998 x . [...]

[...] C'est un détecteur d'erreur. Propriété : Exemple 2 La probabilité qu'il y ait erreur et qu'elle soit détectée est égale à : Proportion des erreurs détectées p 1 q + 8 p 3 q + 8 p 5 q + 8 p 1 - 98 Probabilité qu'il y ait erreur Ce codage est utilisé quand p est très faible Avec p = 0,001 on corrige des erreurs Avec p = 0,01 on corrige des erreurs Avec p = 0,1 on corrige des erreurs P a ge q CODAGES & AUTOMATISMES 2.2 Code correcteur Codage par répétition .0 est codé est codé 111 L'information est codée On reçoit 000 on considère que c'est 0 qui est envoyé On reçoit 001 on considère que c'est 0 qui est envoyé On reçoit 010 on considère que c'est 0 qui est envoyé On reçoit 011 on considère que c'est 1 qui est envoyé Etc Ce codage améliore la qualité au détriment de la rapidité .000 p(erreur) = p3 Probabilité qu'il y ait erreur p(erreur) = 100% = 1 Si un seul bit est faux, la correction est bonne Si deux bits sont faux, la correction est mauvaise .111 p(erreur) = p3 Après la correction automatique, la probabilité qu'il y ait erreur est donc : p 2 q + 3 p 3 Probabilité 3 erreurs Probabilité 2 erreurs Exemple : 3 répétitions p = 0,01 (sur un bit) Probabilité d'erreur = 0,0003 On est passé de à 0,03% P a ge 4 CODAGES & AUTOMATISMES 2.3 Autre Codage correcteur : Codage linéaire Distance de Hamming On considère B = { } avec les deux lois + n Les espaces vectoriels (finis) B sur lesquels on travaille. [...]