5.1. Présentation

Notation : tout vecteur peut être présenté sous une forme polynômiale :

• U = <u0,u1,u2,...,un> <==> U(x) = u0+u1.x+u2.x2+...+un.xn

Attention : les opérations sont binaires (construits sur le corps Z/2Z) : 1.x + 1.x = 0.x !

• Somme polynomiale :
• somme deux à deux de chaque coefficient (somme vectorielle)
• exemp[le : <x3+1> + <x4+x2+1> = <x4+x3+x2+1>
• Produit polynomiale :
• produit vectoriel
• exemple : <x3+1> . <x+1> = <x4+x3+x+1>
• Division polynomiale
• idem
• Exemple : <x4+x3+x2+x+1> / <x+1> = <x3+ x2+1>

Définition : Un code polynômial est un code linéaire systématique dont chacun des mots du code est un multiple du polynôme générateur (noté g(x)).

• <==> les lignes de la matrice génératrice sont engendrées par le polynôme générateur.
• Le degré du polynôme définit la longueur du champ de contrôle d'erreur.
• Exemple :
• soit le polynôme générateur : g(x) = x+1
• on s'intéresse à un code C5(2,3) donc les calculs se feront modulo x3+1
• premère ligne : g(x). 1 = x+1
• deuxième : g(x).(x2+1) mod (x3+1) = (x3+x2+x+1) mod (x3+1) = x2+x
• ce qui donne la matrice génératrice suivante : G5(2,3) =

Exemples de codes polynômiaux :

• L'avis V41 du CCITT conseille l'utilisation de codes polynômiaux (de longueurs n = 260, 500, 980 ou 3860 bits) avec le polynôme générateur :
• g(x) = x16 + x12 + x5 + 1.
• Le polynôme CRC-16 est utilisé par le protocole HDLC :
• g(x) = x16 + x15 + x2+ 1.
• Le polynôme suivant est utilisé par Ethernet :
• g(x) = x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+1.

5.2. Capacité de détection

Capacité de détection des erreurs :

Un code polynômial (k, n) dont le polynôme générateur a plus d'un coefficient non-nul (donc il ne divise pas xi, i<n) permet de détecter toutes les erreurs simples.

• idée de preuve : (C(x) + xi ) mod g(x) != 0

Si le polynôme générateur d'un code polynômial (k, n) a un facteur irréductible de trois termes (il ne divise ni xi ni 1 + xj-i, i<j<n), le code permet de détecter les erreurs doubles.

• par exemple : g(x) = x3 + x + 1

Pour qu'un code polynômial détecte toutes les erreurs d'ordre impair, il suffit que son polynôme générateur ait (x+1) comme facteur.

• Par exemple : le code de polynôme générateur (x+1) qui est équivalent à la parité.

Capacité de détection des paquets d'erreurs:

Un code polynômial (k, n) permet de détecter toutes les erreurs d'ordre l =< n-k (c'est-à-dire inférieur au degré du polynôme générateur).

Et la probabilité de ne pas détecter les erreurs d'ordre l>n-k est très faible et égale à : 2-(n-k)

5.3. Principe du codage

Le mot de code m(x) d'un code polynômial (k, n) de polynôme générateur g(x) associé au mot initial i(x) est défini par :

• m(x) = i(x). xn-k + r(x), où r(x) est le reste de la division de i(x).xn-k par le polynôme générateur g(x) (noté : r(x) = (i(x).xn-k) mod g(x) ).

Remarques :

• (i) Les r = n-k bits de r(x) (de degré =< n-k-1) forment les bits du champ de contrôle.
• (ii) Les bits de poids fort (de degré > n-k-1) forment le mot initial (--> code systématique)
• (iii) L'opération de codage effectuée à l'émission est ramenée à une division polynômiale, qui peut être réalisée simplement (électroniquement).

5.4. Principe du décodage

A la réception, chaque mot reçu m'(x) est divisé par le polynôme générateur g(x).

• Un reste non-nul indique qu'il y a eu erreur lors de la transmission.
• Syndrome de m'(x) : m'(x) mod g(x) != 0 ==> Erreur !

Attention : la réciproque est fausse ! Si le reste est nul cela ne veut pas dire qu'il n'y a pas eu d'erreurs --> subsistance d'erreurs dites résiduelles.

5.5. Schéma électronique d'un diviseur polynômial

La multiplication est réalisée par un ET logique, l'addition par un OU exclusif, plus des registres à décalage.

Le diviseur : g(x) = g0+g1.x+g2.x2+...+gn-k.xn-k

Procédé :

• (i) les registres ri sont mis à zéros
• (ii) les bits du mot à diviser sont insérés en entrée (k étapes), bits de poids fort en tête.
• (iii) les registres ri contiennent alors le reste, qu'on extrait (n-k étapes).

De nombreuses optimisations sont possibles :

• Lorsque gi=0 on supprime simplement la connexion et la porte ET !
• phase spécifique d'initialisation, etc.