Schémas de codage de données

La redondance est obtenue grâce à divers schémas de codage. L'expéditeur ajoute des bits redondants via un processus qui crée une relation entre les bits redondants et les bits de données réels. Le récepteur vérifie les relations entre les deux ensembles de bits pour détecter les erreurs. Le rapport des bits redondants aux bits de données et la robustesse du processus sont des facteurs importants dans tout schéma de codage.

Nous pouvons diviser les schémas de codage en deux grandes catégories : le codage par blocs et le codage par convolution.

Dans le codage par blocs, nous divisons notre message en blocs, chacun de k bits, appelés mots de données. Nous ajoutons r bits redondants à chaque bloc pour obtenir la longueur n = k + r. Les blocs de n bits résultants sont appelés mots de code. Comment les bits r supplémentaires sont choisis ou calculés. Pour le moment, il est important de savoir que nous avons un ensemble de mots de données, chacun de taille k, et un ensemble de mots de code, chacun de taille n. Avec k bits, nous pouvons créer une combinaison de 2^k mots de données ; avec n bits, nous pouvons créer une combinaison de 2ⁿ mots de code.

Comme n > k, le nombre de mots de code possibles est plus grand que le nombre de mots de données possibles. Le processus de codage par blocs est one-to-one ; le même mot de données est toujours codé par le même mot de code. Cela signifie que nous avons 2ⁿ - 2^k mots de code qui ne sont pas utilisés. Nous appelons ces mots de code invalides ou illégaux. L'astuce de la détection d'erreurs réside dans l'existence de ces codes invalides, comme nous le verrons plus loin. Si le récepteur reçoit un mot de code invalide, cela indique que les données ont été corrompues pendant la transmission.

Comment les erreurs peuvent-elles être détectées en utilisant le codage par blocs ? Si les deux conditions suivantes sont remplies, le récepteur peut détecter un changement dans le mot de code d'origine.

•  Le récepteur a (ou peut trouver) une liste de mots de code valides.
•  Le mot de code d'origine est devenu invalide.

L'expéditeur crée des mots de code à partir de mots de données en utilisant un générateur qui applique les règles et procédures de codage. Chaque mot de code envoyé au récepteur peut changer pendant la transmission. Si le mot de code reçu est identique à l'un des mots de code valides, le mot est accepté ; le mot de données correspondant est extrait pour être utilisé. Si le mot de code reçu n'est pas valide, il est écarté. Toutefois, si le mot codé est corrompu pendant la transmission mais que le mot reçu correspond toujours à un mot codé valide, l'erreur n'est pas détectée.

La correction d'erreur se fait principalement à l'aide du code de Hamming.

L'un des concepts centraux du codage pour le contrôle des erreurs est l'idée de la distance de Hamming. La distance de Hamming entre deux mots (de même taille) est le nombre de différences entre les bits correspondants. Nous représentons la distance de Hamming entre deux mots x et y sous la forme d(x, y). On peut se demander pourquoi la distance de Hamming est importante pour la détection des erreurs. La raison est que la distance de Hamming entre le mot de code reçu et le mot de code envoyé est le nombre de bits qui sont corrompus pendant la transmission. Par exemple, si le mot de code 00000 est envoyé et que 01101 est reçu, 3 bits sont en erreur et la distance de Hamming entre les deux est d(00000, 01101) = 3. En d'autres termes, si la distance de Hamming entre le mot de code envoyé et le mot de code reçu n'est pas nulle, le mot de code a été corrompu pendant la transmission.

La distance de Hamming peut facilement être trouvée si nous appliquons l'opération XOR (⊕) sur les deux mots et en comptant le nombre de 1 dans le résultat. Notez que la distance de Hamming est une valeur supérieure ou égale à zéro.

Distance de Hamming minimale pour la détection des erreurs

Dans un ensemble de mots de code, la distance de Hamming minimale est la plus petite distance de Hamming entre toutes les paires possibles de mots-codes. Trouvons maintenant la distance de Hamming minimale dans un code si nous voulons être en mesure de détecter jusqu'à s erreurs. Si s erreurs se produisent pendant la transmission, la distance de Hamming entre le mot de code envoyé et le mot de code reçu est s. Si notre système doit détecter jusqu'à s erreurs, la distance minimale entre les codes valides doit être de (s + 1), de sorte que le mot-code reçu ne corresponde pas à un mot-code valide. En d'autres termes, si la distance minimale entre tous les mots-codes valides est (s + 1), le mot-code reçu ne peut pas être confondu par erreur avec un autre mot-code. L'erreur sera détectée.

Bien qu'un code avec d_min = s + 1 puisse détecter plus de s erreurs dans certains cas particuliers, seules s erreurs ou moins sont garanties d'être détectées.

Presque tous les codes de blocs utilisés aujourd'hui appartiennent à un sous-ensemble de codes de blocs appelés codes de blocs linéaires. L'utilisation de codes de blocs non linéaires pour la détection et la correction d'erreurs n'est pas aussi répandue car leur structure rend l'analyse théorique et la mise en œuvre difficiles.

Sans parler de la définition formelle qui nécessite un bagage mathématique, nous donnons une définition informelle. Pour notre propos, un code en bloc linéaire est un code dans lequel le OU exclusif (XOR) de deux mots de code valides crée un autre mot de code valide.

Distance minimale pour les codes de blocs linéaires

Il est simple de trouver la distance de Hamming minimale pour un code de bloc linéaire. La distance de Hamming minimale est le nombre de 1 dans le mot de code valide différent de zéro avec le plus petit nombre de 1.

Code de contrôle de parité

Le code de détection d'erreurs le plus connu est peut-être le code de contrôle de parité. Ce code est un code de bloc linéaire. Dans ce code, un mot de données de k bits est remplacé par un mot de code de n bits où n = k + 1. Le bit supplémentaire, appelé bit de parité, est sélectionné pour rendre le nombre total de 1 dans le mot de code pair. Bien que certaines implémentations spécifient un nombre impair de 1, nous discutons du cas pair. La distance de Hamming minimale pour cette catégorie est d_min = 2, ce qui signifie que le code est un code de détection d'erreur à un seul bit.

La figure ci-dessous montre une structure possible d'un encodeur (au niveau de l'émetteur) et d'un décodeur (au niveau du récepteur).

Le calcul se fait en arithmétique modulaire. L'encodeur utilise un générateur qui prend une copie d'un mot de données de 4 bits (a0, a1, a2 et a3) et génère un bit de parité r0. Les bits de mot de données et le bit de parité créent le mot de code à 5 bits. Le bit de parité qui est ajouté rend le nombre de 1 dans le mot de code pair. Cela se fait normalement en ajoutant les 4 bits du mot de données (modulo-2); le résultat est le bit de parité. En d'autres termes,

r0 = (a3 + a2 + a1 + a0) modulo 2

Si le nombre de 1 est pair, le résultat est 0 ; si le nombre de 1 est impair, le résultat est 1. Dans les deux cas, le nombre total de 1 dans le mot de code est pair.

L'expéditeur envoie le mot de passe, qui peut être corrompu lors de la transmission. Le récepteur reçoit un mot de 5 bits. Le vérificateur du récepteur fait la même chose que le générateur de l'émetteur à une exception près : l'addition se fait sur les 5 bits. Le résultat, qui s'appelle le syndrome, n'est que de 1 bit. Le syndrome est 0 lorsque le nombre de 1 dans le mot de code reçu est pair ; sinon, c'est 1.

s0 = (b3 + b2 + b1 + b0 + q0) modulo 2

Le syndrome est transmis à l'analyseur logique de décision. Si le syndrome est 0, il n'y a pas d'erreur détectable dans le mot de code reçu ; la partie de données du mot de code reçu est acceptée en tant que mot de données ; si le syndrome est 1, la partie de données du mot de code reçu est rejetée. Le mot de données n'est pas créé.

Regardons quelques scénarios de transmission. Supposons que l'expéditeur envoie le mot de données 1011. Le mot de code créé à partir de ce mot de données est 10111, qui est envoyé au récepteur. Nous examinons cinq cas :

1. Aucune erreur ne se produit ; le mot de code reçu est 10111. Le syndrome est 0. Le mot de données 1011 est créé.
2. Une erreur sur un seul bit modifie a1. Le mot de code reçu est 10011. Le syndrome est 1. Aucun mot de données n'est créé.
3. Une erreur sur un seul bit modifie r0. Le mot de passe reçu est 10110. Le syndrome est 1. Aucun mot de données n'est créé. Notez que bien qu'aucun des bits de mot de données ne soit corrompu, aucun mot de données n'est créé car le code n'est pas assez sophistiqué pour montrer la position du bit corrompu.
4. Une erreur modifie r0 et une seconde erreur modifie a3. Le mot de code reçu est 00110. Le syndrome est 0. Le mot de données 0011 est créé au niveau du récepteur. Notez qu'ici le mot de données est créé de façon erronée à cause de la valeur du syndrome. Le décodeur à contrôle de parité simple ne peut pas détecter un nombre pair d'erreurs. Les erreurs s'annulent et donnent au syndrome une valeur de 0.
5. Trois bits—a3, a2 et a1—sont modifiés par des erreurs. Le mot de passe reçu est 01011. Le syndrome est 1. Le mot de données n'est pas créé. Cela montre que le simple contrôle de parité, garanti pour détecter une seule erreur, peut également trouver un nombre impair d'erreurs.

Les codes cycliques sont des codes de blocs linéaires spéciaux avec une propriété supplémentaire. Dans un code cyclique, si un mot de code est cycliquement décalé (tourné), le résultat est un autre mot de code. Par exemple, si 1011000 est un mot de code et que nous décalons cycliquement vers la gauche, alors 0110001 est également un mot de code. Dans ce cas, si nous appelons les bits du premier mot a0 à a6, et les bits du deuxième mot b0 à b6, nous pouvons décaler les bits en utilisant ce qui suit :

b1 = a0 ; b2 = a1 ; b3 = a2 ;b4 = a3 ; b5 = a4 ; b6 = a5 ; b0 = a6.

Nous pouvons créer des codes cycliques pour corriger les erreurs. Cependant, une formation théorique est requise. Dans ce cours, nous discutons simplement d'un sous-ensemble de codes cycliques appelé contrôle de redondance cyclique (CRC), qui est utilisé dans des réseaux tels que les réseaux LAN et WAN.

Le tableau suivant montre un exemple de code CRC C(7,4). Nous pouvons voir à la fois les propriétés linéaires et cycliques de ce code.

La figure ci-dessous montre une conception possible pour l'encodeur et le décodeur.

Dans le codeur, le mot de données a k bits (4 ici) ; le mot de code a n bits (7 ici). La taille du mot de données est augmentée en ajoutant n − k (3 ici) 0 à la droite du mot. Le résultat de n bits est introduit dans le générateur. Le générateur utilise un diviseur de taille n − k + 1 (4 ici), prédéfini et convenu. Le générateur divise le mot de données augmenté par le diviseur (division modulo-2). Le quotient de la division est ignoré ; le reste (r2 r1 r0) est ajouté au mot de données pour créer le mot de code.

Le décodeur reçoit le mot de code (éventuellement corrompu en transition). Une copie de tous les n bits est transmise au vérificateur, qui est une réplique du générateur. Le reste produit par le vérificateur est un syndrome de n − k (3 ici) bits, qui est fourni à l'analyseur logique de décision. L'analyseur a une fonction simple. Si les bits de syndrome sont tous à 0, les 4 bits les plus à gauche du mot de code sont acceptés comme mot de données (interprétés comme aucune erreur) ; sinon, les 4 bits sont rejetés (erreur).