1 CRC (Cyclic Redundancy Check)

The CRC is an encoding method that consist to group when transmitting information in words of "n-k" bits and to associate them to a word of "n" bits. The redundancy consists of the "k" bits. The number of possible words of "n" elements is "2 ^n-k" and the other words correspond to words affected by errors.

The methods of "verification by key" objectives are to compress the information. From a finished sequence of information of length "n-k" , a compression mechanism (CRC - Cyclic Redundancy Check), characterizes this sequence of information with condensed information: the key. This key does not correct the errors, this key can detect the differences between several sequences.

 

1.1.Error detection Mecanism

Consider the following data:

• m _i = the number of sequences of informationhaving the same key .
• n-k = size of the information sequence (fixed or variable).
• k = key size (resulting from the polynomial division).
• n = size of the message.

The verification mechanism with key is to compress a message consisting of "n-k" symbols in a finite number of bits (k) .

Each key, of resulting value"S _i" is representative of a number "m _i" of sequences of information of fixed or variable size. The key "S _i", is a word of 'k' bits that can take ^"2^k" different values.

For an information sequence "m_i" of constant size "n" , there are 2ⁿ possible forms, and each of these form, there is only one possible key whose value is comprised between "0" and "2^k " and the following is obtained:

The probability of detection of error for a sequence "m _i" (rpresented by the key "S_i"₎  represent the probability of obtain the same value of the key "S _i" from an erroneous  sequence "m _i" .

The probability of detection of error associated with a key "S _i",  is defined as follows:

 

m_i-1 : represents the number of m-sequences m_i having the same key as the exact sequence,

2ⁿ-1 : correspond to the total number of possible sequences (2ⁿ) minus the exact sequence (1).

Either:

In order to calculate the average detection power, we must sum all the cases corresponding to "m_i" information sequences. There are m _i sequences of information whose probability of error detection is P _{det_i.} The average value for all the "2ⁿ" possible sequences is :

 

or 

,  

from where

 

 

In the case of networks transmission, "n" is not generally constant (frames vary in length). Therefore, the residual errors are composed of all the possible combinations of errors on different frame length.

An "m _i" sequence information can be written as follows:

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

Thus we get:

whether

Are derived from the above formula that the probability of error detection of a compression mechanism is maximum when m _i is constant regardless S_i,

we obtain  m_i = 2^n-k  :

And we have:

When the key is a constant number of information sequences, the probability of error detection is optimal.

Otherwise, if there is a different number of information sequences, the probability of error detection will be less than P_{det max}  and must be estimated in each case.

 

1.2.Properties and choice of a polynomial generator key 

The polynomials generator keys are generally classified into the following three types, regardless of their degree:

· Irreducible polynomials

• A polynomial of degree k is irreducible if it is not divisible by a polynomial of degree less than k, except by 1.

For instance,

a(x) = x⁴  x³  x²  x  1 of degree 4, and

b(x) = x⁸  x⁴  x³  x  1  of degree 8,

are irreducible polynomials.

primitive polynomials

• An irreducible polynomial of degree k is primitive if it is a divisor of the polynomial xⁿ - 1 with n = 2^k - 1, without the fact to be a divisor of all polynomial of x^m - 1 where m < n. This polynomial may also be divisor of certain polynomials x^p - 1 where p> n.

Irreducible or primitive polynomials are obtained by a complex mathematical algorithm that is difficul to perform manually if the level is high. Note that there are still primitive polynomials whatever the desired degree.

· The arbitrary polynomial (nor irreducible nor primitive)

Detect the maximum possible error generator polynomial key aims. For that he must comply with the following rules:

1 - if we take a key s(x) corresponding to the input sequence m(x) and obtained using the generator polynomial g(x) primitive and irreducible. If we call e(x) an error sequence, ie which has "1" in the wrong locations and "0" elsewhere, then the origin message m(x) and the wrong message m(x)  e(x) have the same key s(x) if and only if e(x) is a multiple of g(x) modulo 2.

Therefore, the smaller erroneous sequence is g(x), where:

2 - If the generator polynome is of degree k, any errors that may affect an input sequence of length n £ k are detected. It is then possible to determine the number of undetected erroneous ³ for n k sequences, as they are all multiples of g (x).

The length input sequences correspond to n polynomials of degree n-1. There is thus 2 ⁿ -1 possible sequences for each polynomial has "n" and these coefficients may take "0" or "1" values.

We prove by induction that there are N = 2 ^nk - 1 erroneous sequences that are undetectable. Thus, for m = n, we obtain  erroneous base sequences,  erroneous sequences by combining base pairs, etc ..., and finally an erroneous sequences by combining all base sequence sequences or  . From where:

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 8) et parallèle (voir Figure 9) 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.