Voir la source de Code correcteur

{{Voir homonymes|ECC}}
{{À sourcer|date=mai 2019}}
[[Fichier:Reed–Solomon error correction Mona Lisa LroLrLasercomFig4.jpg|vignette|Pour nettoyer les erreurs de transmission introduites par l'atmosphère terrestre (à gauche), les scientifiques de Goddard ont appliqué la correction d'erreur Reed-Solomon (à droite), qui est couramment utilisée dans les CD et DVD. Les erreurs typiques incluent les pixels manquants (blanc) et les faux signaux (noir). La bande blanche indique une brève période pendant laquelle la transmission a été interrompue.]]

Un '''code correcteur''', souvent désigné par le sigle anglais '''ECC''' (de l'{{lang-en|''error-correcting code''}}), aussi appelé '''code correcteur d'erreur(s)''' ou '''code de correction d'erreur(s)''' ('''CCE''')<ref>{{GDT|mot=code correcteur d'erreur|fiche=2074758}}</ref>, est une technique de [[Codage en ligne|codage]] basée sur la redondance. Elle est destinée à corriger les erreurs de transmission d'une [[information]] (plus souvent appelée [[message]]) sur un [[Canal de communication (théorie de l'information)|canal de communication]] peu fiable.

La [[théorie des codes]] correcteurs ne se limite pas qu'aux communications classiques (radio, [[câble coaxial]], [[fibre optique]], etc.) mais également aux supports pour le stockage comme les [[Disque compact|disques compacts]], la  [[mémoire vive]] et d'autres applications où la garantie de l'intégrité des données est importante.

== Problème ==
=== Description intuitive ===
Les codes correcteurs d'erreurs ont leur source dans un problème très concret lié à la transmission de données. Dans la grande majorité des cas, une [[transmission de données]] se fait en utilisant une voie de communication, le ''canal de communication'', qui n'est pas entièrement fiable. Autrement dit, les données, lorsqu'elles circulent sur cette voie, sont susceptibles d'être altérées.

Par exemple lors d'une communication [[onde radio|radio]], la présence de parasites sur la ligne va perturber le son de la voix. Il y a alors essentiellement deux approches possibles : 
* augmenter la puissance de l'émission ;
* ajouter de la redondance à l'information.

Si l'on reprend l'exemple de la communication radio, augmenter la puissance de l'émission signifie crier ou avoir un meilleur émetteur. Cette technique a bien évidemment ses limites, et aura du mal à être utilisée dans des sondes spatiales, sans même prendre en considération des contraintes sur les ressources en énergie.

L'autre solution va consister à ajouter des données, ce qui donne lieu au code des aviateurs qui diront « Alpha Tango Charlie » dans le seul but de transmettre correctement « ATC » à travers leur radio. La séquence « Alpha Tango Charlie », même déformée par la friture, sera bien plus reconnaissable pour l'oreille humaine qu'un « ATC » déformé.

== Formalisation du problème ==
=== Alphabet ===
Afin de préciser les questions que se pose la [[théorie des codes]], et les problèmes qu'elle rencontre, voici le cas d'un [[canal discret]]. L'information à transmettre peut être vue comme une suite ''x'' de symboles pris dans un [[ensemble fini]] (il s'agit le plus souvent de [[bit]]s, donc de 0 et de 1).
* Un alphabet est un ensemble fini non vide, ses éléments sont appelés lettres ou symboles.
* Un message ou un mot est une suite à valeur dans un alphabet, il correspond à une suite de lettres.
L'objectif d'un code correcteur est la transmission fiable d'un message. Dans cet article les alphabets sont notés ''A'' ou ''A{{'}}'', le cardinal d'un alphabet est noté ''q'', et un message ''m''.

=== Code en bloc ===
Dans le cas général, les messages à transmettre n'ont pas de longueur fixe. Cette situation existe, par exemple, pour une communication téléphonique. En revanche, il est plus simple de développer un code correcteur pour des messages d'une longueur fixe.

La solution utilisée consiste à segmenter la difficulté. Dans un premier temps, est traité le cas d'un message de longueur fixe. Pour le cas général, une solution simple consiste à [[Concaténation|concaténer]] une suite de blocs. La méthode la plus répandue, car la plus efficace est celle du {{Lien|trad=Convolutional code|fr=Code convolutif|texte=code convolutif}}.
* La longueur d'un message désigne le nombre de lettres qu'il contient.
* Un code en bloc est un code correcteur traitant des messages de longueur fixe.
Dans la suite de l'article, la longueur d'un message est notée ''k''. L'ensemble des messages est noté ''E'' et son cardinal ''M''. ''M'' est un entier naturel inférieur ou égal à ''q''<sup>k</sup>.

=== Codage ===
Comme le montre ''supra'' [[#Redondance et fiabilité|redondance et fiabilité]], il n'est pas toujours judicieux de transmettre le message ''m''. L'ajout d'une redondance peut être pertinente. Pour répondre à cet objectif, on se dote d'une fonction φ [[Injection (mathématiques)|injective]] de ''E'' dans un ensemble ''F'', la transmission a lieu sur φ(''m'') et non sur ''m''. L'injectivité est nécessaire, car sinon deux messages distincts ne seraient plus distinguables par le récepteur. ''F'' est l'ensemble des suites finies de longueur ''n'' un entier strictement positif à valeur dans ''A' ''un alphabet. Dans le cas général l'alphabet de ''F'' diffère de celui de ''E''.

Avant sa transmission, le message est encodé, c'est-à-dire qu'il est transformé en une autre suite ''y''=φ(''x'') de symboles. Ensuite, ''y'' est transmis par un canal bruité qui va, éventuellement le modifier en ''y'.'' Pour terminer, un décodeur essaie de retrouver le message ''x'' à partir de ''y'.'' Il est théoriquement équivalent de rechercher ''y'', puisque le codage est une injection. Lorsque ''y'' diffère de ''y','' on parle d'erreur(s) ou d'altération(s).

* L'application φ de ''E'' dans ''F'' est appelée codage.
* La longueur ''n'' des suites de ''F'' est appelée dimension du code ou simplement dimension.
* L'image φ(''E''), sous-ensemble de ''F'' est appelée code.
* Un mot du code est un élément du code.

== Exemples de codes en bloc ==
=== Code de répétition ===
{{Article détaillé|Code de répétition}}
Un exemple simple est celui du code de répétition. Le cas étudié ici est celui d'un code [[Système binaire|binaire]], c’est-à-dire que les deux alphabets ''A'' et ''A{{'}}''sont confondus et égaux à {0,1}. La longueur du code est égale à 3 et la dimension à 1.

L'application φ est définie sur les deux valeurs: 0 et 1, par une triple définition du message. De manière formelle, on obtient :
<center><math>\varphi(0) = 000 \quad et \quad \varphi(1) = 111 </math></center>
Si une unique altération se produit, alors un système de vote permet de retrouver le message d'origine. Ce code correcteur possède l'avantage de non seulement détecter une erreur, mais aussi de permettre une correction automatique. En revanche, il est ''cher'', c’est-à-dire que sa dimension est élevée par rapport à la longueur des mots transmis.

=== Somme de contrôle ===
{{Article détaillé|Somme de contrôle}}
[[Fichier:Bit de parité.jpg|vignette|gauche|Code de longueur deux avec un bit de parité.]]

{| class="wikitable droite"
!Messages = ''E''
!Codes = φ(''E'')
|-
| 00
| 000
|-
| 01
| 101
|- 
| 10
| 110
|- 
| 11
| 011
|}

L'objectif n'est plus ici la correction automatique mais la détection d'une unique erreur. Les deux alphabets sont binaires, les messages sont de longueur ''deux'' et le code de dimension ''trois''.

Le codage consiste à ajouter un ''bit de parité'', qui vaut ''zéro'' si la somme des lettres est paire et ''un'' sinon. La table de correspondance du codage est donnée à droite.

La figure de gauche est une illustration géométrique du code. Elle représente l'ensemble d'arrivée ''F''. Les mots du code sont en vert. Une unique erreur correspond à un déplacement sur le cube le long d'une arête. Dans ce cas, le récepteur reçoit un point noir dont la somme de toutes les lettres est un entier impair. Il est donc possible de déterminer l'existence d'une erreur.

En revanche, un point noir est toujours à proximité de trois points verts, le récepteur ne dispose donc d'aucun moyen pour une correction automatique.

Cette technique est généralisable à d'autres alphabets et pour des codes de longueurs quelconques. Elle est économique, c'est la raison pour laquelle elle est largement utilisée. En revanche, et à la différence de l'exemple précédent, la correction impose une nouvelle transmission.

== Redondance et fiabilité ==
=== Distance de Hamming ===
{{Article détaillé|Distance de Hamming}}

[[Fichier:Hamming distance 4 bit binary example.svg|vignette|[[Hypercube (graphe)|hypercube]] binaire <math>Q_4</math> de dimension quatre.]]
Le concept le plus utilisé pour la modélisation de la redondance est celui de la ''distance de Hamming''. À deux mots du code, elle associe le nombre de lettres qui diffèrent.
:''La distance de Hamming entre « ramer » et « cases » est 3.''
La figure de droite illustre le cas où les lettres de l'alphabet sont [[Système binaire|binaires]] et la dimension du code égale à quatre. La distance entre 0110 et 1110 est égale à ''un'' car il est nécessaire de parcourir un segment du graphique pour joindre les deux mots. On peut aussi remarquer que les deux mots diffèrent seulement par leur première lettre. La même approche montre que la distance entre 0100 et 1001 est égale à ''trois''.

Ce concept permet la définition suivante :
* La distance minimale d'un code correcteur est la plus petite distance au sens de Hamming entre deux mots du code.
Cette définition permet de formaliser les trois paramètres les plus importants d'un code en blocs.
* Les paramètres d'un code en blocs sont la longueur du code ''n'', le nombre ''M'' de mots du code et la distance minimale δ. Ils sont en général notés {''n'', ''M'', δ}

=== Code parfait ===
{{Article détaillé|Code parfait}}

[[Fichier:Code correcteur parfait.jpg|vignette|gauche|Illustration d'un [[code parfait]].]]
En général, on considère que le mot de code émis est celui se trouvant le plus près du mot reçu, ce qui revient à supposer que le minimum de lettres a été modifié. Ce procédé conduit à une erreur de décodage chaque fois que l'erreur est supérieure à la capacité corrective du code. La question naturelle est celle de la valeur de ''t'' correspondant au nombre maximum d'erreurs corrigibles.

Une interprétation géométrique donne un élément de réponse. Les [[boule (mathématiques)|boules]] fermées de rayon ''t'' centrées sur les mots de code doivent être disjointes. La capacité de correction d'un code correspond au plus grand entier ''t'' vérifiant cette propriété, c'est aussi le plus grand entier strictement plus petit que δ/2. Elle permet de définir une première majoration, appelée ''borne de Hamming'' :
<center><math>M \leq \frac{q^n}{V_t}\quad avec \quad V_t=\sum_{i=0}^{t} {n \choose i}  (q-1)^i</math></center>

La figure de gauche correspond à une configuration idéale, correspondant au cas où les boules fermées de rayon ''t'' et de centre les mots du code forment une [[partition (mathématiques)|partition]] de l'espace ''F''. Les points du code, en vert, sont espacés d'une distance de ''cinq'' entre eux. Si la transmission ne produit jamais plus de deux altérations, alors les erreurs sont toutes corrigibles. Les points à une distance de ''un'' d'un mot de code sont en bleu, ceux à une distance de ''deux'' en rouge et la frontière des boules est indiquée en vert. Il n'existe aucune redondance inutile, le code est le plus compact possible pour garantir la correction certaine de ''t'' erreurs. Pour de tels codes, la majoration de la borne de Hamming est une égalité. Ils sont dits ''parfaits''. L'exemple le plus simple est celui de [[Code de Hamming (7,4)|Hamming]] binaire de paramètres [7,4,3].

== Théorie algébrique des codes en blocs ==
Si l'analyse qu'apporte la [[distance de Hamming]] et les codes parfaits propose un cadre permettant d'évaluer l'''efficacité'' d'un code, elle n'offre pas de solution pratique pour en construire.

La solution consiste à équiper les ensembles ''E'' et ''F'' de structures [[algèbre|algébriques]] plus riches. Pour cela, les alphabets ''A'' et ''A{{'}}'' sont identifiés et munis d'une structure de corps fini. Le cas le plus fréquent consiste à choisir le corps ''F''<sub>2</sub> ou l'une de ses [[extension finie|extensions finies]]. Ce corps correspond à l'alphabet binaire dont les tables d'addition et de multiplication sont données ci-dessous :
{| class="wikitable centre"
|
{| border="1"
|  +  ||  0  ||  1  
|-
|  0  ||  0 ||  1
|-
|  1  ||  1 ||  0
|}
|
{| border="1"
|  . ||  0  ||  1  
|-
|  0  ||  0 ||  0
|-
|  1  ||  0 ||  1
|}
|}

Ce corps, ou ses extensions sont adaptés à un traitement informatique, qui, dans sa grande généralité, travaille sur l'alphabet binaire.

=== Codes linéaires ===
{{Article détaillé|Code linéaire}}

Si les alphabets sont un même corps fini, ''E'' et ''F'' héritent naturellement d'une structure d'[[espace vectoriel]]. Choisir alors comme application de codage φ une [[application linéaire]] simplifie grandement le problème.

Les paramètres d'un code linéaire sont notés de manière légèrement différente de ceux des codes quelconques. L'espace ''E'' est vectoriel, il est décrit uniquement par sa dimension, correspondant à la longueur du code. Ils sont notés [''n'', ''k'', δ].

Peu de codes linéaires sont parfaits, et ils sont soit de petites dimensions soit de petite distance minimale. Une autre majoration, plus générale et de même nature que la borne de Hamming existe :
* La majoration suivante est vérifiée pour tous les codes linéaires. Elle se nomme borne de Singleton :
<center><math>n-k\ge \delta - 1</math></center>
Si la borne est atteinte, on parle alors de code MDS pour {{anglais|maximum distance separable}}.

==== Matrice génératrice ====
{{Article détaillé|matrice génératrice}}

Le codage est obtenu par l'application d'une [[matrice (mathématiques)|matrice]], dite matrice génératrice. Elle est toujours équivalente à une forme particulièrement simple, appelée code systématique, les premières coordonnées d'un mot du code correspondent au message, les dernières décrivent la redondance, elles sont appelées [[somme de contrôle|sommes de contrôle]] ou, dans le cas d'un [[code cyclique]] [[contrôle de redondance cyclique|contrôles de redondance cyclique]].

==== Matrice de contrôle ====
{{Article détaillé|matrice de contrôle}}

La validation du décodage est encore simplifiée. Il existe une application linéaire de ''F'' dans un espace de dimension ''n'' -''k'' ayant comme [[noyau (algèbre)|noyau]] exactement le code. Sa matrice est dite de matrice de contrôle. Dans le cas le plus fréquent dans l'industrie, celui du code systématique, la matrice de contrôle s'obtient directement à partir de la matrice génératrice et elle possède encore une forme particulièrement simple.

Valider un message reçu revient à vérifier que l'application de la matrice de contrôle à ce message est bien égale au vecteur nul.

==== Syndrome et décodage ====
{{Article détaillé|Décodage par syndrome}}

La linéarité du code assure un décodage aisé. Si un message ''x'' est reçu, alors la détection d'erreurs est réalisée par la matrice de contrôle ''H''. En effet, des altérations détectables ont eu lieu si et seulement si ''H''.<sup>t</sup>''x'' est différent du vecteur nul. Si le nombre d'erreurs présentes dans le message est inférieur à ''t'', le nombre d'altérations assurément détectables, alors ''H''.<sup>t</sup>''x'' possède un unique antécédent ''e'' dans la boule fermée de centre le vecteur nul et de rayon ''t''. Le message corrigé est ''x'' - ''e''. Le vecteur ''H''.<sup>t</sup>''x'' est appelé syndrome.

Dans le cas où le nombre d'erreurs est supérieur à ''t'' il existe plusieurs antécédents de poids minimal et les altérations ne sont plus assurément corrigibles. La solution idéale consiste à demander une nouvelle transmission.

Si le nombre de syndromes est petit, une table de correspondance entre les syndromes et leurs antécédents de plus petits poids est envisageable. Une telle table est nommée tableau standard et le décodage associé décodage par tableau standard. Si l'espace des syndromes est trop vaste, il est nécessaire de calculer son antécédent à la réception du message altéré.

=== Codes cycliques ===
{{Article détaillé|Code cyclique}}
Ces codes sont plus compliqués et reposent sur l'utilisation des propriétés des polynômes dans un corps fini. Le [[Cyclic redundancy check|contrôle de redondance cyclique]] (CRC pour ''cyclic redundancy check'') consiste à considérer un bloc de données comme la représentation des coefficients d'un polynôme que l'on divise ensuite par un polynôme fixe et prédéterminé. Les coefficients issus de cette division constituent le CRC et servent de code correcteur. La vérification des données se fait en multipliant le polynôme fixe par les coefficients du CRC et en comparant le résultat avec les données. On peut également calculer le CRC des données reçues et comparer avec le CRC reçu.

=== Autres codes ===
Les structures utilisées dans les codes correcteurs ont tout d'abord été très simples (par exemple celle d'espace vectoriel), puis se sont complexifiées avec une meilleure compréhension des problèmes théoriques. La théorie des codes correcteurs en arrive même à utiliser la [[géométrie arithmétique]] pour construire des codes.

== Quelques codes correcteurs ==
Voici différents types de codes correcteurs :
* [[code de Hamming]] ;
* [[code de Golay]] ;
* [[code de Reed-Muller]] ;
* [[code de Goppa]] ;
* [[code de Xing]] ;
* [[code de Reed-Solomon]].

== Quelques applications typiques ==
La transmission d'informations peut-être sujet à des perturbations. Voici quelques applications touchées par ces perturbations :
* les [[Téléphonie mobile|téléphones cellulaires]] sont mobiles, relativement peu puissants, et souvent utilisés soit loin des antennes relais, soit dans un environnement urbain très bruyant du point de vue électromagnétique ;
* les [[Sonde spatiale|sondes spatiales]] n'ont pas à leur disposition d'énormes quantités d'énergie pour émettre des messages, se trouvent à des distances astronomiques, et leur antenne, même si elle est orientée le mieux possible, n'est pas parfaite ;
* en cas de conflit armé, les communications adverses sont une des cibles privilégiées pour le brouillage et la [[guerre électronique]] ;
* les [[Image ISO|images disque]] contiennent pour certains formats (par exemple Mode 2 Form 1) des codes EDC et ECC pour contrôler les données gravées, et cela par secteur.

== Notes et références ==
{{Références}}

== Voir aussi ==

=== Articles connexes ===
* [[Graphe de Hamming]]
* [[Limite de Shannon]]
* [[Turbo code]]
* [[Méthode de décodage]]
* [[Chipkill]]
* [[Code comma-free]]

=== Bibliographie ===
* {{Demazure1}}, chap. 6 à 13
* J.-G. Dumas, J.-L. Roch, E. Tannier et S. Varrette, ''Théorie des codes (Compression, cryptage, correction)'', [[Dunod]], 2013, {{2e}} éd. ({{1re}} éd. 2007), 384 p. {{ISBN|978-2-10-059911-0}} {{présentation en ligne|lien=http://www.dunod.com/informatique-multimedia/fondements-de-linformatique/mathematiques-et-informatique-theorique/theorie-des-codes}}
* B. Martin, ''Codage, cryptologie et applications'', [[PPUR]], 2004, 354 p. {{ISBN|978-2-88074-569-1}}

=== Lien externe ===

* [https://lipsum.dev/2020-05-1-pourquoi-les-polynomes/ Introduction aux polynômes] et application aux codes correcteurs dans le cas des codes QR{{Portail|mathématiques|informatique|sécurité informatique|télécommunications|informatique théorique}}

[[Catégorie:Détection et correction d'erreur|*]]