Sécurité fonctionnelle - les codes détecteurs d'erreur - parité et chechsum

Submitted by root on Tue, 10/07/2014 - 21:54

Les transmissions d'information

Cas de la liaison RS 232 (liaison série)

La RS 232 ou V24 définit deux choses :

des niveaux électriques (+ 3 Volts à +25 Volts; -3 Volts à -25 Volts)
une liste de signaux aux fonctions définies

Dans le cas des liasons séries asynchrones, 2 informations sont ajoutées (au repos, le niveau éléctrique / logique de la ligne est à "1").

avant la transmission : un bit de START (valeur "0"; 1 période)
après la transmission : bit de STOP (valeur "1"; 1 à 2 périodes)

Dans le cas de la transmission des codes ASCII, 7 informations sont nécessaires. A cette information de 7 bit, est ajoutée un bit de parité.

Description de codages détecteurs - correcteurs d’erreurs

La distance de Hamming et le taux d’erreurs résiduelles sont différents pour toutes les méthodes qui permettent de détecter et de corriger ces erreurs de transmission. Les méthodes de codage qui seront présentées dans la première partie de ce document sont :

Les codes détecteurs d’erreurs par parité,
Les codes détecteurs d’erreurs CHECKSUM,
Les codes détecteurs d’erreurs C.R.C.
Les codes détecteurs et correcteurs d’erreurs par codes de HAMMING

Les deux premières méthodes sont décrites ci-après. Le CRC et les codes détecteurs / correcteurs d'erreurs sont décrits dans un autre article

1. La parité

1.1.Principe de la parité

C'est une somme modulo 2 des bits d'informations. La parité est dite paire lorsque le code de parité est égal à la somme modulo 2 des bits d'informations et impaire lorsque le code de parité est égal au complément de cette somme.

Ce mode de contrôle est utilisé dans les liaisons séries de type RS-232 et dans les microprocesseurs.

Avant chaque transmission d’un mot, un digit supplémentaire est ajouté. Il est appelé bit de parité. Après transmission, la présence d’une erreur simple change la parité et rend l’erreur incriminée détectable.

1.2.Détection d’erreurs - Erreurs résiduelles

Soient « p » la probabilité d’erreur individuelle d’un digit et « n » la longueur du mot.

La probabilité d’avoir une erreur unique est :

P(1) = P[1^er digit faux et les (n-1 suivants) justes] + P[1^er digit juste 2^ème digit faux et les (n-2 suivants) justes] + ...

P(1) = p(1-p)^n-1 + (1-p)p(1-p)^n-2+ (1-p)²p(1-p)^n-2+ ...

P(1) = n[p(1-p)^n-1]

De même on obtient :

La parité permet de détecter l’ensemble des erreurs impaires d’où un pouvoir de détection P_D de :

P_D = P(1) + P(3) + ... + P(2k-1)

Les erreurs non détectées sont l’ensemble des erreurs paires d’où un pouvoir de non détection P_ND de :

P_ND = P(2) + P(4) + ... + P(2k)

Ces chiffres sont fonction de p, et doivent être calculés en fonction des environnements.

En supposant que nous ayons une trame constituée de 8 bits d'informations et une clé de vérification par bit de parité (n=9). En modifiant un nombre pair de bits e={2, 4, 6, 8} dans la trame nous avons une autre trame dont les erreurs ne seront pas détectées par le contrôle de la clé de vérification.

Le taux d'erreur résiduelle peut être calculé conformément aux éléments fournis en page http://www.industry-finder.fr/la-securite-fonctionnelle-et-les-reseaux-de-terrain.html , et la probabilité d'erreur résiduelle qui en résulte est égale à la somme des erreurs paires soit :

R = R₁*R₂

avec : R₁=P(2)+P(4)+P(6)+P(8) - probabilité d'erreur sur la donnée

R₂ = probabilité pour que les délimiteurs de trame soient juste. Dans le cas de la parité simple, nous avons deux délimiteurs (début et fin de trame) soit une probabilité q * q = q²

Soit :

2. Le CHECKSUM

Il existe plusieurs méthodes utilisées pour réaliser un CHECKSUM telles que :

La méthode de la somme de contrôle modifiée,
L’addition arithmétique du contenu du message,
Les codes à parités entrelacées.

C’est cette dernière méthode que nous allons détailler.

2.1.Principe du CHECKSUM

Le principe du CHECKSUM à parités entrelacées consiste en un message de M digits, écrit sous la forme d’un tableau de « L » lignes et « C » colonnes (M = CL). A ce tableau, on ajoute une (L+1)^ème ligne et une (C+1)^èmecolonne construites de telle façon que les mots lus horizontalement et verticalement soient tous pairs.

La méthode consiste à déterminer le nombre de « 1 » contenu dans une ligne (colonne). Si ce nombre est pair, on affecte à l’intersection de cette ligne (colonne) et de la dernière colonne (ligne), l’état « 0 » ou l’état « 1 » si le nombre est impair. Cette opération est effectuée pour chaque ligne et chaque colonne. Le digit placé au croisement de la dernière ligne et de la dernière colonne est choisi pour assurer la parité de l’ensemble du message.

Par exemple, pour un message de M = 49 digits (7 mots de 7 bits):

Un ensemble de 64 digits (49 digits transmettant l’information et 15 digits réservés au contrôle) est obtenu et transmis en série dans le canal de transmission. A la réception, le tableau est reconstitué. Une seule erreur fait échouer les contrôle de parité de la ligne et de la colonne correspondante, il y a donc détection et correction possible.

Une erreur double ou quadruple est détectée mais ne peut pas être corrigée, l’erreur triple n’est pas toujours détectée.

Ce code est plus puissant que la parité mais nécessite des ressources matérielles supplémentaires. Un message ayant à l’origine M digits (M = CL) nécessite C + L + 1 digits de contrôle, soit un accroissement de redondances DR de :

Pour 7 bits d’informations, M = 49 DR = 15/49 = 0.31

Pour 15 bits d’informations, M = 225 DR = 31/225 = 0.14

2.2.Pouvoir de détection du CHECKSUM - Erreurs résiduelles

Le pouvoir de détection du CHECKSUM se calcule de façon différente selon le nombre d’octets, soit à partir d’une méthode principale, soit à partir d’une méthode probabiliste.

2.2.1.Méthode principale

Cette méthode consiste en un dénombrement exact de toutes les combinaisons de « N » mots de « P » bits d’une séquence d’informations conduisant à une somme identique à la somme « S » obtenue sur les « N » mots de la séquence contenant les informations originales.

Le pouvoir de détection théorique P_D est défini comme le rapport (exprimé en pourcentage) entre le nombre d’erreurs détectées N_DET par le contrôle et le nombre total d’erreurs N_TOT pouvant survenir sur la séquence d’informations à contrôler.

L’expression du nombre total d’erreurs N_TOT représente le nombre de combinaisons que peuvent prendre les (P x N) bits de la séquence à contrôler, ce qui donne pour N octets:

N_TOT = 2^P.N

La détermination du nombre N_DETou encore du nombre d’erreurs non détectées N_NDET sachant que N_DET + N_NDET = 2^P.N.

N_NDET correspond au nombre de combinaisons des « N » octets dont la somme est identique à la somme « S » obtenue sur les octets de la séquence d’informations en l’absence d’erreurs.

Le pouvoir de détection peut alors s’exprimer de la manière suivante :

Les calculs réalisant le dénombrement de toutes les combinaisons des « N » octets d’une séquence d’informations dont la somme est « S » conduisent aux formules suivantes :

pour S = 0 ; ; P = 8 bits (Nombre de bits dans un octet)

P_D = 100 x (1-1/2^8.N) » 100 %

Pour S [ k (2^P - 1),(k+1) (2^P - 1)] avec k entier [ 0 , N-1-INT(N/2^P)]

0! = 1

Le calcul numérique n’est possible que pour de petites valeurs de N (N < 40). Au-delà de ce niveau, il faut avoir recours à la méthode « probabiliste ».

2.2.2.« Méthode probabiliste »

Avec la « méthode probabiliste », chaque octet peut être considéré comme une variable aléatoire. Une configuration donnée étant la séquence des « N » variables aléatoires correspondantes.

Si l’on considère que la loi de distribution est la même pour chaque octet, (moyenne m, variance s²), lorsque « N » est grand (N>50), la distribution de la somme « S » des variables aléatoires est très sensiblement normale, de moyenne Nm et de variance Ns², d’où la probabilité que la somme des « N » variables soit égale à une valeur « s » :