Chapitre 4 Codage et Protection contre les erreurs

1. Codage et représentation de l’information textuelle :

Un code est caractérisé par sa longueur, qui n’est autre que le nombre de bits représentant chaque caractère. Les
codes les plus fréquents en téléinformatique ont des longueurs de 5, 6 ou 7 ou 8 bits permettant de coder
respectivement 32, 64, 128 ou 256 caractères différents.

 Code CCITT (comité consultatif international télégraphique et téléphonique-) Ce code, encore appelé code
Baudot est utilisé pour la transmission sur le réseau télégraphique (TELEX). C’est un code à 5 bits qui ne
permet donc que 32 combinaisons
 Code DCB (décimal code binaire) ce code à 6 bits a été très utilisé pour la transmission avec des terminaux
asynchrones.
 Code CCITT n°5 à 7 bits, appelé aussi code ASCII (American Standard Code for Information Interchange)
ou encore alphabet international n°5 est très utilisé et permet de coder 128 caractères
 Code EBCDIC ce code (Extended Binary Coded Decimal Interchange Code) à 8 bits et très utilisé du fait
que chaque caractère est représenté par un octet.

La transmission de données entre machines distantes s’effectue en général en série par bit et la communication
entre équipements informatiques donne lieu à l’échange de messages qui comportent un nombre variables de
bits. Les messages qui constituent la partie utile de l’information sont complétés par des informations de contrôle
et de supervision telles que l’adresse du destinataire et une séquence de contrôle d’erreurs.
Entete (header) + texte (text) + terminaison (trailer).

2. Problématique:
Nous avons vu dans le chapitre précédent que les lignes de transmission n’étaient pas parfaites et que des erreurs
pouvaient être introduites sur les symboles d’une suite binaire. Les origines de ces erreurs peuvent être recensées
et dépendent :
- du nombre de répéteur
- du support de transmission
- du débit, du type de codage, modulation ...

L’objet de cette partie est de décrire les méthodes couramment utilisées pour protéger les informations émises
des erreurs de transmission. La stratégie d’utilisation du codeur et du décodeur dépend de l’ensemble du système
de transmission de données.
- Cette stratégie d’utilisation est une simple détection lorsque les symboles sont restitués au collecteur avec une
alarme dès que le décodeur détecte une erreur. Cette erreur peut faire l’objet d’une correction d’erreurs mais
deux cas apparaissent :
- Le décodeur corrige automatiquement certaines erreurs : Correction d’erreur directe.
- Le décodeur ne peut que détecter les erreurs et il est donc nécessaire de retransmettre une partie des données
pour réaliser la correction. Cette stratégie est une correction par retransmission.

3. Méthodes simples de détection et de corrections des erreurs :

a) vérification par répétition :

Consiste à faire suivre le message d’une réplique du message d’origine, à la réception. Le récepteur compare les
deux copies, il est accepté que s’il y ‘a identité. Dans le cas contraire, il est demandé à l’émetteur de
retransmettre le message.
On peut améliorer cette méthode on procédant à la correction, on envoyant un nombre impaire de copies au
récepteur, le récepteur détermine le nombre majoritaire de copies identiques et les considère comme étant le
message d’origine ou au pire des cas, il renvoie une copie à l’émetteur pour vérification.

b) le mode Echoplex :

Ce mode permet dans le cas d’un mécanisme de transmission le plus élémentaire d’échanger des informations
entre deux machines informatiques avec un taux d’erreur nul. Lors d’une communication, les caractères transmis
d’une machine vers une autre sont retransmis à l’arrivée vers la machine émettrice. De ce fait, si une erreur se
produit dans la transmission ou la retransmission le caractère en erreur est automatiquement détecté et
retransmis. Le mécanisme des échanges est montré par la figure ci-dessous
c) Méthodes de corrections des erreurs par retransmission : concepts de base
Consiste à renvoyer, à chaque réception d’un message de données M, un message court appelé ‘ACK’ qui est
positif si le message ne comporte pas d’erreurs et négatifs sinon dans ce cas l’émetteur ré-émet le message.

Inconvénients:
Cas où l’ACK est perdu : dans ce cas on implémente un temporisateur qui s’enclenche dés que le message est
envoyé, si après ‘ t’ secondes l’ACK n’a pas été reçu, on conclue que le message a été perdu ou que l’ACK a été
perdu. On procède au renvoi du message.

Problématique: difficulté d’estimer le temps de transfert.

3.5 La détection d’erreur par vérification de la parité par caractère

Dans ce mode de fonctionnement, les caractères transmis sont automatiquement codés avec un bit de contrôle
relevant d’une parité paire ou impaire.
Dans le cas d’une parité paire, ce bit est positionné à 0 si le nombre d’éléments binaires positionnés au niveau 1
dans le mot est pair et il est positionné à 1 si ce nombre est impaire.

Exemple: En utilisant un code 7 bits du CCITT (code n° 5), on peut utiliser le 8 ième bit comme bit de parité.

Suite binaire sur 7 bits Parité paire parité impaire

A 1000001 10000010 10000011
E 1010001 10100011 10100010
V 0110101 01101010 01101011

Cette solution permet de détecter une erreur simple sur chacun des mots transmis, mais dès que ce nombre est
excédé il est impossible de détecter des erreurs avec certitude.
Cette méthode ajoute 1 bit tous les 7 bits transmis. Le rendement de la transmission est donc de:

R 7 = 87%
8
où, R= Nombre de bits utiles/Nombre total de bits transmis

Une amélioration à ce système peut être apportée en transmettant tous les n caractères un caractère de contrôle
sur les n précédents : Contrôle de parité vertical.

A 1000001 10000010
B 1000010 10000100
C 1000011 10000111
D 1000100 10001000
E 1000101 10001011
F 1000110 10001101
G 1000111 10001110
H 1001000 10010000
Contrôle 0001000 00010001

Cette méthode ajoute 1 bit tous les 7 bits transmis et 8 bits tous les 8 mots transmis. Le rendement de la
transmission est donc de :

R  7*8 = 77 %
(7+ 1) * 8+ 8
Exemple:

Exemple d'envoi d'un bloc de 4 caractères à 3 bits chacun avec un contrôle LRC/VRC (pour
Vertical Redundancy Checking / Longitudinal Redundancy Checking):
Information utile : 110 001 011 000,
Information envoyée : 1100 0011 0110 0000.1001

LRC

VRC

Principe : une erreur simple modifie simultanément la parité d’une ligne et d’une colonne.
Correction : inverser le bit situé à l’intersection de la ligne et de la colonne ayan une parité incorrecte.

Exemple:

10100011
01101010
10001010
01001011

3.7 Codes linéaires systématiques

Définition 1: On appelle un code noté C(n,k) telle que n est la taille du code et k est la taille de l’information,
un ensemble de mots distincts construits sur l’ensemble {0,1}.
Exemple: Un code C(4,2) : 0010 1000 0111 1110

Définition2 : On appelle un code linéaire C(n,k) un code linéaire systématique un code tel que les (n-k) bits de
contrôle sont obtenues par combinaison linéaire des k bits d’info utile.
Formellement:
Soit X  x1  xn  le mot de code à générer

Soit U=(u1, .. ,uk) est le vecteur d’information utile.

Soit A le vecteur de contrôle A= (a1,..an-k). alors ai=  u1+2i u1+..+ki uk.

X=(u1,.....,uk,,a1,..,an-k)

Ces combinaisons linéaires peuvent être formulées par un produit matricielle : X =U G

La matrice G est une matrice de dimension (k, n), de la forme (Ik, P ) avec P de dimension (k,r) avec r=n-k

11 12 1k

21 22 2k
P

r1 r2 rk

1) Codage.

Soit la matrice génératrice d’un code G de dimension k  n vérifie

Le calcul du mode de code X est effectuée par : U  G  X .

Le sous-produit matriciel. U A calcule les bits de contrôle.

1 0 0 0 1 1
 
Considérons le code (n = 6, k = 3) défini par la matrice. G   0 1 0 1 0 1  .
 0 0 1 1 1 0
 

Considérons un bloc de données U décrivant toutes les entrées possibles:

0 0 0 0 0 0 0 0 0
   
0 0 1 0 0 1 1 1 0
U  X 
        
. On calcule .
   
1 1 1 1 1 1 0 0 0 
  

2) Décodage.

Soit Y le vecteur du mot de code reçu.

La vérification de l’intégrité de Y ( si X=Y) se fait par le calcul du syndrome S :
Le vecteur syndrome du vecteur Y est S(Y)=Y  H, tel que H est une matrice de dimension (n, n-k).
H est appelée matrice de décodage ou matrice de contrôle et est définie par :

P
H= In-k

On a S(Y)=0, (vecteur nul) si Y appartient au code. En revanche, si on introduit une erreur, Y  X E

avec E le vecteur d’erreur, alors S(Y)= S(E) car S(X)=0.

Localisation d’erreur:
Si S(Y)=0, alors il n’y a pas d’erreur et Y=X.

Il y a au moins une erreur, si S(Y) 0

On peut localiser une erreur simple en recherchant la ligne identique à S(Y) dans la matrice H. La position
de l’erreur dans Y correspond au rang de la ligne trouvée. On peut ensuite la corriger.

0 1 1
 
1 0 1
1 1 0
Poursuivons notre exemple avec la matrice H    et Y = (0 0 1 1 1 0)..
T

1 0 0
0 1 0 

0 0 1 

 On vérifie : S(Y)=(0,0,0) . Supposons qu’une erreur se produise sur le second bit, on reçoit

Y= 0 1 1 1 1 0. On calcule alors le syndrome S(Y)=(1,0,1) qui correspond à la deuxième ligne de H ;

l’erreur est localisée et peut être corrigée.

Application 1:
Un code linéaire a pour matrice de contrôle

1 1 0
0 1 1
H= 1 0 0
1 0 0
0 1 0
0 0 1

a. Préciser la longueur n des mots de code et la longueur k des mots d'information.

b. Les messages suivants sont-ils des mots du code ?
o m1 = (1 1 1 0 1 1)
o m2 = (1 0 0 1 1 0)
c. Donner la matrice génératrice du code et le codage de chaque mot d'information.

Application 2:

Soit le code linéaire C7,4 qui au vecteur d'information i = (i1,i2,i3,i4) associe le mot de code c=
(i1,i2,i3,i4,c5,c6,c7) avec c5 = i1+i3+i4, c6 = i1+i2+i3, et c7 = i2+i3+i4.
a. Donner la matrice génératrice et la matrice de contrôle de ce code
b. Soit i = (1 0 1 0), quel est le mot de code associé ?
c. Soit le message m = (1 1 1 1 0 0 1). Est-il un mot du code ?