Code de correction d'erreur

L'idée centrale est que l'émetteur encode le message de manière redondante , le plus souvent à l'aide d'un code correcteur d'erreurs ( ECC ). Cette redondance permet au récepteur non seulement de détecter les erreurs pouvant survenir n'importe où dans le message, mais aussi, souvent, d'en corriger un nombre limité. Par conséquent, un canal de retour pour demander une retransmission peut s'avérer inutile. Le coût est une augmentation de la bande passante fixe du canal de transmission.

Le mathématicien américain Richard Hamming a été un pionnier dans ce domaine dans les années 1940 et a inventé le premier code correcteur d'erreurs en 1950 : le code Hamming (7,4) .

La FEC peut être appliquée dans des situations où les retransmissions sont coûteuses ou impossibles, comme dans le cas de liaisons de communication unidirectionnelles ou lors de la transmission à plusieurs récepteurs en multidiffusion .

Les connexions à longue latence en bénéficient également ; dans le cas des satellites en orbite autour de planètes lointaines, les retransmissions dues aux erreurs engendreraient un délai de plusieurs heures. La correction d'erreurs sans voie de retour (FEC) est aussi largement utilisée dans les modems et les réseaux cellulaires .

Le traitement FEC dans un récepteur peut être appliqué à un flux binaire numérique ou à la démodulation d'une porteuse modulée numériquement. Dans ce dernier cas, le FEC fait partie intégrante de la conversion analogique-numérique initiale au niveau du récepteur. Le décodeur Viterbi met en œuvre un algorithme de décision souple pour démoduler les données numériques à partir d'un signal analogique perturbé par du bruit. De nombreux décodeurs FEC peuvent également générer un signal de taux d'erreur binaire (TEB) qui peut servir de retour d'information pour optimiser l'électronique de réception analogique.

Les informations FEC sont ajoutées aux dispositifs de stockage de masse (magnétiques, optiques et à semi-conducteurs/flash) pour permettre la récupération de données corrompues et sont utilisées comme mémoire informatique ECC sur les systèmes qui nécessitent des dispositions spéciales en matière de fiabilité.

La proportion maximale d'erreurs ou de bits manquants corrigibles est déterminée par la conception du code de correction d'erreurs (ECC). Différents codes de correction d'erreurs sans voie de retour (FEC) conviennent donc à différentes conditions. En général, un code plus robuste induit une plus grande redondance, nécessitant une transmission sur la bande passante disponible. Ceci réduit le débit binaire effectif tout en améliorant le rapport signal sur bruit effectif reçu . Le théorème de codage sur canal bruité de Claude Shannon permet de calculer la bande passante de communication maximale atteignable pour une probabilité d'erreur maximale acceptable donnée. Ce théorème établit des limites au débit d'information maximal théorique d'un canal présentant un niveau de bruit de base donné. Cependant, la démonstration n'est pas constructive et n'apporte donc aucune indication sur la manière de construire un code atteignant la capacité théorique. Après des années de recherche, certains systèmes FEC avancés, comme le code polaire se rapprochent considérablement du maximum théorique (limite de Shannon) donné par la capacité du canal de Shannon, sous l'hypothèse d'une trame de longueur infinie.

Un exemple simple de codage ECC consiste à transmettre chaque bit de données trois fois, ce que l'on appelle un code de répétition (3,1) . Sur un canal bruité, un récepteur peut recevoir huit versions du signal ; voir le tableau ci-dessous.

Cela permet de corriger une erreur dans l'un des trois échantillons par « vote majoritaire » ou « vote démocratique ». La capacité de correction de ce code ECC est la suivante :

• jusqu'à un bit de triplet erroné, ou
• jusqu'à deux bits du triplet omis (cas non indiqués dans le tableau).

Bien que simple à mettre en œuvre et largement utilisée, cette redondance modulaire triple est une ECC relativement inefficace. Les meilleurs codes ECC examinent généralement les dernières dizaines, voire les dernières centaines de bits reçus précédemment afin de déterminer comment décoder le petit nombre de bits actuels (généralement par groupes de deux à huit bits).

Les deux principales catégories de codes ECC sont les codes en blocs et les codes convolutifs .

• Les codes par blocs fonctionnent par blocs (paquets) de taille fixe, composés de bits ou de symboles de taille prédéterminée. En pratique, le décodage des codes par blocs s'effectue généralement en temps polynomial jusqu'à la longueur de leur bloc.
• Les codes convolutifs fonctionnent avec des flux de bits ou de symboles de longueur arbitraire. Leur décodage souple est le plus souvent réalisé à l'aide de l' algorithme de Viterbi , bien que d'autres algorithmes soient parfois utilisés. Le décodage de Viterbi offre une efficacité de décodage asymptotiquement optimale lorsque la longueur de contrainte du code convolutif augmente, mais au prix d' une complexité exponentiellement croissante. Un code convolutif terminé est également un « code par blocs » car il code un bloc de données d'entrée. Cependant, la taille des blocs d'un code convolutif est généralement arbitraire, tandis que celle des codes par blocs est fixe et déterminée par leurs caractéristiques algébriques. Parmi les types de terminaison pour les codes convolutifs, on trouve la terminaison par « tail-biting » et la terminaison par « bit-flushing ».

Les codes en blocs classiques sont généralement décodés à l'aide d'algorithmes à décision binaire , ce qui signifie que pour chaque signal d'entrée et de sortie, une décision binaire est prise quant à sa correspondance avec un bit 1 ou 0. En revanche, les codes convolutifs sont généralement décodés à l'aide d'algorithmes à décision souple , tels que les algorithmes de Viterbi, MAP ou BCJR , qui traitent des signaux analogiques (discrétisés) et permettent des performances de correction d'erreurs bien supérieures à celles du décodage à décision binaire.

Presque tous les codes par blocs classiques exploitent les propriétés algébriques des corps finis . C'est pourquoi on les appelle souvent codes algébriques.