Calcul d’un CRC polynomial

Mathématiquement, on peut écrire un polynôme tel que \[P(X)=X^5+X^3+X^2+X+1\]

On pourra alors traduire ce polynôme par le suite de bits :

\[P(X)=X^5+X^3+X^2+X+1 = 1X^5+0X^4+1X^3+1X^2+1X+1 \iff M=101111\]

Exercices

  1. Quel mot binaire est associé au polynôme suivant : \(P(x)=X^7+X^6+X^2\) ?
  2. Inversement, quel est le polynôme associé au mot binaire suivant \(11000011\) ?

Division des polynômes

On peut diviser deux mots binaires de la manière suivante :

voir la vidéo : division

Remarques :

Exercice

Soit le mot \(M=1010100001\) à diviser par \(G=1010\). Déterminer le reste de la division de \(M\) par \(G\)

Algorithme du calcul de CRC

  1. Soit \(M\) le mot dont on veut calculer le CRC et on suppose que le le mot est de longueur \(n\)
  2. SOit \(G\) le polynôme générateur du CRC, on suppose que le polynôme \(G\) est de degré \(k\), avec \(k < n\)
  3. On ajoute au mot \(M\), \(k\) bits égaux à \(0\). Cela forme alors un mot \(M'\) de longueur \(n+k\) bits
  4. On effectue alors la division de \(M'\) par \(G\)
  5. Le reste de la division précédente est le CRC du mot \(M\)

Exemple de calcul du CRC

  1. SOit \(M=1100100100\) donc de longueur \(10\) bits
  2. Soit \(G\) le polynôme générateur \(G(X)=X^4+X+1\). qui correspond à \(G=10011\) donc de longueur \(5\)
  3. On ajoute à \(M\) les \(4\) bits égaux à \(0\), soit \(M'=11001001000000\)
  4. On effectue la division de \(M'\) par \(G\), et on obtient le résultat suivant :

division01

  1. Le reste est de longueur \(4\) (ce qui correspond au degré du polynôme \(G\)) et vaut 0100
  2. Le CRC de \(M\) est 0100

Exercice

Calculer le CRC du polynôme \(P(x)=x^8+1\) avec le polynôme générateur suivant \(G(x)=x^4+x^2+1\)