parité

Une définition du Jargon Français.
Aller à : Navigation, rechercher

nom féminin.  [flux de données]  [réseau]  [RAID]. Désigne toute information grâce à laquelle le récepteur ou lecteur d'un lot de données détecte voire corrige certaines erreurs de transmission ou de stockage.

Att.png Il ne s'agit ici que de détection d'erreur et non d'assurance d'intégrité (voir empreinte numérique).

Bit de parité

Il s'agissait tout d'abord d'un bit, dit bit de parité, dont on convient qu'il flanque tout lot de données et dont la valeur, calculée par l'émetteur, dépend des valeurs de ces dernières. Le destinataire ou lecteur effectue le même calcul : si les données dont il dispose ont été par erreur modifiées il pourra dans certains cas le détecter.

Un qualificatif précise ce que le bit de parité exprime : « parité paire » signifie qu'il est armé si le nombre de bits à 1 à transmettre, bit de parité compris, est impair. « Parité impaire » est la réciproque. Inclure ainsi le bit de parité dans le calcul permet de détecter une erreur ayant modifié sa valeur.

Ce procédé n'offre moyen de détecter que les erreurs portant sur un nombre de bits impair et ne permet pas de corriger.

Exemple

Il faut tout d'abord définir une convention portant sur le volume de chaque lot, l'emplacement du bit de parité et le type de parité. Nous choisirons ici de « communiquer après chaque groupe de 4 bits transmis un bit de 'parité paire' ».

Si l'expéditeur doit envoyer « 1100 » il déterminera tout d'abord que le nombre de bits armés, qui est égal à 2, chiffre pair, donc qu'il lui faudrait armer le bit de parité. Le fait même de l'armer rend impair le nombre théorique de bits armés dans le lot expédié (bit de parité compris), donc le bit de parité expédié sera désarmé. Il expédiera « 11000 ».

Si l'expéditeur reçoit contenant un nombre de bits erronés impairs il le détectera en effectuant le même calcul puis en vérifiant le résultat. Si le nombre de bits erronés est pair cette méthode ne fonctionne pas : recevoir « 11101 », par exemple, n'inquiétera pas le destinataire.

Sens contemporain

Le sens s'est étendu à tout lot de données jouant ce genre de rôle : résultat d'un OU exclusif binaire appliqué aux données, checksum, CRC, ECC ... Noter que les algorithmes produisant certaines de ces dernières permettent de corriger certaines erreurs.

Cas du « OU exclusif binaire »

Stocker le OU exclusif binaire de toutes les données offre moyen de recouvrer l'une d'elles, par exemple dans une baie RAID de type compris entre 3 et 6 dont un spindle est défectueux. La logique RAID stocke pour cela, lors de toute écriture d'un stripe, le résultat du XOR exclusif binaire des données écrites, appelé parité. Par « binaire » on entend ici que l'opération s'applique au niveau de chaque bit.

Exemple : un stripe de 3 octets contenant 3, 66 et 117 aura pour parité 22. Pour le vérifier, par exemple en Perl, il suffit d'invoquer « perl -e 'printf "Résultat : " . (( 33 ^ 66 ) ^ 117 ) . "\n";' », car en Perl l'opérateur « ^ » est le OU exclusif binaire.

Lors d'une lecture si l'un des octets du stripe est inaccessible il sera facile de le recouvrer en calculant le OU exclusif des données restantes et de la parité. Exemple : si la deuxième valeur manque on calculera : perl -e 'printf "Résultat : " . (( 33 ^ 22 ) ^ 117 ) . "\n";' ... qui fournit bien 66.

Voici la table de vérité du OU exclusif :

a b a XOR b
0 0 0
0 1 1
1 0 1
1 1 0

... la comparer à la suivante révèle pourquoi on appelle le résultat parité :

a b a + b
PAIR PAIR PAIR
PAIR IMPAIR IMPAIR
IMPAIR PAIR IMPAIR
IMPAIR IMPAIR PAIR