Ê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 GraphSearch.
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.