III.3. le multiplexage statistique :
Il améliore le multiplexage temporel en n'attribuant la voie haute vitesse qu'aux voies basse vitesse qui ont effectivement quelque chose à transmettre. En ne transmettant pas les silences des voies basses cette technique implantée dans des concentrateurs améliore grandement le débit global des transmissions mais elle fait appel à des protocoles de plus haut niveau et est basée sur des moyennes statistiques des débits de chaque ligne basse vitesse.
Multiplexage d’une ligne
Chapitre IV : Détection et Correction des erreurs
Problématique :
Indépendamment des supports de communication et des techniques de transmission utilisés, des perturbations vont se produire entraînant des erreurs.
Dans ses conditions, la suite binaire reçue ne sera pas identique à la suite émise.
Comment B peut détecter l'occurrence d’une erreur ?
Comment B peut localiser une erreur ?
Comment B peut corriger une erreur ?
Stratégies de protection contre les erreurs de transmission :
L’Approche Naïve :
Détection d’erreurs :
Le message envoyé est constitué du double du message initial.
Envoyer 10010011001001 au lieu de 1001001
Le récepteur détecte une erreur si les exemplaires ne sont pas identiques.
Auto-correction :
Le message envoyé est constitué du triple du message initial.
Envoyer 100100110010011001001 au lieu de 1001001
Le message correct correspond aux 2 exemples identiques.
La détection et la correction des erreurs nécessitent d’introduire de la redondance dans les messages transmis.
Certaines erreurs ne peuvent pas être détectées
Exemple : la même erreur sur les deux exemplaires
Certaines erreurs détectées ne peuvent pas être corrigées
Exemple : Une erreur différente sur au moins deux exemplaires.
Certaines erreurs sont mal corrigées
Une même erreur sur deux exemplaires simultanément
L’auto-correction nécessite plus de redondance que la simple détection.
Principe général pour la correction par retransmission des erreurs de transmission :
- Après détection d’une erreur, le récepteur demande à l’émetteur, implicitement (temporisateur) ou explicitement, de retransmettre une nouvelle fois le message (codé).
- Exemple : de très nombreux protocoles de télécommunication : HDLC, X25, TCP, TP.
- 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 auto correcteurs.
Les codes correcteurs des erreurs :
II.1. Classification des codes :
Deux grandes familles de codes :
les codes par bloc : le codage/décodage bloc.
les codes convolutionnels (ou récurrents) informations d’autres blocs (généralement de blocs précédemment
Remarque : On préfère généralement le codage par bloc dans les applications téléinformatiques classiques. Le codage/décodage est plus simple et Par la suite, on ne va présenter que les codes par bloc.
II.2. Définitions générales :
Un code (k, n) transforme (code) tout bloc initial de k bits d’information en un bloc codé de n bits. Le code introduit une redondance . Le code est systématique si les k premiers bits du bloc codé sont égaux aux bits du bloc initial. Alors les r (r=n-k) derniers bits forment un champ de contrôle d’erreur. Le rendement d’un code (k, n) est : R = k/n
On appelle mot du code, la suite de n bits obtenue après un codage (k, n). Le nombre n de bits qui composent un mot du code est appelé la longueur du code. La dimension k étant la longueur initiale des mots.
Le poids de Hamming d’un mot est le nombre de bits à 1 qu’il contient. La distance de Hamming entre deux mots de même longueur est définie par le nombre de positions binaires qui diffèrent entre ces deux mots. On l’obtient par le poids de Hamming de la somme binaire des 2 mots. La distance de Hamming d’un code est la distance minimum entre tous les mots du code.
La capacité de détection (de correction) d’un code est définie par les configurations erronées qu’il est capable de détecter (corriger). Une erreur simple (resp. double, ou d’ordre p) affecte une seule (resp. 2, ou p) position(s) binaire(s) d’un mot. Pour qu’un code ait une capacité de détection (resp. correction) des erreurs d’ordre e, il faut que sa distance de Hamming soit supérieure à 1+e (resp. 1 + 2e).
Exemple : distance =3 capacité de détection ≤ 2, capacité de correction ≤ 1.
II.3. Exemples simples de codes par bloc :
II.3.1. Le contrôle de parité :
La parité ajoute à chaque bloc de i bits (i=7 ou 8) émis un bit de parité de telle sorte que parmi les i + 1 bits émis le nombre de bits à 1 soit toujours pair (ou impair). Par exemple, pour une parité paire si le bloc initial est de 7 bits et est égal à 1000001 le bloc de 8 bits émis est 10000010, pour envoyer 0110100 le bloc 01101001 est émis. À la réception, le décodeur calcule le nombre de bits à 1 et dans le cas d'une parité paire si ce nombre de bits est pair on suppose qu'il n'y a pas eu d'erreur. Sinon, on sait alors qu'il y a eu une erreur de transmission mais on ne sait pas la localiser et il faut alors demander la réémission du bloc. La technique de parité est simple à mettre en oeuvre cependant elle ne permet pas de détecter 2n erreurs dans le même bloc de bits transmis, car dans ce cas la parité ne sera pas changée.
Exemple :
Le contrôle de parité est appelé parfois VRC, pour Vertical Redundancy Check ou Vertical Redundancy Checking)
II.3.2. Parité longitudinale et transversale
Le bloc de données est disposé sous une forme matricielle (k=a.b). On applique la parité (uniquement paire) sur chaque ligne et chaque colonne. On obtient une matrice (a+1, b+1).
Le contrôle de parité croisé (aussi appelé contrôle de redondance longitudinale ou Longitudinal Redundancy Check, noté LRC) consiste non pas à contrôler l'intégrité des données d'un caractère, mais à contrôler l'intégrité des bits de parité d'un bloc de caractères.
Soit « HELLO » le message à transmettre, en utilisant le code ASCII standard. Voici les données telles qu'elles seront transmises avec les codes de contrôle de parité croisé :
Lettre
|
Code ASCII
(sur 7 bits)
|
Bit de parité
(LRC)
|
H
|
1001000
|
0
|
E
|
1000101
|
1
|
L
|
1001100
|
1
|
L
|
1001100
|
1
|
0
|
1001111
|
1
|
VRC
|
1000010
|
0
|
Capacité de détection et d’autocorrection :
- 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 ayant une parité incorrecte.
Exemple :
1 0 1 0 0 0 1 1
0 1 1 0 1 0 1 0
1 0 0 0 1 0 1 0
0 1 0 0 1 0 1 1
Attention : une erreur triple peut faire croire à une erreur simple et sa correction sera inadaptée !
Exemple :
1 0 1 0 0 0 1 1
0 1 1 0 1 0 1 0
1 0 0 0 1 0 1 0
0 1 0 0 1 0 1 1
II.3.3. Les codes linéaires :
Les codes linéaires sont des codes dont chaque mot du code (noté c) est obtenu après transformation linéaire des bits du mot initial (noté i).
Ces codes sont caractérisés par leur matrice G(k, n) (appelée matrice génératrice) telle que :
i . G = c
Exemple :
La matrice H(n-k, n) (appelée matrice de contrôle) permet de savoir si un mot reçu est un mot du code, en calculant son syndrome. Si le syndrome du mot est nul, ce mot appartient au code.
Syndrome du mot reçu c’ :
L’équation G . HT = 0 définit la relation entre les deux matrices.
Preuve : c’. HT = i. G. HT = i. 0
Propriétés
La distance de Hamming d’un code linéaire est égale au plus petit poids de Hamming non nul des mots du code.
Si un code linéaire est systématique, sa matrice génératrice s’écrit :
- G(k, n) = [Id(k), P(k, n-k)]
alors sa matrice de contrôle s’écrit :
Exemples : Soit le code C1(4, 6) de matrice
- Le mot de code c associé au mot initial
est le mot
Le code C2(7, 8) associée à la parité paire a pour matrice de contrôle
Correction
Correction par proximité : le procédé de correction transforme un mot reçu et détecté comme erroné dans le mot de code le plus proche au sens de la distance de Hamming.
Il peut exister plusieurs mots équidistants. On choisit un représentant
procédé de correction lourd
Exemple :
La méthode matricielle impose de travailler sur des mots de taille fixe, ce qui est un inconvénient majeur pour les réseaux informatiques où les messages sont de taille variable.
II.3.4. Les Codes Cycliques :
Un code cyclique (k, n) est un code linéaire (k, n) tel que toute permutation circulaire d’un mot du code est encore un mot du code.
Exemple :
• Un code cyclique (1, 2) possède les mots de code suivants : {01, 10} ou {00, 11}, mais pas {01, 11}.
• Un code cyclique (1, 3) possède les mots de code suivants : {000, 111}.
Le contrôle de redondance cyclique (noté CRC, ou en anglais Cyclic Redundancy Check) est un moyen de contrôle d'intégrité des données puissant et facile à mettre en oeuvre. Il représente la principale méthode de détection d'erreurs utilisée dans les télécommunications.
Principe
Le contrôle de redondance cyclique consiste à protéger des blocs de données, appelés trames (frames en anglais). A chaque trame est associé un bloc de données, appelé code de contrôle (parfois CRC par abus de langage ou FCS pour Frame Check Sequence dans le cas d'un code de 32 bits). Le code CRC contient des éléments redondants vis-à-vis de la trame, permettant de détecter les erreurs, mais aussi de les réparer.
Le principe du CRC consiste à traiter les séquences binaires comme des polynômes binaires, c'est-à-dire des polynômes dont les coefficients correspondent à la séquence binaire. Ainsi la séquence binaire 0110101001 peut être représentée sous la forme polynomiale suivante :
0*X9 + 1*X8 + 1*X7 + 0*X6 + 1*X5 + 0*X4 + 1*X3 + 0*X2 + 0*X1 + 1*X0
soit
X8 + X7 + X5 + X3 + X0
ou encore
X8 + X7 + X5 + X3 + 1
De cette façon, le bit de poids faible de la séquence (le bit le plus à droite) représente le degré 0 du polynôme (X0 = 1), le 4ème bit en partant de la droite représente le degré 3 du polynôme (X3)... Une séquence de n bits constitue donc un polynôme de degré maximal n-1. Toutes les expressions polynomiales sont manipulées par la suite avec une arithmétique modulo 2.
Dans ce mécanisme de détection d'erreur, un polynôme prédéfini (appelé polynôme générateur et noté G(X)) est connu de l'émetteur et du récepteur. La détection d'erreur consiste pour l'émetteur à effectuer un algorithme sur les bits de la trame afin de générer un CRC, et de transmettre ces deux éléments au récepteur. Il suffit alors au récepteur d'effectuer le même calcul afin de vérifier que le CRC est valide.
Application
Soit M le message correspondant aux bits de la trame à envoyer et M(X) le polynôme associé. Appelons M' le message transmis, c'est-à-dire le message initial auquel aura été concaténé le CRC de n bits. Le CRC est tel que M'(X)/G(X)=0. Le code CRC est ainsi égal au reste de la division polynomiale de M(X) (auquel on a préalablement concaténé n bits nuls correspondant à la longueur du CRC) par G(X).
Le plus simple est encore de prendre un exemple : prenons le message M de 16 bits suivant : 1011 0001 0010 1010 (noté B1 en hexadécimal). Prenons G(X) = X3 + 1 (représenté en binaire par 1001). Etant donné que G(X) est de degré 3, il s'agit d'ajouter 4 bits nuls à M : 10110001001010100000. Le CRC est égal au reste de la division de M par G :
10110001001010100000
1001...,..,.,.,.....
----...,..,.,.,.....
0100..,..,.,.,.....
0000..,..,.,.,.....
----..,..,.,.,.....
1000.,..,.,.,.....
0000.,..,.,.,.....
----.,..,.,.,.....
1000.,..,.,.,.....
1001,..,.,.,.....
----,..,.,.,.....
1111..,.,.,.....
1001..,.,.,.....
----..,.,.,.....
1100.,.,.,.....
1001.,.,.,.....
----.,.,.,.....
1101,.,.,.....
1001,.,.,.....
----,.,.,.....
1000.,.,.....
0000.,.,.....
----.,.,.....
10001,.....
1001,.,.....
----,.,.....
10000.,.....
1001.,.....
----
1111,.....
1001,.....
----,.....
1100.....
1001.....
----.....
1100....
1001....
----....
1010...
1001...
----...
0110..
0000..
----..
1100.
1001.
----.
1010
1001
----
0011
Pour créer M' il suffit de concaténer le CRC ainsi obtenu aux bits de la trame à transmettre :
M' = 1011000100101010 + 0011
M' = 10110001001010100011
Ainsi, si le destinataire du message effectue la division de M' par G, il obtiendra un reste nul si la transmission s'est effectuée sans erreur :
10110001001010100011
1001...,..,.,.,...,,
----...,..,.,.,...,,
0100..,..,.,.,...,,
0000..,..,.,.,...,,
----..,..,.,.,...,,
1000.,..,.,.,.....
1001.,..,.,.,.....
----.,..,.,.,.....
0010,..,.,.,.....
0000,..,.,.,.....
----,..,.,.,.....
0101..,.,.,.....
0000..,.,.,.....
----..,.,.,.....
1010.,.,.,.....
1001.,.,.,.....
----.,.,.,.....
0110,.,.,.....
0000,.,.,.....
----,.,.,.....
1101.,.,.....
1001.,.,.....
----.,.,.....
1010,.,.....
1001,.,.....
----,.,.....
0111.,.....
0000.,.....
----
1110,.....
1001,.....
----,.....
1111.....
1001.....
----.....
1100....
1001....
----....
1010...
1001...
----...
0110..
0000..
----,,
1101,
1001,
----,
1001
1001
----
0
Les polynômes générateurs
Les polynômes générateurs les plus couramment employés sont :
CRC-12 : X12 + X11 + X3 + X2 + X + 1
CRC-16 : X16 + X15 + X2 + 1
CRC CCITT V41 : X16 + X12 + X5 + 1
(Ce code est notamment utilisé dans la procédure HDLC.)
CRC-32 (Ethernet) : = X32 + X26 + X23 + X22 + X16 + X12 + X11 + X10 + X8 + X7 + X5 + X4 + X2 + X + 1
CRC ARPA : X24 + X23+ X17 + X16 + X15 + X13 + X11 + X10 + X9 + X8 + X5 + X3 + 1
|
