Ce document constitue une introduction aux codes polynomiaux, une méthode fondamentale pour la détection et la correction d'erreurs en télécommunications et stockage de données. Il est destiné aux étudiants universitaires souhaitant acquérir une compréhension solide de ce domaine.
Il couvre les notions suivantes:
- Les définitions et généralités des codes polynomiaux et linéaires.
- Les procédures détaillées d'encodage et de décodage, avec des exemples pratiques.
- Les propriétés essentielles et les applications concrètes de ces codes, notamment dans les réseaux informatiques.
Réseaux Informatiques : Cours codes polynomiaux réseaux informatiques
Télécharger PDFIntroduction aux Codes Polynomiaux
Les codes polynomiaux sont une méthode essentielle en télécommunications et en stockage de données pour détecter et parfois corriger les erreurs. Ils transforment un message binaire en un message codé plus long, y ajoutant des informations de redondance qui permettent de vérifier l'intégrité des données.
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.
Définitions Clés
Code systématique
Un code est dit systématique si, pour 1 < i < k, on a ci = mi. Les bits ck+1 ... cn sont alors appelés bits de contrôle (ou de parité).
Code linéaire
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.
Code polynomial
Un code polynomial est un code linéaire dont chacun des polynômes associés aux mots du code est divisible par un polynôme générateur spécifique, noté G(x).
Procédure d'Encodage
- Mettre le message à coder sous forme polynomiale, M(x).
- Former le polynôme xn-k * M(x) en décalant M(x) de n-k positions vers la gauche.
- Diviser xn-k * M(x) par le polynôme générateur G(x) pour obtenir le reste B(x) de cette division (les calculs sont effectués dans le corps fini GF(2), ce qui signifie que les additions et soustractions sont des XOR).
- Former le polynôme du mot de code C(x) = B(x) + xn-k * M(x).
- Mettre C(x) sous forme binaire.
Exemple d'encodage
Considérons les hypothèses suivantes : n = 12, k = 8, le polynôme générateur G(x) = x4 + x3 + 1 (ce qui équivaut à la séquence binaire 11001), et le message à envoyer M = 10011010.
- Le message binaire 10011010 correspond au polynôme M(x) = x7 + x4 + x3 + x.
- Nous formons xn-k * M(x) = x12-8 * M(x) = x4 * M(x) = x11 + x8 + x7 + x5. Cela équivaut au message binaire 100110100000.
- La division de x11 + x8 + x7 + x5 par G(x) = x4 + x3 + 1 (11001) donne un reste B(x) = x3 + x2 + x + 1 (équivalant à 1111). Voici la division polynomiale binaire (les coefficients sont dans Z2) :
100110100000|11001 -------------|------- 11001 |11100111 ----- | 010100 | 11001 | ----- | 011011 | 11001 | ----- | 0001000 | 11001 | ----- | 010010 | 11001 | ----- | 01111 | - Le polynôme du mot de code C(x) = B(x) + xn-k * M(x) est donc C(x) = (x3 + x2 + x + 1) + (x11 + x8 + x7 + x5) = x11 + x8 + x7 + x5 + x3 + x2 + x + 1.
- En binaire, C(x) équivaut à 100110101111. Ce mot est formé du message original M(x) décalé à gauche de n-k positions, suivi des bits de contrôle de B(x).
Procédure de Décodage
- Mettre le message reçu sous forme polynomiale, R(x).
- Diviser R(x) par le polynôme générateur G(x) pour obtenir le syndrome S(x) (le reste de cette division).
- Si S(x) = 0, le message est considéré comme correct ; sinon, cela indique la présence d'une ou plusieurs erreurs.
Exemple de décodage
En reprenant l'exemple précédent : n = 12, k = 8, G(x) = x4 + x3 + 1 (11001), et un message reçu R = 100110101111 (le mot de code précédemment encodé, sans erreur introduite).
- Le message reçu R(x) est : x11 + x8 + x7 + x5 + x3 + x2 + x + 1.
- La division de R(x) par G(x) = x4 + x3 + 1 donne un reste S(x) = 0. Ceci est attendu, car aucune erreur n'a été introduite dans le message encodé. Voici la division polynomiale binaire :
100110101111|11001 -------------|------- 11001 |11100111 ----- | 010100 | 11001 | ----- | 011011 | 11001 | ----- | 0001001 | 11001 | ----- | 010101 | 11001 | ----- | 011001 | 11001 | ----- | 00000 |
Propriétés des codes polynomiaux
Un code polynomial qui utilise un polynôme générateur G(x) ayant les caractéristiques suivantes permet de détecter des erreurs :
- G(x) possède au moins deux termes.
- G(x) ne divise pas 1 + xr avec r = {1, ..., n}.
- G(x) est de degré p.
Un tel polynôme générateur permet de détecter une ou deux erreurs indépendantes, ainsi que tous les paquets d'erreurs de longueur inférieure ou égale à p (où p est le degré de G(x)), à condition que l'erreur E(x) ne soit pas un multiple de G(x). La probabilité qu'une erreur E(x) soit un multiple de G(x) est très faible et dépend du polynôme générateur choisi.
Les codes polynomiaux sont largement utilisés pour calculer le checksum (somme de contrôle) contenu dans les en-têtes des protocoles de communication, à tous les niveaux. Le calcul du checksum peut être implémenté efficacement en hardware (matériel) à l'aide de registres à décalage à rétroaction linéaire (LFSR).
Exemples d'application
- Le CCITT (Comité Consultatif International Télégraphique et Téléphonique) recommande l'utilisation de codes polynomiaux de longueurs 260, 500, 980 et 3860 bits avec le polynôme générateur G(x) = x16 + x12 + x5 + 1.
- Pour Ethernet, le polynôme générateur G(x) est x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1.
Foire Aux Questions (FAQ)
Qu'est-ce qu'un code polynomial et à quoi sert-il ?
Un code polynomial est un type de code correcteur d'erreurs linéaire utilisé pour détecter et parfois corriger les erreurs de transmission de données ou de stockage. Il repose sur des opérations arithmétiques avec des polynômes, permettant d'ajouter une redondance calculée (bits de contrôle) à un message original.
Comment les codes polynomiaux détectent-ils les erreurs ?
Lors du décodage, le message reçu est divisé par le même polynôme générateur utilisé à l'encodage. Si le reste de cette division (appelé syndrome) est égal à zéro, le message est considéré comme exempt d'erreurs. Un syndrome non nul indique la présence d'une ou plusieurs erreurs.
Où sont principalement utilisés les codes polynomiaux ?
Les codes polynomiaux sont largement employés dans divers domaines, notamment les réseaux informatiques (par exemple, Ethernet, Wi-Fi pour le calcul des sommes de contrôle), les systèmes de stockage de données (disques durs, CD/DVD), et les protocoles de communication pour garantir l'intégrité des données.