Les opérations bit à bit/Bit de parité

Les données d'un ordinateur ne sont pas des plus sûres qui soit. Évidemment, ces données peuvent être corrompues par un tiers malveillant, contenir des virus, etc. Mais certaines données sont corrompues pour des raisons qui ne relèvent pas de la volonté de nuire. Par exemple, les transmissions de données via un réseau local ou internet peuvent subir des perturbations électromagnétiques entre leur envoi et leur réception. Évidemment, les câbles réseaux sont conçus pour limiter les erreurs, mais ils ne sont pas une protection magique, capable de supprimer les erreurs de transmission. Dans le même genre, les mémoires ne sont pas des dispositifs parfaits, capables de fonctionner sans erreur. Pour donner un exemple, on peut citer l'incident de Schaerbeek. Le 18 mai 2003, dans la petite ville belge de Schaerbeek, une défaillance temporaire d'une mémoire faussa les résultats d'une élection. Cette ville utilisait une machine à voter électronique, qui contenait donc forcément une mémoire. Et on constata un écart de 4096 voix en faveur d'un candidat entre le dépouillement traditionnel et le dépouillement électronique. Mais ce n'était pas une fraude : le coupable était un rayon cosmique, qui avait modifié l'état d'un bit de la mémoire de la machine à voter. Cet incident n'était pas trop grave : après tout, il a pu corriger l'erreur. Mais imaginez la même défaillance dans un système de pilotage en haute altitude... Mais qu'on se rassure : il existe des techniques pour détecter et corriger les erreurs de transmission, ou les modifications non-prévues de données. Pour cela, divers codes de détection et de correction d'erreur ont vu le jour. Ce chapitre vous parlera du code le plus simple qui soit : le bit de parité/imparité, et de ses variantes.

Bit de parité horizontal mono-dimensionnel

Le bit de parité est une technique utilisée dans un grand nombre de circuits électroniques, comme certaines mémoires RAM, ou certains bus (RS232, notamment). Il permet de détecter des corruptions qui touchent un nombre impair de bits. Si un nombre pair de bit est modifié, il sera impossible de détecter l'erreur avec un bit de parité. Il faut noter que ce bit de parité, utilisé seul, ne permet pas de localiser le bit corrompu. Ce bit de parité est ajouté aux bits à stocker. Avec ce bit de parité, le nombre stocké (bit de parité inclus) contient toujours un nombre pair de bits à 1. Ainsi, le bit de parité vaut 0 si le nombre contient déjà un nombre pair de 1, et 1 si le nombre de 1 est impair. Si un bit s'inverse, quelle qu'en soit la raison, la parité du nombre total de 1 est modifié : ce nombre deviendra impair si un bit est modifié. Et ce qui est valable avec un bit l'est aussi pour 3, 5, 7, et pour tout nombre impair de bits modifiés. Mais tout change si un nombre pair de bit est modifié : la parité ne changera pas. Ainsi, on peut vérifier si un bit (ou un nombre impair) a été modifié : il suffit de vérifier si le nombre de 1 est impair. Le bit d'imparité est similaire a bit de parité, si ce n'est que le nombre total de bits doit être impair, et non pair comme avec un bit de parité. Sa valeur est l'inverse du bit de parité du nombre : quand le premier vaut 1, le second vaut 0, et réciproquement. Mais celui-ci n'est pas meilleur que le bit de parité : on retrouve l'impossibilité de détecter une erreur qui corrompt un nombre pair de bits.

Reste que ce bit de parité doit être calculé, avec un morceau de code dédié qui prend un nombre et renvoie le bit de parité.

Poids de Hamming et bit de parité

Par définition, le bit de parité n'est autre que la parité du poids de Hamming. Par définition, le bit de parité a pour but de faire en sorte que la population count d'une donnée soit toujours pair : la donnée à laquelle on ajoute le bit de parité sera pair, et aura toujours son bit de poids faible à zéro. En conséquence, le bit de parité d'un nombre est égal au bit de poids faible de la population count d'un nombre. Et cette propriété permet de donner des algorithmes de calcul du bit de parité d'un nombre assez efficace. Son calcul demande donc simplement de calculer le poids de Hamming et de déterminer s'il est pair ou non. Vu que le calcul du poids de Hamming a une complexité logarithmique en le nombre de bits de la donnée d'entrée, le code qui va suivre sera aussi dans ce cas. Cet algorithme est parfois utilisé sur des systèmes qui ont peu de mémoire, quand on a déjà programmé une fonction pour le poids de Hamming : cela permet d'économiser un peu de mémoire programme. Mais cet algorithme n'est pas le plus efficace en terme de temps de calcul.

unsigned population_count (unsigned word) ;

unsigned parity_bit (unsigned word)
{
    return population_count (word) & 1 ;
}

Il est cependant possible d'obtenir un code plus simple, qui est plus rapide. Pour cela, il suffit de spécialiser le code pour le poids de Hamming, de manière à ce qu'il calcule uniquement le bit de parité. En conséquence, la suite de cette partie se contentera de reprendre les algorithmes pour calculer le code de Hamming et de les adapter pour le bit de parité.

Algorithme itératif

Nous allons commencer par adapter le code itératif du calcul du poids de Hamming. Pour faire simple, la structure générale du code est conservée, mais il nous faudra remplacer les additions par une autre opération. Pour savoir quelle est cette opération, nous allons voir un cas simple : le calcul de la parité d'un nombre de 2 bits. Le circuit étant simple, il suffit d'utiliser les techniques vues précédemment, avec la table de vérité. En écrivant la table de vérité du calcul, on remarque rapidement que la table de vérité est celle d'une porte XOR.

Bit 1	Bit 2	Bit de parité
0	0	0
0	1	1
1	0	1
1	1	0

Pour la suite, nous allons rajouter un troisième bit au nombre de 2 bits précédent. L'ajout de ce troisième bit modifie naturellement le bit de parité du nombre précédent. Dans ce qui va suivre, nous allons voir comment calculer le bit de parité final, à partir : du bit de parité du nombre de 2 bits, et du bit ajouté. On voit alors que la table de vérité est celle d'une porte XOR.

Bit de parité précédent	Bit ajouté	Bit de parité final
0	0	0
0	1	1
1	0	1
1	1	0

Chose assez intéressante, ce mécanisme fonctionne quel que soit le nombre de bits du nombre auquel on ajoute un bit. Ajouter un bit à un nombre modifie sa parité, celle-ci état alors égale à : bit ajouté XOR bit-parité du nombre. L’explication est relativement simple : ajouter n 0 ne modifie pas le nombre de 1, et donc le bit de parité, tandis qu'ajouter un 1 inverse le bit de parité. Ainsi, on déduit que le bit de parité peut se calculer simplement : il suffit de faire un XOR entre tous les bits du nombre. Effectué naïvement, il suffit d'enchainer des portes XOR les unes à la suite des autres. Mais en réfléchissant, on peut faire autrement. Prenons deux nombres et concaténons-les. On peut déduire facilement le bit de parité de la concaténation à partir des bits de parité de chaque nombre : il suffit de faire un XOR entre ces deux bits de parité.

Il suffit donc de faire un XOR de tous les bits pour calculer le bit de parité d'un nombre. L’algorithme de calcul du nombre de parité est alors assez évident.

unsigned parity_bit (unsigned word ,unsigned size)
{    
    unsigned parity_bit = 0 ;

    // on itère sur chaque bit du mot à traiter
    for(unsigned index = 0 ; index < size ; ++index)
    {
        //sélection du bit de poids faible
        unsigned temp = word & 1
        word = word >> 1 ;

        // XOR entre le bit sélectionné et le bit de parité des bits précédents.
        parity_bit = parity_bit ^ temp ;
    }

    return parity_bit ;
}

Cette solution a un temps de calcul qui est linéaire en le nombre de bits de la donnée dont on veut calculer le bit de parité. On peut faire mieux en utilisant d'autres propriétés du bit de parité. Naturellement, on peut travailler non sur des bits, mais aussi sur des octets. Prenons un mot de 16 bits, par exemple : il me suffit de faire un XOR entre les bits de parité de ces deux octets. Or, la parité d'un octet peut se pré-calculer et être stockée dans un tableau une fois pour toute, afin d'éviter de nombreux calculs. Ainsi, l'algorithme vu précédemment peut être amélioré pour traiter non pas un bit à la fois, mais plusieurs bits à la fois.

unsigned ParityBit (unsigned x)
{ 
    static char table[256] = { 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, ... , 0, 1, 0, 1, 0, 1, 0, 1, 0, 1,} ; // Tableau qui contient les bits de parité de chaque octet

    FirstByte = x & 0xFF ;
    SecondByte = (x >> 8) & 0xFF ;
    ThirdByte = (x >> 16) & 0xFF
    ForthByte = (x >> 24) & 0xFF

    return table[FirstByte] ^ table[SecondByte] ^ table[ThirdByte] ^ table[ForthByte] ;
}

Algorithme récursif

On peut améliorer l'algorithme du dessus en utilisant la propriété suivante : si on concatène deux mots binaire, alors le bit de parité du mot obtenu est égal au XOR des bits de parité des deux mots concaténés. Cette propriété peut s'expliquer assez simplement. Pour cela, il suffit de regarder le nombre de bits à 1 dans chaque mot à concaténer.

Nombre de bits à 1 dans le mot binaire de gauche	Nombre de bits à 1 dans le mot binaire de droite	Nombre de bits à 1 dans le résultat
Pair	Pair	Pair
Pair	Impair	Impair
Impair	Pair	Impair
Impair	Impair	Pair

Si on remplace Pair et Impair par la valeur du bit de parité correspondant, on obtient exactement le fonctionnement d'une porte XOR.

On peut aussi inventer un autre algorithme du calcul du bit de parité, assez inefficace, basé sur une fonction récursive. Le principe est de couper le mot dont on veut la parité en deux morceaux. On calcule alors la parité de ces deux morceau, et on fait un XOR entre ces deux parités. Le code obtenu est alors celui-ci :

unsigned parity (unsigned word, size)
{
    if (word <= 1)
    {
        return word ;
    }
    else
    {
        unsigned gauche = word >> (size/2) ;
        unsigned droite = word % (size/2) ;
        return parity(gauche, size/2) ^ parity (droite, size/2)) ;
    }
}

Algorithme optimisé

Il est aussi possible de réutiliser l'algorithme de calcul du poids de Hamming, celui récursif basé sur des masques et des additions, pour calculer le bit de parité. La différence est que les bits ne doivent pas être additionnés, mais XORés. Fort de ce qui a été dit précédemment, on trouve que le code de calcul du bit de parité est le suivant pour un entier de 32 bits :

unsigned ParityBit (unsigned x)
{
    x = (x & 0x55555555) ^ ((x >> 1) & 0x55555555);
    x = (x & 0x33333333) ^ ((x >> 2) & 0x33333333);
    x = (x & 0x0F0F0F0F) ^ ((x >> 4) & 0x0F0F0F0F);
    x = (x & 0x00FF00FF) ^ ((x >> 8) & 0x00FF00FF);
    x = (x & 0x0000FFFF) ^ ((x >> 16) & 0x0000FFFF);

    return x ;
}

Il faut noter que cet algorithme est cependant simplifiable pour le calcul du bit de parité. L'usage des masques permet de XOR les bits de position paire et impaire, puis des groupes consécutifs de 2 bits, puis de 4 bits, etc. Mais pour le bit de parité, on peut effectuer le calcul dans l'autre sens. Pour des entiers de 64 bits, on peut commencer par XOR les 32 bits de poids fort avec les 32 bits de poids faible. Plus, sur les 32 bits du résultat, on peut XOR les 16 bits de poids fort et les 16 de poids faible. Et ainsi de suite... L'algorithme est donc plus simple, vu que l'on a pas besoin d'utiliser des masques, mais que l'on peut se contenter de décalages. Le code est donc le suivant :

unsigned ParityBit (unsigned x)
{
    x ^= (x >> 32) ;
    x ^= (x >> 16) ;
    x ^= (x >> 8) ;   
    x ^= (x >> 4) ;
    x ^= (x >> 2) ;
    x ^= (x >> 1) ;

    return x & 1 ;
}

Mot de parité

Si on peut calculer le bit de parité d'un mot, il est aussi possible de calculer des octets de parité pour un ensemble de Byte/mots machine. Le résultat de cette opération est ce qu'on appelle un mot de parité, une extension du bit de parité pour plusieurs nombres. On peut le voir comme l'équivalent d'un bit de parité pour un paquet de nombre. Cela sert sur les bus de communication entre composants, sur lesquels on peut envoyer plusieurs nombres à la suite, ou dans les mémoires qui stockent plusieurs nombres les uns à côté des autres. Il faut noter que le bit de parité peut être vu comme une spécialisation de la technique du mot de parité, où les blocs font tous 1 bit. Le calcul du mot de parité se calcule en disposant chaque nombre/bloc l'un au-dessus des autres, le tout donnant un tableau dont les lignes sont des nombres Le mot de parité se calcul en calculant le bit de parité de chaque colonne du tableau, et en le plaçant en bas de la colonne. Le résultat obtenu sur la dernière ligne est un octet de parité. Pour comprendre le principe, supposons que nous disposions de 8 entiers de 8 bits. Voici comment effectuer le calcul du mot de parité :

11000010 : nombre ;
10001000 : nombre ;
01001010 : nombre ;
10010000 : nombre ;
10001001 : nombre ;
10010001 : nombre ;
01000001 : nombre ;
01100101 : nombre ;
------------------------------------
10101100 : mot de parité.

L'avantage de cette technique est qu'elle permet de reconstituer un octet manquant. C'est cette technique qui est utilisée sur les disques durs montés en RAID 3, 5 6, et autres : si un disque dur ne fonctionne plus, on peut quand même reconstituer les données du disque dur manquant. Retrouver la donnée manquante est assez simple : il suffit de calculer la parité des nombres restants et de faire un XOR avec le mot de parité. Pour comprendre pourquoi cela fonctionne, il faut se souvenir que faire un XOR entre un nombre et lui-même donne 0. De plus, le mot de parité est égal au XOR de tous les nombres. Si on XOR un nombre avec le mot de parité, cela va annuler la présence de ce nombre (son XOR) dans le mot de parité : le résultat correspondra au mot de parité des nombres, nombre xoré exclu. Ce faisant, en faisant un XOR avec tous les nombres connus, ceux-ci disparaitrons du mot de parité, ne laissant que le nombre manquant.

Bit de parité multidimensionnel

On a vu que le bit de parité ne permet pas de savoir quel bit d'un nombre a été modifié. Mais il existe une solution pour que cela devienne possible, dans le cas où plusieurs nombres sont envoyés. Si on suppose qu'un seul bit a été modifié lors de la transmission du paquet de nombre, on peut détecter quel bit exact a été modifié. Pour cela, il suffit de coupler un mot de parité avec plusieurs bits de parité, un par nombre. Détecter l bit modifié est simple. Pour comprendre comment, il faut se souvenir que les nombres sont organisés en tableau, avec un nombre par ligne. Le bit modifié est situé à l'intersection d'une ligne et d'une colonne. Sa modification entraînera la modification du bit de parité de la ligne et de la colonne qui correspondent, respectivement un bit de parité sur la verticale, et un bit de parité dans le mot de parité. Les deux bits fautifs indiquent alors respectivement la ligne et la colonne fautive, le bit erroné est situé à l'intersection. Cette technique peut s'adapter non pas avec une disposition en lignes et colonnes, mais aussi avec des dimensions en plus où les nombres sont disposés en cube, en hyper-cube, etc.

◄ Retour vers « Le poids de Hamming »

Sommaire du livre

Continuer vers « Manipulations sur les bits de poids faible/fort » ►