Code de transformation Luby - Luby transform code

En informatique , les codes de transformation de Luby ( codes LT ) sont la première classe de codes de fontaine pratiques qui sont des codes de correction d'effacement presque optimaux . Ils ont été inventés par Michael Luby en 1998 et publiés en 2002. Comme certains autres codes fontaine, les codes LT dépendent de graphes bipartis clairsemés pour échanger le surcoût de réception contre la vitesse d'encodage et de décodage. La particularité des codes LT est d'utiliser un algorithme particulièrement simple basé sur l' opération exclusive ou ( ) pour coder et décoder le message. ${\style d'affichage \oplus }$

Les codes LT sont sans débit car l'algorithme de codage peut en principe produire un nombre infini de paquets de messages (c'est-à-dire que le pourcentage de paquets qui doivent être reçus pour décoder le message peut être arbitrairement petit). Ce sont des codes de correction d'effacement car ils peuvent être utilisés pour transmettre des données numériques de manière fiable sur un canal d'effacement .

La prochaine génération au-delà des codes LT sont les codes Raptor (voir par exemple IETF RFC 5053 ou IETF RFC 6330), qui ont un codage et un décodage temporels linéaires. Les codes Raptor sont fondamentalement basés sur les codes LT, c'est-à-dire que le codage des codes Raptor utilise deux étages de codage, le deuxième étage étant le codage LT. De même, le décodage avec les codes Raptor repose principalement sur le décodage LT, mais le décodage LT est mélangé à des techniques de décodage plus avancées. Le code RaptorQ spécifié dans IETF RFC 6330, qui est le code fontaine le plus avancé, a des probabilités de décodage et des performances largement supérieures par rapport à l'utilisation d'un seul code LT.

Pourquoi utiliser un code LT ?

Le schéma traditionnel de transfert de données à travers un canal d'effacement dépend d'une communication bidirectionnelle continue.

L'expéditeur encode et envoie un paquet d'informations.
Le récepteur tente de décoder le paquet reçu. S'il peut être décodé, le récepteur renvoie un accusé de réception à l'émetteur. Sinon, le récepteur demande à l'émetteur de renvoyer le paquet.
Ce processus bidirectionnel se poursuit jusqu'à ce que tous les paquets du message aient été transférés avec succès.

Certains réseaux, tels que ceux utilisés pour la diffusion sans fil cellulaire, n'ont pas de canal de retour. Les applications sur ces réseaux nécessitent toujours de la fiabilité. Les codes fontaine en général, et les codes LT en particulier, contournent ce problème en adoptant un protocole de communication essentiellement unidirectionnel.

L'expéditeur encode et envoie paquet après paquet d'informations.
Le récepteur évalue chaque paquet au fur et à mesure qu'il est reçu. S'il y a une erreur, le paquet erroné est rejeté. Sinon, le paquet est enregistré en tant que partie du message.
Finalement, le récepteur a suffisamment de paquets valides pour reconstruire l'intégralité du message. Lorsque tout le message a été reçu avec succès, le récepteur signale que la transmission est terminée.

Comme mentionné ci-dessus, le code RaptorQ spécifié dans IETF RFC 6330 surpasse un code LT dans la pratique.

codage LT

Le processus de codage commence par diviser le message non codé en n blocs de longueur à peu près égale. Les paquets codés sont ensuite produits à l'aide d'un générateur de nombres pseudo-aléatoires .

Le degré d , 1 d ≤ n , du prochain paquet est choisi au hasard.
Exactement d blocs du message sont choisis au hasard.
Si M _i est le i ième bloc du message, la partie de données du paquet suivant est calculé comme

M_{i_{1}}\oplus M_{i_{2}}\oplus \cdots \oplus M_{i_{d}}\,

où { i ₁ , i ₂ , …, i _d } sont les indices choisis au hasard pour les d blocs inclus dans ce paquet.

Un préfixe est ajouté au paquet encodé, définissant combien de blocs n sont dans le message, combien de blocs d ont été exclusifs-orés dans la partie de données de ce paquet, et la liste des indices { i ₁ , i ₂ , …, je _d }.
Enfin, une certaine forme de code de détection d'erreurs (peut-être aussi simple qu'un contrôle de redondance cyclique ) est appliquée au paquet, et le paquet est transmis.

Ce processus se poursuit jusqu'à ce que le récepteur signale que le message a été reçu et décodé avec succès.

décodage LT

Le processus de décodage utilise l'opération " exclusif ou " pour récupérer le message codé.

Si le paquet courant n'est pas propre, ou s'il réplique un paquet qui a déjà été traité, le paquet courant est rejeté.
Si le paquet actuel correctement reçu est de degré d > 1, il est d'abord traité par rapport à tous les blocs entièrement décodés dans la zone de file d'attente de messages (comme décrit plus en détail à l'étape suivante), puis stocké dans une zone tampon si son degré réduit est supérieur à 1.
Lorsqu'un nouveau paquet propre de degré d = 1 (bloc M _i ) est reçu (ou que le degré du paquet actuel est réduit à 1 par l'étape précédente), il est déplacé vers la zone de mise en file d'attente des messages, puis comparé à tous les paquets de degré d > 1 résidant dans le tampon. Il fait l'objet d'un or exclusif dans la partie de données de tout paquet mis en mémoire tampon qui a été codé à l'aide de M _i , le degré de ce paquet correspondant est décrémenté et la liste d'indices pour ce paquet est ajustée pour refléter l'application de M _i .
Lorsque ce processus déverrouille un bloc de degré d = 2 dans le tampon, ce bloc est réduit au degré 1 et est à son tour déplacé vers la zone de file d'attente des messages, puis traité contre les paquets restants dans le tampon.
Lorsque tous les n blocs du message ont été déplacés vers la zone de file d'attente de messages, le récepteur signale à l'émetteur que le message a été décodé avec succès.

Cette procédure de décodage fonctionne car A A = 0 pour toute chaîne de bits A . Une fois que d − 1 blocs distincts ont été soumis à un or exclusif dans un paquet de degré d , le contenu original non codé du bloc non apparié est tout ce qui reste. Dans les symboles, nous avons ${\style d'affichage \oplus }$

{\begin{aligned}&{}\qquad (M_{i_{1}}\oplus \dots \oplus M_{i_{d}})\oplus (M_{i_{1}}\oplus \dots \oplus M_{i_{k-1}}\oplus M_{i_{k+1}}\oplus \dots \oplus M_{i_{d}})\\&=M_{i_{1}}\oplus M_ {i_{1}}\oplus \dots \oplus M_{i_{k-1}}\oplus M_{i_{k-1}}\oplus M_{i_{k}}\oplus M_{i_{k+1 }}\oplus M_{i_{k+1}}\oplus \dots \oplus M_{i_{d}}\oplus M_{i_{d}}\\&=0\oplus \dots \oplus 0\oplus M_ {i_{k}}\oplus 0\oplus \dots \oplus 0\\&=M_{i_{k}}\,\end{aligned}}

Variantes

Plusieurs variantes des processus de codage et de décodage décrits ci-dessus sont possibles. Par exemple, au lieu de préfixer chaque paquet avec une liste des indices de bloc de message réels { i ₁ , i ₂ , …, i _d }, l'encodeur pourrait simplement envoyer une courte "clé" qui a servi de germe pour le générateur de nombres pseudo-aléatoires (PRNG) ou table d'index utilisée pour construire la liste des index. Étant donné que le récepteur équipé du même RNG ou table d'index peut recréer de manière fiable la liste "aléatoire" d'index à partir de cette graine, le processus de décodage peut être terminé avec succès. Alternativement, en combinant un code LT simple de faible degré moyen avec un code de correction d'erreurs robuste, un code raptor peut être construit qui surpassera un code LT optimisé dans la pratique.

Optimisation des codes LT

Il n'y a qu'un seul paramètre qui peut être utilisé pour optimiser un code LT simple : la fonction de distribution de degrés (décrite comme un générateur de nombres pseudo-aléatoires pour le degré d dans la section de codage LT ci-dessus). En pratique, les autres nombres "aléatoires" (la liste des indices { i ₁ , i ₂ , …, i _d } ) sont invariablement tirés d'une distribution uniforme sur [0, n ), où n est le nombre de blocs dans lesquels le le message a été divisé.

Luby lui-même a discuté de la « distribution idéale des solitons » définie par

{\begin{aligned}\mathrm {P} \{d=1\}&={\frac {1}{n}}\\[2pt]\mathrm {P} \{d=k\} &={\frac {1}{k(k-1)}}\qquad (k=2,3,\dots ,n).\,\end{aligned}}

Cette distribution de degrés minimise théoriquement le nombre attendu de mots de code redondants qui seront envoyés avant que le processus de décodage puisse être terminé. Cependant, la distribution idéale des solitons ne fonctionne pas bien dans la pratique car toute fluctuation autour du comportement attendu rend probable qu'à une certaine étape du processus de décodage, il n'y aura pas de paquet disponible de degré 1 (réduit), donc le décodage échouera. De plus, certains des blocs d'origine ne seront xorés dans aucun des paquets de transmission. Par conséquent, en pratique, une distribution modifiée, la « distribution des solitons robustes », se substitue à la distribution idéale. L'effet de la modification est, généralement, de produire plus de paquets de très petit degré (autour de 1) et moins de paquets de degré supérieur à 1, à l'exception d'un pic de paquets à une quantité assez importante choisie pour s'assurer que tous les blocs originaux seront inclus dans certains paquets.

Voir également

Notes et références

^ ^un ^{b M.} Luby, " LT Codes ", Le 43e Symposium annuel IEEE sur les fondements de l'informatique, 2002.
^ L' exclusif ou l' opération (XOR), symbolisée par ⊕, a la propriété très utile que A ⊕ A = 0, où A est une chaîne arbitraire de bits de .
^ Codes de fontaine , par DJC MacKay, d'abord publié dans IEEE Proc.-Commun., Vol. 152, n° 6, décembre 2005.
^ ^un ^b Optimisation de la distribution des degrés des codes LT avec une approche d'échantillonnage d'importance , par Esa Hyytiä, Tuomas Tirronen et Jorma Virtamo (2006).

Liens externes

[Luby-1] un ^{b M.} Luby, " LT Codes ", Le 43e Symposium annuel IEEE sur les fondements de l'informatique, 2002.

[2] L' exclusif ou l' opération (XOR), symbolisée par ⊕, a la propriété très utile que A ⊕ A = 0, où A est une chaîne arbitraire de bits de .

[MacKay-3] Codes de fontaine , par DJC MacKay, d'abord publié dans IEEE Proc.-Commun., Vol. 152, n° 6, décembre 2005.

[Tirronen-4] un ^b Optimisation de la distribution des degrés des codes LT avec une approche d'échantillonnage d'importance , par Esa Hyytiä, Tuomas Tirronen et Jorma Virtamo (2006).

Languages

In other projects