Réseaux Informatiques : Cours codes polynomiaux réseaux informatiques
Télécharger PDFObtenir le pack complet des cours, TDs, examens sur Réseaux Informatiques!
Vous souhaitez maîtriser Réseaux Informatiques ? Ne cherchez plus, nous avons le pack bien choisi pour vous.
Accédez à une collection complète des supports de cours, des travaux dirigés (TD) corrigés, examens...
Télécharger pack29/10/2015Codes polynomiaux1/3 Codes polynomiaux1) Généralités· Soit M = m
1 m
2 ... m
k un bloc de k bits à transmettre· Le codeur transforme M en un bloc de n bits C = c
1 c
2 ... cn ·
Un tel code est noté code (n, k)· Le code est en bloc si le mot C ne dépend que de M· Le rendement du code R = k ̧ n· Le poids de Hamming d’un mot du code est le nombre de 1 qu’il contient· La distance de Hamming entre deux mots de code est le poids du vecteur somme2) Définitions
1. Le code est systématique si pour 1 < i < k on a c
i = m
i , les bits c
k+1 ... c
n sont appelés bits de
contrôle
2. Un code (n, k) est linéaire s’il est systématique et si les n - k bits de contrôle dépendent linéairement
des k bits d’information.
3. Un code polynomial est un code linéaire dont chacun des polynômes associés aux mots du code sont
divisibles par un polynôme générateur.3) Encodage
1. Mettre le message à coder sous forme polynomiale
2. Former x
n - k ́ M(x)
3. Diviser x
n - k ́ M(x) par G(x) pour avoir le reste B(x) de cette division
4. Former C(x) = B(x) + x
n - k ́ M(x)
5. Mettre C(x) sous forme binaire
Exemple d’encodage avec pour hypothèses n = 12, k = 8, G(x) = x
4 + x
3 + 1 (équivaut à 11001) et un
message à envoyer = 10011010 :
1. 10011010 ® M(x) = x
7 + x
4 + x
3 + x
2. x
n - k ́ M(x) ® x
11 + x
8 + x
7 + x
5 (équivaut à 100110100000)
3. x
n - k ́ M(x) ̧ G(x) ® un reste B(x) = x
3 + x
2 + x + 1 (équivaut à 1111) par la division polynomiale ci-
dessous (les coefficients sont dans Z2 ) :
4. C(x) = B(x) + x
n - k ́ M(x) ® C(x) = ® x
11 + x
8 + x
7 + x
5 + x
3 + x
2 + x + 1
5. C(x) équivaut à 100110101111 (M(x) décalé à gauche de n - k plus B(x))
100110100000|11001
|--------11001 |11100111----- | 10100
| 11001
| -----
| 11011
| 11001
| -----| 100| 1000 |
10000 |
11001 |
29/10/2015Codes polynomiaux2/3 ----- |
10010 |
11001 |
----- |10110| 11001|-----| 1111|4) Décodage
1. Mettre le message reçu sous forme polynomiale
2. Diviser R(x) par G(x) pour obtenir le syndrome S(x) (reste de cette division)
3. Si S(x) = 0, le message est correct sinon il est erroné
Exemple de décodage avec pour hypothèses n = 12, k = 8, G(x) = x
4 + x
3 + 1 (équivaut à 11001) et un
message reçu = 100110101111 (celui qu’on a envoyé précédemment) :
1. R(x) = x
11 + x
8 + x
7 + x
5 + x
3 + x
2 + x + 1
2. R(x) ̧ G(x) ® un reste S(x) = 0 par la division polynomiale ci-dessous (c’est normal nous n’avons
introduit aucune erreur dans C(x)) :
100110101111|11001
|--------11001 |11100111----- | 10100
| 11001
| -----
| 11011
| 11001
| -----| 100| 1001 |
10011 |
11001 |
----- |
10101 |
11001 |
----- |11001| 11001|-----| 00000|5) Propriétés
Un code polynomial qui utilise un polynôme générateur G(x) ayant les caractéristiques suivantes :1. G(x) possède deux termes ou plus,2. G(x) ne divise pas 1 + x
r avec r = {1, ..., n},3. G(x) est de degré p,
permet de détecter 1 ou 2 erreurs indépendantes et tous les paquets d'erreurs de longueur inférieure
ou égale à p ( deg (G) = p) à condition que l’erreur E(x) ne soit pas un multiple de G(x) (probabilité
très faible et dépendant du polynôme générateur choisi).
Les codes polynomiaux sont utilisés pour calculer le checksum contenu dans les entêtes des protocoles
de tous niveaux.
Le calcul du checksum peut être implémenté en hardware avec des registres à décalage.
29/10/2015Codes polynomiaux3/3 6)
Exemples
1. CCITT conseille l'utilisation de codes polynomiaux de longueurs 260, 500, 980, 3860 bits avec le
polynôme générateur g(x) = x
16 + x
12 + x
5 + 1
2. Ethernet g(x) = x
32 + x
26 + x
23 + x
22 + x
16 + x
12 + x
11 + x
10 + x
8 + x
7 + x
5 + x
4 + x
2 + x + 1