Code Hamming : détection et correction des erreurs avec exemples

Qu'est-ce qu'une erreur ?

Les données transmises peuvent être corrompues pendant la communication. Il est susceptible d'être affecté par des bruits extérieurs ou d'autres défaillances physiques. Dans une telle situation, les données d’entrée ne peuvent pas être les mêmes que les données de sortie. Cette inadéquation est connue sous le nom d’« erreur ».

Les erreurs de données peuvent entraîner la perte de données importantes ou sécurisées. La plupart des transferts de données dans les systèmes numériques se feront sous la forme de « transferts de bits ». Même un petit changement peut affecter les performances de l’ensemble du système. Dans une séquence de données, si 1 est remplacé par 0 ou si 0 est remplacé par 1, cela est appelé « erreur de bit ».

Types d'erreurs

Il existe principalement trois types d'erreurs binaires qui se produisent lors de la transmission de données de l'expéditeur au récepteur.

• Erreurs sur un seul bit
• Erreurs sur plusieurs bits
• Erreurs d'éclatement

Erreurs sur un seul bit

La modification apportée à un bit dans toute la séquence de données est appelée « erreur sur un seul bit ». Cependant, l’apparition d’erreurs sur un seul bit n’est pas si courante. De plus, cette erreur ne se produit que dans un système de communication parallèle car les données sont transférées au niveau bit sur une seule ligne. Par conséquent, il y a plus de chances qu’une seule ligne soit bruyante.

Erreurs sur plusieurs bits

Dans la séquence de données, s'il y a un changement dans deux bits ou plus d'une séquence de données d'un émetteur à un récepteur, on parle d'« erreurs sur plusieurs bits ».

Ce type d'erreur se produit principalement dans les réseaux de communication de données de type série et parallèle.

Erreurs d'éclatement

Le changement de l'ensemble des bits dans la séquence de données est appelé « erreur de rafale ». Ce type d'erreur de données est calculé du premier changement de bit au dernier changement de bit.

Qu'est-ce que la détection et la correction des erreurs ?

Dans le système de communication numérique, l’erreur sera transférée d’un système de communication à un autre. Si ces erreurs ne sont pas détectées et corrigées, les données seront alors perdues. Pour une communication efficace, les données du système doivent être transférées avec une grande précision. Cela se fera en identifiant d’abord les erreurs et en les corrigeant.

La détection d'erreurs est une méthode de détection des erreurs présentes dans les données transmises d'un émetteur à un récepteur dans un système de communication de données.

Ici, vous pouvez utiliser des codes de redondance pour trouver ces erreurs, en les ajoutant aux données lorsqu'elles sont transmises depuis la source. Ces codes sont appelés « codes de détection d’erreurs ».

Il existe trois types de codes de détection d'erreur :

• Contrôle de parité
• Contrôle de redondance cyclique (CRC)
• Contrôle de redondance longitudinale (LRC)

Contrôle de parité

• On l’appelle également contrôle de parité.
• Il dispose d’un mécanisme rentable pour la détection des erreurs.
• Dans cette technique, le bit redondant est appelé bit de parité. Il est annexé à chaque unité de données. Le nombre total de 1 dans l'unité doit devenir pair, ce que l'on appelle un bit de parité.

Vérification de la redondance longitudinale

Dans cette technique de détection d'erreurs, un bloc de bits est organisé sous forme de tableau. La méthode LRC vous aide à calculer le bit de parité pour chaque colonne. L'ensemble de cette parité est également envoyé avec les données originales. Le bloc de parité vous aide à vérifier la redondance.

Contrôle de redondance cyclique

Le contrôle de redondance cyclique est une séquence de redondance qui doit être ajoutée à la fin de l'unité. C'est pourquoi l'unité de données résultante doit devenir divisible par un deuxième nombre binaire prédéterminé.

À destination, les données entrantes doivent être divisées par le même nombre. S'il n'y a pas de reste, l'unité de données est supposée correcte et est acceptée. Sinon, cela indique que l'unité de données est endommagée lors de la transmission et qu'elle doit donc être rejetée.

Dans le code de Hamming, la source code le message en ajoutant des bits redondants dans le message. Ces bits redondants sont principalement insérés et générés à certaines positions du message pour accomplir le processus de détection et de correction des erreurs.

Histoire du code de Hamming

• Le code Hamming est une technique développée par RWHamming pour détecter les erreurs.
• Le code de Hamming doit être appliqué aux unités de données de n'importe quelle longueur et utilise la relation entre les données et les bits de redondance.
• Il a travaillé sur le problème de la méthode de correction d'erreurs et a développé un ensemble d'algorithmes de plus en plus puissants appelés code de Hamming.
• En 1950, il a publié le code de Hamming, largement utilisé aujourd'hui dans des applications telles que la mémoire ECC.

Application du code de Hamming

Voici quelques applications courantes de l’utilisation du code Hamming :

• Satellites
• Mémoire d'ordinateur
• Modems
• PlasmaCAM
• Connecteurs ouverts
• Fil de blindage
• Processeur Embarqué

Avantages du code de Hamming

• La méthode du code de Hamming est efficace sur les réseaux où les flux de données sont fournis pour les erreurs sur un seul bit.
• Le code de Hamming permet non seulement de détecter une erreur de bit, mais vous aide également à indenter le bit contenant l'erreur afin qu'elle puisse être corrigée.
• La facilité d'utilisation des codes de Hamming les rend particulièrement adaptés à une utilisation dans la mémoire informatique et à la correction d'erreurs uniques.

Inconvénients du code de Hamming

• Code de détection et de correction d'erreur sur un seul bit. Cependant, si plusieurs bits sont fondés sur une erreur, le résultat peut alors entraîner la modification d'un autre bit qui devrait être correct. Cela peut entraîner des erreurs supplémentaires dans les données.
• L'algorithme de code de Hamming ne peut résoudre que les problèmes de bits uniques.

Comment encoder un message dans le code Hamming

Le processus utilisé par l'expéditeur pour coder le message comprend les trois étapes suivantes :

• Calcul du nombre total de bits redondants.
• Vérification de la position des bits redondants.
• Enfin, calculer les valeurs de ces bits redondants.

Lorsque les bits redondants ci-dessus sont intégrés dans le message, celui-ci est envoyé à l'utilisateur.

Étape 1) Calcul du nombre total de bits redondants.

Supposons que le message contienne :

• n– nombre de bits de données
• p – nombre de bits redondants qui y sont ajoutés pour que np puisse indiquer au moins (n ​​+ p + 1) états différents.

Ici, (n + p) représente l'emplacement d'une erreur dans chacune des (n + p) positions de bits et un état supplémentaire n'indique aucune erreur. Comme p bits peuvent indiquer 2^p états, 2^p doit être au moins égal à (n + p + 1).

Étape 2) Placer les bits redondants dans leur position correcte.

Les bits redondants doivent être placés à des positions de bits de puissances de 2. Par exemple, 1, 2, 4, 8, 16, etc. Ils sont appelés p₁ (en position 1), p₂ (en position 2), p₃ (en position 4), etc.

Étape 3) Calcul des valeurs du bit redondant.

Les bits redondants doivent être des bits de parité, ce qui rend le nombre de 1 pair ou impair.

Les deux types de parité sont ?

• Le nombre total de bits dans le message est égal, appelé parité paire.
• Le nombre total de bits dans le message est rendu impair et est appelé parité impaire.

Ici, tout le bit redondant, p1, doit être calculé comme parité. Il doit couvrir toutes les positions de bits dont la représentation binaire doit inclure un 1 en 1ère position à l'exclusion de la position de p1.

P1 est le bit de parité pour tous les bits de données dans des positions dont la représentation binaire inclut un 1 dans la position la moins importante, sans compter 1 Like (3, 5, 7, 9,…. )

P2 est le bit de parité pour tous les bits de données dans les positions dont la représentation binaire inclut 1 dans la position 2 en partant de la droite, sans compter 2 Like (3, 6, 7, 10, 11,…)

P3 est le bit de parité pour chaque bit dans les positions dont la représentation binaire inclut un 1 dans la position 3 de droite sans inclure 4 Like (5-7, 12-15,… )

Décrypter un message en code de Hamming

Le récepteur reçoit des messages entrants qui nécessitent d'effectuer des recalculs pour rechercher et corriger les erreurs.

Le processus de recalcul effectué selon les étapes suivantes :

• Compter le nombre de bits redondants.
• Positionnement correct de tous les bits redondants.
• Contrôle de parité

Étape 1) Compter le nombre de bits redondants

Vous pouvez utiliser la même formule pour l'encodage, le nombre de bits redondants

2^p ? n + p + 1

Ici, le nombre de bits de données et p est le nombre de bits redondants.

Étape 2) Positionner correctement tous les bits redondants

Ici, p est un bit redondant qui est situé à des positions de bits de puissances de 2, par exemple 1, 2, 4, 8, etc.

Étape 3) Contrôle de parité

Les bits de parité doivent être calculés en fonction des bits de données et des bits redondants.

p1 = parité(1, 3, 5, 7, 9, 11…)

p2 = parité(2, 3, 6, 7, 10, 11… )

p3 = parité(4-7, 12-15, 20-23… )

Résumé

• Les données transmises peuvent être corrompues pendant la communication
• Il existe trois types d'erreurs sur les bits : 1) Erreurs sur un seul bit 2) Erreurs sur plusieurs bits 3) Erreurs sur les bits en rafale
• La modification apportée à un bit dans l’ensemble de la séquence de données est appelée « erreur sur un seul bit ».
• Dans la séquence de données, s'il y a un changement dans deux bits ou plus d'une séquence de données d'un émetteur à un récepteur, on parle d'« erreurs sur plusieurs bits ».
• Le changement de l'ensemble des bits dans la séquence de données est appelé « erreur de rafale ».
• La détection d'erreurs est une méthode de détection des erreurs présentes dans les données transmises d'un émetteur à un récepteur dans un système de communication de données.
• Trois types de codes de détection d'erreur sont 1) Contrôle de parité 2) Contrôle de redondance cyclique (CRC) 3) Contrôle de redondance longitudinale (LRC)
• Le code de Hamming est un code de ligne utile pour la détection d'erreurs jusqu'à deux erreurs binaires immédiates. Il est capable d'erreurs sur un seul bit.
• Le code Hamming est une technique développée par RWHamming pour détecter les erreurs.
• Les applications courantes de l'utilisation du code Hamming sont la mémoire informatique des satellites, les modems, les processeurs intégrés, etc.
• Le plus grand avantage de la méthode du code de Hamming est efficace sur les réseaux où les flux de données sont fournis pour les erreurs sur un seul bit.
• Le plus gros inconvénient de la méthode du code de Hamming est qu’elle ne peut résoudre que les problèmes de bits uniques.
• Nous pouvons effectuer le processus de cryptage et de décodage du message à l’aide du code Hamming.