Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Code d'effacement
Résumé
En théorie de l'information, un code d'effacement est un code de correction d'erreur directe pour le canal binaire d'effacement qui transforme un message composé de symboles en un message plus long composé de symboles tel que le message original peut être retrouvé à partir d'un sous-ensemble de ces symboles. La fraction est appelé « débit du code ». La fraction , où représente le nombre de symboles requis pour restaurer le message est appelée efficacité de la réception.
Les codes d'effacement optimaux possèdent la propriété que symboles de mots-code quelconques, appartenant à l'ensemble des symboles de mots-code, sont suffisants pour restaurer le message original (en d'autres termes, ils possèdent une efficacité de réception optimale). Les codes d'effacement optimaux sont des codes séparables de distance maximum (codes MDS).
Les codes d'effacement optimaux sont souvent couteux (en termes d'utilisation mémoire, de temps processeur, ou les deux) lorsque est grand. A l’exception de schémas très simple, les solutions pratiques ont, en général, un codage et un décodage quadratique. En utilisant les techniques de transformation de Fourier rapide, la complexité peut être réduit à ; Ce qui reste toutefois inexploitable.
Le contrôle de la parité est un cas spécial où . Depuis un ensemble de valeurs , une somme de contrôle est calculée et ajoutée aux valeurs sources :
L'ensemble des k + 1 valeurs est cohérent par rapport à la somme de contrôle. Si l'une de ces valeurs, , est effacée, elle peut être retrouvée facilement en sommant les variables restantes tel que :
Dans le cas simple où k = 2, les symboles redondants peuvent être créés par échantillonnage de différents points le long de la ligne entre deux symboles originaux. Ceci est présenté grâce à un exemple simple appelé err-mail:
Alice veut envoyer son numéro de téléphone (555629) à Bob en utilisant err-mail. Err-mail fonctionne comme l'e-mail sauf que :
Approximativement la moitié du courrier est perdue.
Les messages plus grand que 5 caractères sont interdits.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Proximité ontologique
Cours associés (6)
CS-438: Decentralized systems engineering
A decentralized system is one that works when no single party is in charge or fully trusted. This course teaches decentralized systems principles while guiding students through the engineering of thei
COM-102: Advanced information, computation, communication II
Text, sound, and images are examples of information sources stored in our computers and/or communicated over the Internet. How do we measure, compress, and protect the informatin they contain?
CS-308: Introduction to quantum computation
The course introduces the paradigm of quantum computation in an axiomatic way. We introduce the notion of quantum bit, gates, circuits and we treat the most important quantum algorithms. We also touch
Séances de cours associées (33)
Codes de Salomon des roseaux
Explore les codes Reed Solomon, les codes linéaires, les matrices de générateurs et les capacités de correction d'erreurs dans les systèmes de communication.
Correction d'erreur: Chor III
Couvre le code de choc, les matrices stabilisantes, les techniques d'encodage et les concepts de correction d'erreurs.
Codes de Salomon des roseauxMOOC: Information, Calcul, Communication: Introduction à la pensée informatique
Couvertures Codes Reed-Solomon pour le traitement des erreurs dans la communication et les applications pratiques dans les codes-barres 2D.
Publications associées (244)
Personnes associées (46)