Théorie de l'information et codage
Master de cryptographie
Cours 4 : Codes linéaires
19 et 22 janvier 2009
Université Rennes 1
Master Crypto (2008-2009) Théorie de l'information et codage 19 et 22 janvier 2009 1 / 11
Dé nition
On note F2 = {0, 1} le corps à 2 éléments.
Un code (n, k , d )-code linéaire C est un sous espace vectoriel de F2 de n
dimension k et de distance minimale d .
Propriété
La distance minimale d'un code linéaire est égal à son poids minimal
Matrice génératrice
C'est une matrice k × n G dont les lignes forment une base de C.
L'application linéaire associée de F2 dans F2 dé nit le codage
k n
C = {aG , a ∈ F2 }. k
G est dite sous forme normale si elle est de la forme (Id , P ). Les k
k
premiers bits d'un mot de C sont alors les bits d'information et les n − k
suivant les bits de redondance.
Master Crypto (2008-2009) Théorie de l'information et codage 19 et 22 janvier 2009 2 / 11
Codes équivalents
Dé nition
C et C 0 sont équivalents si C 0 peut être obtenu à partir de C en appliquant
une permutation sur les symboles.
Théorème
En appliquant les opérations
permutation des lignes ou des colonnes
addition de deux lignes
sur une matrice génératrice d'un code C , on obtient une matrice
génératrice d'un code équivalent à C .
Conséquence : on suppose qu'un code est toujours donné par une matrice
sous forme normale.
Master Crypto (2008-2009) Théorie de l'information et codage 19 et 22 janvier 2009 3 / 11
Codage/Décodage
Codage
Si on veut coder x ∈ F2 , on calcule xG
k
= [x , xP ]
Matrice de Contrôle
C'est la matrice H = [ P, I t
n −k ]. On a alors
x = [x1 , · · · , x n ]∈C ⇔H t
x =0
Décodage de y ∈ F2 n
On calcule H y , le syndrome d'erreur.
t
Le vecteur d'erreur e = y − x est l'unique élément de F2 de poids n
minimal tel que H e = H y . t t
On construit la table des syndromes de taille 2 − composée des e de n k
i
poids minimum tel que les H e forment l'image de H (i.e. F2− ).
t
i
n k
Il su t de chercher à quel e correspond H y et de renvoyer y − e
i
t
i
Master Crypto (2008-2009) Théorie de l'information et codage 19 et 22 janvier 2009 4 / 11
Codes duaux
Dé nition
Si hx , y i = n
x y , le code dual C ⊥ de C est donné par
P
i =1 i i
C ⊥ = {y ∈ F2 /∀x ∈ C , hx , y i = 0}
n
Propriété
Si C est un (n, k )-code linéaire de matrice de contrôle H , alors C ⊥ est un
(n, n − k )-code linéaire engendré par H .
Un code est dit auto-dual si il est équivalent à son dual.
Master Crypto (2008-2009) Théorie de l'information et codage 19 et 22 janvier 2009 5 / 11
Quelques propriétés des codes linéaires
Borne de Singleton
Si C est un (n, k , d )-code linéaire, alors
d ≤n−k +1
Théorème
Soit C un (n, k )-code linéaire de matrice de contrôle H .
Si D désigne le nombre maximal de colonnes de H linéairement
indépendantes, alors la distance minimale de C vaut D + 1.
Master Crypto (2008-2009) Théorie de l'information et codage 19 et 22 janvier 2009 6 / 11
Codes de Hamming
Donnés par leur matrice de contrôle.
la i -ème colonne de H se trouve le vecteur (ε1 , · · · , ε ) où
Sur P r
i = =−01 ε − 2 .
r
i r i
i
Théorème
C'est un (2 − 1, 2 − r − 1)-code linéaire.
r r
Il corrige une erreur (d = 3).
C'est un code parfait.
Décodage de y ∈ F2 n
On calcule z = H y . t
z est l'écriture binaire de i (la i -ème colonne vaut alors H y ).
t
On retourne y après avoir changé son i -ème bit.
Master Crypto (2008-2009) Théorie de l'information et codage 19 et 22 janvier 2009 7 / 11
Codes de Reed-Muller
Très utiles sur des canaux très brouillés (satellites)
Dé nition inductive
On note RM (r , m) le code de Reed-Muller d'ordre r ≤ m et de longueur
2 dé nit par
m
RM (0, m) = {00 · · · 00, 11 · · · 11}
RM (m, m) = {0, 1}2m
RM (r , m) = {(x , x + y )/x ∈ RM (r , m − 1), y ∈ RM (r − 1, m − 1)}
Matrices génératrices
G (r , m − 1)
G (r , m − 1 )
G (r , m ) = 0 G (r − 1, m − 1)
G (m − 1, m)
avec G (0, m) = (11 · · · 11) et G (m, m) =
00 · · · 01
Master Crypto (2008-2009) Théorie de l'information et codage 19 et 22 janvier 2009 8 / 11
Propriétés des codes de Reed-Muller
Théorème
RM (r , m) a les caractéristiques suivantes
1 longueur n = 2 . m
2 distance minimale d = 2 − . m r
dimension k = =0 C . r
P i
3
i m
4 contenu dans RM (r + 1, m) pour r < m.
5 dual RM (m − 1 − r , m) si r < m.
Décodage de R (1, m)
Pour un mot recu, trouver le mot de RM (1, m) le plus proche.
Par recherche exhaustive.
Transformée de Hadamard.
Master Crypto (2008-2009) Théorie de l'information et codage 19 et 22 janvier 2009 9 / 11
Code de Golay étendu
Soit B la matrice symétrique 12x12
110111000101
101110001011
011100010111
111000101101
110001011011
100010110111
000101101111
001011011101
010110111001
101101110001
011011100011
111111111110
On note C24 le code de matrice génératrice G = (Id12 , B ).
Master Crypto (2008-2009) Théorie de l'information et codage 19 et 22 janvier 2009 10 / 11
Propriétés de C24
1 C24 est un (24, 12)-code linéaire.
2 H1 = (Id12 B ) et H2 = (B Id12 ) sont des matrices de contrôle de C24 .
3 (B , Id12 ) est aussi une matrice génératrice de C24 .
4 C24 est auto-dual.
5 Sa distance minimale est 8 et il corrige 3 erreurs.
6 C24 est parfait et unique.
Décodage de y
1 Calculer le syndrome s1 = H1 y t
si w (s1 ) ≤ 3 alors e = ( s1 , 0)
t
si w (s1 + B ) ≤ 2 alors e = ( s1 + B , ε )
i
t t
i i
2 Calculer le syndrome s2 = H2 y = Bs1
t
si w (s2 ) ≤ 3 alors e = (0, s2 )
t
si w (s2 + B ) ≤ 2 alors e = (ε , s2 + B )
i i
t t
i
où B est la i -ème colonne de B et ε
i i = (0..010..0).
Master Crypto (2008-2009) Théorie de l'information et codage 19 et 22 janvier 2009 11 / 11
