Codes correcteurs#
Quelques Références:
Textes d’agrégation:
Introduction#
Objectif du codage#
Un expéditeur Alice transmet un message
Problématique
Comment Bob peut-il détecter l’existence d’erreurs de transmission
Comment Bob peut-il corriger des erreurs éventuelles
Note
Contrairement à la cryptographie, la problématique n’est pas de se protéger d’un tiers malicieux, mais d’un bruit aléatoire.
Exemples d’applications#
NASA/CNES/…: communication avec des sondes et satellites
CD / DVD
Transfert de données par Internet (TCP, CRC, MD5 checksum)
Téléphones portables
Quelles sont les contraintes spécifiques à chacune de ces applications?
Premiers exemples de codes#
Langages humains!#
Syntaxe: orthographe, grammaire, lexique
Anglais:
Exemple: pomme, abrucot, poime (pomme, poire, prime, poème)
Sémantique: sens, contexte, …
Exemple: codage de parité sur 7 bits#
Alice veut envoyer le message
Elle le code en un mot à 8 bit avec un nombre pair de 1,
en rajoutant un bit de parité:
Le code est transmis
Bob reçoit
Si non, comme pour
, détecte qu’il y a eu erreurSi oui comme pour
, suppose que
Premiers concepts#
Définitions
Un code
est un alphabet, comme .
Typiquement (codes binaires). est un entier, la dimension du code
Codage: on transforme le message envoyé
Transmission: en passant à travers le canal,
Détection d’erreur: on essaye de déterminer si
Correction d’erreur: on essaye de retrouver
Décodage: on retrouve le message
Décodage par distance de Hamming#
Définition
Distance de Hamming entre deux mots: nombre de lettres qui diffèrent (en comparant lettre à lettre).
Stratégie:
Détection d’erreur: est-ce que
est dans le code ?Correction d’erreur par distance minimale: on renvoie le mot de
le plus proche de .
Exercice: Est-ce raisonnable?
On suppose que lors de la transmission chaque lettre a une probabilité
Calculer la probabilité qu’un mot de longueur
Application numérique:
n = 7; p = 0.1
(1-p)^n
(1-p)^n + n*p*(1-p)^(n-1)
(1-p)^n + n*p*(1-p)^(n-1) + binomial(n,2) * p^2*(1-p)^(n-2)
n = 7; p = 0.01
(1-p)^(n-1)
(1-p)^n + n*p*(1-p)^(n-1)
(1-p)^n + n*p*(1-p)^(n-1) + binomial(n,2) * p^2*(1-p)^(n-2)
Définitions
Capacité de détection:
nombre maximal d’erreurs que l’on est sûr de détecterCapacité de correction:
nombre maximal d’erreurs que l’on est sûr de corrigerDistance
du code: distance minimale entre deux points distincts du code
Formalisation#
Pour formaliser cela, il est pratique d’introduire la notion
de boule naturellement associée à une métrique: étant donné
Alors:
Cas dégénérés#
Lorsque
Exercice: en petite dimension
On fixe
Trouver tous les codes de
pour , , .Pour chacun d’entre eux, donner la distance
, la capacité de détection , la capacité de correction . Dessiner les boules de centres dans et de rayon .Permettent-t’ils de corriger une erreur?
Donner un code de
permettant de corriger une erreur.Peut-on faire mieux?
Proposition
Capacité de détection:
Capacité de correction:
Borne de Hamming, codes parfaits#
Problème: Kepler discret
On se fixe un alphabet
De manière équivalente: combien de boules non intersectantes de rayon
Exemples: visualisation des boules de rayon
Chargement de quelques fonctions, et configuration des plots 3D:
%run "codes_correcteurs.py"
from sage.plot.plot3d.base import SHOW_DEFAULTS
SHOW_DEFAULTS['frame'] = False
SHOW_DEFAULTS['aspect_ratio'] = [1,1,1]
SHOW_DEFAULTS['viewer'] = 'threejs'
Les boules dans
@interact
def _(r=slider(0,3,1), q=slider(2,7,1)):
A = IntegerModRing(q)
M = A^3
return dessin_boules([M.zero()], r)
Le code binaire de triple répétition:
A = GF(2)
M = A^3
C = M.subspace([[1,1,1]])
C.list()
dessin_boules(C,1)
et sur
A = GF(3)
M = A^3
M.list()[:9]
C = M.subspace([[1,1,1]])
C.list()
dessin_boules(C,1)
Le code de Hamming:
A = GF(2)
M = A^7
C = codes.HammingCode(A, 3)
C.cardinality()
dessin_boules(C, 1, projection=projection_7_3)
Exercice: Borne de Hamming sur
Soit
Taille de la boule
de de centre et de rayon ? Indication: commencer par et .Taille de
?Conclusion?
Solution
Application numérique:
@interact
def _(q=slider(1,7,default=2), n=slider(0,10, default=3), e=slider(0,10,default=1)):
m = q^n
b = sum(binomial(n,k)*(q-1)^k for k in range(0, e+1))
print(f"|M|={m}, |B(x,e(C))|={b}, |C|≤ {1.0*m/b:.2}")
Définition: code parfait
Un code
Exemples
Dans tous les exemples vus jusqu’ici, les seuls codes parfaits sont les codes triviaux, le code de triple répétition sur un alphabet à deux lettres et le code de Hamming.
Problème
Algorithmes de codage? de décodage?
Codes linéaires#
Principe: on rajoute de la structure pour rendre les algorithmes plus efficaces.
Définition
Un code linéaire est un sous-espace vectoriel de
Commençons par un petit échauffement.
Exercice: algèbre linéaire sur
Soit
A = GF(2); A
H = matrix(A, [[0,1,1,1, 1,0,0],
[1,0,1,1, 0,1,0],
[1,1,0,1, 0,0,1]]); H
Appliquez le pivot de gauss à
.Est-ce que les vecteurs
et sont dans le sous-espace vectoriel engendré par les lignes de ?Conclusion?
Solution:
H[1], H[0] = H[0], H[1]
H
H[2] = H[2] + H[0]
H
H[2] = H[2] + H[1]
H
H[0] = H[0] + H[2]
H[1] = H[1] + H[2]
H
u = vector(A, (1,1,0,0,1,1,0))
v = vector(A, (1,0,1,1,1,0,1))
Question: est-ce que
On cherche
u
u = u - H[0]
u
u = u - H[1]
u
Donc
v
v = v - H[0]
v
v = v - H[2]
v
Donc
Exemples#
Exemple: bit de parité
Sept bits plus un huitième bit dit de parité tel que le nombre total
de bit à
v: mon mot
Exemple: code de Hamming
Quatre bits
Algorithmes#
Exercice:#
Combien y-a-t’il de mots dans le code de Hamming
?Calculer la distance de ce code (indice: se ramener en zéro!)
Quelle est sa capacité de détection? de correction? Est-il parfait?
Solution:
C.cardinality()
def poids(c): return len([i for i in c if i])
poids(M([0,1,0,0,0,0,0]))
poids(M([1,0,1,1,0,1,0]))
min(poids(m) for m in C if m)
Comment coder un message en un mot du code?#
Matrice génératrice:
G = C.matrix(); G
M = A^4
m = M([1,0,1,0])
c = m * G; c
Comment décoder un mot du code en un message?#
Du fait de la forme de la matrice génératrice:
G
le mot du code c
est simplement obtenu en ajoutant des bits
supplémentaires à la fin du mot original. C’est une propriété
souhaitable des codes correcteurs car elle permet de bien séparer
information originale et information redondante. En particulier,
décoder est trivial: il suffit de récupérer les quatre premiers bits.
Exemples: la clé de contrôle de votre numéro de sécurité sociale.
Correction d’erreur par syndrome#
Exercice
Partir du mot zéro, le coder, et faire alternativement une erreur sur chacun des bits. Noter le résultat après multiplication par la matrice de contrôle.
Prendre un mot à 4 bits de votre choix, le coder, faire une erreur sur un des 7 bits, corriger et décoder. Vérifier le résultat.
Que se passe-t’il s’il y a deux erreurs?
Soit
Après transmission, on obtient
Alors:
On voit
Cela nous donne la stratégie du décodage par syndrome suivante:
Précalculer tous les syndromes
pour toutes les «maladies» dans la capacité de correction, et en faire une table.Pour corriger
, on calcule son syndrôme . S’il est nul, est déjà dans le code: . Sinon on retrouve dans la table tel que , et on corrige par .
Codes cycliques#
Principe: encore plus de structure pour être encore plus efficace.
Définition
Un code
Les praticiens ont noté que les codes cycliques avaient de bonnes propriétés.
Donnons une structure d’anneau quotient à
Sous cette identification, les mots ci-dessus correspondent à
Remarque
Dans
Par exemple, pour
Codes cycliques
Soit
Code: idéal engendré par
Codage:
Détection d’erreur:
Décodage: division par
modulo (par ex. par Euclide étendu)
Codes BCH
On peut construire des codes cycliques de capacité de correction déterminée à l’avance. Pour en savoir plus, voir Wikipedia, Codes BCH.
Codage par interpolation (Reed-Solomon)#
Exercice (secret partagé)
Un vieux pirate est sur son lit de mort. Dans sa jeunesse il a enfoui un Fabuleux Trésor dans la lagune de l’Ile de la Tortue, quelque part à l’est du Grand Cocotier. Il a réuni ses dix lieutenants préférés pour leur transmettre l’information secrète indispensable: la distance entre le Grand Cocotier et le Trésor. Connaissant bien ses lieutenants, et dans un étonnant dernier sursaut de justice, il ne voudrait pas qu’une conjuration de quelques uns d’entre eux assassine les autres pour empocher seuls le trésor. En tenant cependant compte de la mortalité habituelle du milieu, il souhaite donner une information secrète à chacun de ses lieutenants pour que huit quelconques d’entre eux puissent retrouver ensemble le trésor, mais pas moins. Comment peut-il s’y prendre?
Application aux CD/DVD: Codage CIRC
Paramètres du système de codage:
un corps fini
.trois entiers
, , et avec points d’évaluation dansun procédé D de codage sur
avec bonne capacité de détection
Codage d’un message dans
Découpage du message en
blocs, chaque bloc étant interprété comme un polynôme de degré dans :Premier étage: évaluation et entrelacement.
On construit la séquence suivant avec
blocs de longueur :Codage de chacun des
blocs de longueur avec P
Décodage:
On utilise D pour détecter les blocs corrompus. On les jette.
S’il en reste au moins
: on déterminer chaque à partir de ses valeurs sur points d’évaluation.
Comment tester si un mot appartient au code?#
Avec Sage:
Matrice de contrôle:
Test d’appartenance au code:
Refaites le à la main!
Le code lui-même est le noyau de :
Refaites le à la main!
Est-ce que l’on pourrait trouver encore plus rapidement?
Oui: