Codage de l’Information en Vue de sa Protection

Signal Filtre de Echant. & Codeur

Analogique Garde Quantif. Canal de

Signal Transmission
Reconstruction Décodeur
Analogique

Codage de Codage Codage pour

Source Cryptographique Transmission

Réduction du volume Protection de l ’information Codes Détecteurs d ’erreur

d ’information Contrôle d ’accès Codes Correcteurs d ’erreur
Elimination de la Authentification (signature)
redondance Protection contre manipulation
Watermarking

Codage de l’Information en Vue de sa Protection

Considérations Pratiques : Transmission Video

Exemple : Taux d’Erreur = 10-5

• H263 (Video Conférence)

! 10 images/s
! Débit 640 kb/s " 1 image sur 2 en erreur

• MPG1 (Equivalent VHS, VCD)

! 25 images/s
! 1.5 Mb/s " 1 image sur 2 en erreur

• MPG2 (CableTV, HDTV, DVD) :

! De 25 à 60 images/s
! De 10 à 40 Mb/s " 4 erreurs / image !
Codage de l’Information en Vue de sa Protection

• Objet " garantir une qualité de service

• Techniques " détection des erreurs + répétition du message

" correction des erreurs (stockage)

" structure du code adaptée à la nature de l’application

• Principe " introduire de la redondance :

" message à coder : blocs de m bits " codés sur n bits (table) : n = m + r

" 2n mots de code possibles, dont seuls 2 m mots sont valides

" choix des mots valides : erreurs les + fréquentes " génèrent un mot non valide

" Optimiser capacité de détection des erreurs / redondance introduite !

Codage de l’Information en Vue de sa Protection

Exemple : « bit de parité » (r = 1) " ∀ mot du code ∋ un nombre pair de « 1 »

Codeur " Détection d’un nombre impair d'erreurs

parité
Canal de transmission
ou
support de mémorisation
" Mais : un nombre pair d'erreurs ne
pourra être détecté !
Décodeur

erreur
Codage de l’Information en Vue de sa Protection
« parité croisée » " Détecter deux erreurs ou en corriger une
" Transmettre le message par groupes de mots
" A chaque groupe de mot, on associe deux info de parité :
Bit de parité pour chaque mot + mot de parité à la fin de chaque groupe
" A la réception : contrôle horizontal + contrôle vertical
bits de parité
100111 0
groupe de 010010 0
5 mots 011110 0
Si nombre d'erreurs <= 2 : à protéger 101011 0
001101 1

mot de parité 001101 1

SCHEMA DE DETECTION
1001110 0 1001110 0 1001110 0 1001110 0
0100100 0 0100100 0 0100100 0 0100100 0
0111100 0 0101100 1 0111 000 1 0101110 0
1010110 0 1010110 0 1010110 0 1010110 0
" « Produit de Codes » 0011011 0 0011011 0 1011011 1 0011011 0
0011011 0 0011011 0 0011011 0 0011011 0

0000000 0010000 1000100 0010010

sans erreur une erreur deux erreurs deux erreurs
lignes et sur une
colonnes même
différentes ligne

Codage de l’Information en Vue de sa Protection

Types de codes

" codes en bloc : calculés uniquement à partir des m bits du message source
" codes convolutionnels : calculés à partir des bits d'information de plusieurs blocs

m m m m
m m m m m m m m

r r r r

n n n n n n n n n n n n

Code en bloc Code convolutionnel Code systématique

• Code Systématique : yt = [ y1 y2 y3 L yn ] = [ x1 x 2 L xm a1 a2 L ar ]

• Bits de redondance : a = [a1 a2 L ar ] : « bits de contrôle »

Propriétés Générales des Codes Détecteurs et Correcteurs d’Erreurs

Principe : m"n=m+r
∀ code ∋ 2n mots possibles, dont seuls 2 m sont valides

• Si erreur(s) : un des ( 2 n - 2m ) mots non valides est présenté au décodeur

• Si la redondance ( r = n – m ) est suffisante, détection et correction sont possibles
• « rendement d'un code » (« taux de codage », « coding rate ») R=m/n

" Codes à structures particulières :

• l’efficacité d'un code augmente avec la taille des blocs codés, mais l’utilisation de tables
devient alors impraticable
• les opérations de codage, décodage, détection et correction doivent pouvoir s’effectuer sur
base de circuits logiques simples

Propriétés Générales des Codes Détecteurs et Correcteurs d’Erreurs

Définitions

• « complexité » : facilité d'implantation, dépend de la solution technologique employée

(taille mém., nbre d'opérateurs, volume d'opérations)

• « poids de Hamming » d'un vecteur yt = nombre de « 1 » qu'il contient

Ex : yt = 1010 " pH = 2

• « distance de Hamming » : nombre de bits par lesquels deux mots de code diffèrent

Ex : yt = 1010 ; zt = 1110 " dH = 1

" Distance de Hamming entre y t1 et y t2 1010

= poids du vecteur somme (modulo 2) de y t1 et de y t2 +1110
0100
Propriétés Générales des Codes Détecteurs et Correcteurs d’Erreurs

• Deux mots de code distincts sont différents d'au moins un bit ( d min = 1 ) :

- si dm = 1 " erreur transforme un mot valide en un autre mot valide, détection impossible !
Ex : yt = 1010 ; zt = 1110
Si et = 0100 " yt + et = 1110 = zt

- si dm = 2 " une seule erreur transforme un mot valide en un mot invalide (diff. d’1 bit)
Ex : yt = 10101 ; zt = 11100
Si et = 01000 " yt + et = 11101 != zt

Possibilité de détection d'une erreur unique lorsque dm = 2 (ex : code avec vérif. de parité)

Propriétés Générales des Codes Détecteurs et Correcteurs d’Erreurs

Code (n,m) Mot reçu : y t⊕ = yt + e t = [ y 1 y 2 y 3 L y n ] + [ e1 e2 e3 L en ]

# ei = 0 si pas d'erreur sur le bit d'indice i / ei = 1 sinon

# poids e du vecteur d'erreur = nombre d'erreurs subies par un mot de code

# Code (n,m) : détection des erreurs de poids e si d m = 1 + e

• Corriger une erreur " erreur positionnée sur chacun des n bits d'un mot de code valide
" n mots de code non valides, pour chacun des 2m mots valides

• Si le code contient un total de (n + 1) • 2 m mots distincts :

# 2m de ces mots $ 2m mots d'information

# n • 2m de ces mots $ mots non valides obtenus avec 1! erreur sur les mots valides

" chaque erreur provoque un mot invalide distinct ∀ mot valide, que l’on peut donc retrouver
Propriétés Générales des Codes Détecteurs et Correcteurs d’Erreurs

• Condition nécessaire pour corriger une erreur :

2 n ≥ (n + 1) • 2 m c.− à − d. 2r ≥ n + 1

# Condition non suffisante : 2 mots de codes ≠ ne doivent jamais aboutir à un même mot
en cas d’erreur, ce qui peut se produire si d < = 2e
Ex : yt = 10101 ; zt = 11100
Si et = 01000 ; ft = 00001 " yt + et = 11101 = zt + f t

" pour pouvoir corriger e erreurs, il faut : dm = 1 + 2e

# Exemple : dm = 3 pour corriger une erreur (e = 1) Ex : Code avec parités croisées

• Rendement du code : d'autant plus grand que les mots de code sont longs

# Code capable de corriger une erreur : 2 ≥ n + 1

r

n−r r log2 (n + 1)
# R = m (m + r) = (n − r) n R=
n
= 1− = 1−
n n
"1 lorsque n " infini

Propriétés Générales des Codes Détecteurs et Correcteurs d’Erreurs

• Probabilité des erreurs : fonction des caractéristiques du canal de transmission

( Haute Qualité < 10-6 ; Très Bruité > 10-2)

" Si erreurs uniformément réparties : p(e = = 1) >> p(e = = a)

En effet : p(e = = 0) = (1-p)n p(e = = 1) = p (1-p)n-1 p(e = = a) = pa (1-p)n-a

" Conception d’un code : optimiser sa capacité à détecter (ou corriger) les erreurs les
plus probables
Les Codes Linéaires
" Opérations simples pour codage et décodage : « code en bloc linéaire systématique »

Mot code y : n bits = m bits xt d'information à coder

+ r bits at de redondance = combinaison linéaire des bits d'information

 
m m m
y t =  x1 x2 L xm ∑p i ,1 • xi LL ∑ pi,r • xi  aj = ∑ pi,j • xi ∀ j = 1, 2, L , r (modulo 2)
 i =1 i= 1  i= 1

m bits r bits
avec xi et pi,j = 0 ou 1
d' information de redondance

Ex : code (7,4)
= x •H H (m× n) :
t t
y où
 1 0 0 0 p1,1 p1,2 p1,3  
 p 
= « matrice génératrice de code » 0 1 0 0 p2 ,2 p2 ,3 
H = [Im P] =     2 ,1  
 0 0 1 0 p3 ,1 p3 ,2 p3 ,3  
= matrice unité Im (m ×m) + matrice P (m×r)      
 0 0 0 1 p4 ,1 p4 ,2 p4 ,3  

aj : = bit de vérification de parité portant sur les bits de xi qui correspondent à pi,j = 1

Les Codes Linéaires

Décodage du mot de code " retrouver les m bits d'information ?

" Mot de code reçu, après perturbations : y t⊕ = [x ⊕

1 x2⊕ L xn⊕ a1⊕ a2⊕ L a⊕r ]
*
" Si pas d'erreur, parité a j calculée au décodage sur x⊕i = a⊕j , calculée au codage sur xi
m

" Leur somme (modulo 2) est nulle : ∑p i, j • xi⊕ + a⊕j = 0 ∀ j = 1, 2 , L , r

i=1

yt • Gt = 0  p1,1 p1,2 p1,3 

p p2 ,2 p2 ,3 
 2 ,1 
G = « matrice de contrôle de parité » p3 ,1 p3 ,2 p3 ,3 
  P
G t
= p4 ,1 p4 ,2 p4 ,3  = I 
Gt (n×r) : P (m×r) + Ir (r×r)  1 0 0 
r
 
0 1 0 
 P
G lié à H : y t • G t = x t • H • G t = xt • [ I m P ] •   = 0 0
 0 1 
Ir

• Propriétés : - Tout mot de code valide est une combinaison linéaire des bits à coder
- La somme de deux mots de code valides est un mot de code valide
Code Linéaire Systématique : Principe du Codage

Codes Linéaires Systématiques " opérations de codage très simples :

• codes séparables " premiers m bits du code = les bits à coder

• r bits de redondance : circuits logiques

Mot à coder (4 bits)

Exemple : code (7,4)
x4 , x3 , x2 , x1
registre à décalage
1 0 1 x4 x3 x2 x1
1 1 1 Mot codé (7 bits)
P =  
1 1 0 y
 
0 1 1 + + +

a1 = x1 + x2 + x3 a3 a2 a1

bits de red. : a2 = x2 + x3 + x4 registre à décalage

a3 = x1 + x2 + x4 (additions modulo2)

" codeur (n,m) : • r add. à m entrées, 1 commutateur

• 2 registres à décalage de m et r bits de capacité

Code Linéaire Systématique : Principe de la Détection d’Erreurs

Calcul de st = « syndrome » : r bits = combili des erreurs≡ 0 si pas d'erreur

st = y t ⊕ • Gt = [s1 s2 L sr ] si erreur(s) : et = [ e1 e2 L en ] , y t ⊕ = yt + e t

st = (y t
)
+ et • G t = e t • Gt (car yt . Gt = 0, par definition)

• et : dimension n " 2n valeurs distinctes (dont 0 $ pas d'erreur)

" 2n-1 configurations différentes d'erreurs possibles

• Erreur non détectée : si elle transforme un mot valide en un autre mot valide

yt ⊕ = y t + e t = mot valide SSI les 2 mots additionnés sont valides

les seules erreurs non détectées sont celles qui ont la configuration d'un mot de code valide
Code Linéaire Systématique : Principe de la Détection d’Erreurs

• Nombre de mots de code valides : 2m (dont, en l'absence d'erreurs, et = 0)

• Nombre de config. d'erreurs : 2n – 1 " 2m - 1 config. d'erreurs non détectées
" 2n - 2m config. d'erreurs détectées

• Efficacité du code : code tel que les erreurs non détectées soient les moins probables,
compte tenu des caractéristiques de l'application
(canal de transmission, support de stockage)

" Adaptation du code, par un choix judicieux de la matrice génératrice du code

• Probabilité pN de ne pas détecter d’erreur ? Si erreurs indépendantes ( Perreur = pB )

" Probabilité et ∋ i erreurs = pB i (1 - pB )n - i

n n− i

" Si Li = nombre de mots de code de poids i " pN = ∑ Li • piB • (1 − pB )

i=1

Code Linéaire Systématique : Principe de la Détection d’Erreurs

Exemple du code (7,4) :

Mot de code Poids • 7 mots de poids 3

x1 x2 x3 x4 a1 a2 a3
0
1
0
0
0
0
0
0
0
1
0
0
0
1
0
3 • 7 mots de poids 4
0 1 0 0 1 1 1 4
1 1 0 0 0 1 0 3
0 0 1 0 1 1 0 3 • 1 mot de poids 7
1 0 1 0 0 1 1 4
0 1 1 0 0 0 1 3
1 1 1 0 1 0 0 4
0 0 0 1 0 1 1 3

pN = 7 • pB3 • (1 − pB ) + 7 • pB4 • (1 − pB ) + p7B ≈ 7 • pB3

1 0 0 1 1 1 0 4 4 3
0 1 0 1 1 0 0 3 "
1 1 0 1 0 0 1 4
0 0 1 1 1 0 1 4
1 0 1 1 0 0 0 3
0 1 1 1 0 1 0 4
1 1 1 1 1 1 1 7 • Si pB = 10-2 " pN ~ 7 10-6
• Si pB = 10-5 " pN ~ 7 10-15

" Excellente Détection des Erreurs Uniformément Réparties !

Code Linéaire Systématique : Principe de la Détection d’Erreurs

• Présence d'erreurs : Décelée par st ≠ 0

• Correction d’erreurs : ∀ config. d'erreurs ⇔ mot de code erroné ≠

" pour 2 configurations e1t et e2t : ( )
s1t − s t2 = e1t • Gt − e2t • Gt = e1t − e2t • G t ≠ 0

• st ( r ) " 2r = 2n-m syndromes différents

" Correction au max. de 2n-m config. d'erreurs ≠ (∋ config. sans erreurs)

" En outre, correction possible de toutes les erreurs de poids : e≤

( dm − 1)
2
" Pour simultanément corriger e1 erreurs et détecter e2 erreurs (e2 > e1) : dm ≥ e1 + e2 + 1

• Code Linéaire Systématique " dm = poids le plus faible d'un mot de code non nul
(car un mot de code est toujours égal à la somme de deux autres mots de code)

• Exemple : code (7,4) r=3 " correction possible de 23 = 8 config. d'erreurs ≠

" dm = 3 " e ≤ (3-1)/2 = 1 " correction de toutes les erreurs simples

Code Linéaire Systématique : Principe de la Détection d’Erreurs

• Stratégie de correction (idéalement) :
Choisir comme mot de code émis yt celui pour lequel la distance d( yt, yt⊕ ) entre ce mot
et le mot de code reçu est la plus faible, parmi tous les mots de code possibles

" Décodage par maximum de vraisemblance : yit : P ( y t⊕ | yit ) > P ( y t ⊕ | y tj ) ∀j≠i

• Très souvent : erreurs par salves ou paquets

"codes conçus pour assurer une protection raisonnable contre ces salves d’erreurs
" salve d’erreurs = vecteur de dim. k dans lesquels se trouvent confinées toutes les erreurs
du vecteur d'erreur du code de dimension n, avec n ≥ k

• Propriétés des codes de bloc linéaires :

• possibilité de concevoir un code (n,m) qui détecte ∀ salves d'erreurs de long. ≤ r = n - m ;

• possibilité de concevoir un code (n,m) qui corrige toutes les salves de longueur r / 2 ;

• pour simultanément corriger toutes les salves de long. ≤ l1 et détecter toutes les salves de long.
≤ l2 (l2 ≥ l1), un code linéaire doit vérifier r = l1 + l2 ;
Code Linéaire Systématique : Principe de la Correction d’Erreurs
Principe de la correction d'erreurs

• mot reçu yt⊕ stocké dans un registre à décalage

• syndrome st⊕ calculé par s t = y t ⊕ • G t

Registre à décalage
⊕
Mot reçu
y⊕n y⊕n-1 y⊕ y⊕
" r bits du syndrome : 2 1

circuit pour estimation du vect. d'erreurs

le + probable avec le syndrome calculé Calcul du syndrome
sn sn-1 s2 s1
" n bits du vecteur d'erreurs :
Estimation du vecteur d'erreurs
additionnés (modulo 2) aux n bits du
en en-1 e2 e1
mot reçu pour produire le mot corrigé + + + +
y⊕n y⊕n-1 y⊕2 y⊕1
yn yn-1 y2 y1

Calcul du syndrome simple, mais réalisation de 1'estimateur d'erreurs difficile (en général)

Code Linéaire Systématique : Principe de la Correction d’Erreurs

Exemple : Code (7,4)

• Capable de corriger toutes les erreurs simples (dm = 3)

• Code de longueur de 7 bits " ∃ 7 config. différentes ∋ une erreur et une seule :

Vecteurs d'erreurs Syndromes

1 0 1
1 1 1 e1 e2 e3 e4 e5 e6 e7 s1 s2 s3
 
1 1 0 1 0 0 0 0 0 0 1 0 1
  0 1 0 0 0 0 0 1 1 1
s = e • G = e • 0
t t t t
1 1 0 0 1 0 0 0 0 1 1 0
1
où et :
0 0 0 0 0 1 0 0 0 0 1 1
  0 0 0 0 1 0 0 1 0 0
0 1 0 0 0 0 0 0 1 0 0 1 0
0 0 1
0 0 0 0 0 0 1 0 0 1


Chaque syndrome : correspond à une ligne de Gt (dont ttes les lignes sont ≠ par construction)

" les syndromes correspondant à toutes les configurations d'erreurs sont différents
Code Linéaire Systématique : Principe de la Correction d’Erreurs

Correction des erreurs simples

• Syndrômes : Additionneurs modulo 2 Exemple : Code ( 7, 4 )
y⊕
y⊕ e 1

% chaque add. $ colonne de Gt

1 1
+ y
1
y⊕
y⊕
2
e
2
2
+ y
% ∀ bit à « 1 » de la col. $ liaison entre y⊕
s1
e3
y⊕
3
2

3 +
l’add. et le bit de code corresp. + y3
s y⊕
y⊕
4 +
2 e4 4
+ y4
s y⊕
• Erreurs : Circuits ET , sur base des syndr. y⊕
5 +
3 e5
+
5
y5
y⊕
y⊕ e6 6
6
+ y6

• Correction :ajout des erreurs (modulo 2) y⊕

7
e7
y⊕
7
+ y7
au mot reçu
Calcul de Correction
Calcul des syndromes
l'erreur de l'erreur

• Le plus souvent : codes de grande longueur, avec r élevé (cfr. efficacité)

2r syndromes ≠ " complexité augmente fortment et réalisation pratique impossible !

" Codes linéaires de structure choisie afin de simplifier la correction des erreurs

Les Codes de Hamming

" Conçus spécialement pour pouvoir corriger une erreur de transmission (et une seule), avec une
efficacité proche du maximum théorique
+ avantage : réalisation très simple du décodeur

• Codes Linéaires Systématiques (n,m) : N 3 7 15 31 63 127

n = 2r − 1 M 1 4 11 26 57 120

m = n − r = 2r − r − 1 r 2 3 4 5 6 7

• dm = 3 " correction possible de toutes les erreurs simples

• ∀ code (n,m) : correction au max. de 2n-m = 2r config. d'erreurs ≠ ( ∋ config. sans erreur)

" Codes de Hamming : n = 2r - 1 ⇔ 2r - 1 config. d’erreurs simples

" Codes optima : toutes les erreurs qu’ils sont susceptibles de corriger
⇔ ensemble de toutes les erreurs simples

• Si n ≠ 2 − 1
r
" Code de Hamming Réduit : choisir r immédiatement > valeur désirée
Les Codes de Hamming
• r bits de parité " rangés dans le mot de code aux positions d’indice = puissance de 2
• m bits d’info. " rangés dans les autres positions du mot de code (ordre croissant des indices)

Mot de code y1 y2 y3 y4 y5 y6 y7 y8 y9 y10 y11 y12 y13 y14 y15

Parité a0 a1 x1 a2 x2 x 3 x4 a3 x5 x6 x7 x8 x9 x10 x11
a0 X X X X X X X X 20
a1 X X X X X X X X 21
a2 X X X X X X X X 22
a3 X X X X X X X X 23
Code de Hamming (15,11)

• Bit de parité ai " calcule la parité des bits du mot de code dont la position dans ce mot,
exprimée en binaire, contient le bit 2i

Exemple : bit de parité a1 (position 2 du mot de code) yt = xt • H

" vérifie la parité de x1, x3, x4, x6, x7, x10, x11 (positions 3,6,7,10,11,14,15 du mot de code),
dont les numéros de position contiennent le bit 21 = 2

Les Codes de Hamming : Correction d’une Erreur - Exemple

Mot d'information xt 1 0 1 0 1 1 0 0 0 1 0

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
↓ ↓ ↓ ↓
Mot de code émis y t 0 0 1 0 0 1 0 1 1 1 0 0 0 1 0

Erreur et 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0

Mot reçu yt⊕ 0 0 1 0 1 1 0 1 1 1 0 0 0 1 0

Parités calculées sur le mot reçu 1 0 1 0

• Erreur sur le bit y5 " le bit y5 affecte les bits de contrôle de parité a0 et a2

Mot de code y1 y2 y3 y4 y5 y6 y7 y8 y9 y10 y11 y12 y13 y14 y15

Parité a0 a1 x1 a2 x2 x3 x4 a3 x5 x6 x7 x8 x9 x10 x11
a0 X X X X X X X X 20
a1 X X X X X X X X 21
a2 X X X X X X X X 22
a3 X X X X X X X X 23

• a0 et a2 calculés ≠ a0⊕ et a2⊕ reçus " Position de l’erreur = 20 + 22 = 1 + 4 = 5

Les Codes de Hamming
t ⊕
Bits d'information du mot reçu x
• Principe de la correction d’erreurs
avec un code de Hamming : Calcul des t
Mot yt⊕ Mot x
parités Correction
reçu corrigé
" Syndrome de r bits = représentation
binaire de 1a position du bit en erreur
" Correction très simple : il suffit Décodage de
position
d'inverser le bit en erreur exprimé
en binaire

• Il est possible de redonner à la matrice 

1 0 0 0 0 0 0 0 0 0 0

1 1 0 0
génératrice H sa forme classique :  
0 1 0 0 0 0 0 0 0 0 0 1 0 1 0
0 0 1 0 0 0 0 0 0 0 0 0 1 1 0
 
0 0 0 1 0 0 0 0 0 0 0 1 1 1 0
" Calcul du mot de code yt = xt • H 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1
 
H = 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1
0 0 0 0 0 0 1 0 0 0 0 1 1 0 1

" codeurs et décodeurs de Hamming basés 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1
sur des principes de réalisation semblables à  
0 0 0 0 0 0 0 0 1 0 0 1 0 1 1
ceux précédents 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1
 
0 0 0 0 0 0 0 0 0 0 1
1444444424444444 3
1 1 1 1
144244 3
 Matrice IH Matrice P 

Extension des Codes de Hamming

Mot d'information x t 1 0 1 0 1 1 0 0 0 1 0

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
↓ ↓ ↓ ↓
Mot de code émis y t 0 0 1 0 0 1 0 1 1 1 0 0 0 1 0

Erreur et 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0

Mot reçu y t⊕ 0 0 1 0 1 1 1 1 1 1 0 0 0 1 0

Parités calculées sur le mot reçu 0 1 0 0

• Erreurs sur les bits y5 et y7 " affectent les bits de contrôle de a0 , a1 et a2

Mot de code y1 y2 y3 y4 y5 y6 y7 y8 y9 y10 y11 y12 y13 y14 y15

Parité a0 a1 x1 a2 x2 x3 x4 a3 x5 x6 x7 x8 x9 x10 x11
a0 X X X X X X X X 20
a1 X X X X X X X X 21
a2 X X X X X X X X 22
a3 X X X X X X X X 23
1
• " Position de « l’erreur » = 2 = 2 " Erreur simple en y2 !!!
Extension des Codes de Hamming
Codes de Hamming : dm = 3 " impossible de corriger 1 erreur et d’en détecter 2

• Extension à dm = 4 : ajout d’un bit de contrôle = bit de parité sur l'ensemble des bits du mot

" Au décodage : contrôle de parité " 0 si # pair ou pas d'erreurs, " 1 si # impair d'erreurs

Une erreur = erreur ET parité → " correction "

" Combinaison des deux indicateurs : Deux erreurs = erreur ET parité → " détection "
x1 x2 x3 x4 y1 y2 y3 y4 y5 y6 y7 y8
Parité

Codeur de Hamming
Décodeur de Hamming Deux Erreurs
Erreur

y1 y2 y3 y4 y5 y6 y7 y8 x1 x2 x3 x4

• Codes de Hamming étendus : longueur n = 2r bits

" particulièrement adaptés aux mots dans les ordinateurs, microprocesseurs, mémoires
" « SECDED code » (Single Error, Correcting, Double Error Detecting code)

Extension des Codes de Hamming

 1 0 0 1 1 0
H =  0 1 0 1 0 1
Soit le codeur :  
 0 0 1 0 1 1

• Rendement : n = 6, m = 3, r = 3 " R = m/n = 50 %

• Code de Hamming réduit (non parfait), rendu systématique.

• Décodage : Exploiter la position normalement occupée par les bits d’information !

Bits de code Y1 Y2 Y3 Y4 Y5 Y6
Pos. Hamming base a0 a1 x1 a2 x2 x3
Pos. Systématique x1 x2 x3 a0 a1 a2
Code pos. base 3 5 6 1 2 4
Code pos. binaire 011 101 110 001 010 100
décodage a2’a1a0 a2a1’a0
Extension des Codes de Hamming

Mot à coder (3 bits)

x3, x2, x1
registre à décalage Mot codé
x3 x2 x1 (6 bits)

+ + +

a2 a1 a0
registre à décalage

y⊕
y⊕
1
e1 1
+ y
1
y⊕
y⊕ e
2
2
2
+ y2
+ + +
 a0 = x + x + a
1 2 0 a y⊕
y⊕

0 e 3
3 + 3
+ + + +
 a1 = x1 + x3 + a1
y3
a y⊕
 + + +
y⊕ + 1 e 4

 a2 = x 3 + x 2 + a 2
4 4
+ y4
a y⊕
y⊕ + 2 e5 5
5
+ y
5
y⊕
y⊕
6
e6 6
+ y
6

Calcul des syndromes Calcul de l’erreur Correction