Soit un mot "m" de "n" digits :

m = (a₁, a₂, a₃, a₄, a₅, a₆, a₇, a₈)  avec a_i= 0 ou 1

en associant un polynome on obtient :

m(x) = a₁x⁷ + a₂x⁶ + a₃x⁵ + a₄x⁴ + a₅x³ + a₆x² + a₇x + a₈

Lemme :

• si un mot m de n digits peut représenter un message (il fait partie du code) alors toute permutation circulaire fait également partie du code.
• en algèbre modulo 2, l'addition et la soustraction sont identiques

Chaque mot transmis "C" comporte :

C(x) = m(x) + K(x)

C(x) = g(x) X Q(x)  

avec g(x) = polynome générateur

d'ou :

m(x) = g(x) X Q(x)  + K(x) - (+ K(x) car en algèbre modulo 2, l'addition et la soustraction sont identiques)

avec K(x) = reste de la division de m(x) par g(x)

Exemple :

C(x) = m(x) + K(x)

[1 1 0 1 a₅ a₆ a₇] = [1 1 0 1 0 0 0 ]  [a₅ a₆ a₇] 

soit m = [1 1 0 1]

en posant  g(x) = x³ + x + 1

en associant un polynome  g(x) = x³ + x + 1 à m on obtient m(x) - Cf. ci-avant :

m(x) = x⁶ +x⁵ + x³ 

En divisant m(x)  /  g(x), on obtient :  x⁶ + x⁵ + .. + x³                |    x³ + x + 1

                         

x6 + x5 + .. + x3	x3 + x + 1
[x6 + .. + x4 + x3]	(x3 +  x2) + x + 1
=                x5 + x4
[x5 + .. + x3 + x2]
=                       x4 + x3 + x2
[x4 + .. + x2 + x]
=                              x3 + .. + x
[x3 + .. + x + 1]
(reste)                               1

Le reste : 1 =  0 x² + 0 x + 1

Le reste peut s'écrire 1 = [0 0 1] qui est le groupe de contrôle

Le mot final transmis est [1 1 0 1 0 0 1]

Application à la génération d'un CRC

le message à diviser est présenté bits de poids forts en tête, soit

poids faible [0 0 0 1 0 1 1] poids fort

		Registres			Reste des divisions par g(x)
Etat	Bit transmis	1	2	3
INIT	/	0	0	0
1er coup	1	1	0	0
2eme coup	1	1	1	0
3eme coup	0	0	1	1
4eme coup	1	0	1	1	0x3 + x4 + x5	Reste de la division / x3
5eme coup	0	1	1	1	x2 + x3 + x4	Reste de la division / x2
6eme coup	0	1	0	1	x + 0x2 + x3	Reste de la division / x
7eme coup	0	1	0	0	1 + 0x + 0x2	Reste de la division /1

Les coefficients du polynome diviseur sont matérialisés par des interrupteurs

Les informations sont stockées dans des registres

• A l'init, les registres sont vides
• A l'issue des "k" impulsions nous avons dans les registres les valeurs a_n-k-1, ..., a_n-1, a_n

A l'impulsion suivante, nous avons le registre qui a pour valeur la nouvelle entrée  la sortie. Les valeurs des registres sont donc :

• Valeur du registre 1 = a_n-k-2 a_nb_o (dans notre cas = a_n-k-2 a_n  car (bo=1)
• Valeur du registre 2 = a_n-k-1 a_nb₁ 
• Valeur du registre 3 = a_n-k a_nb₂ 

On constate en effectuant la division m(x) / g(x)

• que le premier reste est le contenu des registres 1, 2, 3, ... k
• au (n - k + 1)^ème coup, le reste cherché se trouve dans le registre

 

 

 

 

1.      Le C.R.C. (Cyclic Redundancy Check)

Le CRC est une méthode de codage qui consiste à grouper à l'émission les bits à transmettre en mots de "n-k" bits et à les associer à un mot de "n" bits. La redondance est constitué par les "k" bits. Le nombre de mots possibles de "n" éléments est de "2^n-k" et les autres mots correspondent à des mots entachés d'erreurs.

Les méthodes de « vérification de clé » consistent à comprimer l'information. A partir d'une séquence d'information de longueur "n-k" finie, un mécanisme de compression (CRC - Cyclic Redundancy Check), caractérise cette séquence d'information à l'aide d'une information condensée : la clé. Cette clé ne permet pas de corriger les erreurs, elle permet de détecter les différences entre plusieurs séquences.

1.1.Mécanisme de détection d'erreurs

Soient les données suivantes :

• m_i = nombre de séquences d’information possédant la même clé.
• n-k = taille de la séquence d’information (fixe ou variable).
• k = taille de la clé (résultant de la division polynomiale).
• n = taille du message transmis.

Le mécanisme de vérification de clé consiste à comprimer un message composé de "n-k" symboles en un nombre fini de bits (k).

Chaque clé, de valeur résultante « S_i » est représentative d'un nombre « m_i » de séquences d'informations de taille fixe ou variable. La clé « S_i », un mot de « k » bits, peut prendre « 2^k » valeurs différentes.

Pour une séquence d’information « m_i » de taille « n » constant, il y a 2ⁿ formes possibles, et pour chacune de ces formes, il n'y a qu'une seule clé possible dont la valeur est comprise entre « 0 » et « 2^k » et l'on obtient :

La probabilité de détection d'erreurs pour une séquence « m_i » (représentée par sa clé « S_i ») correspond à la probabilité d'obtenir la même valeur de clé « S_i » à partir d'une séquence « m_i » erronée.

La probabilité de détection d'erreurs associée à une clé « S_i »,  est définie de la façon suivante :

m_i-1 : correspond au nombre de séquences m_i ayant la même clé que la séquence exacte,

2ⁿ-1 : correspond au nombre total de séquences possibles (2ⁿ) moins la séquence juste (1).

Soit :

Afin de calculer le pouvoir de détection moyen, il faut sommer l’ensemble des cas correspondant aux "m_i" séquences d’informations. Il existe m_i séquences d'informations dont la probabilité de détection d'erreurs vaut P_{det_i}. La valeur moyenne pour l'ensemble des « 2ⁿ » séquences possibles vaut :

 

or 

,  

d’ou 

 

 

Dans le cas des réseaux de transmission, « n » n’est en général pas constant (les trames ont une longueur variable). De ce fait, les erreurs résiduelles sont composées de l’ensemble des combinaisons possibles d’erreurs sur les différentes longueur de trame.

Une séquence d'information « m_i » peut donc s'écrire sous la forme suivante :

m_i = « 2^n-k + x_i »,

nous obtenons donc :

soit 

On déduit de la formule précédente que la probabilité de détection d'erreurs d'un mécanisme de compression est maximale lorsque m_i est constant quel que soit S_i,

on obtient m_i = 2^n-k  :

Et nous avons :

Lorsque la clé représente une nombre constant de séquences d’informations, le probabilité de détection d’erreur est optimale.

Dans le cas contraire, s’il existe un nombre différent de séquences d’informations, la probabilité de détection d’erreur sera inférieure à  et devra être estimée au cas par cas.

---

1.2.Propriétés et choix du polynôme générateur de clé

Les polynômes générateurs sont généralement classés selon les trois types suivants, quels que soit leur degré :

·      les polynômes irréductibles,

• Un polynôme de degré k est irréductible s’il n’est pas divisible par un polynôme de degré inférieur à k, sauf par 1.

Par exemple,

a(x) = x⁴  x³  x²  x  1 de degré 4, et

b(x) = x⁸  x⁴  x³  x  1 de degré 8,

sont des polynômes irréductibles. 

les polynômes primitifs,

• Un polynôme irréductible de degré k est primitif si celui-ci est un diviseur du polynôme xⁿ - 1, avec n = 2^k - 1, sans être diviseur de tous les autres polynômes x^m - 1 avec m < n. Il peut aussi être diviseur de certains polynômes x^p - 1 avec p > n.

Les polynômes irréductibles ou primitifs sont obtenus par un algorithme mathématique complexe qu’il est fastidieux d’exécuter manuellement si le degré est élevé. A noter qu’il existe toujours des polynômes primitifs quels que soit le degré désiré.

·      les polynômes quelconques (ni irréductibles et ni primitifs)

Un polynôme générateur de clé a pour objectif de détecter le maximum d'erreurs possibles. Pour cela il doit satisfaire aux règles suivantes :

1 -     Soit la clé s(x) correspondant à la séquence d’entrée m(x) et obtenue en utilisant le polynôme générateur g(x) primitif et irréductible. Si nous appelons e(x) une séquence d’erreur, c’est-à-dire qui possède des « 1 » aux emplacements erronés et des « 0 » partout ailleurs, alors le message origine m(x) et le message erroné m(x) e(x) ont la même clé s(x) si et seulement si e(x) est un multiple de g(x) modulo 2.

          Donc, la plus petite séquence erronée est g(x), d’où :

2 -     Si le polynôme générateur est de degré k, toutes les erreurs pouvant affecter une séquence d’entrées de longueur n £ k sont détectées. Il est alors possible de déterminer le nombre de séquences erronées non détectées pour n ³ k, car elles sont toutes multiples de g(x).

Les séquences d’entrée de longueur n correspondent à des polynômes de degré n-1. Il y a donc 2ⁿ-1 séquences possibles car chaque polynôme a « n » coefficients et ceux-ci peuvent prendre les valeurs « 0 » ou « 1 ».

On démontre par récurrence qu’il y a N = 2^n-k - 1 séquences erronées qui sont indétectables. Ainsi, pour m = n, on obtient séquences erronées de base, séquences erronées en combinant les séquences de base deux à deux, etc..., et enfin une séquence erronée en combinant toutes les séquences de base, soit . D’où :

3 -     Pour une séquence d’entrées de longueur « n » avec « n-k », la probabilité pour que le générateur de clé de degré k ne détecte pas d’erreurs, est égale à [2^n-k-1]/[2ⁿ-1]. Ceci en supposant que toutes les séquences erronées ont une probabilité d’apparition identique. Lorsque n est très grand, le rapport tend vers 2^-k. Cette propriété est la plus importante car elle caractérise avec précision le pouvoir de détection P de l’analyse de clé qui est presque uniquement fonction du degré du polynôme générateur choisi.

4 -     Tout générateur de clé construit à partir d’un polynôme générateur qui possède au moins deux coefficients non nuls, détecte toutes les erreurs simples.

5 -     Tout générateur de clé construit à partir d’un polynôme générateur contenant (x^hÅ1) en facteur, détecte toutes les erreurs impaires.

6 -     Tout générateur de clé construit à partir d’un polynôme générateur primitif de degré k, détecte toutes les erreurs simples et doubles si la séquence d’entrée est de longueur au plus égale à 2^k - 1.

7 -     Tout générateur de clé construit à partir d’un polynôme générateur de la forme g(x)=(x Å 1).f(x) avec f(x) polynôme primitif de degré k, détecte toutes les erreurs impaires et doubles, donc en particulier les erreurs simples, doubles et triples, si la séquence d’entrée est de longueur au plus égale 2^k - 1.

8 -     Tout générateur de clé construit à partir d’un polynôme générateur de degré k, détecte tous les types d’erreurs de longueur inférieure ou égale à k dans un message de longueur n (n > k).

9 -     Si le polynôme générateur choisi est irréductible de degré k, alors il détecte ces erreurs répétitives avec une probabilité proche de 1-2^-k. S’il n’est pas irréductible, il ne détecte ce type d’erreurs qu’avec une probabilité de 1-2^-k/b, où b est la plus forte puissance relative au polynôme décomposé en facteurs irréductibles.

Ces propriétés montrent que le polynôme générateur joue un rôle capital, selon son type (primitif, irréductible, quelconque) et selon son degré. Même avec un polynôme de degré réduit, on constate que la vérification de clé est dotée d’un pouvoir de détection de fautes élevé, quelles que soient les hypothèses de fautes supposées.

A chaque code détecteur d'erreur est associé une distance caractéristique "la distance minimale de HAMMING".

Un code de distance d_min détectera toute les configurations de d_min - 1 erreurs.

---

1.3.Réalisation d’un C.R.C.

Deux méthodes permettent de réaliser le C.R.C :

·      La division polynomiale

·      La méthode du OU-Exclusif

1.3.1.La division polynomiale

Une suite d’informations numériques représente un message. A tout message est associé une représentation algébrique, c’est-à-dire un polynôme de degré n-1 si le message comprend n informations.

Le message m = [ a_n-1 a _n-2 a_n-3 ... a ₂ a₁ a₀ ] est associé à un polynôme m(x) :

m(x) = a_n-1.X^n-1  a_n-2.X^n-2  ... a₁.X¹  a₀ ,

où X est une variable muette et les coefficients a_i des valeurs binaires. Par convention, le coefficient a_n-1 est le premier bit transmis et correspond au plus fort degré du polynôme. Par exemple, le message n=(1,0,1,1,0,0,0,1) donne le polynôme n(x) = x⁷  x⁵  x⁴  1.

L’opérateur (OU Exclusif) est utilisé car nous ne considérons que des valeurs binaires, chaque bit du message étant traité séparément. L’algèbre sur les polynômes modulo 2 se définit par les opérations binaires suivantes : l’addition, la soustraction, la multiplication et la division. En arithmétique modulo 2, l’addition et la soustraction sont identiques.

La division polynomiale est une division de m(x) par g(x) qui consiste à chercher un quotient q(x) et un reste r(x) de degré inférieur à celui de g(x) tel que :

m(x) = [q(x) g(x)] r(x)

ou :   m(x) - [q(x) g(x)] = r(x)

Cette deuxième forme fait apparaître un mécanisme de soustractions successives où g(x) est décalé de k rangs à gauche, c’est-à-dire multiplié par x^k, afin d’atteindre le monôme de plus haut degré de m(x). Alors, q(x) possède un monôme en x^k.

Une séquence d’informations correspondant au polynôme m(x) est comprimée au moyen d’une division de m(x) par un polynôme générateur g(x). La clé est le résultat de cette division : soit le quotient, soit le reste selon le type de réalisation effectué.

Posons le polynôme générateur g(x) = x^k + b_n-1.x^n-1 + ... + b₁.x¹ + 1

 

1.1.Réalisation pratique d’un C.R.C. par la méthode de la division polynomiale

Le principe de la division de deux polynômes peut être mis en oeuvre de façon :

• ·      matériel,
• ·      logiciel.

D’un point de vue matériel, des registres à décalage et des OU-exclusifs sont utilisés, et peuvent avoir une structure série ou parallèle. La clé est alors le reste de la division de m(x) par g(x) qui est le contenu final du registre à décalage

Pour la structure série, les données arrivent en série sur la ligne d’informations. Avec une structure parallèle, les données arrivent sur plusieurs lignes d’informations.

Les générateurs de clé série (voir Figure) et parallèle (voir Figure) construits à partir d’un même polynôme générateur primitif ont la même efficacité.

Dans la structure série présentée ci-dessous, les informations arrivent par l’entrée E, puis entrent dans le registre à décalage.

           Figure : Générateur de clé de type SERIE avec g(x) = x⁴ + x + 1

Soit la séquence d’entrée (1,1,0,1,0,0,0,1,1), soit le polynôme d’entrée E(x) = x⁸+x⁷+x⁵+x+1.

Les états des registres sont décrits pour chaque front d’horloge dans le Tableau  : Etats des registres d'un générateur de clé de type série.

 

 

Tableau  : Etats des registres d'un générateur de clé de type série

E(x) = [ q(x) g(x) ] r(x)

d’où E(x)/g(x) = q(x) [ r(x)/g(x) ]

Le contenu final du registre est égal au reste de la division. De la même manière, nous pouvons construire un générateur à entrées parallèles.

Les informations en série notées (a_n-1, a_n-2, a_n-3, a_n-4, ..., a₁, a₀) sont groupées par bloc de 4, soient (a_n-1, a_n-2, a_n-3, a_n-4 / a_n-5, a_n-6, a_n-7, a_n-8 / ...) et présentées en parallèle sur chacune des entrées E₀, E₁,.E₂, E₃. En un seul front d’horloge, le résultat est établi pour ces 4 valeurs.

Soient y₀, y₁,.y₂, y₃, les états des registres à un instant « t » quelconque et a, b, c, d, les valeurs des registres évoluant suivant le Tableau  : Etats des registres d'un générateur de type parallèle.

Figure  : Générateur de clé à entrées parallèles avec g(x) = x⁴ + x + 1

La division polynomiale nécessite plus de cycles machine puisqu’il faut autant d’opérations (décalage + OU exclusif) que de bits contenus dans le message à contrôler.

 

Tableau  : Etats des registres d'un générateur de type parallèle

Nous obtenons les 4 fonctions suivantes :

a = a’  y₂ = a_n-1  y₃  y₂

b = b’  y₁ = a_n-2  y₂  y₁

c = c’  y₀ = a_n-3  y₃  y₁  y₀

d = d’ = a_n-4  y₀  y₃

1.3.2.Méthode et réalisation pratique d’un CRC à partir d’un OU-Exclusif

Il existe une autre méthode afin de déterminer la clé. L’obtention d’une clé peut faire appel à un registre à décalage où certains bits sont bouclés sur l’entrée par l’intermédiaire de la fonction logique OU-Exclusif (Figure : Registre à décalage 16 bits (générateur de clé)). La clé correspond alors au contenu final du registre après passage en série de l’ensemble des informations. La longueur du registre ainsi que les bouclages sont fonction du polynôme P(x) qui, pour des applications usuelles, est généralement de degré 8 ou 16.

Soit P(x) = x¹⁶ + a₁₅.x¹⁵ + a₁₄.x¹⁴ + ... + a₁.x + a₀       avec a₁₅ ... a₀ = « 0 » ou « 1 »,

Figure  : Registre à décalage 16 bits (générateur de clé)

La clé obtenue grâce à ce principe peut également être calculée par logiciel avec un algorithme adapté. L’algorithme correspondant s’obtient en observant le contenu du registre après 16 décalages successifs.

Si (y₀ ... y₁₅) est l’état initial du registre à t = 0 et (a₀ ... a₁₅) les 16 bits du message d’entrée, alors le contenu final du registre (x₀ ... x₁₅) après 16 décalages sera :

 

 

La colonne 1 représente la totalité du message d’entrée, les colonnes 2 à 7, hors la zone encadrée, représentent le contenu initial du registre décalé respectivement de 5 à 0 rangs.

Il ne reste plus alors qu’à effectuer les OU-Exclusifs entre les valeurs issues du bouclage (partie encadrée). Celles-ci seront déterminées par simple lecture à l’adresse pointée par l’adresse du début du tableau indexée de la valeur du quintuplet.

Ces valeurs seront lues directement dans un tableau de 2⁵ = 32 éléments dans lequel on trouve, pour chaque quintuplet (x₁₅, x₁₄, x₁₃, x₁₂, x₁₁), la valeur correspondante de x₁₅, x₁₅  x₁₄, x₁₅  x₁₄  x₁₃  , x₁₅  x₁₄  x₁₃  x₁₂, x₁₅  x₁₄  x₁₃  x₁₂  x₁₁.

 

---

1.4.      Les codes correcteurs d’erreurs (codes de HAMMING).

Il est important de ne pas confondre distance de Hamming et codes de Hamming. Les codes de Hamming sont des codes détecteurs et correcteurs d’erreurs particuliers.

1.4.1.Principe des codes de Hamming

Si un transfert d’informations n’est pas correct, il existe 2 manières de retrouver la donnée :

·      en demandant la ré-émission du message,

·      en corrigeant l’erreur.

Il n’est pas toujours possible de demander une ré-émission du message. Le fait de corriger ces erreurs de transmission est alors primordial.

Les codes de Hamming permettent de détecter et de corriger les erreurs simples.

La méthode consiste à ajouter à un message de M digits, K digits de contrôle constituant ainsi un ensemble de (M + K) digits.

Il faut pour un mot de taille M digits, K digits de contrôle, or K digits ne permettent de définir que 2^K combinaisons, d’où :

M + K + 1 £ 2^K

Ce qui donne pour différente valeur de M, le tableau suivant :

M     (bits)	K (contrôle)
4	3
8	4
16	5
32	6

1.4.2.Utilisation des Codes de Hamming

Pour montrer de quelle façon sont élaborés ces digits, on se place dans le cas d’un message de 4 digits (M = 4) ; 3 digits de contrôle (K = 3) sont alors nécessaires.

L’ensemble du message codé constitue alors un mot de 7 digits écrit sous la forme :

X = [ a₁, a₂, a₃, a₄, a₅, a₆, a₇ ]

Les K digits de contrôle sont placés en a₁, a₂ et a₄ sous réserve qu’il y en ait au moins un dans chacun des groupes (a₁, a₃, a₅, a₇), (a₂, a₃, a₆, a₇) et (a₄, a₅, a₆, a₇). Les digits de contrôle sont disposés de façon à ne contrôler que des digits « informatifs » et non d’autres digits de contrôle.

Les états des digits de contrôle sont donnés par les relations suivantes :

a₁ = a₃  a₅  a₇

a₂ = a₃  a₆  a₇

a₄ = a₅  a₆  a₇

Les codes de Hamming sont des codes détecteurs d’erreurs mais aussi correcteur d’erreurs. Il est donc possible de déterminer la position de l’erreur dans un message codé.

Dans notre exemple, l’erreur peut se placer parmi 7 positions. Il est alors nécessaire d’utiliser 3 bits pour coder en binaire la position de l’erreur dans le message codé.

La position de l’erreur se note en binaire [e₃, e₂, e₁ ], et les états e₃, e₂ et e₁ sont définis de la manière suivante :                         e₁ = a₁  a₃  a₅  a₇

                                                           e₂ = a₂  a₃  a₆  a₇

                                                           e₃ = a₄  a₅  a₆  a₇

A l’émission, les égalités e₃ = e₂ = e₁ = 0 doivent être assurées, ce qui signifie qu’aucune erreur n’est détectée.

Si les égalités ne sont pas vérifiées, la position de l’erreur est indiquée dans le Tableau 3 : Position du bit erroné en fonction du code binaire de l’erreur ci-dessous :

Position de l’erreur	e3	e2	e1	digit n°
Aucune erreur	0	0	0
a1	0	0	1	1
a2	0	1	0	2
a3	0	1	1	3
a4	1	0	0	4
a5	1	0	1	5
a6	1	1	0	6
a7	1	1	1	7

Tableau : Position du bit erroné en fonction du code binaire de l’erreur

X = [ a₁, a₂, a₃, a₄, a₅, a₆, a₇ ]       E = [e₃, e₂, e₁ ]

Les codes de Hamming ne détectent pas l’erreur double. Pour y parvenir, un digit de contrôle supplémentaire (bit de parité) portant sur l’ensemble du message X est ajouté. La longueur du nouveau message codé est alors (M+K+1) digits. Après transmission du message, ce dernier est contrôlé afin de vérifier sa validité.

Si la parité globale est inexacte : le test précédent est appliqué au mot de (M+K) digits :

• · Si une erreur simple, double ou triple est détectée, elle est corrigée.
• · Si aucune erreur n’est détectée le mot est exact, l’erreur porte sur le dernier digit de contrôle global.

Si la parité globale est exacte, il y a 0 ou 2 erreurs ; le test de Hamming est appliqué.

• · Si aucune erreur n’est détectée, il n’y a pas d’erreur.
• · Si une erreur est détectée, il y a 2 erreurs, le mot est faux et aucune correction n’est possible.