Codes de détection et de correction d'erreur
On sait que les bits 0 et 1 correspondent à deux plages de tensions analogiques différentes. Ainsi, lors de la transmission de données binaires d'un système à l'autre, le bruit peut également être ajouté. Pour cette raison, il peut y avoir des erreurs dans les données reçues sur un autre système.
Cela signifie qu'un bit 0 peut changer à 1 ou un bit 1 peut changer à 0. Nous ne pouvons pas éviter l'interférence du bruit. Mais, nous pouvons d'abord récupérer les données d'origine en détectant si des erreurs sont présentes, puis en corrigeant ces erreurs. Pour cela, nous pouvons utiliser les codes suivants.
- Codes de détection d'erreur
- Codes de correction d'erreur
Error detection codes- sont utilisés pour détecter la ou les erreurs présentes dans les données reçues (flux binaire). Ces codes contiennent des bits, qui sont inclus (ajoutés) au train de bits d'origine. Ces codes détectent l'erreur, si elle s'est produite lors de la transmission des données d'origine (train de bits).Example - Code de parité, code de Hamming.
Error correction codes- sont utilisés pour corriger la ou les erreurs présentes dans les données reçues (flux binaire) afin que nous obtenions les données d'origine. Les codes de correction d'erreur utilisent également la stratégie similaire des codes de détection d'erreur.Example - Code de Hamming.
Par conséquent, pour détecter et corriger les erreurs, des bits supplémentaires sont ajoutés aux bits de données au moment de la transmission.
Code de parité
Il est facile d'inclure (ajouter) un bit de parité soit à gauche de MSB soit à droite de LSB du train binaire d'origine. Il existe deux types de codes de parité, à savoir le code de parité pair et le code de parité impaire en fonction du type de parité choisi.
Code de parité pair
La valeur du bit de parité paire doit être zéro, si le nombre pair de un est présent dans le code binaire. Sinon, ça devrait en être un. De sorte que, même nombre de ceux présents danseven parity code. Le code de parité pair contient les bits de données et même le bit de parité.
Le tableau suivant montre les even parity codescorrespondant à chaque code binaire 3 bits. Ici, le bit de parité paire est inclus à droite du LSB du code binaire.
| Code binaire | Même bit de parité | Code de parité pair |
|---|---|---|
| 000 | 0 | 0000 |
| 001 | 1 | 0011 |
| 010 | 1 | 0101 |
| 011 | 0 | 0110 |
| 100 | 1 | 1001 |
| 101 | 0 | 1010 |
| 110 | 0 | 1100 |
| 111 | 1 | 1111 |
Ici, le nombre de bits présents dans les codes de parité paire est 4. Ainsi, le nombre pair possible de bits dans ces codes de parité paire est 0, 2 et 4.
Si l'autre système reçoit l'un de ces codes de parité paire, alors il n'y a pas d'erreur dans les données reçues. Les bits autres que le bit de parité paire sont les mêmes que ceux du code binaire.
Si l'autre système reçoit des codes autres que des codes de parité pairs, alors il y aura une ou des erreurs dans les données reçues. Dans ce cas, nous ne pouvons pas prédire le code binaire d'origine car nous ne connaissons pas la (les) position (s) du bit d'erreur.
Par conséquent, le bit de parité pair n'est utile que pour la détection d'une erreur dans le code de parité reçu. Mais il ne suffit pas de corriger l'erreur.
Code de parité impaire
La valeur du bit de parité impair doit être zéro, si un nombre impair de un est présent dans le code binaire. Sinon, ça devrait en être un. De sorte que, nombre impair de ceux présents dansodd parity code. Le code de parité impair contient les bits de données et le bit de parité impair.
Le tableau suivant montre les odd parity codescorrespondant à chaque code binaire 3 bits. Ici, le bit de parité impair est inclus à droite du LSB du code binaire.
| Code binaire | Bit de parité impaire | Code de parité impaire |
|---|---|---|
| 000 | 1 | 0001 |
| 001 | 0 | 0010 |
| 010 | 0 | 0100 |
| 011 | 1 | 0111 |
| 100 | 0 | 1000 |
| 101 | 1 | 1011 |
| 110 | 1 | 1101 |
| 111 | 0 | 1110 |
Ici, le nombre de bits présents dans les codes de parité impairs est 4. Ainsi, le nombre impair possible de uns dans ces codes de parité impairs est 1 et 3.
Si l'autre système reçoit l'un de ces codes de parité impairs, alors il n'y a pas d'erreur dans les données reçues. Les bits autres que le bit de parité impaire sont identiques à ceux du code binaire.
Si l'autre système reçoit des codes autres que des codes de parité impairs, alors il y a une ou des erreurs dans les données reçues. Dans ce cas, nous ne pouvons pas prédire le code binaire d'origine car nous ne connaissons pas la (les) position (s) du bit d'erreur.
Par conséquent, le bit de parité impair n'est utile que pour la détection d'une erreur dans le code de parité reçu. Mais il ne suffit pas de corriger l'erreur.
Code de Hamming
Le code de Hamming est utile à la fois pour la détection et la correction des erreurs présentes dans les données reçues. Ce code utilise plusieurs bits de parité et nous devons placer ces bits de parité dans les positions de puissances de 2.
le minimum value of 'k' pour laquelle la relation suivante est correcte (valide) n'est rien d'autre que le nombre requis de bits de parité.
$$ 2 ^ k \ geq n + k + 1 $$
Où,
'n' est le nombre de bits dans le code binaire (information)
'k' est le nombre de bits de parité
Par conséquent, le nombre de bits dans le code de Hamming est égal à n + k.
Laisse le Hamming codeest $ b_ {n + k} b_ {n + k-1} ..... b_ {3} b_ {2} b_ {1} $ & bits de parité $ p_ {k}, p_ {k-1}, .... p_ {1} $. Nous pouvons placer les bits de parité «k» en puissances de 2 positions seulement. Dans les positions de bits restantes, nous pouvons placer les «n» bits de code binaire.
En fonction des besoins, nous pouvons utiliser une parité paire ou une parité impaire tout en formant un code de Hamming. Mais, la même technique de parité doit être utilisée afin de déterminer si une erreur est présente dans les données reçues.
Suivez cette procédure pour trouver parity bits.
Trouvez la valeur de p1, basé sur le nombre de uns présents dans les positions binaires b 3 , b 5 , b 7 et ainsi de suite. Toutes ces positions de bits (suffixes) dans leur équivalent binaire ont «1» à la place de 2 0 .
Trouvez la valeur de p2, sur la base du nombre de uns présents dans les positions binaires b 3 , b 6 , b 7 et ainsi de suite. Toutes ces positions de bits (suffixes) dans leur équivalent binaire ont «1» à la place de 2 1 .
Trouvez la valeur de p3, sur la base du nombre de uns présents dans les positions binaires b 5 , b 6 , b 7 et ainsi de suite. Toutes ces positions de bits (suffixes) dans leur binaire équivalent ont '1' à la valeur de position de 2 2 .
De même, recherchez d'autres valeurs de bits de parité.
Suivez cette procédure pour trouver check bits.
Trouvez la valeur de c 1 , basée sur le nombre de uns présents dans les positions binaires b 1 , b 3 , b 5 , b 7 et ainsi de suite. Toutes ces positions de bit (suffixes) dans leur équivalent binaire ont «1» à la place de 2 0 .
Trouvez la valeur de c 2 , basée sur le nombre de uns présents dans les positions binaires b 2 , b 3 , b 6 , b 7 et ainsi de suite. Toutes ces positions de bits (suffixes) dans leur binaire équivalent ont '1' à la valeur de position de 2 1 .
Trouvez la valeur de c 3 , basée sur le nombre de uns présents dans les positions binaires b 4 , b 5 , b 6 , b 7 et ainsi de suite. Toutes ces positions de bits (suffixes) dans leur binaire équivalent ont '1' à la valeur de position de 2 2 .
De même, recherchez d'autres valeurs de bits de contrôle.
L'équivalent décimal des bits de contrôle dans les données reçues donne la valeur de la position du bit, là où l'erreur est présente. Complétez simplement la valeur présente dans cette position de bit. Par conséquent, nous obtiendrons le code binaire d'origine après avoir supprimé les bits de parité.
Exemple 1
Trouvons le code de Hamming pour le code binaire, d 4 d 3 d 2 d 1 = 1000. Considérons les bits de parité pairs.
Le nombre de bits dans le code binaire donné est n = 4.
Nous pouvons trouver le nombre requis de bits de parité en utilisant la relation mathématique suivante.
$$ 2 ^ k \ geq n + k + 1 $$
Remplacez, n = 4 dans la relation mathématique ci-dessus.
$$ \ Flèche droite 2 ^ k \ geq 4 + k + 1 $$
$$ \ Flèche droite 2 ^ k \ geq 5 + k $$
La valeur minimale de k qui satisfait la relation ci-dessus est 3. Par conséquent, nous avons besoin de 3 bits de parité p 1 , p 2 et p 3 . Par conséquent, le nombre de bits dans le code de Hamming sera de 7, car il y a 4 bits en code binaire et 3 bits de parité. Nous devons placer les bits de parité et les bits de code binaire dans le code de Hamming comme indiqué ci-dessous.
le 7-bit Hamming code est $ b_ {7} b_ {6} b_ {5} b_ {4} b_ {3} b_ {2} b_ {1} = d_ {4} d_ {3} d_ {2} p_ {3} d_ {1 } p_ {2} bp_ {1} $
En substituant les bits de code binaire, le code de Hamming sera $ b_ {7} b_ {6} b_ {5} b_ {4} b_ {3} b_ {2} b_ {1} = 100p_ {3} Op_ {2 } p_ {1} $. Maintenant, trouvons les bits de parité.
$$ p_ {1} = b_ {7} \ oplus b_ {5} \ oplus b_ {3} = 1 \ oplus 0 \ oplus 0 = 1 $$
$$ p_ {2} = b_ {7} \ oplus b_ {6} \ oplus b_ {3} = 1 \ oplus 0 \ oplus 0 = 1 $$
$$ p_ {3} = b_ {7} \ oplus b_ {6} \ oplus b_ {5} = 1 \ oplus 0 \ oplus 0 = 1 $$
En substituant ces bits de parité, le Hamming code sera $ b_ {7} b_ {6} b_ {5} b_ {4} b_ {3} b_ {2} b_ {1} = 1001011 $.
Exemple 2
Dans l'exemple ci-dessus, nous avons obtenu le code de Hamming sous la forme $ b_ {7} b_ {6} b_ {5} b_ {4} b_ {3} b_ {2} b_ {1} = 1001011 $. Maintenant, trouvons la position d'erreur lorsque le code reçu est $ b_ {7} b_ {6} b_ {5} b_ {4} b_ {3} b_ {2} b_ {1} = 1001111 $.
Maintenant, trouvons les bits de contrôle.
$$ c_ {1} = b_ {7} \ oplus b_ {5} \ oplus b_ {3} \ oplus b_ {1} = 1 \ oplus 0 \ oplus 1 \ oplus1 = 1 $$
$$ c_ {2} = b_ {7} \ oplus b_ {6} \ oplus b_ {3} \ oplus b_ {2} = 1 \ oplus 0 \ oplus 1 \ oplus1 = 1 $$
$$ c_ {3} = b_ {7} \ oplus b_ {6} \ oplus b_ {5} \ oplus b_ {4} = 1 \ oplus 0 \ oplus 0 \ oplus1 = 0 $$
La valeur décimale des bits de contrôle donne la position de l'erreur dans le code de Hamming reçu.
$$ c_ {3} c_ {2} c_ {1} = \ left (011 \ right) _ {2} = \ left (3 \ right) _ {10} $$
Par conséquent, l'erreur présente dans le troisième bit (b 3 ) du code de Hamming. Complétez simplement la valeur présente dans ce bit et supprimez les bits de parité afin d'obtenir le code binaire d'origine.