D ES CODES HYPER UTILIS ÉS

I on les rencontre partout dès lors que le canal est bruité

du flash-code au satellite, en passant par le G SM, les C D, les

D VD, l’A DSL, le W I -F I ...

I on distingue différentes familles de codes correcteurs :

I les codes de répétition

I les codes linéaires (Hamming, Golay)
3 – Codes correcteurs – codes de Hamming I les codes cycliques (B CH, Reed-Solomon dont C IRC)
I les codes convolutifs
I les turbo-codes

I la plupart de ces codes utilisent des polynômes ou de l’algèbre

linéaire
I des techniques permettent d’améliorer encore et toujours ces
codes : extension, entrelacement, croisement et concaténation.

C ODAGE PAR BLOCS D ÉTECTION ET CORRECTION D ’ ERREURS

I le codage par blocs commence par découper un message binaire en blocs

de {0, 1}k
I on code ensuite bloc par bloc et on transmet dans un canal bruité I on dispose de l’ensemble C des mots du code
I si le bloc reçu diffère du bloc émis, il y a eu erreur I un message m codé devient égal à un c = c1 ... cn de C et est envoyé par le canal
I le codage va consister en un ajout de redondance de taille r I le récepteur reçoit c0 = c10 ... cn0
I on parle alors de (n, k)-code avec n = k + r I si c0 est un mot de code de C, on estime que c0 est sans erreur et on le décode
I les images de {0, 1}k par le code sont appelées les mots de code naturellement en m
I sinon, il y a détection d’une erreur et l’ensemble V des mots de code les plus
il s’agit de codes à longueur fixe donc de codes préfixes (i.e. instantannés) proches de c0 est considéré :
l’injectivité de la fonction de codage suffit à garantir la non-ambiguı̈té du
code si V = {v} est singleton, on corrige c0 en v puis on décode
sinon, on peut corriger de façon plus hasardeuse par rapport à un des mots
I le rendement R d’un (n, k)-code est égal à de code de V avant de décoder

k I si la correction n’est pas possible, la retransmission (ARQ) est effective

R=
n

Exemple
I la redondance vise à permettre la détection d’erreurs et éventuellement la
Bits de parité 2D (cf. TD no 2)
correction
D EUXI ÈME TH ÉOR ÈME DE S HANNON C ANAL BSC
I Canal Binaire Symétrique (Binary Symmetric Channel)
X est la v.a. d’entrée du canal et Y celle de sortie
I p correspond à la probabilité de recevoir 1 alors que 0 a été émis ou,
I H (X) : entropie de la source X à l’entrée du canal symétriquement, de recevoir 0 alors que 1 a été émis
I l’entropie conditionnelle H (X/Y) traduit la perte d’information entre X à I si p = 1/2 : la capacité du canal devient nulle et un tel canal est inutilisable
l’entrée et Y à la sortie du canal
I si p < 1/2, le théorème assure qu’il existe un (n, k)-code permettant de
c’est ce qu’il reste encore à découvrir sur X alors qu’on a reçu Y
transmettre sans erreur sur un canal de capacité non nulle
I la capacité du canal est la quantité maximale d’information sur l’entrée I cela dit, le rendement du code est limité par la capacité du canal.
effectivement transmise par le canal

C = max H (X) H (X/Y)

p

I Deuxième théorème de Shannon 0 1 p 0

Soit un canal de capacité C . Pour tout # > 0, il existe au moins un (n, k)-code de
rendement R = nk et de probabilité d’erreur p < # ssi : p

0R<C p
si H (X/Y) = 0 : la source n’apprend rien de plus que la sortie du canal, c’est que le canal est fiable 1 1
si l’entropie H (X) est maximale et celle de H (X/Y) aussi : la capacité devient nulle et la
transmission impossible
1 p

TAUX D ’ ERREUR C ODES C RC

I Codes de Redondance Cyclique (Cyclic Redundancy Check) inventés en 1961
I utilisés dans les réseaux informatiques (satellites, clef W EP, G SM, formats zip et
rar etc)
I Ordres de grandeur du taux d’erreur I un mot binaire m = mk 1 ... m0 est représenté par un polynôme Pm :
k 1

ligne taux d’erreur Pm = Â = mi xi

i=0
Disquette 10 9 : à 5Mo/s, 3 bits erronés/mn
I un tel code est caractérisé par un polynôme générateur Pg de degré r :
CD-ROM optique 10 5 : 7ko erronés sur 700 Mo
DAT audio 10 5 : à 48 kHz, 2 erreurs/s r 1

Mémoires à semi-conducteurs < 10 9 Pg = xr + Â gi xi

i=0
Liaison téléphonique entre 10 4 et 10 7
I m codé par c = mk 1 ... m0 cr 1 ... c0 où cr 1 ...c0 représente le reste de la division
Télécommande infrarouge 10 12
euclidienne de xr . Pm par Pg :
Fibre optique 10 9
Satellite 10 6 (Voyager), 10 11 (TDMA) Pc = Pm . xr + (Pm . xr mod Pg )
ADSL 10 3 à 10 9
I à la réception, on contrôle que Pc mod Pg = 0 (à défaut, l’ARQ opère)
Réseau informatique 10 12
(In : Théorie des codes, Dunod, 2007)
I le décodage consiste à retirer les r bits de redondance.

Exemple m = 10110 correspond à Pm = x4 + x2 + x

si Pg = x2 + 1 alors xr . Pm = x2 . (x4 + x2 + x) = x6 + x4 + x3
comme (x6 + x4 + x3 ) mod x2 + 1 = x (cf. division de polynôme) donc le mot m est codé
en c = 1011010.
C ODES LIN ÉAIRES : G ÉN ÉRALIT ÉS C ODES DE H AMMING (1950)

I ce sont des codes de canal

I ils sont basés sur de l’algèbre linéaire I les codes de Hamming sont emblématiques des codes linéaires

I ces codes sont linéaires car l’ensemble de mots du code forment I un message binaire M est augmenté d’une redondance de r bits
un sous-espace vectoriel I la dimension du code est n = 2r 1
I la longueur des mots du code est fixe et s’appelle la dimension
I la taille des messages d’origine est donc k =n r
I ce sont des codes correcteurs d’erreurs
I la matrice génératrice G est une (k, n)-matrice
I pour coder ou décoder, on utilise la seule matrice génératrice G
I la matrice de contrôle H est une (r, n)-matrice
I pour détecter une erreur et la réparer, on utilise la matrice de
I les vecteurs-colonnes de H sont les entiers en binaire de 1 à n
contrôle H
dans n’importe quel ordre
I le code est entièrement spécifié par l’une ou l’autre de ces deux
I un code de Hamming détecte et corrige 1 erreur.
matrices
I la somme de deux mots du code reste un mot du code

E XEMPLE : UN CODE H7,4 E XEMPLE ( SUITE ) : CODAGE ET D ÉCODAGE

I on définit la matrice génératrice G de l’application linéaire f :
f (x1 , x2 , x3 , x4 ) = (x1 + x2 + x4 , x1 + x3 + x4 , x1 , x2 + x3 + x4 , x2 , x3 , x4 )
I à l’issue du codage de source, on groupe la sortie binaire par paquets de
0 1
1 1 1 0 0 0 0 longueur 4
B 1 0 0 1 1 0 0 C
G=B C
@ 0 1 0 1 0 1 0 A I soit le paquet-message M = (1001) à encoder
1 1 0 1 0 0 1
I on code M en un message codé C
I par permutation des colonnes on fait apparaı̂tre la matrice Id4 :
0 1 0 1 C = M . G = (0011001)
1 1 0 1 0 0 0 1 1 0
B 1 0 1 0 1 0 0 C B 1 0 1 C
G0 = C. Id4 = B
@ 0
C avec C = B C
1 1 0 0 1 0 A @ 0 1 1 A
1 1 1 0 0 0 1 1 1 1
I on envoie C au récepteur qui reçoit le message reçu R
I en prenant H 0 = (Id3 t C) on obtient que : H 0 . t G0 = [0]3,4 I pour détecter une éventuelle erreur, il contrôle le message R :
✓ t ◆
C
H 0 . t G0 = (Id3 t C). t (C Id4 ) = (Id3 t C). t Id = (Id3 . t C) + (t C. Id4 ) = [0]3,4
4 H . t R = [0]r,1 ?
0 1
1 0 0 1 1 0 1
H0 = @ 0 1 0 1 0 1 1 A I si oui, il peut espérer que le message codé est bien C = (0011001)
0 0 1 0 1 1 1
I en l’absence d’erreur, il décode C en M conformément à G :
I on défait la permutation sur les colonnes pour obtenir la matrice de contrôle H :
0 1 M = p3,5,6,7 (C) = (1001)
1 0 1 0 1 0 1
H=@ 0 1 1 0 0 1 1 A
0 0 0 1 1 1 1
D ISTANCE ET POIDS DE H AMMING B OULES DE H AMMING

Soient x et y deux mots binaires de longueur n Soit x un mot binaire de longueur n.

I distance de Hamming entre x = x1 . . . xn et y = y1 . . . yn : I boule de centre x et de rayon e avec 0 en:

dH (x, y) = card({i, 1  i  n et xi 6= yi }) Be (x) = {z : z 2 {0, 1}n , dH (x, z)  e}

Ce sont les mots binaires de longueur n qui ne diffèrent pas

C’est le nombre de positions où 2 mots binaires diffèrent de x sur plus de e positions.
I poids de Hamming du mot x :
I nombre d’éléments de la boule de centre x et de rayon e :
wH (x) = dH (0, x) = card({i, 1  i  n et xi = 1}) ✓ ◆
e
n
| Be (x)| = Â
i=0
i
C’est la distance du mot x au mot (0, . . . , 0), elle coı̈ncide avec le
nombre de 1 dans x
Exemple Exemple
x = (0, 1, 1, 0, 1, 1, 0) et y = (1, 1, 1, 0, 0, 1, 1) donnent dH (x, y) = 3, wH (x) = 4 et La boule de centre x = (0, 1, 1, 0, 1, 1, 0) et de rayon 2 contient z = (0, 1, 1, 0, 0, 1, 1) mais
wH ( y ) = 5 pas y = (1, 1, 1, 0, 0, 1, 1). Cette boule contient Â2i=0 (7i ) = 1 + 7 + 21 = 29 éléments.

D ÉTECTION D ’ ERREUR ET CORRECTION U NE MULTITUDE DE CODES CORRECTEURS

I un code de Hamming détecte et corrige 1 erreur due au bruit
I la matrice de contrôle a pour rôle de vérifier que le message reçu R n’a
pas été altéré, il doit vérifier : Le code du Minitel est le code de Hamming (128, 120, 3)
H . t R = [0]r,1 15 octets transmis plus 1 octet de redondance (taux de 0,93%)
, R =C
I sinon, une erreur a altéré C et le syndrome S de l’erreur est :
En plus de ceux étudiés, voici les codes correcteurs les plus classiques :
S = H . t R 6 = [0] I codes de Reed-Solomon (codes CIRC des CD audio)

I dans H, il existe forcément un vecteur-colonne Hi avec 1  i  n tel I codes de Golay

que : I codes de Reed-Muller
S = Hi I codes convolutifs
I on en déduit que l’erreur a porté sur le ieme bit de C et on peut corriger R I etc
en C
I les codes de Hamming sont des codes linéaires parfaits

en effet, les boules centrées sur les mots de code forment une A suivre ...
partition de l’ensemble des suites binaires de longueur n