Les codes autocorrecteurs
Principe d'un code autocorrecteur
Les codes autocorrecteurs
Dans les systèmes autocorrecteurs, on
substitue au mot à transmettre (mot naturel)
un nouveau mot (mot code), tel que deux
mots codes successifs diffèrent de d bits, où d
est appelé distance de Hamming.
1
Distance de Hamming de 2 mots
Il s’agit du nombre de bits qui diffèrent entre
deux mots de code x et y.
1000 1001
10 110001
= 0011 1000
Donc Dist(x,y) = 3
Distance de Hamming d’un code
Soit C un code (détecteur et/ou correcteur)
Distance de Hamming du code C
Distmin(C) = min { Dist(x,y) } tel que xC , yC et x≠y
Il s’agit du minimum des distances de Hamming entre les
mots du code
– Tous les mots du code sont au moins à une distance Dist(C)
2
Capacité d’un code
Pour qu’un code soit capable de détecter k
erreurs, sa distance de Hamming doit être égal
à k+1.
Pour qu’un code soit capable de corriger k
erreurs, sa distance de Hamming doit être égal
à 2*k+1.
Exemple :
Distance de Hamming = 3
– peut détecter 1 ou 2 erreurs
– peut corriger 1 erreur
3
Code de Hamming
Considérons un mot binaire de données de taille
n
d=(d1,d2,d3,...,dn)
Insertion dans d de k bits de contrôle pi aux
positions
20, 21, 22, 23, ... c'est-à-dire 1, 2, 4, 8, ...
Soit s le mot à transmettre de taille m=n+k
s = (s1,s2,s3,...,sj,..., sn+k ) = (p1,p2,d1,p3,d2,d3,...,pi,...,dn)
Le nombre de bits de contrôle est le premier
entier k supérieur à log2(m).
– Ex. : log2(11) < 4 donc k=4 et n=7
Code de Hamming
Calcul des bits de contrôle
– Le bit de donnée sj est contrôlé par les bits dont les
positions sont les coefficients de la décomposition
binaire de j.
– Le bit de contrôle pi (en position i) est choisi de telle
sorte que la somme des bits qu'il contrôle (ainsi que
lui-même) fasse 0 modulo 2 (contrôle de parité).
Détection et correction d'erreur
– à la réception d'un message, on effectue le contrôle
de parité sur le bits de contrôle
– si pa et pb (qui correspondent respectivement à sA et
sB )sont faux, alors il y a une erreur sur le bit sA+B qui
peut être corrigée !
4
Code de Hamming
Exemple de calcul des bits de parités dans le
code de Hamming (11,7)
Exemple
5
Code de Hamming
Exercice : Code de Hamming (11,7)
Quels sont les bits qui contrôlent s11 ?
Quels sont les bits contrôlés par p1, par p4 ?
Calculer le code de Hamming du mot 1101011
?
Code de Hamming
Correction
le bit s11= d7 est contrôlé par p1, p2 et p4 (11 =
1 + 2 + 8)
p1 contrôle s3+s5+s7+s9+s11 ; p4 contrôle
s9+s10+s11
d = 1101011 ; s = p1.p2.1.p31.0.1.p4.0.1.1 =
00101010011
6
Code de Hamming
Exercice : Code de Hamming (11,7)
Quels sont les bits qui contrôlent s11 ?
Quels sont les bits contrôlés par p1, par p4 ?
Calculer le code de Hamming du mot 1101011
?
On reçoit le message suivant 11111011100 ?
– Y-a-t-il une erreur ? Si oui, corriger cette erreur !
Code de Hamming
Correction
s' = 11111011100 (après réception)
– p1 faux, p2 faux, p3 faux et p4 ok
– erreur sur le bit d'indice 1+2+4=7
– s = 11111001100 (après correction)
– d = 1100100 (mot reçu)
7
Stratégies de protection
Stratégies de protection contre les erreurs de
transmission
Contrôle de flux
8
Problème
Supposons que A soit un ordinateur et B une
imprimante lente, dotée d’une capacité
mémoire limitée, lui imposant de garder en
mémoire toutes les informations envoyées par
A tant qu’elles ne sont pas imprimées.
Si le rythme d’envoi des informations est
nettement supérieur à son rythme
d’impression
– il y a rapidement saturation de la mémoire et
perte d’informations par B.
Problème
9
Introduction
Il faut mettre en place un mécanisme de
contrôle du rythme d’envoi des informations
vers le récepteur, appelé contrôle de flux.
Introduction
Le contrôle de flux : l’émetteur ne doit
envoyer des trames que si le récepteur est
en mesure de les traiter.
10
Les protocoles ARQ
ARQ ( Automatic Repeat reQuest) : l'émetteur
attend des acquittements positifs ou négatifs ;
le récepteur détecte les erreurs, et selon le
cas, ignore la trame ou demande sa
retransmission.
Deux types de protocoles ARQ :
– protocoles « envoyer et attendre » (send and wait)
– protocoles « continus » (continuous ou pipelined
ARQ) ou « à fenêtre d'anticipation ».
Protocoles ARQ «envoyer et attendre»
But : empêcher l'émetteur d'envoyer des
données plus rapidement que le récepteur ne
peut les traiter.
Méthode :
– Obliger le récepteur à informer l'émetteur de son
état →acqui ements.
– Côté émetteur : envoyer et attendre.
11
Protocoles ARQ «envoyer et attendre»
Trame erronée : acquittement positif ou négatif
Protocoles ARQ «envoyer et attendre»
Trame perdue : temporisateur
12
Protocoles ARQ «envoyer et attendre»
Acquittement perdu, duplication : numérotation des trames
Protocoles ARQ «envoyer et attendre»
Temporisateur expire trop tôt : numérotation des acquittements
13
Protocoles ARQ «envoyer et attendre»
Ces protocoles sont unidirectionnels, et ne permettent
qu’une pauvre utilisation de la capacité du canal.
Protocoles ARQ «envoyer et attendre»
Utilisation du canal par ’envoyer et attendre’
14
Protocoles ARQ «envoyer et attendre»
Exemple :
– Ligne satellite à 56kbps et trames de 1000 bits. Le
satellite est stationné à 33.000km sur la terre et la
vitesse de propagation 3. 108 m/sec.
– L’utilisation U=Tx/Tt est de 3.4% seulement en
utilisant un protocole « envoyer et attendre »
pour envoyer la trame et renvoyer l’acquittement.
Protocoles «à fenêtre d'anticipation»
Améliorations:
– Données (et acquittements) dans les 2 sens (mode
bidirectionnel).
– Envoi d'un certain nombre de trames sans
attendre d'acquittement (pipelining)
– Acquittements ajoutés à des trames de données
envoyées dans l'autre sens (piggypacking).
+ d'efficacité, + de complexité de gestion aussi
besoin de tampons pour trames non encore
acquittées (et susceptibles d'être réémises).
15
Transmission continue
L’émetteur peut envoyer des trames sans
attendre l’acquittement (pipelining).
Pour utiliser encore davantage la capacité du
canal, on passe à un mode bidirectionnel où
les acquittements sont ajoutés à des trames
envoyées dans l’autre direction (piggypacking)
: besoin de tampons pour les trames non-
acquittées.
Protocoles «à fenêtre d'anticipation»
Transmission continue
16
Protocoles «à fenêtre d'anticipation»
La transmission continue permet à l’émetteur de
transmettre plusieurs trames sans avoir reçu leurs
acquittements.
– Il faut limiter le nombre de trames non-acquittées
pour des raisons de capacité de traitement et de taille
de mémoire (tampons) chez le récepteur et l’émetteur
: contrôle du flux.
La méthode des fenêtres d’anticipation nécessite
l’introduction de numéros de séquence pour les
trames ainsi qu’une taille de fenêtre maximale
pour l’émetteur et le récepteur.
Fenêtre d'anticipation
Trames : ont un numéro de séquence codé sur
n bits (0 →2n -1).
Fenêtre d'émission (côté émetteur) : liste des
numéros de séquence des trames autorisées à
être émises.
Fenêtre de réception (côté récepteur) : liste
des numéros de séquence des trames
autorisées à être reçues.
17
Fenêtre d’émission
Taille (maximale) = nombre de trames
autorisées être émises sans attendre
acquittement.
Contenu = numéros de séquence des trames
envoyées mais non encore acquittées.
Fenêtre d’émission
L'émetteur stocke les trames non acquittées
dans des zones tampons (au plus m trames, si
m est la taille de la fenêtre).
Si la fenêtre atteint son maximum, on n'envoie
plus rien jusqu'à une libération, ie un
acquittement.
18
Fenêtre de réception
Taille (fixe)= nombre de trames autorisées à
être reçues.
Contenu= numéros de séquence de ces
trames attendues.
Exemples de protocoles
Une fenêtre d’anticipation de taille 1 avec des numéros de
séquence codés sur 3 bit: (a) initialement, (b) après l’envoie
de la première trame, (c) après la réception de la première
trame, (d) après la réception du premier acquittement.
19
Acquittements
Lorsque plusieurs trames doivent être
acquittées, il est possible :
– d’envoyer un acquittement « individuel » pour
chaque trame
– d’envoyer un acquittement « collectif » en
indiquant
• le plus grand numéro de trame parmi celles qui sont
acquittées
• ou le numéro de la prochaine trame attendue.
Erreurs de transmission
Si une trame située au milieu d'une série est
perdue ou erronée ?
Deux techniques de rejet sont possibles :
– technique du rejet total
– technique du rejet sélectif
20
Technique de rejet total
Le récepteur rejettent toutes les trames qui
suivent celle qui est erronée.
– inconvénient : le canal est mal exploité
– avantage : pas besoin de mémoires tampons
Cette technique correspond à l’utilisation
d’une fenêtre de réception de taille 1.
Exemple
21
Technique de rejet sélectif
Le récepteur accepte les suivantes (en les stockant)
jusqu'à une certaine limite donnée par la taille de la
fenêtre.
– avantage : le canal est mieux exploité
– inconvénient : besoin de mémoires tampons
Cette technique correspond à l’utilisation d’une
fenêtre de réception de taille supérieure à 1.
Le récepteur utilise un acquittement « collectif ».
Exemple
22
Utilisation des fenêtres d’anticipation
L'utilisation des fenêtres d'anticipation pour
les protocoles avec une transmission continue
doit respecter les conditions suivantes :
– un temporisateur individuel pour chaque trame
non acquittée
– L'émetteur et le récepteur possèdent une
mémoire tampon pour chacune des trames dont
le numéro de séquence figure dans la fenêtre
Protocoles ARQ : Résumé
Si la station réceptrice détecte un erreur de
transmission, elle demande la retransmission de
la trame erronée : Automatic Repeat Request
(ARQ).
Les mécanismes pour la retransmission
automatique reposent sur:
– Temporisateur
– Acquittement positif et/ou négatif; individuel ou
collectif.
– Numérotation des trames
– Numérotation de acquittement
23
Quelques protocoles
Réseaux publics de télécommunications
– HDLC
Réseaux locaux
– MAC et LLC
24
