Codes correcteurs d'erreurs
Les codes correcteurs d'erreurs ajoutent une redondance structurée aux données afin que les erreurs introduites lors de la transmission ou du stockage puissent être détectées et corrigées.
Definition
Un code est un ensemble de mots de code, généralement des chaînes sur un alphabet fini, choisis de manière à ce que deux mots quelconques diffèrent en suffisamment de positions pour que les erreurs modifiant quelques symboles puissent être détectées ou corrigées par décodage vers le mot de code le plus proche.
Scope
Ce sujet couvre les paramètres de base des codes de bloc – longueur, dimension et distance minimale –, la métrique de Hamming, les codes linéaires et leurs matrices génératrices et de contrôle de parité, ainsi que les familles clés telles que les codes de Hamming, Reed-Solomon, BCH et Reed-Muller. Il présente les bornes fondamentales sur les paramètres des codes, notamment les bornes de Singleton, de Hamming et de Gilbert-Varshamov.
Core questions
- Combien d'erreurs un code peut-il détecter et corriger étant donné sa distance minimale ?
- Comment les bons codes sont-ils construits sur des corps finis ?
- Quels sont les compromis fondamentaux entre la longueur, le débit et la distance ?
- Comment les codes peuvent-ils être décodés efficacement ?
Key concepts
- Distance et poids de Hamming
- Distance minimale
- Codes linéaires
- Matrices génératrices et de contrôle de parité
- Codes de Hamming et de Reed-Solomon
- Bornes de Singleton et de Hamming
Key theories
- Distance minimale et correction d'erreurs
- Un code avec une distance de Hamming minimale d peut détecter jusqu'à d-1 erreurs et corriger jusqu'à la partie entière inférieure de (d-1)/2 erreurs, ce qui constitue le principe central reliant la séparation géométrique des mots de code à la capacité de gestion des erreurs.
- Borne de Singleton et codes MDS
- La distance minimale d'un code de longueur n et de dimension k ne peut excéder n-k+1 ; les codes atteignant cette borne avec égalité, tels que les codes de Reed-Solomon, sont à distance maximale séparable (MDS) et d'une efficacité optimale.
Clinical relevance
Les codes correcteurs d'erreurs sont indispensables dans la communication et le stockage numériques : ils protègent les données sur les disques compacts et les disques durs, dans les codes QR, les liaisons cellulaires et satellitaires, et la transmission dans l'espace lointain, et ils sont liés aux conceptions combinatoires et à la géométrie finie.
History
Le théorème de codage de canal de Shannon de 1948 a prouvé qu'une communication fiable est possible en dessous de la capacité, et les codes de Hamming de 1950 ont fourni la première construction pratique, lançant ainsi la théorie du codage en tant que discipline.
Key figures
- Claude Shannon
- Richard Hamming
- Irving Reed
Related topics
Seminal works
- macwilliams1977
- vanlintcoding1999
Frequently asked questions
- Comment un code corrige-t-il une erreur sans savoir où elle se trouve ?
- Étant donné que les mots de code valides sont très espacés, un mot reçu avec peu d'erreurs est le plus proche d'un seul mot de code, et le décodage vers le mot de code le plus proche permet de récupérer l'original.
- Quelle est la différence entre la détection et la correction ?
- La détection signale seulement qu'une erreur s'est produite et peut demander une retransmission, tandis que la correction récupère directement les données prévues ; la correction nécessite une distance minimale plus grande.