Codes polynomiaux

1) Généralités

· Soit M = m₁ m₂ … m_k un bloc de k bits à transmettre

· Le codeur transforme M en un bloc de n bits C = c₁ c₂ … c_n

· 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 somme

2) 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⁴ + x³ + 1 (équivaut à 11001) et un message à envoyer = 10011010 :

1. 10011010 ® M(x) = x⁷ + x⁴ + x³ + x
2. x^{n - k} ´ M(x) ® x¹¹ + x⁸ + x⁷ + x⁵ (équivaut à 100110100000)
3. x^{n - k} ´ M(x) ¸ G(x) ® un reste B(x) = x³ + x² + x + 1 (équivaut à 1111) par la division polynomiale ci-dessous (les coefficients sont dans Z₂) :
4. C(x) = B(x) + x^{n - k} ´ M(x) ® C(x) = ® x¹¹ + x⁸ + x⁷ + x⁵ + x³ + x² + 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 |

----- |

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⁴ + x³ + 1 (équivaut à 11001) et un message reçu = 100110101111 (celui qu’on a envoyé précédemment) :

1. R(x) = x¹¹ + x⁸ + x⁷ + x⁵ + x³ + x² + 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.

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¹⁶ + x¹² + x⁵ + 1
2. Ethernet g(x) = x³² + x²⁶ + x²³ + x²² + x¹⁶ + x¹² + x¹¹ + x¹⁰ + x⁸ + x⁷ + x⁵ + x⁴ + x² + x + 1