Concepts fondamentaux
Correction et d´tection e Codes lin´aires e Codes d´tecteurs correcteurs e Arnaud Labourel
Courriel : arnaud.labourel@lif.univ-mrs.fr
Universit´ de Provence e 15 novembre 2011
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs
Coder et transmettre
Codage de l’information
Information cod´e par des 0 et des 1 e Codage transmis sous la forme de courants, ondes, etc.
Erreurs de transmission
Remplacements de 0 par 1 (et inversement)
Un bit par microseconde : accumulation d’erreurs de transmission taux d’erreur de 10−6 et connexion ` 1Mo/s, en moyenne 8 a bits erron´s transmis chaque seconde ! e Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs
Exemples
Exemples concrets
Internet Protocole TCP : erreur d´tect´e, correction par e e retransmission Le CD Rayures ou impuret´s du support (peu fr´quentes e e mais tr`s volumineuses) : correction ` la vol´e e a e Le port s´rie Correction de petites erreurs relativement fr´quentes e e mais isol´es : correction imm´diate e e
Contraintes diverses
Faible coˆt d’implantation u Pas d’alt´ration de la vitesse de transmission e Fiabilit´ ! e Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs
Quelles solutions ?
Agir sur le canal de transmission
Rendre le taux d’erreur n´gligeable e Impossibilit´ de remplacer toutes les infra-structures e existantes !
Taux nul impossible
Agir sur le message transmis
Etre capable de d´tecter si des erreurs ont eu lieu e Etre capable de les corriger au mieux
Principe des codes correcteurs d’erreurs
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs
D´tecter et corriger les erreurs e D´tecter une erreur : et apr`s ? e e
Recommencer la transmission ?
Pas toujours possible
Manque de temps
Nouvelles erreurs possibles
Corriger l’erreur
Th´orie des codes e Comment coder les messages pour favoriser d´tection et correction e des erreurs de transmission
001110101011000111110000111111011011000111110010110001111100
000111000111101000111000111111111111000111000001111111000000
(01011010111101001100)
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs
Principe de la redondance
Pour me transmettre un num´ro de t´l´phone, parmi les solutions e ee possibles :
Message transmis
0654122235
zero six cinquante-quatre douze deux deux trente-cinq Message re¸u c 0654172236 zer0 slx cinquamte-quatte doyze deux deyx trsnte-c1nq Information concise : difficile ` corriger a Information redondante : d´tection et correction d’erreur e possible avec contexte !
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs
Exemples de redondances
Le plus souvent, r´p´tition du message ! e e
Au t´l´phone : ee R´p´tition des num´ros e e e Epeler le mot (A comme Abracadabra, R comme Ribambelle, etc.) Alphabet radio universel (Alpha Bravo Charlie Delta etc.)
Orthographe traditionnelle moins sensible aux erreurs que langage type SMS
Code g´n´tique e e
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs
Utilit´ du codage e D´tection et correction d’erreurs : redondance e Compression (abr´viations, code de Huffman, codec, e archivage, etc.)
Changement d’alphabets (code Morse, ASCII, etc.)
Cryptographie (rendre le d´codage difficile) e Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs
Sch´ma g´n´ral de la communication e e e
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs
Formalisation du codage
Cas g´n´ral e e
Soient les alphabets An et B m .
Un codage est une application injective φ : An → B m
N´cessit´ de l’injection : d´codage e e e Soit M = φ(M).
D´codage : ` partir de M , retrouver M tel que φ(M) = M e a
Si ce M existe, il doit ˆtre unique ! e Cas du codage binaire
A = B = B, et m > n.
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs
Addition modulo 2
Codage des messages = codage binaire
Un message de n bits = un mot binaire de longueur n
Op´rations classique de Bn e Un nouvel op´rateur dans B (XOR) e 0⊕0=0
0⊕1=1
1⊕0=1
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
1⊕1=0
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs
Addition modulo 2 (cont’d)
Propri´t´s
ee a⊕b =b⊕a
(1)
a ⊕ (b ⊕ c) = (a ⊕ b) ⊕ c
(2)
a⊕0=a
(3)
a⊕a=0
(4)
a ⊕ b = c ⇐⇒ a ⊕ c = b ⇐⇒ b ⊕ c = a
(5)
De plus :
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs
Addition modulo 2 (cont’d)
Extension ` Bn a Si a = a1 a2 . . . an et b = b1 b2 . . . bn sont deux mots binaires, leur e somme modulo 2 est le mot binaire ayant pour p`me bit ap ⊕ bp . a b a⊕b 01001110
11011100
10010010
(on v´rifie dans Bn les propri´t´s 1 ` 5 en rempla¸ant 0 par le mot e ee a c binaire de taille n dont tous les bits sont nuls)
Poids w (a) d’un mot binaire a
Nombre de bits dans a ´gaux ` 1 : w (01100100001100001) = 6 e a
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs
a ⊕ b indique une distance
Interpr´tation de a ⊕ b e a et b mots binaires de longueur n e p`me bit de a ⊕ b : 0 si ap = bp et 1 si ap = bp a ⊕ b indique les endroits o` a et b diff`rent u e w (a ⊕ b) indique le nombre de diff´rences e D´finition (Distance de Hamming) e La distance de Hamming entre deux mots binaires a et b de taille n est le poids de a ⊕ b. d(a, b) = w (a ⊕ b)
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs
Propri´t´s de la distance de Hamming ee Exemple d(111001111000, 101000111001) = 3
d(a, b) = d(b, a)
(sym´trie) e (6)
d(a, b) ≥ 0
(positivit´) e (7)
d(a, b) = 0
si et seulement si a = b
(8)
d(a, b) + d(b, c) ≥ d(a, c)
(in´galit´ triangulaire) e e
(9)
d(a ⊕ x, b ⊕ x) = d(a, b)
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
(invariance par translation) (10)
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs
Interpr´tation g´om´trique e e e
Alg`bre de Boole sur les mots binaires ! e El´ments de Bn dispos´s dans un n-cube : e e
Th´or`me e e
La distance d(a, b) est le nombre d’arˆtes qu’il faut longer pour se e rendre de a ` b par le chemin le plus court possible. a Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs
Vecteur d’erreur
Message envoy´ et message re¸u e c
Exp´diteur : message T de longueur n e Destinataire : message R de longueur p = n
Tout va bien si R = T , erreur de transmission si R = T
D´finition (Vecteur d’erreurs) e Le vecteur d’erreur entre un message transmis T et un message re¸u R est le vecteur e = T ⊕ R c w (e) = d(T , R) est le nombre de bits mal transmis.
T = e ⊕ R et R = T ⊕ e
Exemple : e = 1011 ⊕ 1101 = 0110
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs
Code et mots de code
D´tecter une erreur de transmission ? e Si destinataire connaissait e, il pourrait retrouver T !
Mais e reste inconnu !
Accord entre exp´diteur et destinataire sur certaines e particularit´s de messages e D´finition du code C : ses ´l´ments sont des mots de code e ee
Le code favorise la d´tection d’erreurs, dans le cas o` R ∈ C e u
Erreurs non reconnues si R ∈ C pourtant erron´ e Exemple : triplement de chaque bit
T = 000111111111, R = 000111111000 ∈ C
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs
Corriger une erreur de transmission ?
Ensemble des vecteurs d’erreur possibles pour R
Le destinataire connaˆ C et R ! ıt Il peut d´terminer Γ(R) = {C ⊕ R|C ∈ C} : e ∈ Γ(R) e Exemple : R = 000110, C = {m.b}. o` chaque bit est tripl´ u e
C = {000000, 000111, 111000, 111111}, Γ(R) = {000110, 000001, 111110, 111001}
Une approche probabiliste pour corriger
Le destinataire souhaite corriger R si une erreur est suspect´e e Il sait que e ∈ Γ(R), mais ne peut le connaˆ avec certitude ıtre Paris de corrections avec ´valuation des risques e Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs
Estimation des risques ?
Canal binaire
Dispositif pour la transmission de bits
Risque d’erreur d’un canal binaire estim´ par e p=
nombre de bits faux nombre de bits transmis
Exp´dition d’un bit = ph´nom`ne al´atoire ` deux issues e e e e a 1. Le bit est bien transmis
2. Le bit est mal transmis
Probabilit´ d’erreur du canal = p e q =1−p p tr`s petit (sauf si canal tr`s mauvais !) e e
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs
Quelques hypoth`ses sur le canal e Canal sym´trique e p identique, que l’on transmette des 0 ou des 1
Pas toujours valable (pr´sence ou absence de trous sur un e CD...)
Canal sans m´moire e Les erreurs ne se groupent pas et mˆme r´partition des erreurs e e
Transmission de chaque bit ind´pendante des autres e Pas toujours valable non plus !
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs
Transmission d’un message : un ph´nom`ne al´atoire e e e Exp´dition d’un mot binaire de longueur n = r´p´tition n fois e e e de l’exp´dition d’un bit : bien ou mal transmis e Issues du ph´nom`ne al´atoire E = vecteurs d’erreur e e e Nombre d’erreurs E suit une loi binomiale B(n, p)
Rappels
Soit Φ un ph. al´a. ne comprenant que deux issues, X et Y , muni e d’une loi p. Soit x = p(X ) et y = p(Y ), avec y = 1 − x.
Si n essais r´p´t´s sont ind´pendants, alors : e ee e p(M) = x k y n−k si M est un mot particulier (cible connue) contenant k issues X et n − k issues Y k p(M) = Cn x k y n−k si M est un mot quelconque contenant k issues X et n − k issues Y .
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs
En pratique...
Soit un canal sur lequel le taux d’erreurs p = 10−2 (et q = 0.99).
Envoi de messages de 64 bits sur ce canal
Probabilit´ d’avoir : e aucune erreur de transmission :
P(E = 0) = (1 − p)n = q n = 0.9964 ∼ 0, 526 une seule erreur : P(E = 1) = np(1 − p)n−1 ∼ 0, 340 deux erreurs : P(E = 2) = trois erreurs : P(E = 3) =
n(n−1) 2 p (1 − p)n−2 ∼ 0, 108
2
3
Cn p 3 (1 − p)n−3 ∼ 0, 023
plus de 4 erreurs : P(E > 4) < 0, 0005
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs
R´sultat fondamental e Th´or`me e e
Lorsque l’on transmet des mots binaires de longueur n sur un canal binaire sym´trique et sans m´moire, dont la prob. d’erreur est p : e e
1. Si l’on se donne e, la probabilit´ que le vecteur d’erreur soit e e est p w (e) q n−w (e)
2. Si l’on se donne k, la probabilit´ que le nombre d’erreurs de e k transmission soit k est : Cn p k q n−k
3. Si l’on transmet T , la probabilit´ de recevoir R est e p d(T ,R) q n−d(T ,R)
Exemple
On transmet T = 0110, soit p = 0.001 : visualisons p(R) et le nombre d’erreurs d
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs
Probabilit´s de R, T = 0110, p = 0.001 e R
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
valeur (p = 0.001)
0.0000009 . . .
0.0000000009 . . .
0.0009 . . .
0.0000009 . . .
0.0009 . . .
0.0000009 . . .
0.9 . . .
0.0009 . . .
0.0000000009 . . .
0.000000000001 . . .
0.0000009 . . .
0.0000000009 . . .
0.0000009 . . .
0.0000000009 . . .
0.0009 . . .
0.0000009 . . .
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs
Comment d´tecter et corriger ? e Interpr´tation e p q : probabilit´ de substitution de M1 par M2 diminue e tr`s vite quand d(M1 , M2 ) augmente e Plus le poids de e augmente, moins il est probable
Id´e : e est l’´l´ment de Γ(R) de plus faible poids e ee
Remplacer le mot re¸u par le mot vraisemblable le plus proche c Strat´gie : un pari e 1. e est le mot de plus petit poids dans Γ(R)
2. Remplacement de R par T = e ⊕ R (e = 0 si T = R)
Correction la plus vraisemblable, mais pas toujours valable
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs
Exemple : mots 0xx · · · x0
Soit C = {0000, 0010, 0100, 0110}
R´ception de R = 0111, R ∈ C e Calcul de Γ(R) :
Γ(R) = {0000 ⊕ 0111, 0010 ⊕ 0111, 0100 ⊕ 0111, 0110 ⊕ 0111}
Γ(R) = {0111, 0101, 0011, 0001} e 0111
0101
0011
0001
w (e)
3
2
2
1
P(e) p3 q p2 q2 p2 q2 pq 3
T
0000
0010
0100
0110
Choix de e de plus petit poids
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs
Codage par blocs : tr`s r´pandu e e
L’exp´diteur : e 1. D´couper le message binaire en blocs (paquets de bits) de e longueur fixe
2. Coder chaque bloc avec ajout de bits de contrˆle : mots de o code
3. Envoi des mots de code
Le receveur
1. R´ception des mots de code et d´tection d’erreur (le mot e e est-il un mot de code ?)
2. Correction ´ventuelle du mot re¸u en le rempla¸ant par le mot e c c de code le plus proche
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
Codes e
3. Extraction des blocs : d´codage d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs
Constitution du mot de code
Codage des blocs
Bloc de dimension k = un mot binaire de longueur k
Ajout de r bits de contrˆle (ou bits de parit´) o e
Obtention de mots binaires de longueur n = k + r
Mots de code de taille n ⊆ mots binaires de taille n
Codage syst´matique e Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs
Codage = application
Quelle application ?
Ensemble des blocs = Bk , ensemble des messages = Bn
2k mots de codes et 2n messages
Codage = φ : Bk → Bn associe un mot de code ` un bloc a Rendement (taux) d’un code
Proportion du bits d’information parmi les transmis τ =
k n Le plus ´lev´ possible e e
M´taphore du colis : r´sistance (poids) et prix de l’emballage e e
Compromis s´curit´ vs. coˆt de l’envoi e e u proportion de mots de code = 2k /2n = 2k /2k+r = 1/2r
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs
Test de parit´ e Principe
Un bit de contrˆle pour garantir la parit´ du nombre de 1 (r = 1) o e
Dans le cas k = 3 : n = 4 et τ = 3/4
Exemple :Φ(001) = 0011, Φ(110) = 1100
Mots de codes
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs
Test de parit´ (cont’d) e Exemples de (non-)d´tection e R´ception de R = 1011 : une ou trois erreurs commises e R´ception de R = 1111 : aucune, 2 ou 4 erreurs commises e Semble correct : on laisse passer !
Correction impossible
Si erreur d´tect´e, le bit de contrˆle ne fournit aucune information e e o sur l’endroit de l’erreur
C = {0000, 0011, 0101, 0110, 1001, 1010, 1100, 1111}
R = 1011 ∈ C une ou trois erreurs ?
4 vecteurs d’erreur de poids 1 = {1000, 0010, 0001, 0100}
T les plus vraisemblables : T ∈ {0011, 1001, 1010, 1111}
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs
Test de parit´ (cont’d) e Risque pris lors de l’acceptation d’un mot de code p(R = T ) = q 4 , p(R = T ) = 1 − q 4 = 1 − (1 − p)4 = 4p − 6p 2 + 4p 3 − p 4
Cas d’erreur de jugement : si 2 ou 4 erreurs p(deux erreurs) = 6p 2 q 2 , p(quatre erreurs) = p 4 donc p(laisser passer un message faux) = 6p 2 q 2 + p 4
Proportion de messages faux non d´tect´s (FP) : e e
6p 2
6p 2 − 12p 3 + 7p 4
∼
∼ 1.5p si p petit
4p − 6p 2 + 4p 3 − p 4
4p
Si p = 0.001 : 0, 15% de FP (vs. 100% sans codage !)
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs
Codage par r´p´tition e e
Principe
Bits d’informations transmis un ` un, mais en les triplant. a Φ(1) = 111, Φ(0) = 000, Φ(01) = 000111
Avec k = 1, r = 2, n = 3, pauvre rendement τ = 1/3
Taux de d´tection (cas de deux mots de codes) e Si T = 000 et R = 111, l’erreur n’est pas d´tect´e ! e e p3 p(faux non d´tect´s) = 3p−3p2 +p3 ∼ p 2 /3 e e quand p est petit.
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs
Codage par r´p´tition (cont’d) e e
Capacit´ de correction e 3 bits faux ils sont accept´s, pas de correction e 2 bits faux majoritaires, donc le troisi`me est corrig´ e e
1 bit faux minoritaire, il est corrig´ e pas de bit faux pas de correction. p(mauvaise correction) = p 3 + 3p 2 q = 3p 2 − 2p 3
Proportion de messages faux qui le restent apr`s correction e 3p 2 − 2p 3
∼p
3p − 3p 2 + p 3
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e Mesures de codages et r´sultats e Vers un bon codage
R´capitulatif e Pari que l’erreur commise est l’erreur la plus probable
M´thode pratique pour corriger un message e 1. D´terminer Γ(R) (vecteurs d’erreurs pour R) e 2. D´terminer le message de plus faible poids dans Γ(R) e 3. Ajout modulo 2 (⊕) de ce message ` R : obtention du mot de a code le plus vraisemblable qui remplacera R
Sur un n-cube
Rep´rer le message M ∈ C le plus proche de R e Quid en cas d’ex-aequo ?
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e Mesures de codages et r´sultats e Vers un bon codage
Visualisation des corrections concurrentes
R´p´tition e e
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
Parit´ e Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e Mesures de codages et r´sultats e Vers un bon codage
Distance minimale
D´finition (Distance minimale) e La plus petite distance s´parant deux mots de code distincts est e appel´e la distance minimale du code, not´e d. e e
Exemples
Test de parit´ : d = 2 e Codage par r´p´tition : d = 3 e e
Th´or`me e e
Le receveur d´tecte de fa¸on certaine TOUS les messages faux, e c tant que le nombre d’erreurs N v´rifie 0 < N < d. e Certains messages faux comportant d erreurs (ou plus) ne sont pas d´tect´s. e e Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e Mesures de codages et r´sultats e Vers un bon codage
Distance minimale (cont’d)
Th´or`me
e e
Les messages sont bien corrig´s tant que le nombre d’erreurs N e v´rifie 0 ≤ N < d/2 (strict). e Les messages faux tels que d/2 ≤ N ne sont pas toujours bien corrig´s. e
Exemple
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e Mesures de codages et r´sultats e Vers un bon codage
Nombre d’erreurs corrig´es e t = d/2 = d 1
2
3
4
5
6
t
0
0
1
1
2
2
d
1 − (−1)d
−
2
4
D’apr`s le th´or`me pr´c´dent : e e e e e
Tout message faux ayant t erreurs ou moins est corrig´ de fa¸on parfaite e c
Il existe des messages faux mal corrig´s qui ont t + 1 erreurs e La correction peut parfois ˆtre bonne e mˆme si N > t e Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e Mesures de codages et r´sultats e Vers un bon codage
Triplet de description d’un code [n, k, d]
Exemples
Test de parit´ : code [4, 3, 2] e Codage par r´p´tition : [3, 1, 3] e e
Int´rˆt d’une grande d ee Pour plus de d´tection et de correction d’erreurs e Mots de code ´loign´s e e
Si k est fix´ : nombre de mots de code fix´ e e
Si k fix´ : intercaler le plus possible de messages entre mots e de code : augmenter n, mais alors k/n diminue !
Bon code : d et n grands
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e Mesures de codages et r´sultats e Vers un bon codage
Interpr´tation sur les n-cubes e k et r fix´s. Donc Bn fix´ : tous les messages possibles, mots de e e code ou pas.
A r´soudre e Comment marquer d’un point bleu 2k sommets d’un n-cube de telle sorte que tous les sommets bleus soient le plus ´loign´s e e possible les uns des autres ?
Exemples : k = 1, r = 2, d ∈ {1, 2, 3}
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e Mesures de codages et r´sultats e Vers un bon codage
In´galit´ de Hamming e e
Objectif, n fix´ e Majorer t, donc d
On a toujours d ≤ n, mais grossier !
In´galit´ de Hamming e e
Les quantit´s n, r , et t, sont li´es par l’in´galit´ de Hamming : e e e e
0
1
2
t
Cn + Cn + Cn + · · · + Cn ≤ 2r p Soit message M de taille n, et p ≤ n, il y a exactement Cn messages situ´s ` la distance p de M (modification de e a
p bits parmi n) ; Consid´rons la sph`re S(M, m) des messages situ´s ` une distance plus petite que m de M : e e e a
0
1 m nombre de messages dans S(M, m) = Cn + Cn + · · · + Cn . On cherche h tq l’intersection de S(Ci , h) et
S(Cj , h) soit vide pour tous mots de code Ci et Cj diff´rents : h = t. Il y a 2k sph`res S(C , t) centr´es sur les e e e 0
1
t mots de code. Donc 2k (Cn + Cn + · · · + Cn ) ≤ 2n ).
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e Mesures de codages et r´sultats e Vers un bon codage
Borne de Hamming
Majoration de t
1. Calculer, dans l’ordre :
0
1 u0 = Cn u1 = u0 + Cn r d´passer 2 e 2 u 2 = u 1 + Cn
···
Jusqu’` a 2. Le premier indice m t.q. um > 2r est un majorant strict de t
(convergence assur´e car un = 2n > 2r ) e Borne de Hamming d ≤ 2m
Exemple : r = 1 u0 = 1 ≤ 2, u1 = 1 + n ; or n ≥ 2 puisque n = k + r . Donc u1 ≥ 3 > 2r . Majoration obtenue : 1 > t !
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e Mesures de codages et r´sultats e Vers un bon codage
Code parfait
Egalit´ de Hamming e 0
1
2 t Cn + Cn + Cn + · · · + Cn = 2r ⇐⇒ les 2k sph`res S(C , t) forment e n. une partition de B
D´finition (Code parfait) e Un code est parfait s’il v´rifie l’´galit´ de Hamming. e e e d(M, C ) ≤ t
Exp´dition de C , r´ception de R : e e soit d(C , R) ≤ t : le message est bien corrig´ e soit d(C , R) > t : le message est mal corrig´ e Un code parfait ne corrige jamais plus que t erreurs
Exemple : code par r´p´tition [3,1,3] e e
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs
Codes lin´aires e D´finition (Code lin´aire) e e
Un code C est lin´aire lorsque Ci ⊕ Cj = Ck o` Ci , Cj et Ck sont e u des mots du code.
Cons´quence e Quand un code est lin´aire, 0...0 est toujours un mot de code. e Exemples : test de parit´, code par r´p´tition e e e
Facilit´ pour d´terminer d e e
La distance minimale d est le poids du mot de code non nul de plus petit poids d(C1 , C2 ) ≥ d
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs
Codage lin´aire e D´finition (Codage lin´aire) e e
Soit les blocs ui . Un codage est lin´aire quand l’application φ e v´rifie : e φ(u1 ⊕ u2 ⊕ · · · ⊕ up ) = φ(u1 ) ⊕ φ(u2 ) ⊕ · · · ⊕ φ(up ), ∀p ≥ 1
Remarques somme de blocs = somme de leur mots de code par r´currence : φ(a ⊕ b) = φ(a) ⊕ φ(b) e Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs
Codage lin´aire (cont’d) e D’o` vient l’appellation lin´aire u e
(B,⊕,∧) est un corps
Bn est un espace vectoriel de dimension n sur ce corps
Code lin´aire = sous-espace vectoriel de Bn e Codage lin´aire : application Bk → Bn e Code ou codage lin´aire : th´or`me e e e
1. Codage lin´aire : son code est lin´aire, et 0...0 est le mot de e e code associ´ au bloc nul e 2. Codage syst´matique, de code lin´aire, est lin´aire. e e e Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs
Simplification propre aux codes lin´aires e Codage non-lin´aire : besoin des 2k mots de code pour coder e chaque bloc
Codage lin´aire : k mots de code suffisent (base canonique) e D´finition (Base canonique de code) e b1 =1000 ... 00 b2 =0100 ... 00
= .... ... bk−1 =0000 ... 10 bk =0000 ... 01
(b1 , b2 , · · · , bk ) forme la base canonique de Bk
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs
Base canonique de code lin´aire [7, 4] : code Cycl e φ(1000) = 1000101, φ(0100) = 0100111, φ(b3 ) = 0010110 et φ(b4 ) = 0001011 b1 b2 b4 b
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs
Repr´sentations matricielles e Motivation
D´terminer un mot de code ` partir d’un bloc = produit de e a matrices Matrice g´n´ratrice (codages syst´matiques) e e e Ik : matrice identit´ de taille k e P (r colonnes) : matrice de parit´ (bits de contrˆle) e o
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs
Matrices g´n´ratrices : exemples e e
Test de parit´ e
1 0 0 1
G = 0 1 0 1
0 0 1 1
1
P = 1
1
Codage par r´p´tition e e
G= 1 1 1
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
P= 1 1
Codes d´tecteurs correcteurs e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs
Concepts fondamentaux
Correction et d´tection e Codes lin´aires e Matrices g´n´ratrices : exemples (cont’d) e e
Code Cycl
1
0
G =
0
0
0
1
0
0
0
0
1
0
0
0
0
1
1
1
1
0
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
0
1
1
1
1
1
0
1
1
1
P=
1
0
0
1
1
1
Codes d´tecteurs correcteurs e
1
1
0
1
Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs
Codage lin´aire d´fini par P ! e e
Codage tr`s simple ! e Sp´cifier kr valeurs (bits) au lieu de 2k r dans le cas g ´n´ral e e e des codages syst´matiques e Calcul facile du code d’un bloc
Le mot de code φ(b) est repr´sent´ par la matrice ligne bG e e
(produit de b par matrice G )
Exemple : test de parit´, codage de 101 e
1 0 0 1
1 0 1 0 1 0 1 = 1 0 1 0
0 0 1 1
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs
Correction des codes lin´aires e R´ception de R, calcul de Γ(R), recherche du mot e de plus petit e poids dans Γ(R), et calculer e ⊕ R.
Objectif
Optimiser la rapidit´ de correction : enregistrer les actions e r´p´t´es, et les lire quand on en a besoin (au lieu de les recalculer) e ee
Th´or`me e e
1. La relation d´finie sur Bn par : u v quand u ⊕ v est un e mot de code, est une relation d’´quivalence e 2. Elle poss`de 2r classes d’´quivalence e e
3. Γ(R) est la classe d’´quivalence de R e 4. Le code C est la classe de 0...0
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs
Correction des codes lin´aires : tableau standard e Cons´quence du th´or`me e e e
Les ensembles Γ(R) forment une partition de Bn
Id´e ing´nieuse de stockage des Γ(R) e e
Construction d’une table de correction : le tableau standard
Regrouper les mots de Bn par classe
Rep´rer le mot de plus faible poids dans chaque classe e Structure du tableau standard
2r lignes (contrˆle), 2k colonnes (blocs) o Rangement des ´l´ments, de telle sorte que : ee 1. une ligne contient une classe d’´quivalence e 2. l’´l´ment le plus ` gauche est celui de plus faible poids ee a
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs
Construction du tableau standard
M´thode pratique e 1. Ranger les mots de Bn par poids croissants (si ex-aequo : ordre lexico) : obtention d’une liste B
2. Dessiner un tableau de 2r lignes et 2k colonnes
3. Ranger les mots de code (taille n) dans la premi`re ligne, en e conservant l’ordre qu’ils ont dans B (donc 0..0 ` gauche !) a 4. Tout ` gauche de la premi`re ligne vide , placer le premier a e
´l´ment qui reste dans B. ee 5. Remplir chaque case de en additionnant premier ´l´ment de ee la ligne, et ´l´ment au dessus de la case en premi`re ligne. ee e
6. Quand une ligne est remplie, recommencer la mˆme op´ration e e ligne suivante.
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs
Construction du tableau standard (cont’d)
Structure
Tableau standard du code de parit´ [4, 3, 2] e 0000
0001
0011
0010
0101
0100
0110
0111
1001
1000
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
1010
1011
1100
1101
Codes d´tecteurs correcteurs e 1111
1110
Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs
Construction du tableau standard (cont’d)
Exemple du code par r´p´tition [3, 1, 3] e e
000
001
010
100
111
110
101
011
Propri´t´ ` retenir eea Chaque ligne ´nonce Γ(R) pour tous les messages re¸us R de e c cette ligne
Dans une ligne, les mots sont ordonn´s par ordre croissant de e poids !
Si on re¸oit R pr´sent sur la ligne i colonne j, la correction c e sera vers R ⊕ ei = Cj !
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs
Comment corriger ` partir du tableau standard a M´thode pratique de correction e 1. Chercher la position (i, j) du message re¸u R c 2. Remplacer le message R par le mot de code de la mˆme e colonne, sur la premi`re ligne e Exemple sur code de parit´ [4, 3, 2] e (d faible)
On remplace R = 1000 par M = 1001
On remplace R = 0001 par M = 0000
Pas toujours satisfaisant ! Pourquoi ne pas remplacer 0001 par 1001 ou 0101, ou...
Sur code par r´p´tition : plus juste e e
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs
Tableau standard : peut mieux faire
Observations
Le tableau standrard peut ˆtre gigantesque ! e Seules les premi`res lignes sont exploit´es (mots de faible e e poids) N´cessit´ d’une alternative e e
Matrice de contrˆle H o Privil´gions les calculs sur le stockage e Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs
Exemples de matrices de contrˆle o Parit´ [4, 3, 2] e
1
1 tH =
1
1
Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs
Notion de syndrome
D´finition (Syndrome du message m = a1 a2 . . . an ) e Le syndrome de m, est σ(m) = mt H
On a : σ(m ⊕ n) = σ(m) ⊕ σ(n)
Exemple : codage par r´p´tition [3, 1, 3] e e
1 1 σ(101) = 1 0 1 1 0 = 1 0
0 1
message
011
101
110
syndrome
11
10
01
Remarque
Lignes de t H = tous les syndromes des messages de poids 1
Sommes 2 ` 2 des lignes de t H = syndromes des messages de a poids 2, etc.
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs
Utilit´ des syndromes e Th´or`me e e
M1 M2 ⇐⇒ σ(M1 ) = σ(M2 )
Cons´quence e On attache un syndrome ` chaque classe d’´quivalence a e
2r syndromes : tous les mots de r bits sont des syndromes
Correction rapide d’un message
Remplacement du tableau standard
Liste des syndromes : ` chaque 2r mots a faible poids dont le mot est le syndrome
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
message de plus
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs
Etablir les liste des syndromes
M´thode pratique e 1. Ranger en colonne tous les mots binaires de longueur r (ordre lexico) : les syndromes. Pr´voir une seconde colonne ` cˆt´. e a oe
2. Construire B : ´l´ments de Bn rang´s par poids croissants ee e
3. Pour chaque b ∈ B (dans l’ordre) : calculer σ(b). Si la place est libre dans la seconde colonne en face de σ(b), y inscrire b.
4. Stop quand seconde colonne emplie.
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs
Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs
Messages 2n
0000000
0000001
0000010
0000100
0001000
0010000
0100000
1000000
0000011
···
1111111
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs
Messages 2n
0000000
0000001
0000010
0000100
0001000
0010000
0100000
1000000
0000011
···
1111111
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs
Messages 2n
0000000
0000001
0000010
0000100
0001000
0010000
0100000
1000000
0000011
···
1111111
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs
Messages 2n
0000000
0000001
0000010
0000100
0001000
0010000
0100000
1000000
0000011
···
1111111
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs
Messages 2n
0000000
0000001
0000010
0000100
0001000
0010000
0100000
1000000
0000011
···
1111111
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs
Corriger avec les syndromes
Principe
Avec R re¸u : on le corrige en lui ajoutant l’´l´ment de Γ(R) de c ee plus petit poids, donc l’´l´ment de Bn qui a le mˆme syndrome que ee e
R avec le plus petit poids possible.
M´thode pratique pour corriger R e 1. Calculer σ(R)
2. Rep´rer S : le message associ´ ` σ(R) dans la liste. e ea
3. Corriger R en le rempla¸ant par R ⊕ S c Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs
Exemple avec Cycl
Soit R = 1010101,
1
1
1
t σ(R) = R H = 1 0 1 0 1 0 1 0
1
0
0
0
1
1
1
0
1
0
1
1
0
1 = 1 1 0
0
0
1
Avant derni`re ligne de la liste des syndromes : M = 0010000 e C = 1010101 ⊕ 0010000 = 1000101
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs
Code parfait
Un code correcteur parfait doit corriger parfaitement les messages qui n’ont qu’une erreur : t ≥ 1 ou d ≥ 3
Th´or`me e e
Un codage lin´aire corrige de fa¸on certaine toutes les erreurs de e c t H a toutes ses lignes distinctes et non poids 1 ⇐⇒ sa matrice nulles. Les lignes de t H sont les syndromes des messages de poids 1 : pas de mot de code de poids 1 ⇐⇒ pas de ligne nulle dans t H
D´finition (Code de Hamming) e Un code de Hamming est un code lin´aire [2r − 1, 2r − 1 − r ] dont la matrice e t
H est constitu´e de tous les mots binaires non nuls de longueur r . e d =3
Code parfait
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
