Code d'effacement

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 $k$ symboles en un message plus long composé de $n$ symboles tel que le message original peut être retrouvé à partir d'un sous-ensemble de ces $n$ symboles. La fraction $r=k/n$ est appelé « débit du code ». La fraction $k'/k$, où $k'$ représente le nombre de symboles requis pour restaurer le message est appelée efficacité de la réception.

Codes d'effacement optimal

Les codes d'effacement optimaux possèdent la propriété que $k$ symboles de mots-code quelconques, appartenant à l'ensemble des $n$ 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 $n$ 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 à $O(nlog(n))$; Ce qui reste toutefois inexploitable.

Contrôle de la parité

Le contrôle de la parité est un cas spécial où $n=k+1$. Depuis un ensemble de $k$ valeurs $\{v_{i}\}_{1\leq i\leq k}$, une somme de contrôle est calculée et ajoutée aux $k$ valeurs sources :

$v_{k+1}=-\sum _{i=1}^{k}v_{i}.$

L'ensemble des k + 1 valeurs $\{v_{i}\}_{1\leq i\leq k+1}$ est cohérent par rapport à la somme de contrôle. Si l'une de ces valeurs, $v_{e}$, est effacée, elle peut être retrouvée facilement en sommant les variables restantes tel que :

$v_{e}=-\sum _{i=1,i\neq e}^{k+1}v_{i}.$

Sur-échantillonnage polynomial

Exemple : Err-mail (k = 2)

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 :

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 son 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, $f(i)=a+(b-a)(i-1)$, dans le cas présent $f(i)=555+74(i-1)$, tel que $f(1)=555$ et $f(2)=629$.

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 $f(i)=a+(b-a)(i-1)$, 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 coder son numéro de téléphone dans une seule valeur err-mail, car il contient six caractères, et la 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

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 à 2^b, 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 tous deux de o(n (n − k)) opérations et seulement o(n − k) d'espace pour fonctionner « à la volée ».

Implémentation concrète

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

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 coder 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 codé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 codés.

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

Exemples

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

Codes d'effacement quasi-optimaux

• codes Tornado
• LDPC

Codes fontaine quasi-optimaux

• Code en ligne
• codes LT
• codes Raptor

Codes d'effacement optimaux

• Somme de contrôle: utilisé dans les systèmes de stockage RAID.
• Parchive
• Tahoe-LAFS includes zfec
• Code de Reed-Solomon
• Erasure Resilient Systematic Code, un code MDS dépassant les performances de Reed–Solomon en un nombre maximum de paquets redondants, voir RS(4,2) with 2 bits or RS(9,2) avec 3 bits
• Code régénérants.
• tout autre code MDS

Autre

• Alphabet radio

Voir aussi

• 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)

Références

(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

• 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.