Contrôle et corrections des données - Contrôle à parité - Algorithmes de corecction Hamming
1 Contrôle des données
1.1 Introduction
1.2 Contrôle à parité
1.3 Le contrôle de parité croisé
1.4 Le Contrôle de Redondance Cyclique
1.5 D'autres types de code
2 Correction des données
2.1 Principe de la correction
2.2 Les algorithmes de correction
2.2.1 Le code de Hamming
2.2.2 Le Code de Reed-Solomon
1 Contrôle des données
1.1 Introduction
Le contrôle des données consiste à assurer la véracité des données transmises. Ce contrôle est mis en place afin d'assurer la cohérence de celles-ci que ce soit pour garantir une transmission de donnée à travers une ligne de communication ou pour un stockage des données en mémoire ou sur une unité de stockage. Cette recherche de cohérence est liée au fait que les composants ou les transmissions peuvent subir des perturbations dégradant les données.
Afin d'assurer cette véracité plusieurs mécanismes plus ou moins complexes ont été mis en place. Tous ces mécanismes sont basés sur l' out d'informations complémentaire "codant" ce contrôle.
Le contrôle de parité fonctionne selon un principe très simple. Aux n bits que comporte le code à l‘origine, on ajoute un bit supplémentaire.
1.2 Contrôle à parité
Le contrôle de parité a été le premier système mis en place et reste l'un des plus simple.
Son principe est basé sur l' utilisation d'un bit supplémentaire assurant la fonction de parité paire ou impaire.
En cas de parité paire:
o le bit de parité vaut 0 si le nombre de bits précédents est pair
o le bit de parité vaut 1 si le nombre de bits précédents est impair
En cas de parité impaire:
o le bit de parité vaut 0 si le nombre de bits précédents est impair
o le bit de parité vaut 1 si le nombre de bits précédents est pair
Ce type de codage est utilisé :
- En transmission série (norme V24)
o On parle de transmission en 7 bits parité paire, 8 bits parité impaire..
- En contrôle de plan de mémoire dynamique
Le principe fait appel à deux mécanismes :
o Un système réalise le codage du bit de contrôle
o Un système réalise la vérification du bit de contrôle
1.2 Contrôle à parité
1.3 Le contrôle de parité croisé
1.4 Le Contrôle de Redondance Cyclique
1.5 D'autres types de code
2 Correction des données
2.1 Principe de la correction
2.2 Les algorithmes de correction
2.2.1 Le code de Hamming
2.2.2 Le Code de Reed-Solomon
1 Contrôle des données
1.1 Introduction
Le contrôle des données consiste à assurer la véracité des données transmises. Ce contrôle est mis en place afin d'assurer la cohérence de celles-ci que ce soit pour garantir une transmission de donnée à travers une ligne de communication ou pour un stockage des données en mémoire ou sur une unité de stockage. Cette recherche de cohérence est liée au fait que les composants ou les transmissions peuvent subir des perturbations dégradant les données.
Afin d'assurer cette véracité plusieurs mécanismes plus ou moins complexes ont été mis en place. Tous ces mécanismes sont basés sur l' out d'informations complémentaire "codant" ce contrôle.
Le contrôle de parité fonctionne selon un principe très simple. Aux n bits que comporte le code à l‘origine, on ajoute un bit supplémentaire.
1.2 Contrôle à parité
Le contrôle de parité a été le premier système mis en place et reste l'un des plus simple.
Son principe est basé sur l' utilisation d'un bit supplémentaire assurant la fonction de parité paire ou impaire.
En cas de parité paire:
o le bit de parité vaut 0 si le nombre de bits précédents est pair
o le bit de parité vaut 1 si le nombre de bits précédents est impair
En cas de parité impaire:
o le bit de parité vaut 0 si le nombre de bits précédents est impair
o le bit de parité vaut 1 si le nombre de bits précédents est pair
Ce type de codage est utilisé :
- En transmission série (norme V24)
o On parle de transmission en 7 bits parité paire, 8 bits parité impaire..
- En contrôle de plan de mémoire dynamique
Le principe fait appel à deux mécanismes :
o Un système réalise le codage du bit de contrôle
o Un système réalise la vérification du bit de contrôle
Mécanisme de codage et de contrôle de parité sur un plan mémoire
Ce contrôle est très utilisé, cependant est fragile car incapable de détecter plus d'une erreur, voire même la donnée peut être entièrement erronée sans que cela ne se remarque.
Si plus d'un bit est en erreur, celle-ci ne sera pas détectée.
Exemple en parité paire :
o 1100 0011 0 Codage de départ
o 1100 1011 0 Erreur : octet => 5 chiffres 1 donc le bit de parité devrait être 1
o 1100 0000 0 Erreur non détectable (2 bits sont passés de 1 à 0)
1.3 Le contrôle de parité croisé
Ce type de contrôle ne consiste pas uniquement à contrôler l'i intégrité des données d'un caractère mais à contrôler l'i intégrité des bits de parité d'un bloc de caractères.
Ce type de contrôle est basé sur deux mots de contrôle :
- Le VRC (Vertical Redundancy Check) Contrôle vertical de redondance. Désigne la parité appliquée à un mot et non pas à la suite des mots (parité longitudinale).
- Le LRC (Longitudinal Redundancy Check) Contrôle longitudinal de redondance :
système de détection d'erreurs par parité s'appliquant à la totalité d'un bloc, par opposition à la parité « verticale » qui s'applique à chaque mot de ce bloc.
Exemple :
Dans ce cas, l'information est codée sur 7 bit le 8éme bit étant réservé qu'au codage du bit de contrôle.
Exemple :
Dans ce cas, l'information est codée sur 7 bit le 8éme bit étant réservé qu'au codage du bit de contrôle.
La vérification du bloc est plus robuste aux erreurs que le précédent puisqu'il assure un double contrôle horizontal et vertical. En cas d'erreur, l est également possible de corriger celle-ci
puisqu'elle est localisable :
Exemple d'erreur corrigeable :
L'erreur ici est détectable et corrigeable. Ce code fait partie des premiers codes à correction d'erreur
Autre exemple :
Dans ce cas, les 2 erreurs sont détectées mais ne peuvent être corrigées
Exemple d'erreur non corrigeable :
Dans ce cas, les colonnes en cause sont repérées, par contre on ne sait pas quelle ligne est en défaut.
1.4 Le Contrôle de Redondance Cyclique
Ce type de contrôle est souvent désigné par ses lettres CRC.
Ce mécanisme consiste à protéger des blocs de données en ajoutant un code de contrôle. Ce code « CRC » contient des éléments redondants par rapport aux données transmises de manière à permettre la détection des erreurs, mais également de les réparer dans certains cas. Il est utilisé dans le cas de transmission d'une grande série d'octets.
Ce code est basé sur le fait que toute chaîne binaire permet de construire un polynôme, chacun des bits donnant sa valeur au coefficient polynomial correspondant.
Ex :
La mise en place du code CRC nécessite de choisir un polynôme de référence appelé polynôme générateur nommé souvent G(x).
Algorithme de codage et décodage CRC
- Le CCITT a normalisé l'utilisation d'un polynôme de degré 16
- Ethernet, utilise également un contrôle basé sur un CRC. Le "reste" porte le nom de FCS (Frame Check Sequence) et est codé sur 32 bit . Le polynôme utilisé est du 32éme ordre:
- Certains polynômes ont été normalisés, et on parle alors de CRC16, CRC12 … Dans tous les cas, il est important qu'émetteur et récepteur utilisent le même polynôme de référence.
x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x1 + 1
1.5 D'autres types de code :
Indépendamment des codages vus ci-dessus qui sont des codes normalisés, il est possible d'utiliser toute autre méthode de calcul du caractère de contrôle. Celui-ci peut être obtenu à partir d'opérations sur les caractères de la trame (addition, soustraction, fonctions logiques), et peut également être codé sur un ou plusieurs octets.
L'objectif reste dans tous les cas de fiabiliser la transmission en détectant les erreurs de transmission.
2 Correction des données
2.1 Principe de la correction
S'il est facile de détecter les erreurs (voir les méthodes ci-dessus), l est plus difficile de les corriger, puisqu'il faut que la transmission des données assure une redondance de l'information afin de pouvoir assurer cette correction. De plus, les algorithmes à mettre en Œuvre sont plus complexes et donc plus long en temps de traitement.
En transmission de donnée, les méthodes de correction sont rarement appliquées (la redondance impliquant des trames beaucoup plus longues), les algorithmes assurent la détection et en cas d'erreur demandent la ré-émission de la trame en défaut.
Par contre, en cas de stockage des données, cette correction doit être mise en Œuvre puisqu'en cas d'erreur, c'est la donnée elle-même qui est corrompue, et il est nécessaire de la reconstituer.
Les cas d'utilisation les plus courants sont :
o Les méthodes ECC pour les plans mémoires des serveurs
o Les technologies RAID pour les disques durs
2.2 Les algorithmes de correction
2.2.1 Le code de Hamming
Le plus célèbre d'entre eux est le code de Hamming (datant des années 50), ou plutôt la famille de code de Hamming (code normal, étendu, cyclique). L'utilisation de la méthode dépend essentiellement de la tolérance à l'erreur que l'on souhaite (correction d'1 ou de plusieurs bits en défaut).
Le principe est basé sur l’algèbre linéaire et sur l’utilisation de matrices (matrices de Hamming). Il consiste à rajouter des codes de contrôle en plus des informations à transmettre.
Le nombre de ces codes de contrôle dépend directement du niveau de fiabilité que l'on souhaite obtenir.
Application à la mémoire ECC :
o 64 bits ‰ 8 bits pour l'ECC
o 32 bits ‰ 7 bits
o 8 bits ‰ 4 bits
Application à la technologie Raid :
En technologie Raid, différentes techniques sont utilisées (codage par bloc ou secteur… ), et le contrôle n'est pas systématiquement assuré par un code de Hamming au niveau du stockage, celui-ci étant déjà compris dans la transmission de l'information (codage au niveau des contrôleurs). Néanmoins, on peut retenir comme principe l'utilisation d'un disque de contrôle pour 3 disques de données.
2.2.2 Le Code de Reed-Solomon
Les supports sont soumis à de nombreux problèmes :
o Défaut de lecture du Laser
o Défaut de surface : empreintes de doigts, rayures, salissures … attaques :
La correction d‘erreur sur un CD peut corriger jusqu'à‘à des blocs de 3500 erreurs consécutives en utilisant plusieurs niveaux de codes détecteurs et correcteurs d‘erreurs, séparés par un niveau d'entrelacement des informations : Cross Interleave Reed-Solomon (CIRC)
1.5 D'autres types de code :
Indépendamment des codages vus ci-dessus qui sont des codes normalisés, il est possible d'utiliser toute autre méthode de calcul du caractère de contrôle. Celui-ci peut être obtenu à partir d'opérations sur les caractères de la trame (addition, soustraction, fonctions logiques), et peut également être codé sur un ou plusieurs octets.
L'objectif reste dans tous les cas de fiabiliser la transmission en détectant les erreurs de transmission.
2 Correction des données
2.1 Principe de la correction
S'il est facile de détecter les erreurs (voir les méthodes ci-dessus), l est plus difficile de les corriger, puisqu'il faut que la transmission des données assure une redondance de l'information afin de pouvoir assurer cette correction. De plus, les algorithmes à mettre en Œuvre sont plus complexes et donc plus long en temps de traitement.
En transmission de donnée, les méthodes de correction sont rarement appliquées (la redondance impliquant des trames beaucoup plus longues), les algorithmes assurent la détection et en cas d'erreur demandent la ré-émission de la trame en défaut.
Par contre, en cas de stockage des données, cette correction doit être mise en Œuvre puisqu'en cas d'erreur, c'est la donnée elle-même qui est corrompue, et il est nécessaire de la reconstituer.
Les cas d'utilisation les plus courants sont :
o Les méthodes ECC pour les plans mémoires des serveurs
o Les technologies RAID pour les disques durs
2.2 Les algorithmes de correction
2.2.1 Le code de Hamming
Le plus célèbre d'entre eux est le code de Hamming (datant des années 50), ou plutôt la famille de code de Hamming (code normal, étendu, cyclique). L'utilisation de la méthode dépend essentiellement de la tolérance à l'erreur que l'on souhaite (correction d'1 ou de plusieurs bits en défaut).
Le principe est basé sur l’algèbre linéaire et sur l’utilisation de matrices (matrices de Hamming). Il consiste à rajouter des codes de contrôle en plus des informations à transmettre.
Le nombre de ces codes de contrôle dépend directement du niveau de fiabilité que l'on souhaite obtenir.
Application à la mémoire ECC :
o 64 bits ‰ 8 bits pour l'ECC
o 32 bits ‰ 7 bits
o 8 bits ‰ 4 bits
Application à la technologie Raid :
En technologie Raid, différentes techniques sont utilisées (codage par bloc ou secteur… ), et le contrôle n'est pas systématiquement assuré par un code de Hamming au niveau du stockage, celui-ci étant déjà compris dans la transmission de l'information (codage au niveau des contrôleurs). Néanmoins, on peut retenir comme principe l'utilisation d'un disque de contrôle pour 3 disques de données.
2.2.2 Le Code de Reed-Solomon
Les supports sont soumis à de nombreux problèmes :
o Défaut de lecture du Laser
o Défaut de surface : empreintes de doigts, rayures, salissures … attaques :
La correction d‘erreur sur un CD peut corriger jusqu'à‘à des blocs de 3500 erreurs consécutives en utilisant plusieurs niveaux de codes détecteurs et correcteurs d‘erreurs, séparés par un niveau d'entrelacement des informations : Cross Interleave Reed-Solomon (CIRC)
Article plus récent Article plus ancien
