Plan
I.
II.
III.
IV.
Introduction
Problmatique
Techniques de dtection des erreurs
[Link] de Parit
[Link] Polynomiale (CRC)
[Link] Hamming
[Link] entre les techniques (Parit,
CRC, Hamming).
Techniques de correction des erreurs
Retransmission
Forward error correction FEC
V. Conclusion
I.
Introduction :
Quel que soit la qualit des supports de communication et les
performances des techniques de transmission utilises, des
perturbations vont se produire entranant des erreurs sur les
donnes transmises.
En pratique, les messages sont transmis sur un canal
sous la forme dune suite de bits (des 0 et de 1).
Les canaux de transmission imparfaits entranent des
erreurs lors des changes de donnes (un zro qui
devient un 1 ou inversement).
On suppose quon veut simuler ce problme comme ce schma suivant e :
metteur A
10010101
Rcepteur B
10000101
!!
Erreur
Schma reprsente lerreur entre metteur et rcepteur
Problmatique : des questions poser lors des
erreurs de validation des donnes transmis ainsi
rceptionnes :
Comment
le
rcepteur
B
peut
dtecter
l'occurrence dune erreur ?
Comment le rcepteur B peut corriger une
erreur ?
II.
Technique de dtection des erreurs :
[Link] de Parit :
On rajoute un bit 1 ou 0 suivant la parit du nombre de bits :
La somme bits est paire donc ajout bit de valeur 0.
La somme bits est impaire donc ajout bit de valeur 1.
Exemple :
- 10011110111 la somme = 8 : 100111101110
- 1001110111 la somme = 7 : 10011101111
L'information transmettre : 100111011
Le rcepteur 100011011
La somme est 4 et le bit de parit est 1 donc il y a erreur
[Link] Polynomiale (CRC) :
Dans les codes polynmiaux appels CRC (Cyclic
Redundancy Check), on utilise la reprsentation polynmiale qui
associe un mot binaire de n bits, un polynme de la variable x
affecte des coefficients 0 ou 1, dont le degr est n-1.
Exemple :
Mot : 11001
11001
Mot
43210
Degr de
x
Donc : 1*x4+1*x3+0*x2+0*x1+1*x0
P(x)= x4+x3+1
Dans le mcanisme de dtection derreur du CRC, un polynme
prdfini (appel polynme gnrateur et not G(X)) est connu
de lmetteur et du rcepteur.
La dtection derreur consiste pour lmetteur ajouter au
message mettre un code de contrle tel que le polynme
correspondant au message plus le code de contrle soit
divisible par le polynme gnrateur choisi, et de transmettre le
message et le polynme gnrateur au rcepteur.
Le message reu qui contient les donnes et le CRC doit
tre divisible par le polynme gnrateur.
Il suffit alors au rcepteur de vrifier par une division
euclidienne en base 2 que le reste de la division du message
par le polynme est nul.
La Mthode suivre:
le polynme gnrateur
transforme G(x) en un mot binaire
Pour un message transmettre, on ajoute m zros
ce mot binaire tel que m= degr G(x).
On ajoute alors itrativement ce mot le mot
correspondant
au
polynme
gnrateur
jusqu ce que le mot obtenu soit infrieur au
G(x).
Ce mot obtenu correspond au CRC ajouter au
mot avant de lmettre.
A la rception : on effectue la division, Si R(x)
est nul, il ny a pas de dtection derreur. Sinon
il y a erreur.
Exemple :
Mot : 100101, G(x)= x3+x2+1.
- transforme G(x) en un mot binaire donc 1101.
- ajoute m zros ce mot, m=000 : 100101000.
- Ajoute itrativement :
1
1
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
1
1
1
0
1
1
0
0
0
1
1
01000
0
1
1
0
1
1000
1000
1
0000
100101000
1101
1101
1111
010001000
01101
001011000
001101
000110000
000110100
000000100
0001101
000000100
1001101 arrt
- Le CRC est donc 100 et le mot transmettre
100101 100.
- A la rception : on effectue la division, le reste est
nul il ny a donc pas derreur.
[Link] Hamming :
Le code de Hamming est un code correcteur d'erreur. Il dtecte
et corrige une erreur de transmission.
Il faut rajouter pour cela des bits de contrle aux bits transmis.
Ces bits de contrle s'apparentent des bits de parit.
La Mthode suivre:
- Pour n bits transmettre, il faut rajouter p bits, selon la
formule : p est le plus petit entier positif tel que 2 p-p
n+1.
Exemple n = 4 2p-p 5 p = 3 5 3-23
5 5 .
- On utilise la table suivante :
0
1
2
3
4
5
6
7
C3
0
0
0
0
1
1
1
1
C2
0
0
1
1
0
0
1
1
C1
0
1
0
1
0
1
0
1
Les bits
concerns par
ce bit de
contrle
- C1 :(1, 3, 5,7) C2 (2, 3, 6,7) C3 (4, 5, 6,7).
- La position de C1, C2, C3 est 2v tel que v=1, 2 jusqu n
Exemple de transmission d'un message de 4 bits : 1101
7
4
C3
---
3
1
2
C2
---
1
C1
---
- Calcul les valeurs de C1, C2, C3 :
Position
3, 5,7
3, 6,7
5, 6,7
C1
C2
C3
info
1, 0,1
1, 1,1
0, 1,1
Parit
paire
Impaire
paire
valeur
0
1
0
- L'information transmettre est donc : 1100110
7
4
C3
0
2
C2
1
1
C1
0
Vrification et correction
- L'information reue est par exemple : 1110110 Erreur
bit
C1
C2
C3
position
1, 3, 5,7
2, 3, 6,7
4, 5, 6,7
info
0, 1, 1,1
1, 1, 1,1
0, 1, 1,1
Parit
Paire
Impaire
Impaire
- Un bit vrai vaut 0, un bit faux vaut 1
C3
1
C2
0
C1
1
- (101)2=(5) ce qui signifie que c'est le bit numro 5 qui est
erron. Reconstitution du message : 1100110
[Link], CRC, Hemming :
Parit
Dtection derreur
Position derreur
CRC
Hammi
ng
Correction derreur
III.
Technique de correction des erreurs :
Une fois erreur est dtecte, il faut la corriger
Il existe deux faons de la corriger :
1. Retransmission (redondance temporelle)
Dans cette approche, on demande lmetteur de
retransmettre toute trame juge errone.
Elle est lie au mcanisme de contrle de flux
- Un acquittement pour chaque trame (technique
Stop and wait)
- Un acquittement pour plusieurs trames (technique
avec anticipation ou technique de la fentre
coulissante).
2. Forward error correction FEC
IV.
Conclusion :
