Les messages non codés peuvent être composés de lettres ou de caractères, mais ils consistent généralement en des \(m\)-uplets binaires. Ces messages sont encodés en mots de code, consistant en des \(n\)-uplets binaires, par un dispositif appelé encodeur. Le message est transmis puis décodé. Nous considérerons l’occurrence d’erreurs durant la transmission. Une erreur se produit s’il y a une modification d’un ou plusieurs bits dans le mot de code. Un schéma de décodage est une méthode qui convertit soit un \(n\)-uplet reçu arbitrairement en un message décodé significatif, soit donne un message d’erreur pour ce \(n\)-uplet. Si le message reçu est un mot de code (l’un des \(n\)-uplets spéciaux autorisés à être transmis), alors le message décodé doit être le message unique qui a été encodé dans ce mot de code. Pour les non-mots de code reçus, le schéma de décodage donnera une indication d’erreur, ou, si nous sommes plus habiles, tentera réellement de corriger l’erreur et de reconstruire le message original. Notre objectif est de transmettre des messages sans erreur aussi économiquement et rapidement que possible.
Un schéma de codage possible serait d’envoyer un message plusieurs fois et de comparer les copies reçues entre elles. Supposons que le message à encoder est un \(n\)-uplet binaire \((x_{1}, x_{2}, \ldots,
x_{n})\text{.}\) Le message est encodé en un \(3n\)-uplet binaire en répétant simplement le message trois fois :
Pour décoder le message, nous choisissons comme \(i\)-ème chiffre celui qui apparaît à la \(i\)-ème place dans au moins deux des trois transmissions. Par exemple, si le message original est \((0110)\text{,}\) alors le message transmis sera \((0110\; 0110\; 0110)\text{.}\) S’il y a une erreur de transmission dans le cinquième chiffre, alors le mot de code reçu sera \((0110\; 1110\; 0110)\text{,}\) qui sera correctement décodé comme \((0110)\text{.}\) 1
Nous adoptons la convention que les bits sont numérotés de gauche à droite dans les \(n\)-uplets binaires.
Cette méthode de triple répétition détectera et corrigera automatiquement toutes les erreurs simples, mais elle est lente et inefficace : pour envoyer un message de \(n\) bits, \(2n\) bits supplémentaires sont nécessaires, et nous ne pouvons détecter et corriger que les erreurs simples. Nous verrons qu’il est possible de trouver un schéma d’encodage qui encodera un message de \(n\) bits en \(m\) bits avec \(m\) beaucoup plus petit que \(3n\text{.}\)
La parité paire, un schéma de codage couramment utilisé, est beaucoup plus efficace que le simple schéma de répétition. Le système de codage ASCII (American Standard Code for Information Interchange) utilise des \(8\)-uplets binaires, donnant \(2^{8} = 256\)\(8\)-uplets possibles. Cependant, seuls sept bits sont nécessaires puisqu’il n’y a que \(2^7 = 128\) caractères ASCII. Que peut-on ou doit-on faire avec le bit supplémentaire ? En utilisant les huit bits complets, nous pouvons détecter les erreurs de transmission simples. Par exemple, les codes ASCII pour A, B et C sont
Le bit peut être utilisé pour la vérification d’erreurs sur les sept autres bits. Il est mis à \(0\) ou à \(1\) de sorte que le nombre total de bits à \(1\) dans la représentation d’un caractère soit pair. En utilisant la parité paire, les codes pour A, B et C deviennent
Supposons qu’un A est envoyé et qu’une erreur de transmission dans le sixième bit est causée par du bruit sur le canal de communication, de sorte que \((0100\; 0101)\) est reçu. Nous savons qu’une erreur s’est produite puisque le mot reçu a un nombre impair de \(1\)s, et nous pouvons maintenant demander que le mot de code soit retransmis. Lorsqu’il est utilisé pour la vérification d’erreurs, le bit le plus à gauche est appelé bit de parité.
De loin les codes de détection d’erreurs les plus courants utilisés dans les ordinateurs sont basés sur l’ajout d’un bit de parité. Typiquement, un ordinateur stocke les informations dans des \(m\)-uplets appelés mots. Les longueurs de mots courantes sont \(8\text{,}\)\(16\) et \(32\) bits. Un bit du mot est réservé comme bit de parité, et n’est pas utilisé pour stocker de l’information. Ce bit est mis à \(0\) ou à \(1\text{,}\) selon le nombre de \(1\)s dans le mot.
L’ajout d’un bit de parité permet la détection de toutes les erreurs simples car le changement d’un seul bit augmente ou diminue le nombre de \(1\)s d’une unité, et dans les deux cas la parité a été changée de paire à impaire, de sorte que le nouveau mot n’est pas un mot de code. (Nous pourrions également construire un schéma de détection d’erreurs basé sur la parité impaire ; c’est-à-dire que nous pourrions fixer le bit de parité de sorte qu’un mot de code ait toujours un nombre impair de \(1\)s.)
Le système de parité paire est facile à mettre en œuvre, mais présente deux inconvénients. Premièrement, les erreurs multiples ne sont pas détectables. Supposons qu’un A est envoyé et que le premier et le septième bit sont changés de \(0\) à \(1\text{.}\) Le mot reçu est un mot de code, mais sera décodé comme un C au lieu d’un A. Deuxièmement, nous n’avons pas la capacité de corriger les erreurs. Si le 8-uplet \((1001\; 1000)\) est reçu, nous savons qu’une erreur s’est produite, mais nous n’avons aucune idée quel bit a été modifié. Nous allons maintenant examiner un schéma de codage qui nous permettra non seulement de détecter les erreurs de transmission mais aussi de les corriger réellement.
Supposons que notre message original soit soit un \(0\) soit un \(1\text{,}\) et que \(0\) s’encode en \((000)\) et \(1\) s’encode en \((111)\text{.}\) Si une seule erreur se produit lors de la transmission, nous pouvons détecter et corriger l’erreur. Par exemple, si un \((101)\) est reçu, alors le deuxième bit doit avoir été changé d’un \(1\) à un \(0\text{.}\) Le mot de code transmis initialement devait être \((111)\text{.}\) Cette méthode détectera et corrigera toutes les erreurs simples.
Dans Table 8.1.5, nous présentons tous les mots possibles qui pourraient être reçus pour les mots de code transmis \((000)\) et \((111)\text{.}\)Table 8.1.5 montre également le nombre de bits par lesquels chaque \(3\)-uplet reçu diffère de chaque mot de code original.
Sous-section8.1.1Décodage par maximum de vraisemblance
Le schéma de codage présenté dans Exemple 8.1.4 n’est pas une solution complète au problème car il ne tient pas compte de la possibilité d’erreurs multiples. Par exemple, soit un (000) soit un (111) pourrait être envoyé et un (001) reçu. Nous n’avons aucun moyen de décider à partir du mot reçu s’il y avait une seule erreur dans le troisième bit ou deux erreurs, une dans le premier bit et une dans le deuxième. Quel que soit le schéma de codage utilisé, un message incorrect pourrait être reçu. Nous pourrions transmettre un (000), avoir des erreurs dans les trois bits, et recevoir le mot de code (111). Il est important de formuler des hypothèses explicites sur la vraisemblance et la distribution des erreurs de transmission de sorte que, dans une application particulière, il soit connu si un schéma de détection d’erreurs donné est approprié. Nous supposerons que les erreurs de transmission sont rares, et, lorsqu’elles se produisent, elles se produisent indépendamment dans chaque bit ; c’est-à-dire que si \(p\) est la probabilité d’une erreur dans un bit et \(q\) est la probabilité d’une erreur dans un bit différent, alors la probabilité que des erreurs se produisent dans ces deux bits en même temps est \(pq\text{.}\) Nous supposerons également qu’un \(n\)-uplet reçu est décodé en le mot de code qui lui est le plus proche ; c’est-à-dire que nous supposons que le récepteur utilise le décodage par maximum de vraisemblance. 2
Cette section nécessite une connaissance des probabilités, mais peut être sautée sans perte de continuité.
Un canal binaire symétrique est un modèle qui consiste en un émetteur capable d’envoyer un signal binaire, soit un \(0\) soit un \(1\text{,}\) ainsi qu’un récepteur. Soit \(p\) la probabilité que le signal soit correctement reçu. Alors \(q = 1 - p\) est la probabilité d’une réception incorrecte. Si un \(1\) est envoyé, alors la probabilité qu’un \(1\) soit reçu est \(p\) et la probabilité qu’un \(0\) soit reçu est \(q\) (Figure 8.1.6). La probabilité qu’aucune erreur ne se produise pendant la transmission d’un mot de code binaire de longueur \(n\) est \(p^{n}\text{.}\) Par exemple, si \(p=0.999\) et qu’un message de 10 000 bits est envoyé, alors la probabilité d’une transmission parfaite est
Si un \(n\)-uplet binaire \((x_{1}, \ldots,
x_{n})\) est transmis sur un canal binaire symétrique avec une probabilité \(p\) qu’aucune erreur ne se produise dans chaque coordonnée, alors la probabilité qu’il y ait des erreurs dans exactement \(k\) coordonnées est
Fixons \(k\) coordonnées différentes. Nous calculons d’abord la probabilité qu’une erreur se soit produite dans cet ensemble fixe de coordonnées. La probabilité qu’une erreur se produise dans l’une particulière de ces \(k\) coordonnées est \(q\) ; la probabilité qu’une erreur ne se produise dans aucune des \(n-k\) coordonnées restantes est \(p\text{.}\) La probabilité de chacun de ces \(n\) événements indépendants est \(q^{k}p^{n-k}\text{.}\) Le nombre de configurations d’erreurs possibles avec exactement \(k\) erreurs est égal à
le nombre de combinaisons de \(n\) éléments pris \(k\) à la fois. Chacune de ces configurations d’erreurs a une probabilité \(q^{k}p^{n-k}\) de se produire ; donc la probabilité de toutes ces configurations d’erreurs est
Si nous voulons développer des codes efficaces de détection et de correction d’erreurs, nous aurons besoin d’outils mathématiques plus sophistiqués. La théorie des groupes permettra des méthodes plus rapides d’encodage et de décodage des messages. Un code est un code en blocs \((n, m)\) si l’information à coder peut être divisée en blocs de \(m\) chiffres binaires, chacun pouvant être encodé en \(n\) chiffres binaires. Plus précisément, un code en blocs \((n, m)\) consiste en une fonction d’encodage
Un mot de code est tout élément dans l’image de \(E\text{.}\) Nous exigeons également que \(E\) soit injective de sorte que deux blocs d’information ne soient pas encodés dans le même mot de code. Si notre code doit être correcteur d’erreurs, alors \(D\) doit être surjective.
Le système de codage à parité paire développé pour détecter les erreurs simples dans les caractères ASCII est un code en blocs \((8,7)\text{.}\) La fonction d’encodage est
Soit \({\mathbf x} = (x_1, \ldots,
x_n)\) et \({\mathbf y} = (y_1, \ldots,
y_n)\) des \(n\)-uplets binaires. La distance de Hamming ou distance, \(d({\mathbf x}, {\mathbf y})\text{,}\) entre \({\mathbf x}\) et \({\mathbf y}\) est le nombre de bits dans lesquels \({\mathbf x}\) et \({\mathbf y}\) diffèrent. La distance entre deux mots de code est le nombre minimum d’erreurs de transmission nécessaires pour transformer un mot de code en l’autre. La distance minimale pour un code, \(d_{\min}\text{,}\) est le minimum de toutes les distances \(d({\mathbf x}, {\mathbf y})\text{,}\) où \({\mathbf x}\) et \({\mathbf y}\) sont des mots de code distincts. Le poids, \(w({\mathbf x})\text{,}\) d’un mot de code binaire \({\mathbf x}\) est le nombre de \(1\)s dans \({\mathbf x}\text{.}\) Clairement, \(w({\mathbf x}) = d({\mathbf x}, {\mathbf 0})\text{,}\) où \({\mathbf 0} = (00 \cdots 0)\text{.}\)
Soit \({\mathbf x} = (10101)\text{,}\)\({\mathbf y} = (11010)\text{,}\) et \({\mathbf z} = (00011)\) tous les mots de code d’un certain code \(C\text{.}\) Alors nous avons les distances de Hamming suivantes :
La proposition suivante énumère quelques propriétés fondamentales du poids d’un mot de code et de la distance entre deux mots de code. La démonstration est laissée en exercice.
Les poids dans un code particulier sont généralement beaucoup plus faciles à calculer que les distances de Hamming entre tous les mots de code du code. Si un code est soigneusement construit, nous pouvons tirer parti de ce fait.
Supposons que \({\mathbf x} = (1101)\) et \({\mathbf y} = (1100)\) sont des mots de code dans un certain code. Si nous transmettons \((1101)\) et qu’une erreur se produit dans le bit le plus à droite, alors (1100) sera reçu. Puisque \((1100)\) est un mot de code, le décodeur décodera \((1100)\) comme le message transmis. Ce code n’est clairement pas très approprié pour la détection d’erreurs. Le problème est que \(d({\mathbf x}, {\mathbf y}) = 1\text{.}\) Si \({\mathbf x} = (1100)\) et \({\mathbf y} = (1010)\) sont des mots de code, alors \(d({\mathbf x}, {\mathbf y}) = 2\text{.}\) Si \({\mathbf x}\) est transmis et qu’une seule erreur se produit, alors \({\mathbf y}\) ne peut jamais être reçu. Table 8.1.12 donne les distances entre tous les mots de code de 4 bits dans lesquels les trois premiers bits portent l’information et le quatrième est un bit de parité paire. Nous pouvons voir que la distance minimale ici est \(2\) ; donc le code convient comme code de détection d’erreur simple.
Pour déterminer exactement quelles sont les capacités de détection et de correction d’erreurs d’un code, nous devons analyser la distance minimale du code. Soient \({\mathbf x}\) et \({\mathbf y}\) des mots de code. Si \(d({\mathbf x}, {\mathbf y}) = 1\) et qu’une erreur se produit là où \({\mathbf x}\) et \({\mathbf y}\) diffèrent, alors \({\mathbf x}\) est transformé en \({\mathbf y}\text{.}\) Le mot de code reçu est \({\mathbf y}\) et aucun message d’erreur n’est donné. Supposons maintenant que \(d({\mathbf x}, {\mathbf y}) = 2\text{.}\) Alors une seule erreur ne peut pas transformer \({\mathbf x}\) en \({\mathbf y}\text{.}\) Par conséquent, si \(d_{\min} = 2\text{,}\) nous avons la capacité de détecter les erreurs simples. Cependant, supposons que \(d({\mathbf x}, {\mathbf y}) = 2\text{,}\) que \({\mathbf y}\) est envoyé, et qu’un non-mot de code \({\mathbf z}\) est reçu tel que
Alors le décodeur ne peut pas décider entre \({\mathbf x}\) et \({\mathbf y}\text{.}\) Même si nous savons qu’une erreur s’est produite, nous ne savons pas ce qu’est l’erreur.
Supposons \(d_{\min} \geq 3\text{.}\) Alors le schéma de décodage par maximum de vraisemblance corrige toutes les erreurs simples. En partant d’un mot de code \({\mathbf x}\text{,}\) une erreur dans la transmission d’un seul bit donne \({\mathbf y}\) avec \(d({\mathbf x}, {\mathbf y}) = 1\text{,}\) mais \(d({\mathbf z}, {\mathbf y}) \geq 2\) pour tout autre mot de code \({\mathbf z} \neq {\mathbf x}\text{.}\) Si nous n’exigeons pas la correction des erreurs, alors nous pouvons détecter des erreurs multiples quand un code a une distance minimale supérieure ou égale à \(3\text{.}\)
Soit \(C\) un code avec \(d_{\min} = 2n + 1\text{.}\) Alors \(C\) peut corriger \(n\) erreurs ou moins. De plus, toute erreur de \(2n\) ou moins peut être détectée dans \(C\text{.}\)
Supposons qu’un mot de code \({\mathbf x}\) est envoyé et que le mot \({\mathbf y}\) est reçu avec au plus \(n\) erreurs. Alors \(d( {\mathbf x}, {\mathbf y}) \leq n\text{.}\) Si \({\mathbf z}\) est un mot de code autre que \({\mathbf x}\text{,}\) alors
Donc \(d({\mathbf y}, {\mathbf z} ) \geq n+1\) et \({\mathbf y}\) sera correctement décodé comme \({\mathbf x}\text{.}\) Supposons maintenant que \({\mathbf x}\) est transmis et \({\mathbf y}\) est reçu et qu’au moins une erreur s’est produite, mais pas plus de \(2n\) erreurs. Alors \(1 \leq d( {\mathbf x}, {\mathbf y} ) \leq 2n\text{.}\) Puisque la distance minimale entre les mots de code est \(2n +1\text{,}\)\({\mathbf y}\) ne peut pas être un mot de code. Par conséquent, le code peut détecter entre \(1\) et \(2n\) erreurs.
Dans Table 8.1.15, les mots de code \({\mathbf c}_1 = (00000)\text{,}\)\({\mathbf c}_2 = (00111)\text{,}\)\({\mathbf c}_3 = (11100)\) et \({\mathbf c}_4 = (11011)\) déterminent un code correcteur d’erreur simple.
La théorie moderne des codes a commencé en 1948 avec l’article de C. Shannon, « A Mathematical Theory of Information » [7]. Cet article offrait un exemple de code algébrique, et le théorème de Shannon proclamait exactement ce que l’on pouvait attendre des bons codes. Richard Hamming a commencé à travailler avec des codes linéaires aux Bell Labs à la fin des années 1940 et au début des années 1950, après s’être frustré que les programmes qu’il exécutait ne puissent pas se remettre d’erreurs simples générées par du bruit. La théorie des codes a considérablement progressé au cours des dernières décennies. The Theory of Error-Correcting Codes, de MacWilliams et Sloane [5], publié en 1977, contenait déjà plus de 1500 références. Les codes linéaires (codes en blocs Reed-Muller \((32, 6)\)) ont été utilisés sur les sondes spatiales Mariner de la NASA. Des sondes spatiales plus récentes comme Voyager ont utilisé ce qu’on appelle des codes convolutifs. Actuellement, des recherches très actives sont menées sur les codes de Goppa, qui dépendent fortement de la géométrie algébrique.
