TIPE : Codes correcteurs linéaires et cas du code de Hamming

Résumé du document

Une partie énorme des informations échangées à travers la planète est matériellement représentée sous la forme de nombres. Messages électroniques, téléphonie mobile, transactions bancaires, DVD, etc. : dans tous ces exemples, l'information est codée en suite de nombres entiers correspondant physiquement à des signaux électroniques ou autres. Plus précisément, elle est généralement codée sous forme de suites de chiffres binaires, à savoir des "0" ou des "1", appelés aussi bits.

Extraits

[...] - Transmettre le mot de code Pour le receveur : - Vérifier que le mot binaire reçu est un mot de code, et corriger le mot reçu en le remplaçant par le mot de code le plus vraisemblable. - Extraire le bloc du mot de code accepté ou corrigé. - On notera : k la taille des blocs, r le nombre de bits de parité pour chaque bloc, et . Le codage est l'application : qui associe un bloc à son mot de code. [...]

[...] Quand un codage est linéaire, son code est linéaire et le mot de code associé au bloc nul est 0. Analogie avec l'algèbre linéaire : a une structure de corps et est un espace vectoriel sur ce corps. Un code linéaire est un sous espace vectoriel de et un codage linéaire une application linéaire de sur . Représentation matricielle : On définit la base canonique de par : On représente un mot binaire quelconque par la matrice ligne dont les coefficients sont les bits du mot. [...]

[...] Codes Correcteurs linéaires et cas du code de Hamming Introduction: Une partie énorme des informations échangées à travers la planète est matériellement représentée sous la forme de nombres. Messages électroniques, téléphonie mobile, transactions bancaires, DVD, etc. : dans tous ces exemples, l'information est codée en suite de nombres entiers correspondant physiquement à des signaux électroniques ou autres. Plus précisément, elle est généralement codée sous forme de suites de chiffres binaires, à savoir des ou des appelés aussi bits. Un problème majeur de la transmission de l'information est celui des erreurs: en raison de phénomènes parasites, des peuvent être malencontreusement changés en dans le message transmis, ou l'inverse. [...]

[...] Hamming, est un code correcteur linéaire permettant la détection et la correction automatique d'une erreur, du moment qu'elle ne porte que sur une lettre du message. Plan: Les Codes correcteurs d'erreurs Le codage linéaire. Cas des codes de Hamming. Application informatique. Codes correcteurs d'erreurs : La distance de Hamming : On munit de l'addition modulo 2 définie par : Elle possède plusieurs propriétés: De plus : On munit aussi de l'addition modulo 2 : Si et sont deux mots binaires, leur somme modulo 2 et le mot binaire ayant pour bit. [...]

[...] Puisque il permet de ne corriger qu'une erreur pour un mot de code donné. La matrice de Hamming d'un code de Hamming permet de définir les mots de codes : mot de code La correction devient plus facile avec le code de Hamming : Supposons que l'on reçoive qui diffère d'un mot du code c de un bit : , où e est le vecteur d'erreur. Comme , on a . Puisque e contient un seul bit non nul le calcul de donne une des colonnes de , et ainsi, permet de connaitre la position du bit non nul dans et donc de connaître . [...]