Chapitre III : Couche de liaison codage

et protection contre les erreurs

Cours réseau
L3 ACAD
Pr. Abdelli Abdelkrim

1
 PLAN
1. Liaison de données
2. Détection et correction d’erreurs
3. Généralités sur les codes
4. Codes de blocs
5. Protocoles de liaison de données

2
 III. Liaison de données
La couche liaison de données fournit les moyens fonctionnels
pour faire communiquer deux machines voisines reliées par un
canal de transmission.
Gestion de la liaison (établir, maintenir et libérer une connexion)
et acheminement des données sur la liaison physique. Une
interface de service est donc offerte à la couche réseau.
Elle supervise le fonctionnement de la transmission et définit la
structure syntaxique des messages, la manière d'enchainer les
échanges selon un protocole normalisé ou non. Elle détecte et
corrige, si possible, les erreurs de transmission.
Contrôle de flux pour réguler la quantité de données échangées et
éviter la saturation du récepteur qui peut être lent par rapport à
l’émetteur.

3 III. Liaison de données

Pour atteindre ces objectifs, la couche liaison prend les
paquets qu’elle reçoit de la couche réseau et les encapsule
dans des unités appelées trames. La structure d’une trame est
variable selon le protocole utilisé, mais souvent, elle contient
un entête (header), un champ de données destiné au paquet
reçu et une terminaison de trame (en-queue ou trailer).
Expéditeur Récepteur

Paquet Paquet

Trame

En-tête Paquet En-queue En-tête Paquet En-queue

(données) (données)

Figure 3.1 : Encapsulation de paquets dans des trames.

4 III. Liaison de données

 III.2. Détection et correction d’erreurs
 Les canaux de transmission entraînent souvent des erreurs. Le taux
d'erreur moyen sur une liaison est de l'ordre de 10-5..10-8.
 La couche physique assure le transport de flux de bits sur le support de
transmission et leur remise à la station destination. Ces flux de bits
peuvent comporter des erreurs : Le nombre de bits reçus peut être
inférieur, égal ou supérieur au nombre de bits émis ; les bits peuvent
également avoir changé de valeur. La couche liaison doit détecter ces
erreurs et les corriger si nécessaire. Ces erreurs dépendent :
 Du nombre de répéteurs
 Du support de transmission
 Du débit, du type de codage modulation…

5 III.2. Détection et correction d’erreurs

III. 2.1 Méthodes simples de détection des erreurs
a. Vérification par répétition
Elle consiste à faire suivre le message d’une réplique du
message d’origine, à la réception.
Le récepteur compare les deux copies, et 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 en procédant à la
correction, en envoyant un nombre impair 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 renvoie une copie à l’émetteur
pour vérification.

6 III.2. Détection et correction d’erreurs

b.Echoplex : Cette méthode permet théoriquement 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

7 III.2. Détection et correction d’erreurs

III.2.2 Méthodes de correction par acquittement
Dans ces méthodes, chaque trame à transmettre est
augmentée par une autre suite de bits dite bits de redondance
ou somme de contrôle (checksum) FCS ou encore total de
contrôle. Ainsi, pour chaque suite de k bits transmise, on
ajoute r bits.
On dit alors que l’on utilise un code C(n,k) avec n=k+r , où n
est la taille du code et k la taille de l’information utile.
À la réception, les bits ajoutés permettent d’effectuer des
contrôles à l’arrivée. Dans le cas d’une réception sans
anomalie, il suffira d’extraire l'information utile.

8 III.2. Détection et correction d’erreurs

III.2.2 Méthodes de correction par acquittement
Les concepteurs de réseau ont développé deux stratégies dans le
domaine de correction des erreurs de transmission :
 La première consiste à inclure dans les blocs de données transmis
suffisamment de redondance pour que le récepteur soit capable de
restituer les données originales à partir des données reçues. Cette
stratégie utilise des codes correcteurs d’erreur (Error Correcting
Codes, ECC).
 La seconde consiste à ajouter juste assez de redondance dans les
données à transmettre pour que récepteur puisse détecter les erreurs
et demander alors la retransmission des trames erronées. Cette
stratégie utilise des codes détecteurs d’erreur (Error Detecting
Codes, EDC).
 La correction par retransmission est préférée dans les réseaux où le
taux de perte est faible et le délai de retransmission tolérable, car son
surcoût est généralement plus faible que celui induit par les codes
9 auto-correcteurs.
III.2. Détection et correction d’erreurs
  Sur les canaux fiables, comme la FO, on utilise un CDE d’erreurs et
on retransmet un éventuel bloc de données défectueux. Sur des
réseaux sans fil où les erreurs sont courantes, on utilise suffisamment
de redondance pour permettre au récepteur de trouver le bloc
d’origine.
 Dans les deux stratégies, un message d’acquittement appelé « ACK »
est systématiquement envoyé à la réception d’un bloc ou de plusieurs
blocs (acquittement groupé). L’ACK est dit positif si le ou les blocs
ne comportent pas d’erreurs et négatif sinon ; dans ce cas l’émetteur
réémet les blocs erronés.
 Pour le cas où l’ACK ou le message est perdu, on implémente un
temporisateur qui s’enclenche dès que le message est envoyé : si
après « tmax » secondes l’ACK n’a pas été reçu, on conclut que soit
le message ou l’ACK a été perdu. On procède par conséquent au
renvoi du message. Toute la difficulté réside en l’estimation du temps
maximal d’un allée-retour RTT (Round trip Time) déterminant la
valeur « tmax ».
10 III.2. Détection et correction d’erreurs
11 III.2. Détection et correction d’erreurs
 III.3. Généralités sur les codes
III.3.1 Définitions Générales
 Rappel sur les opérations binaires
 Somme modulo 2 00=0 01=1 10=1 11=0
 Multiplication 0.0=0 0.1=0 1.0=0 1.1 =1
Définition 1: On appelle un code de longueur n, noté C(n,k) telle
que n est la taille du code et k est la taille de l’information, un
ensemble C de séquences de n bits (mots distincts), construits sur
l’ensemble {0,1}.
 Une séquence de n bits est dite un mot de code.
 Un mot de code de n bits n'appartenant pas à C sera dit invalide.
 Un code C(n k) contient 2k mots de codes valides.
Exemple : Soit un code C(4,2) : { 0010 1000 0111 1110 };
la séquence 1001 définit un mot de code invalide.
12 III.3. Généralités sur les codes
 A la réception d'une séquence de n bits, deux cas sont possibles :
La séquence correspond à un mot du code et la transmission sera
considérée comme étant correcte (on n'est pas sûr de l'exactitude
de la transmission).
La séquence n'est pas valide. Dans ce cas, on est en présence d'une
erreur (c'est une certitude), et le récepteur peut alors soit corriger
l'erreur (CCD), soit demander une retransmission (CDE).
Example : Soit le code C(4,2) : { 0010 1000 0111 1110 }.
A l’émission : On veut transmettre 00, on récupère son code 0010.
Erreur de transmission : 1er cas 0010 0000 (erreur simple)
2ième cas 0010 1110 (erreur double)
A la réception, on vérifie si le mot est valide (si appartient au code)
1er cas : erreur mot non valide (erreur détectable)
2ième cas : Pas d’erreur mot valide (erreur non détectable)
13 III.3. Généralités sur les codes
 Définition 2 On appelle:
 Distance de Hamming : C’est le nombre de bits en lesquels 2 mots
d’un code diffèrent.
 Distance de Hamming minimal d’un code : On appelle distance de
Hamming minimale, notée Dhmin, d’un code C, le minimum des
distances entre 2 mots quelconques de ce code.
Exemple : M = 10001001 et M’ = 10110001 => Dhmin(M, M’) = 3.
10001001
10110001
00111000
 La Dhmin d'un code C(n,k), est obtenu en comparant ses 2k mots de
code valides. Exemple: { 0010 1000 0111 1110 } Dhmin =2.
 Dhmin d'un code permet d'évaluer son pouvoir détecteur d'erreurs,
ainsi que son pouvoir correcteur. En effet, si la Dhmin entre deux
mots de code est d, il faut d erreurs pour transformer un mot en un
14 autre.
III.3. Généralités sur les codes
 Théorème : Soit un code C(n,k) tel que si sa Dhmin est égale à :
 2d+1 alors la détection est d’ordre 2d et la correction est d’ordre d.
 2d alors la détection est d’ordre 2d – 1 et la correction est d’ordre d –1.
Exemple : {0010 1000 0111 1110} Dhmin=2  détecte une erreur et
corrige 0. Considérons le code suivant :
{0 0000 ; 11111}, k = 1, n= 4. Ce code possède 3 bits de contrôle.
On a Dmin= 4. La détection est d’ordre 3 et la correction est d’ordre 1.
 On envoie: 0000 erreur de transmission simple  1000
A l’arrivée: 1000 on peut corriger en  0000
1000 (mot invalide)  (0000 ou 1111) ?
 On envoie: 1111 erreur de transmission double  0011
A l’arrivée: 0011 on ne peut pas corriger en  1111
0011 (mot invalide)  (0000 ou 1111) ?

15 III.3. Généralités sur les codes

 Définition 3 (Efficacité d’un code) : L’efficacité d’un code
est d’autant meilleure que les mots du code sont plus
distincts les uns des autres. Elle dépend de la distance
minimale de Hamming entre les différents mots de codes.

Plus l’efficacité est proche de 1, plus le code est performant.

Définition 4 : Soit X le bloc émis et X’ le bloc reçu. On
appelle vecteur d’erreur . Si E = 0, alors il n y pas d’erreur.
Si E  0, il y a une erreur, localisé sur les bits 1 de E.
 Exemple : 0000 =1000+ E  E=1000
1111 = 0011 + E  E=1100
16 III. Liaison de données
 III.4. Codes de blocs
L’information transmise est découpée en blocs de k bits, puis on leur
rajoute r bits de redondance. On crée alors un code de bloc de longueur
n=k+r. Sur 2n combinaisons possibles, seules 2k combinaisons sont
valides. Les bits de redondance sont calculés de différentes méthodes.
III.4.1 Méthode basée sur la parité
a. Parité transversale (ou verticale) VRC
 L'information est sectionnée en blocs de k bits qui sont généralement
des caractères, puis on ajoute à chaque bloc un bit de parité (r=1) de
telle sorte que la somme des k+1 bits modulo 2 soit nulle (parité
paire) ou égale à 1 (parité impaire).
Exemple : Envoi d’un bloc de 4 caractères de longueur 3 (k=3) :
 Information utile : 110 001 011 000.
 Information envoyée : 1100 0011 0110 0000.
VRC permet de détecter une erreur simple sur chacun des mots transmis.
17 III.4. Codes de blocs
  Parité longitudinale (ou horizontale) LRC/VRC: On combine
généralement la parité transversale et la parité longitudinale de la
façon suivante : les caractères munis de leur bit de parité
transversale sont regroupés en blocs, et on ajoute à la fin de
chaque bloc un caractère supplémentaire pour la parité
longitudinale. Ce contrôle est appelé Vertical Redundancy
Checking / Longitudinal Redundancy Checking, LRC/VRC.
Exemple : Envoi d'un bloc de 4 caractères avec contrôle LRC/VRC :
 Information utile : 110 001 011 000.
 Information envoyée : 1100 0011 0110 0000 1001.

18 III.4. Codes de blocs

Comme une erreur simple modifie simultanément la parité
d’une ligne et d’une colonne, la correction est possible en
inversant le bit situé à l’intersection de la ligne et de la
colonne ayant une parité incorrecte.
Exemple :
10110011 10111011
10100011
01101010 01101010
01101010 10011010
10001010
1 0 0 0 01 0 1 0 01001011 01001011
01001011 
On peut corriger Impossible de corriger Fausse
correction
(Erreur simple) (Erreur double) (Erreur
quintuple)
19 III.4. Codes de blocs
 III.4.2 Codes polynomiaux
Ce sont des codes de blocs très utilisés dans la pratique car
facilement implantables et qui donnent d'excellents résultats.
On considère que les bits d’une séquence sont les coefficients
d’un polynôme. Ces coefficients ne prennent que les valeurs 0
ou 1. Un bloc de n bits est vu comme la série de coefficients
d’un polynôme de n termes, allant de xn-1 à x0. Un tel polynôme
est dit de degré n-1. Le bit le plus à gauche (fort) est le
coefficient de xn-1, son voisin est le coefficient de xn-2, ainsi de
suite. :
P(x) = pn-1 xn-1 + pn-2 xn-2 + ... + p1 x + p0 x0 (pi {0,1})
Par exemple, la séquence "001101" comprend 6 bits. Elle peut
être représentée par un polynôme à 6 termes dont les
coefficients sont 0, 0, 1, 1, 0 et 1, ce qui donne le polynôme :
x5.0+x4.0+x3.1+x2.1+x.0+x0.1= x3+x2+1
20 III.4. Codes de blocs
 Remarque : Sur les polynômes, nous utilisons les opérations
d'addition et de multiplication modulo 2 (une addition ou une
soustraction équivaut à un OU exclusif). 1+1=1-1 =0 ; 1-
0=1+0=1.
Formellement, supposons un code C(n, k). L’information utile
est représentée par le polynôme Z(x). Z(x) est au maximum de
degré (k-1) puisque l’information comporte k bits :
Z(x)= uk-1 xk-1 + ...+ u1 x + u0 x0. (ui {0,1})
Pour utiliser un code polynomial, l’émetteur et le récepteur
doivent d’abord se mettre d’accord sur le choix d’un polynôme
générateur. Pour des raisons pratiques, les coefficients de poids
fort et faible du générateur doivent être égaux à 1. Soit G(x) un
polynôme de degré r=n-k appelé polynôme générateur.
G(x)= gr xr + ...+ g1 x + g0 x0. (gi {0,1}) gr-1 = g0 =1

21 III.4. Codes de blocs

 Codage à l’émission :
 Il faut multiplier Z(x) par xr pour créer un décalage à gauche de r bits.

Exemple : Soit un code C(11,7). Nous considérons, Z(x)  1011011, on

multiplie par x4 et on obtient : 10110110000.
 On divise le produit obtenu par G(x) ; on obtient:
Z(x) xr = Q(x) G(x) + A(x) Où :
Q(x) : polynôme quotient.
A(x) : polynôme reste de la division, au maximum de degré : r-1.
 Donc on obtient le mot de code à envoyer, représenté par le polynôme de
degré n-1 suivant :
Y(x) = Z(x) xr +A(x) = Q(x) G(x)
 On envoie la séquence de bits de longueur n=k+r associée au polynôme
Y(x). La séquence envoyée est construite en collant (rajoutant) à
l'information utile, le total de contrôle représenté par A(x). Le polynôme
Y(x) obtenu est aussi divisible par G(x). Il en résulte que les mots valides
du code polynomial C(n,k) sont donc les polynômes multiples de G(x).
22 III.4. Codes de blocs
 Exemple :
Soit le code C(9,6) avec G(x)= x3+1.
On veut transférer l'information "001101".
Z(x) = x3+x2 +1.
Z(x).x3 = x6+x5+x3
On divise Z(x).x 3 par G(x), on obtient :

Z(x) . x3 = G(x) . Q(x) + A(x), avec A(x)=x2 et Q(x)=x3+x2.

D'où : Y(x) = Z(x) . x3+ A(x) = x6+x5+x3+x2.

Le polynôme Y(x) correspond à la séquence : 001101100
A(x) doit être écrit sur r bits. Si A(x)=x on l’écrit 010 et non
10.
23 III.4. Codes de blocs
 Décodage à la réception :
 A la réception, un calcul semblable s'effectue sur le mot reçu, mais il
faut, ici, que le reste soit nul. Dans le cas contraire, c'est qu'une erreur
est survenue en cours de transmission.
 Soit Ÿ(x) le polynôme de degré n-1 dénotant le mot de code reçu.
On calcule le polynôme syndrome S(x) de degré r-1 :
S(x) = Ÿ (x) MOD[ G(x)]
 Aucune erreur n’est détectée si le syndrome S(x) =0. Sinon elle est
détectée si S(x)≠ 0. La détection d'erreur consiste à vérifier que le
mot reçu est bien un mot du code C(n,k) c'est-à-dire que Ÿ(x), est
divisible par G(x).
 Si le polynôme est divisible par G(x), alors il suffit alors d'extraire
l'information utile en supprimant les r derniers bits de la séquence
reçue. Si le polynôme n'est pas divisible par G(x), alors une erreur a
eu lieu pendant la transmission et le récepteur demandera une
retransmission du message.
24 III.4. Codes de blocs
 Exemple : On envoie la séquence de bits"001101100". On remarque
bien que cette séquence est construite en concaténant à
l'information utile "001101« , la séquence "100" qui correspond à
la redondance.

25 III.4. Codes de blocs

 Circuit logique d’un codeur polynomial :
La division se fait à l’aide d’un circuit logique appelé diviseur bâti autour
d'un registre à décalage. Le registre est constitué de r bascules ar-1, …, a0,
représentant les bits de contrôle, liés par des opérateurs de OU exclusif .
Les coefficients du polynôme Z(x) sont injectés dans le circuit un à un, à
chaque cycle d’horloge, commençant du coefficient le plus fort au plus faible.
 Initialement, les registres ai sont à zéro. Chaque coefficient en entrée est
sommé avec le bit ar-1. La sortie de cet opérateur va en entrée vers a0. Si dans
le polynôme G(x), le coefficient de xi est égal à 1, une branche de la sortie xi
 ar-1 est créée en entrée de l’opérateur OU exclusif mis avant la bascule du
bit ai-1. Après le passage des k bits de Z(x) en k cycle horloge, le calcul est
achevé et les registres ai contiennent les coefficients du polynôme A(x).

26 III.4. Codes de blocs

 + a2 + a1 + a0
u2
u1
u0

Exemple : Soit un code C(7,4) avec G(x) = x3 + x2 +1

1101 000 c’est équivalent au reste de la division Z(x) x3 /
g(x)
01
ui ui+a2 a0 a1 a2 00 010 00
0 0 0 01
1 1 1 0 1
1 0 0 1 0
0 0 0 0 1
1 0 0 0 0 0
1 0 01
1

27 III.4. Codes de blocs

  Le reste de la division est égal à : 000 et le mot codé à : 1101 000.
 Pour la vérification, on utilise le même circuit en faisant passer tous
les bits du mot reçu. Si le reste est égal à 0 alors il n y a pas d’erreur
détectable. Sinon le mot reçu est erroné et on demande à le
retransmettre.
Propriétés des codes polynomiaux
Soit Y(x) un mot envoyé, et Ÿ(x) le mot reçu correspondant tel que
Ÿ(x)=Y(x)+E(x). On a alors les propriétés suivantes :
 Toute erreur simple est détectée si G(x) comporte plus d’un coefficient
non nul (C’est pour cela que g0=gr=1).
 Les erreurs doubles sont toutes détectées si G(x) ne divise pas xi+1 où
i appartient à {1, n-1}, n étant la taille du code.
 L’erreur sur un message comportant un nombre impair d’erreurs est
toujours détectée si le polynôme générateur G(x) est divisible par (x+1).
 Un code polynomial détecte toutes les salves (suite d’erreurs), de
longueur inférieure ou égale à r avec r le degré de G(x).
28 III.4. Codes de blocs
 Polynômes générateurs utilisés : Le choix du polynôme
générateur est très important : de lui dépendra le pouvoir de
détection de certains types d'erreur de transmission. Les
principaux polynômes utilisés :
LRCC-8 : x8+1
LRCC-16 : x16+1
CRC 12 : x12 + x11 + x3+ x2 + x + 1
CRC 16 Forward : x16+x15+x2+1
CRC 16 Backward : x16+ x14+x + 1
CRC CITT Forward : x16+ x12+ x5 + 1
CRC CITT Backward : x16 + x11 + x4 +1
CRC-32= x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x
+1.
29 III.4. Codes de blocs
 Pour corriger, on utilise des polynômes avec des propriétés
particulières. :
Exemple: Codes cycliques, codes BCH (Bose, Ray-Chaudhuri
et Hocquenghem); Codes de Reed Solomon.

30 III.4. Codes de blocs

 III.5. Protocoles de liaison
Les processus correspondant aux couches physiques et liaison s’exécutent sur
un processeur situé sur une carte d’E/S (carte réseau). Le contrôle d’erreur
est effectué par des circuits électroniques (hardware).
III.5.1 Principe général d’un protocole de liaison
 Une connexion de liaison de données est réalisée entre deux machines
adjacentes dans le réseau, donc sans nœuds intermédiaires entre elles.
 La couche liaison reçoit de la couche réseau des données sous forme de
paquets, et son rôle est de délivrer les paquets à la couche réseau voisine.
 Chaque paquet reçu, est encapsulé dans une trame en lui ajoutant un entête
et un en-queue. L’en-queue contient des informations de contrôle destinées à
la détection d’erreur. La trame est ensuite envoyée vers la machine voisine.
 Lorsque le récepteur reçoit une trame, le matériel calcule le total de
contrôle. S’il est incorrect (erreur de transmission), la couche liaison en est
informée avec une erreur de checksum; sinon elle reçoit la trame. Puis
après vérification qu’elle est bien le destinataire (adresses physiques de
l’entête), elle décapsule le paquet et le transmet à la couche réseau.
31 III.5. Protocoles de liaison
 Algorithme
Début
Tant que vrai Faire
Capturer(evt);
Cas evt=réception_paquet_de_réseau
récupérer_de_couche_réseau(paquet);
construire_entête(e); crc=calculer_crc(); trame;=encapsuler(paquet);
vers_couche_physique(trame);
Cas evt=arrivée_trame
réception_trame récupérer_de_couche_physique(trame);
crc=calculer_crc();
Si erreur_checksum alors envoyer_ack_negatif();
Sinon
paquet=désencapsuler(trame);
envoyer_vers_couche_reseau(paquet);
envoyer_ack_positif();
Fin Cas;
Fin III.5. Protocoles de liaison
32
 1. Récupérer un paquet délivré par la 1. Récupérer une trame à l’aide de la
couche réseau en utilisant la procédure procédure
récuperer_de_couche_réseau(paquet) récupérer_de_couche_physique(trame)
2. construire_entête(e), Construire la 2. Désencapsuler la trame et envoyer les
trame correspondant au paquet reçu, en données récupérées (paquet) vers la
utilisant les procédures puis encapsuler couche réseau en utilisant la procédure
(paquet). Eventuellement, ajouter une envoyer_vers_couche_réseau (paquet)
en-queue.
3. Envoyer la trame construite avec la
procédure vers_couche_physique()

33 III.5. Protocoles de liaison