Codes polynomiaux

1)    Généralités

·        Soit M = m1 m2 … mk un bloc de k bits à transmettre

·        Le codeur transforme M en un bloc de n bits C = c1 c2 … 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 somme

2)    Définitions

  1. Le code est systématique si pour 1 < i < k on a ci  = mi , les bits ck+1 … cn 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 xn - k ´ M(x)
  3. Diviser xn - k ´ M(x) par G(x) pour avoir le reste B(x) de cette division
  4. Former C(x) = B(x) + xn - k ´ M(x)
  5. Mettre C(x) sous forme binaire

 

Exemple d’encodage avec pour hypothèses n = 12, k = 8, G(x) = x4 + x3 + 1 (équivaut à 11001) et un message à envoyer = 10011010 :

  1. 10011010 ® M(x) = x7 + x4 + x3 + x
  2. xn - k ´ M(x) ® x11 + x8 + x7 + x5 (équivaut à 100110100000)
  3. xn - k ´ M(x) ¸ G(x) ® un reste B(x) = x3 + x2 + x + 1 (équivaut à 1111) par la division polynomiale ci-dessous (les coefficients sont dans Z2) :
  4. C(x) = B(x) + xn - k ´ M(x) ® C(x) = ® x11 + x8 + x7 + x5 + x3 + x2 + 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) = x4 + x3 + 1 (équivaut à 11001) et un message reçu = 100110101111 (celui qu’on a envoyé précédemment) :

  1. R(x) = x11 + x8 + x7 + x5 + x3 + x2 + 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

1.      G(x) possède deux termes ou plus,

2.      G(x) ne divise pas 1 + xr 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).

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) = x16 + x12 + x5 + 1
  2. Ethernet g(x) = x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1