Codage de l’information

Codage NRZ : « Non-Retour à Zéro » :

Principe : Le niveau est constant sur un intervalle (pas de transition de retour à zéro).
On utilise deux niveaux pour coder le 0 et le 1

1 0 1 1 0 1 0
Volts
V0
Code Unipolaire
0
Tb 2Tb 3Tb 4Tb 5Tb 6Tb 7Tb NRZ
*

Volts
V0
Code (bi)polaire
0
NRZ
-V0 *
Tb 2Tb 3Tb 4Tb 5Tb 6Tb 7Tb

Le codage NRZ est utilisé par le port de communication série asynchrone des PC.
1
 Codage de l’information
Codage RZ : Return to Zero

Principe : Transition au milieu de chaque temps bit à 1.

1 0 1 1 0 1 0
Volts
V0
Code Unipolaire
0
Tb 2Tb 3Tb 4Tb 5Tb 6Tb 7Tb NRZ
*

V0
Code RZ
0
Tb 2Tb 3Tb 4Tb 5Tb 6Tb 7Tb

2
 Codage de l’information
Codage NRZI : (Non Return to Zero Inverted)

Principe : on produit une transition du signal pour chaque 1, pas de transition pour les 0.

Utilisation : Fast Ethernet

3
 Codage de l’information
Codage bipolaire (AMI) : (Alternate Mark Inversion):

Principe : Les 0 sont représentés par des potentiels nuls, les « 1 » en alternance par +V et –V.

4
 Codage de l’information
Code Manchester :

Principe : Il y a une transition au milieu de chaque temps bit :

- Transition croissante pour un 1,
- Décroissante pour un 0 (version lue sur paire 10BT).

Volts
1 0 1 1 0 1 0 1

Tb 2Tb 3Tb 4Tb 5Tb 6Tb 7Tb 8Tb

Le codage Manchester présente une bonne immunité aux bruits

5
 Codage de l’information
Codage Manchester différentiel
Principe : Il y a une transition au milieu de chaque temps de bit.
Chaque transition est codée par rapport à la précédente.
- Une transition de même sens à la précédente pour un 0
- Une transition de sens inverse à la précédente pour un 1.

Le code est utilisé par le réseau Token Ring 802.5.

6
 Codage de l’information
Codage Miller :

Principe : comme le Manchester simple, mais en supprimant une transition sur

deux, que celle ci soit significative ou non et en conservant une
transition au milieu de chaque temps bit pour la valeur 1.

ClK

Volts
1 0 1 1 0 1 0 1

Tb 2Tb 3Tb 4Tb 5Tb 6Tb 7Tb 8Tb

Le spectre d'un signal codé par la technique de Miller est beaucoup plus étroit que celui du
codage Manchester. Il présente une bonne immunité aux bruits et il est bien adapté aux
supports à bande limitée. 7
 Codage de l’information
Codage Multi Level MLT3

Principe : Dans ce codage, seuls les 1 font changer le signal d’état et sont codés
successivement sur trois états : +V, 0 et –V.
Les 0 sont codés en conservant la valeur précédemment transmise.

Utilisation : Fast Ethernet (100BaseTX, 100BaseT4), ATM

8
 Codage de l’information
Codage multi symbole

Principes : Durant un temps bit le signal peut prendre plus de deux valeurs différentes.

Valence = 2
1 1 1 1
0 0 0 0

3U

2U Valence = 4

0 01 00 11 10

9
 Codes correcteurs d’erreur

Définitions
- Un alphabet A est un ensemble fini, dont les éléments sont appelés symboles.
- Un mot de longueur n est un élément de An : c’est une suite de n symboles de A.
- Un message est une suite de symboles de A de longueur quelconque.
Si w est un élément de An , on note wi le i -ème symbole de w.
On utilisera aussi la notation w = w1 w2 . . . wn , où les wi sont des symboles de A.
Le plus fréquemment on aura A = {0, 1} (on parlera alors de mots et de codes binaires).

Un codage est une application injective  : A B.

C’est une règle spécifiant comment transformer un message d’origine M en
un nouveau message codé M’ =  (M).
(Les alphabets du message d’origine et du message codé seront le plus souvent les mêmes.)

10
 Codes correcteurs d’erreur
Codage par blocs
Dans la pratique des codes correcteurs, on utilise principalement des codages par blocs.
• Le message à transmettre est découpé en blocs (mots) de taille m fixée.
• Chacun des blocs d’origine de taille m est codé séparément. Tous les blocs codés
doivent avoir la même taille n. (n >= m.)
• Les blocs codés sont transmis successivement.

Message à transmettre

Découpage de blocs
m
Mot d’origine Bits de contrôle
m n-m
Mot codé Code systématique
n
Message transmis
n 11
 Codes correcteur d’erreur
Soit  : Am Bn. une application de codage.
On appelle mot de code tout élément de l’image de  c.à.d tout mot de Bn de la forme
 (w), w  Am .
On appelle code l’ensemble des mots de code : C = {(w), w  Am }.
C’est l’image par  de tous les mots de A.
On parle de code de taille (n, m)
Distance entre deux mots
Soit A un alphabet, et soient w et w’ deux mots sur A de longueurs m.
On appelle distance de Hamming entre w et w’, et on note d(w,w’), le nombre de positions
où w et w’ ont des symboles différents :
d(w,w’) = card{i , wi ≠ w’i }
Alternativement, c’est aussi :
• le nombre de symboles à modifier pour passer de w à w’
• le nombre d’erreurs nécessaires pour confondre w et w’

Exemples : d(1101, 1010) = 3

12
 Codes correcteurs d’erreur

Principe des codes de détection d'erreurs

Avant transmission, l‘émetteur va rajouter des bits a ceux transmis.

- Ces bits sont calcules selon un algorithme connu a la fois de l‘émetteur et du récepteur.
- Ils sont ensuite utilisés par le récepteur pour déterminer si la transmission s'est bien
déroulée.
-A part pour la détection d'erreurs ces bits ne transportent aucune information utile.
On dit que l‘émetteur introduit de la redondance.

Codes de contrôle de parité – VRC (VRC = Vertical Redundancy Check)

On insère à chaque mot de N bits un bit de parité pour que le nombre de bits à 1
dans le mot (modifié) de N + 1 bits soit:
- pair (VRC pair) ;
- ou impair (VRC impair).
Le récepteur doit ensuite contrôler que le nombre de bits à 1 dans chaque mot est
pair (ou impair).
13
Exemple : On veut envoyer les quatre caractères ASCII du mot : ENSA
(Les caractères ASCII sont codés sur 7 bits.)
ASCII VRC pair VRC impair
E 1000101 1 0
N 1001110 0 1
S 1010011 0 1
A 1000001 0 1
Donc la séquence envoyée avec un VRC pair :
1000101 1 10011100 10100110 10000010
Codes de contrôle de parité – LRC (Longitudinal Redundancy Check)
Après une séquence de N mots de b bits, on insère un mot de parité de b bits pour que le
nombre de bits à 1 dans chaque colonne soit: pair (LRC pair) ou impair (LRC impair).

Exemple : ASCII
E 1000101
N 1001110
S 1010011
A 1000001
LRC pair 0011001
LRC impair 0110111
Donc la séquence envoyée avec un LRC pair :
1000101 1001110 1010011 1000001 0011001 14
 Codes correcteurs d’erreur
Codes de contrôle de parité - VRC + LRC
On peut combiner les deux codes :
- rajouter un bit de parité a chaque mot (VRC)
- rajouter un mot de parité a la n d'une séquence de mots (LRC)

Exemple : ASCII VRC pair VRC impair

E 1000101 1 0
N 1001110 0 1
S 1010011 0 1
A 1000001 0 1
LRC pair 0011001 1 0
LRC impair 0110111 1 0

Donc la séquence envoyée avec un VRC pair + LRC impair :

1000101 1 10011100 10100110 10000010 01101110
Remarques
- Aucun code n'est parfait : un code pourra toujours laisser passer des erreurs.
- En cas d'erreur, certains codes permettent de corriger l'erreur. On parle alors de code
15
correcteur.
 Codes correcteurs d’erreur
Codes polynomiaux

Codes CRC (Contrôle de Redondance Cyclique) :

- bits d’un caractère = coefficients d’un polynôme (0 ou 1)
- bloc de k bits = série des coefficients d’un polynôme comprenant k termes de xk-1 à x0
- manipulation des expressions polynomiales avec une arithmétique modulo 2

Exemple : 110001  1 x5 + 1 x4 + 0 x3 + 0 x2 + 0 x1 + 1 x0 = x5+x4+1

Le bloc de k bits de données est considéré comme un polynôme de degré k-1.

Il est divisé par un polynôme dit générateur.

Le reste constitue la clé de contrôle (CRC). Elle est transmise avec le bloc de donnée.

16
 Codes correcteur d’erreur
Calcul du CRC
• Exemple
Soit le message 110111 à protéger par le polynôme générateur x 2+x+1
Au message on associe le polynôme : 1 1 0 1 1 1
1.x5 + 1.x4 + 0.x3 + 1.x2 + 1.x1 + 1.1(x0)
• Etape 1 : Décalage
Le CRC devant être transmis en fin de message, on fait un décalage à gauche
d’autant de bit que le degré maximum du polynôme générateur.
On trouve donc : 1 1 0 1 1 1 0 0
1.x7 + 1.x6 + 0.x5 + 1.x4 + 1.x3 + 1.x2 + 0.x1 +
0

17
 Codes correcteurs d’erreur
Calcul du CRC
Etape 2 : Calcul de la division polynomiale
A l’émission:
Etape 3 : Ajout du CRC
Le reste de la division polynomiale
x7 + x6 + 0 + x4 + x3 + x2 + 0 + 0 x2+x+1 est de degré égal au degré maximum
- ( x7 + x6 + x5 ) x5+x3+1 – 1 du polynôme générateur.
0 0 x5 + x4 + x3 Ici il est donc de deux bits. Reste =
- ( x5 + x4 + x3 ) 1.x + 1.1  CRC = 11. Le mot
0 + 0 + 0 + x2 + 0 + 0 transmis sera donc 110111 11.
- ( x2 + x + 1 )
0+x+1
x7 + x 6 + 0 + x 4 + x 3 + x 2 + x + 1 x2+x+1
A la réception - ( x7 + x 6 + x 5 ) x5+x3+1
On effectue de nouveau la division polynomiale avec 0 0 x 5 + x4 + x3
le même polynôme générateur. - ( x5 + x 4 + x 3 )
Si la transmission est correcte alors le reste sera nul.
0 + 0 + 0 + x2 + x + 1
- ( x2 + x + 1 )
0+0+0
18
 Codes correcteur d’erreur
Les principaux codes polynomiaux utilisés en téléinformatique sont :

-code CCITT V41, polynôme générateur

H(z) = z16 + z12 + z5 + 1
utilisation dans la procédure HDLC (High-Level Data Link Control) protocole de niveau 2
(couche de liaison)

-code CRC 16, polynôme générateur

H(z) = z16 + z15 + z2 + 1
utilisation dans la procédure BSC, avec codage EBCDIC (Extended Binary Coded Decimal
Interchange Code)

-code CRC 12, polynôme générateur

H(z) = z12 + z11 + z3 + z2 + z + 1 ;
utilisation dans la procédure BSC, avec codage sur 6 bits

-code Ethernet, polynôme générateur

H(z) = z32 + z26 + z23 + z22 + z16 + z12 + z11 + z10 + z8 + z7 + z5 + z4 + z2 + z + 1
19
 Codes correcteurs d’erreur
Décodage et correction d’erreurs

Supposons que l’on ait reçu un mot w. Comment retrouver le message transmis ?

1 Si w est un mot du code, on suppose qu’il n’y a pas eu d’erreurs de transmission (cas le
plus probable) et que le mot reçu est correct. On peut alors décoder w.

2 Si w n’est pas un mot du code C, on sait qu’il y a eu des erreurs dans la transmission et
que le mot reçu est erroné.

On recherche alors le mot du code le plus proche de w par la distance de Hamming.

• Si le mot de code le plus proche de w est unique, on remplace w par ce mot de code v :
on a corrigé les erreurs de transmission.
• Sinon, on ne peut pas choisir parmi les mots de code les plus proches : la correction
d’erreur échoue.
20
 Codes correcteurs d’erreur
Distance de Hamming d’un code

On appelle distance de Hamming (ou simplement distance) d’un code C, et on note d(C), la
plus petite distance entre deux mots distincts de C :
d(C) = min{d(w, w’) ; w  C, w’  C, w ≠ w’}
C’est donc le nombre minimum d’erreurs permettant de transformer un mot du code en un
autre mot du code. Plus la distance de Hamming du code est grande, plus les mots du code
sont “dispersés” dans An .
Exemple

Codage par bit de parité

C = {000, 011, 101, 110} La distance de Hamming du code est 2.

Distance d’un code et capacité de correction

Un code C de distance d permet donc de détecter jusqu’ à d − 1 erreurs et de corriger

jusqu’ à (d−1)/2 erreurs.
21
 Codes correcteurs d’erreur
Codes linéaires
Un code linéaire est un code en bloc systématique (n, m) dans lequel les r = n-m bits
de contrôle dépendent linéairement des m bits d'information.
w  w1w2 ...wm  Information utile
w'  w'1 w'2 ...w'm w'm 1...w'm  r  Information codée
w’1 = w1 w’2 = w2 ….. w’m = wm w’m+1 = a1 w’m+2 = a2 …. w’m+r = ar
où les ai sont les bits de contrôle, donc w'  w1w2 ...wm a1a2 ...ar 
Le code est alors défini par la relation matricielle : w'  wG
où G est la matrice génératrice du code. La forme générale de G est:

d'où les bits de contrôle :

ai = w1 p1i + w2 p2i + .... + wm pmi

22
 Codes correcteurs d’erreur
1 0 0 0 1 1
 
Exemple : code (6,3) avec G  0 1 0 1 0 1
 0 0 1 1 1 0
 

information utile : w  w1w2 w3  donc 8 mots possibles

information codée : w'  w1w2 w3 a1a2 a3 

La relation conduit à
a1 = w2 + w3
a2 = w1 + w3
a3 = w1 + w2
Les mots du code sont :

000000 001110 010101 011011

100011 101101 110110 111000

On constate que dm = 3 ce qui permet la détection des erreurs doubles et la correction

23
des erreurs simples.
 Codes correcteur d’erreur
Décodage par tableau standard

0 w1 w2 … wi
e1 e1+w1 e1+w2 … e1+wi e1+C
e2 e2+w1 e2+w2 … e2+wi e2+C
. . . . . . .
. . . . . . .
. . . . . . .
ek ek+w1 ek+w2 … … ek+C

Le décodage d’un mot reçu consiste à le repérer dans le tableau standard

et à le remplacer par le mot du code se trouvant en haut de la même colonne.

24
 Codes correcteurs d’erreur
Considérons le code C(6,3) défini par la matrice génératrice :
M w p(w)
1 0 0 1 0 1 Les mots du code 000 000000 0
  001 110110 4
G  0 1 1 1 0 1
010 011101 4
1 1 0 1 1 0 011 101011 4
 
100 100101 3
La distance minimale de ce code est d=dmin = 3. Donc le 101 010011 3
110 111000 3
code peut détecter jusqu’à 2 erreurs et en corriger une.
111 001110 3
Le tableau standard de décodage de ce code est:
000000 110110 011101 101011 100101 010011 111000 001110
100000 010110 111101 001011 000101 110011 011000 101110
010000 100110 001101 111011 110101 000011 101000 011110
001000 111110 010101 100011 101101 011011 110000 000110
000100 110010 011001 101111 100001 010111 111100 001010
000010 110100 011111 101001 100111 010001 111010 001100
000001 110111 011100 101010 100100 010010 111001 001111
100001 010111 111100 001010 000100 110010 011001 101111
010001 100111 001100 111010 110100 000010 101001 011111
001001 111111 010100 100010 101100 011010 110001 000111

25
 Codes correcteurs d’erreur
Supposons que l’on veuille transmettre le message M =(101). Le mot de code correspondant est :
w = M.G = (010011).
Si le canal introduit une erreur simple, par exemple e = (000100), alors le mot reçut w’ est :
w’ = w + e
w’ = (010011) + (000100)
w’ = (010111)
Le mot reçu est w’ = (010111) se trouve dans la colonne au mot du code (010011)
et celui-ci est correctement décodé : le message décodé est M’ = (101).

Supposons maintenant que la séquence d’erreur comprend deux, par exemple e= (010100).
Le mot reçu cette fois-ci est:
w’ = (010011) + (010100)
w’ = (000111)
Le mot reçu se trouve dans le tableau standard sous le mot du code w = (001110) est incorrectement
décodé en M’ = (111). Ici le nombre d’erreurs, 2, dépasse la capacité de correction du code C(6,3).

La méthode de décodage par tableau standard, quoique simple, est limitée au décodage de très petits
codes linéaires.
26
 Codes correcteurs d’erreur
Matrice de contrôle

Soit C un code linéaire de taille (n, m) ayant une matrice génératrice standard :
G  I m , Pmr 

La matrice de contrôle du code C est la matrice de taille n × (n − m):

 Pmr 

H  P , I nm
T
mr  H  
T


 I n m 
 Pmr 
GH T
 I m , Pmr  0

 I n m 
Le mot binaire w  w1w2 ...wn  est un mot du code C(n,m) ssi: wH  0
T

Soit y un mot reçu. Le syndrome est s(w’) = w’HT

w’ = w+e (e étant l’erreur éventuelle) or par linéarité
w’HT = (w+e) HT = w HT +e HT = e HT (w étant un mot de code)

Le syndrome ne dépend que de l’erreur !

27
 Codes correcteurs d’erreur
Reprenons l’exemple du code C(6,3) M w p(w)
000 000000 0
1 0 0 1 0 1 001 110110 4
  010 011101 4
G  0 1 1 1 0 1 011 101011 4
1 1 0 1 1 0 100 100101 3
  101 010011 3
On peut construire la matrice de contrôle H en 110 111000 3
résolvant le système d’équation linéaire: 111 001110 3

wH T  ( w1 w2 w3 w4 w5 w6 ) H T  (000)
On peut construire la table des syndromes correspondant aux
1 1 0 0 0 1 séquences d’erreurs simple (et la séquence d’erreur double précédent) :
 
H  1 1 0 1 1 0
 0 1 1 0 1 0 s= e HT e s
  000000 000
100000 110
010000 111
001000 001
000100 010
000010 011
000001 100
001001 101
28
 Codes correcteurs d’erreur
Supposons que nous recevions le mot w’ = (010111)
Le calcul du syndrome donne :
1 1 0
  Le syndrome est s = (0 1 0) et la séquence d’erreur
1 1 1
0 correspondante est donc : e = (000100).
0 1 Le syndrome indique qu’une erreur s’est produite à la
s  w' H  (010111)
T
  ( 0 1 0)
0 1 0 quatrième position du mot reçu w’ = (010111)
0 1 1  et que le mot du code transmis est w = (010011) qui
 est finalement correctement décodé par M = (101).
1 0 0 

Conclusion
Le décodage par syndrome requiert la mise en mémoire de 2n-m syndromes de longueur (n-m) et de 2n-m
mots d’erreurs de longueur n, c'est-à-dire 2n-m x (2n -m) symboles binaires. En comparaison, le tableau
standard de décodage nécessitait la mise en mémoire de tous les 2n mots binaires de longueur n.
Pour fixer les idées, le tableau standard de décodage pour un code linéaire binaire C(7,3) contient
27 x 7 = 128 x 7 = 896 bits, alors que le tableau de syndromes pour ce même code ne requiert que
24 x (7+4) = 176 bits.
D’autre part, un code linéaire C(20,10) nécessitera un tableau standard de décodage contenant
220 x 20 = 1 048 576 x 20 = 20 971 520 bits. Le décodage par syndrome ne demande que
210 x (20+10)=1024 x 30 = 30 720 bits pour ce même code. 29