Code fontaine

En théorie du codage, les codes fontaine (également appelés codes d'effacement sans rendement fixe, en anglais rateless erasure codes) sont une classe de codes d'effacement ayant la propriété qu'une séquence potentiellement illimitée de symboles encodés peut être générée à partir d'un ensemble donné de symboles source, de telle sorte que les symboles source originaux puissent idéalement être reconstruits à partir de n'importe quel sous-ensemble de symboles encodés dont la taille est égale ou seulement légèrement supérieure au nombre de symboles source. Le terme fontaine ou sans rendement fixe fait référence au fait que ces codes ne présentent pas un rendement de code fixe.

Un code fontaine est optimal si les k symboles source originaux peuvent être reconstruits à partir de n'importe quels k symboles encodés reçus avec succès (c'est-à-dire en excluant ceux qui ont été effacés). Il existe des codes fontaine dotés d'algorithmes efficaces d'encodage et de décodage, qui permettent la reconstruction des k symboles source originaux à partir de n'importe quels k symboles encodés avec une forte probabilité, où k est seulement légèrement supérieur à k.

Les codes LT ont été la première réalisation pratique des codes fontaine. Les codes Raptor et les codes en ligne ont été introduits par la suite et atteignent une complexité d'encodage et de décodage en temps linéaire grâce à une étape de pré-codage des symboles d'entrée. Le codage réseau triangulaire (en) permet un encodage et un décodage linéaires en utilisant un encodage non linéaire et un décodage par la méthode de substitution arrière.

Applications

Les codes fontaine sont applicables de manière flexible à un rendement de code fixe, ou dans les cas où un rendement fixe ne peut pas être déterminé a priori, et où un encodage et un décodage efficaces de grandes quantités de données sont nécessaires.

Un premier exemple est celui d'un carrousel de données (en), où un fichier volumineux est continuellement diffusé vers un ensemble de récepteurs. En utilisant un code d'effacement à rendement fixe, un récepteur qui manque un symbole source (en raison d'une erreur de transmission) est confronté au problème du collectionneur de coupons : il doit recevoir avec succès un symbole encodé qu'il ne possède pas déjà. Ce problème devient beaucoup plus manifeste lors de l'utilisation d'un code d'effacement classique de courte longueur, car le fichier doit être divisé en plusieurs blocs, chacun étant encodé séparément : le récepteur doit alors collecter le nombre requis de symboles encodés manquants pour chaque bloc. En utilisant un code fontaine, il suffit au récepteur de récupérer n'importe quel sous-ensemble de symboles encodés dont la taille est légèrement supérieure à l'ensemble des symboles source. (En pratique, la diffusion est généralement programmée pour une durée fixe par un opérateur, en fonction des caractéristiques du réseau et des récepteurs ainsi que de la fiabilité de livraison souhaitée ; le code fontaine est ainsi utilisé à un rendement de code déterminé dynamiquement au moment où la diffusion du fichier est planifiée.)

Un autre domaine d'application est celui de l'ARQ hybride dans les scénarios de multidiffusion fiable : les informations de parité demandées par un récepteur peuvent potentiellement être utiles à tous les récepteurs du groupe de multidiffusion.

Dans les standards

Les codes Raptor sont les codes fontaine les plus efficaces à ce jour, possédant des algorithmes d'encodage et de décodage très performants en temps linéaire, et ne nécessitant qu'un petit nombre constant d'opérations XOR par symbole généré, tant pour l'encodage que pour le décodage. La RFC 5053 de l'IETF spécifie en détail un code Raptor systématique, qui a été adopté dans de multiples standards au-delà de l'IETF, notamment au sein du standard MBMS du 3GPP pour la livraison de fichiers en diffusion et les services de streaming, du standard IPDC (en) de DVB-H pour la fourniture de services IP sur les réseaux DVB, et de DVB-IPTV (en) pour la fourniture de services de télévision commerciale sur réseau IP. Ce code peut être utilisé avec jusqu'à 8 192 symboles source par bloc source, et un total de jusqu'à 65 536 symboles encodés générés par bloc source. Ce code présente un surcoût de réception relatif moyen de 0,2 % lorsqu'il est appliqué à des blocs source de 1 000 symboles, et un surcoût de réception relatif inférieur à 2 % avec une probabilité de 99,9999 %. Le surcoût de réception relatif est défini comme les données d'encodage supplémentaires nécessaires au-delà de la longueur des données source pour reconstruire les données source originales, exprimé en pourcentage de la taille des données source. Par exemple, si le surcoût de réception relatif est de 0,2 %, cela signifie que des données source d'une taille de 1 mégaoctet peuvent être reconstruites à partir de 1,002 mégaoctet de données encodées.

Un code Raptor plus avancé, offrant une plus grande flexibilité et un surcoût de réception amélioré, appelé RaptorQ, a été spécifié dans la RFC 6330 de l'IETF. Le code RaptorQ spécifié peut être utilisé avec jusqu'à 56 403 symboles source par bloc source, et un total de jusqu'à 16 777 216 symboles encodés générés par bloc source. Ce code est capable de reconstruire un bloc source à partir de n'importe quel ensemble de symboles encodés dont le nombre est égal au nombre de symboles source du bloc source avec une forte probabilité, et dans de rares cas à partir d'un nombre légèrement supérieur au nombre de symboles source du bloc source. Le code RaptorQ fait partie intégrante de l'instanciation ROUTE spécifiée dans la norme ATSC A-331 (ATSC 3.0).

Pour le stockage de données

Les codes d'effacement sont utilisés dans les applications de stockage de données en raison des économies considérables sur le nombre d'unités de stockage pour un niveau donné de redondance et de fiabilité. Les exigences de conception des codes d'effacement pour le stockage de données, en particulier pour les applications de stockage distribué, peuvent être assez différentes par rapport aux scénarios de communication ou de diffusion de données en continu. L'une des exigences du codage pour les systèmes de stockage de données est la forme systématique, c'est-à-dire que les symboles du message original font partie des symboles codés.^{[réf. nécessaire]} La forme systématique permet de lire les symboles du message sans décodage à partir d'une unité de stockage. De plus, étant donné que la bande passante et la charge de communication entre les nœuds de stockage peuvent constituer un goulet d'étranglement, les codes permettant une communication minimale sont très bénéfiques, en particulier lorsqu'un nœud tombe en panne et qu'une reconstruction du système est nécessaire pour atteindre le niveau initial de redondance. À cet égard, les codes fontaine devraient permettre un processus de réparation efficace en cas de défaillance : lorsqu'un seul symbole encodé est perdu, la reconstruction de ce symbole ne devrait pas nécessiter trop de communication et de calcul entre les autres symboles encodés. En fait, la latence de réparation peut parfois être plus importante que les économies d'espace de stockage. Les codes fontaine réparables visent à répondre aux objectifs de conception des codes fontaine pour les systèmes de stockage. Une étude détaillée sur les codes fontaine et leurs applications est disponible dans.

Une approche différente du stockage distribué utilisant les codes fontaine a été proposée dans Liquid Cloud Storage. Liquid Cloud Storage repose sur l'utilisation d'un grand code d'effacement tel que le code RaptorQ spécifié dans la RFC 6330 de l'IETF (qui offre une protection des données significativement meilleure que d'autres systèmes), sur l'utilisation d'un processus de réparation en arrière-plan (qui réduit significativement les besoins en bande passante de réparation par rapport à d'autres systèmes), et sur l'utilisation d'une organisation des données en flux (qui permet un accès rapide aux données même lorsque tous les symboles encodés ne sont pas disponibles).

Voir aussi

• Code en ligne
• Codage réseau linéaire
• Partage de secret
• Codes Tornado, le précurseur des codes fontaine

Notes et références

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

Bibliographie

• Amin Shokrollahi and Michael Luby, « Raptor Codes », Now Publishers, vol. 6, n^os 3–4,‎ 2011, p. 213–322 (DOI 10.1561/0100000060, S2CID 1731099)
• Michael Luby, The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings., 2002, 271–282 p. (ISBN 0-7695-1822-2, DOI 10.1109/sfcs.2002.1181950, S2CID 1861068), « LT codes »
• A. Shokrollahi, Raptor Codes, vol. 52, 2006, 2551–2567 p. (DOI 10.1109/tit.2006.874390, Bibcode 2006ITIT...52.2551S, S2CID 61814971), chap. 6.
• P. Maymounkov, « Online Codes », (Technical Report),‎ novembre 2002 (lire en ligne)
• David J. C. MacKay, Information Theory, Inference, and Learning Algorithms, Cambridge University Press, 2003 (ISBN 0-521-64298-1, Bibcode 2003itil.book.....M, lire en ligne)
• M. Luby, A. Shokrollahi, M. Watson, T. Stockhammer, Raptor Forward Error Correction Scheme for Object Delivery, octobre 2007.
• M. Luby, A. Shokrollahi, M. Watson, T. Stockhammer, L. Minder, RaptorQ Forward Error Correction Scheme for Object Delivery, mai 2011.