Code d'effacement

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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 , ou représente le nombre de symboles requis pour restaurer le message et est appelée efficacité de la réception.

Codes d'effacement optimal[modifier | modifier le code]

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 suffisant 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 encodage 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.

Contrôle de la parité[modifier | modifier le code]

Le contrôle de la parité est un cas spécial ou . 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 :

Sur-échantillonnage polynomial[modifier | modifier le code]

Exemple: Err-mail (k = 2)[modifier | modifier le code]

Dans le cas simple ou 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 :

  1. Approximativement la moitié du courrier est perdue.
  2. Les messages plus grand que 5 caractères sont interdits.
  3. Le prix est prohibitif (comme pour le courrier par avion)

Au lieu de demander à Bob d'acquitter les messages qu'elle envoie, Alice invente le schéma suivant.

  1. Elle découpe sont numéro de téléphone en 2 parties a = 555, b = 629, et envoie 2 messages - "A = 555" et "B = 629" – a Bob.
  2. Elle construit une fonction linéaire, , dans le cas présent , tel que et .
Code d'effacement optimal 1
  1. Elle calcule les valeurs f(3), f(4), et f(5), puis transmet 3 messages redondants : "C = 703", "D = 777" et "E = 851".

Bob sait que f(k) est défini par , où a et b sont les deux parties de son numéro de téléphone.

Maintenant, supposons que Bob reçoive "D = 777" et "E = 851".

Code d'effacement optimal 2

Bob peut retrouver le numéro de téléphone d'Alice en calculant les valeurs de a et b à partir des valeurs (f(4) et f(5)) qu'il a reçu. Bob peut effectuer cette procédure en utilisant n'importe quel couple de deux valeurs err-mail, donc le code d'effacement de cet exemple a un taux de 40%.

Notons qu'Alice ne peut pas encoder son numéro de téléphone dans une seule valeur err-mail, car il contient six caractères, et le longueur maximum d'un message err-mail est de cinq caractères. Si elle envoie son numéro de téléphone en morceaux, demandant à Bob d'acquitter la réception de chacun de ces morceaux, il faudrait au moins quatre messages pour l'envoyer de toute façon (deux d'Alice et deux acquittements de Bob). Donc, le code d'effacement dans cet exemple, qui requiert cinq messages, est économique.

Cet exemple est bien sûr inventé dans le cas présent. Pour qu'un vrai code d'effacement générique fonctionne sur n'importe quel jeu de données, nous aurions besoin de quelque chose de plus pertinent que la fonction f(i).

Cas général[modifier | modifier le code]

La construction linéaire ci-dessus peut être généralisée en interpolation polynomiale. De plus, les points sont calculés dans un corps fini.

Premièrement, on choisit un corps fini F d'ordre minimum n, usuellement une puissance de 2. L'émetteur énumère les symboles de données de 0 à k-1 et les envoie. Il construit ensuite un polynôme de Lagrange p(x) d'ordre k tel que p(i) est égal au symbole de donnée i. Puis, il envoie p(k),...,p(n-1). Le récepteur peut alors utiliser une interpolation polynomiale pour retrouver les paquets perdus, à condition qu'il reçoive k symboles correctement. Si l'ordre de F est inférieur à 2b, ou b est le nombre de bits d'un symbole, alors plusieurs polynômes peuvent être utilisés.

L’émetteur peut construire les symboles k à n-1 « à la volée », c'est-à-dire distribuer la charge de travail de manière égale entre la transmission des symboles. Si le récepteur veut faire ses calculs « à la volée », il peut construire un nouveau polynôme q, tel que q(i) = p(i) si le symbole i < k est reçu correctement et q(i) = 0 quand le symbole i < k n'a pas été reçu. Maintenant, soit r(i) = p(i) − q(i). En premier lieu, nous savons que r(i) = 0 si le symbole i < k a bien été reçu. Ensuite, si le symbole i >= k a été reçu correctement, alors r(i) = p(i) − q(i) peut être calculé. Donc nous avons suffisamment de points de données pour construire r et l’évaluer afin de trouver les paquets manquants. Donc l’émetteur et le récepteur ont besoin tout deux de o(n (n − k)) opérations et seulement o(n − k) d'espace pour fonctionner « à la volée ».

Implémentation concrète[modifier | modifier le code]

Ce processus est implémenté par le code de Reed-Solomon, avec des mots construits dans un corps fini en utilisant le matrice de Vandermonde.

Codes d'effacement quasi-optimaux[modifier | modifier le code]

Les codes d'effacement quasi-optimaux requièrent (1 + ε)k symboles pour retrouver le message (ou ε>0). La réduction de ε peut être effectuée au détriment du temps CPU. Les codes d'effacement quasi-optimaux défavorisent les capacités de correction au profit de la complexité calculatoire:  Les algorithmes utilisés en pratique peuvent encoder et décoder avec une complexité en temps linéaire.

les codes fontaines (aussi appelés codes d'effacement sans débit) sont des exemples notables de codes d'effacement quasi-optimaux. Ils peuvent transformer un message composé de k symboles en une forme encodée quasi infinie, c'est-à-dire qu'ils peuvent générer un nombre quelconque de symboles redondants qui peuvent être tous utilisés pour effectuer la correction d'erreurs. Les récepteurs peuvent commencer à décoder après qu'ils ont reçu un peu plus de k symboles encodés.

Les codes régénérants résolvent le problème de reconstruction (appelé aussi réparation) des fragments encodés perdus à partir de fragments encodés existants. Ce problème survient dans les systèmes de stockage distribués où la communication maintenant la redondance encodée est imparfaite.

Exemples[modifier | modifier le code]

Des exemples de ce type de code sont présentés ci-dessous :

Codes d'effacement quasi-optimaux[modifier | modifier le code]

Codes fontaine quasi-optimaux[modifier | modifier le code]

Codes d'effacement optimaux[modifier | modifier le code]

Autre[modifier | modifier le code]

Voir aussi[modifier | modifier le code]

  • Code correcteur.
  • Secret réparti (diffère dans le fait que le secret original est chiffré et caché jusqu'à ce que le quorum de décodage soit atteint)

References[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Erasure code » (voir la liste des auteurs).

Liens Externes[modifier | modifier le code]

  • Jerasure is a Free Software library implementing Reed-Solomon and Cauchy erasure code techniques with SIMD optimisations.
  • Software FEC in computer communications by Luigi Rizzo describes optimal erasure correction codes
  • Feclib is a near optimal extension to Luigi Rizzo's work that uses band matrices. Many parameters can be set, like the size of the width of the band and size of the finite field. It also successfully exploits the large register size of modern CPUs. How it compares to the near optimal codes mentioned above is unknown.
  • Coding for Distributed Storage wiki for regenerating codes and rebuilding erasure codes.