Codes correcteurs

Alaeddine Ben Rhouma

Informations

• Publié par: ALEDINE.BENRHOUMA
• Publié le: 08 mai 2015
• Nombre de lectures: 20
• Langue: Français

Extrait

Agrégation interne de Mathématiques Académie de Guyane
Codes correcteurs d’erreur
nOn noteF le corpsZ=2Z. Lorsque n est un entier fixé, on peut ainsi définir leF -espace vectorielF .2 2 2
1 Distance de Hamming
Définition (Poids d’un mot).
nSi x est un vecteur deF , on définit w(x) comme le nombre de coordonnées non nul de x.2
5Exemple : Soit x = (1;0;0;1;1)2F , on alors w(x) = 3.2
Définition (distance de Hamming).
n nPour tout (a;b)2F F , on définit la distance entre a et b par d(a;b) =w(a b).2 2
Théorème.

n nd : F F ! N2 2La fonction est une distance.
(a;b) 7! w(a b)
Exercice 1 : Démontrer le théorème précédent.
2 Codes linéaires
k nPour coder un message de longueur k, on utilise une application linéaire injective de F dansF .2 2
k nOn la note ’ et on dit que l’image de ’ est le code. On noteC = ’(F ). C’est un sous-espace vectoriel de F de2 2
dimension k.
On dit qu’un message reçu m est accepté si m2C.
Exemple 1 : le bit de parité On doit transmettre trois bits d’information et on utilise un quatrième bit de contrôle.
Ce bit est choisi de façon à que le nombre de "1" dans les coordonnées du message transmis soit pair.
Par exemple, (0;1;1) est codé en (0;1;1;0) et (1;1;0) est codé en (1;1;0;1).
Exemple 2 : répétition du message On doit transmettre l’information par blocs de 1 bit. le codage consiste à
dupliquer deux fois ce bit. Ainsi 0 est codé (0;0;0) et 1 est codé (1;1;1).
2 3Exemple 3 : définition par la fonction de codage La matrice de ’ dans les bases canoniques deF etF est :2 2
0 1
0 1
@ AG = 1 0
1 1
Exercice 2 : répondre aux questions suivantes pour chaque exemple.
1. Écrire tous les mots du code.
2. Déterminer la distance minimale du code.
3. Sachant qu’un message comporte une seule erreur, peut-on le corriger?
k n4. Quelle est la matrice de ’ dans les bases canoniques deF etF ?2 2
Alaeddine BEN RHOUMA 1 Codes correcteursAgrégation interne de Mathématiques Académie de Guyane
3 Capacité de détection et de correction
Définition (distance minimale).
On appelle distance minimale d’un code le nombre entier
d =Minfw(x)=x2C et x = 0g
Théorème.
Si un message reçu contient strictement moins de d erreurs, il peut être identifié.
d
Si un message contient strictement moins de erreurs, il peut être corrigé.
2
4 Décodage d’un code systématique
Définition (code systématique).
On dit qu’un code est systématique si ’ peut être représentée par une matrice de la forme :

Ik
G = où K est une matrice de taille (n k;k)
K
G est appelée matrice génératrice du code.
Définition (matrice de contrôle).

Ik K IPour toute matrice génératrice G = on définit une matrice H = .n kK
H est appelée matrice de contrôle du code.
Propriété.
m2C()Hm = 0
Méthode de correction :
On reçoit un message m.
On calcule s =Hm.
parmi les antécédents de s par H, on choisit celui de poids minimal : e.
On renvoie le message m+e.
Théorème.
d
lorsque le nombre d’erreurs est strictement inférieur à , la méthode précédente corrige effectivement le
2
message reçu.
Alaeddine BEN RHOUMA 2 Codes correcteurs
6Agrégation interne de Mathématiques Académie de Guyane
Exercice 3 : Soit le code défini par la matrice :
0 1
1 0 0 0
B C0 1 0 0B C
B C0 0 1 0B C
B C0 0 0 1G =B C
B C1 1 1 0B C
@ A1 1 0 1
1 0 1 1
On suppose qu’on a reçu le message (1;0;0;0;1;0;0). Proposer une correction de ce message et retrouver le message
transmis.
5 Cas général
En s’inspirant de ce qui précède, on cherche une matrice H de taille (n k;n) telle que HG = 0.
Cela revient à résoudre un système de k équations à n inconnues. Ces équations sont linéairement indépendantes car
nle rang deg estk. on obtient ainsi une famille libre den k vecteurs deF :X ;:::;X . L’espace vectoriel engendré1 n k2
par X ;:::;X est en fait l’orthogonal deC.1 n k
On pose alors : 0 1
X1
B C.H = .@ A.
Xn k
On note l’application linéaire associée à cette matrice.
Théorème.
(x) = 0()m2C
Exercice 4 : Trouver une matrice syndrome pour le code de l’exemple 3.
6 Code de Hamming
Pour s 2, on dit qu’un code est de Hamming si :
s n = 2 1
k =n s
k Une de ses matrices syndromes est formée par les s coordonnées des n vecteurs colonnes non nuls deF .2
Exercice 5 : Parmi les codes précédents, trouver les codes de Hamming.
Théorème.
La distance minimale d’un code de Hamming est de 3
Alaeddine BEN RHOUMA 3 Codes correcteurs