Worldlex Wiki Les codes Raptor, comme les codes fontaine en général, encodent un bloc de données source composé de k symboles source de taille égale en une séquence potentiellement illimitée de symboles d'encodage. La réception de k symboles d'encodage ou plus permet de récupérer le bloc source avec une probabilité non nulle. Cette probabilité augmente avec le nombre de symboles d'encodage reçus au-delà de k et tend vers 1 dès que ce nombre dépasse légèrement k . Par exemple, avec la dernière génération de codes Raptor, les codes RaptorQ, la probabilité d'échec du décodage après la réception de k symboles d'encodage est inférieure à 1 %, et inférieure à une sur un million après la réception de k+2 symboles. La taille d'un symbole peut varier d'un octet à plusieurs centaines, voire milliers d'octets.
Les codes Raptor peuvent être systématiques ou non systématiques . Dans le cas systématique, les symboles du bloc source d'origine, c'est-à-dire les symboles sources, sont inclus dans l'ensemble des symboles de codage. Le 3GPP ( 3rd Generation Partnership Project) utilise, par exemple, des codes Raptor systématiques pour la diffusion et la multidiffusion sans fil des réseaux cellulaires mobiles , ainsi que pour la norme DVB-H (Digital Virtual Block Channel ) relative à la diffusion de données IP vers les appareils portables. Les codes Raptor utilisés dans ces normes sont également définis dans la RFC 5053 de l'IETF .
Les codes en ligne sont un exemple de code fontaine non systématique.
de l'IETF . Le code RaptorQ est un code systématique, peut être implémenté de manière à obtenir des performances d'encodage et de décodage en temps linéaire, possède des propriétés de récupération quasi optimales, prend en charge jusqu'à 56 403 symboles source et peut prendre en charge un nombre pratiquement illimité de symboles d'encodage.de l'IETF , est spécifié dans le cadre de la norme Next Gen TV ( ATSC 3.0 ) afin de permettre la diffusion vidéo de haute qualité (télévision mobile robuste) et la distribution efficace et fiable de fichiers (diffusion de données). Plus précisément, le code RaptorQ est spécifié dans la section A/331 de l'ATSC 3.0. Voir la liste des normes ATSC pour obtenir la liste des parties de la norme ATSC 3.0. La Next Gen TV (ATSC 3.0) va bien au-delà de la télévision traditionnelle en fournissant un Internet de diffusion permettant des services généraux de distribution de données.Aperçu
Les codes Raptor sont formés par la concaténation de deux codes.
Un code d'effacement à taux fixe , généralement assez élevé, est appliqué comme « précode » ou « code externe ». Ce précode peut lui-même être une concaténation de plusieurs codes ; par exemple, dans le code normalisé par le 3GPP, un code de contrôle de parité haute densité dérivé de la séquence de Gray binaire est concaténé avec un code de contrôle de parité basse densité simple . Une autre possibilité serait la concaténation d'un code de Hamming avec un code de contrôle de parité basse densité.
Le code interne utilise le résultat de l'opération de précodage et génère une séquence de symboles de codage. Ce code interne est un type de code LT . Chaque symbole de codage est le résultat d'un OU exclusif (XOR) appliqué à un ensemble de symboles choisis de manière pseudo-aléatoire parmi la sortie du précodage. Le nombre de symboles combinés par XOR pour former un symbole de sortie est choisi de manière pseudo-aléatoire pour chaque symbole de sortie, selon une distribution de probabilité spécifique.
Cette distribution, ainsi que le mécanisme de génération de nombres pseudo-aléatoires servant à l'échantillonner et à choisir les symboles à combiner par XOR, doivent être connus de l'expéditeur et du destinataire. Dans une approche, chaque symbole est accompagné d'un identifiant qui sert d'initialisation à un générateur de nombres pseudo-aléatoires pour générer cette information ; l'expéditeur et le destinataire suivent ensuite la même procédure.
Dans le cas des codes Raptor non systématiques, les données sources à encoder sont utilisées comme entrée de l'étape de pré-codage.
Dans le cas des codes Raptor systématiques, l'entrée de l'étape de précodage est obtenue en appliquant d'abord l'inverse de l'opération de codage qui génère les k premiers symboles de sortie aux données sources. Ainsi, l'application de l'opération de codage normale aux symboles résultants régénère les symboles sources originaux en tant que k premiers symboles de sortie du code. Il est nécessaire de s'assurer que les processus pseudo-aléatoires qui génèrent les k premiers symboles de sortie produisent une opération inversible.
Décodage
Deux approches sont possibles pour décoder les codes Raptor. Dans une approche par concaténation, le code interne est décodé en premier, à l'aide d'un algorithme de propagation de croyances , comme pour les codes LT. Le décodage réussit si cette opération permet de récupérer un nombre suffisant de symboles pour que le code externe puisse récupérer les symboles restants grâce à l'algorithme de décodage approprié.
Dans une approche combinée, les relations entre les symboles définis à la fois par les codes internes et externes sont considérées comme un seul ensemble combiné d'équations simultanées qui peuvent être résolues par les moyens habituels, généralement par élimination de Gauss .
Complexité computationnelle
Les codes Raptor nécessitent un temps O(taille du symbole) pour générer un symbole d'encodage à partir d'un bloc source, et nécessitent un temps O(taille du bloc source) pour récupérer un bloc source à partir d'au moins k symboles d'encodage.
Probabilité de récupération et frais généraux
Le surcoût correspond au nombre de symboles d'encodage supplémentaires, au-delà des k symboles sources du bloc source d'origine, nécessaires pour reconstituer intégralement ce bloc. (D'après des considérations élémentaires de théorie de l'information , la reconstitution complète d'un bloc source contenant k symboles sources est impossible si moins de k symboles d'encodage sont reçus.) La probabilité de reconstitution est la probabilité que le bloc source soit entièrement reconstitué après réception d'un nombre donné de symboles d'encodage aléatoires générés à partir de ce bloc.
Le code RaptorQ spécifié dans la RFC 6330 de l'IETF présente le compromis suivant entre la probabilité de récupération et la surcharge de récupération :
- Probabilité de récupération supérieure à 99 % avec une surcharge de 0 symbole (récupération à partir de k symboles d'encodage reçus).
- Probabilité de récupération supérieure à 99,99 % avec une surcharge de 1 symbole (récupération à partir de k+1 symboles d'encodage reçus).
- Probabilité de récupération supérieure à 99,9999 % avec une surcharge de 2 symboles (récupération à partir de k+2 symboles d'encodage reçus).
Ces affirmations sont valables pour toute la plage de valeurs de k prises en charge dans la RFC 6330 de l'IETF , c'est-à-dire k = 1,...,56403. Voir la RFC 6330 de l'IETF pour plus de détails.
Statut juridique
Qualcomm , Inc. a publié une déclaration relative aux droits de propriété intellectuelle (DPI) pour le code Raptor spécifié dans la RFC 5053 de l'IETF , ainsi qu'une déclaration relative aux DPI pour le code RaptorQ, plus avancé, spécifié dans la RFC 6330 de l'IETF . Ces déclarations reflètent l'engagement de licence pris par Qualcomm, Inc. concernant la norme MPEG DASH . Cette norme est utilisée par de nombreuses entreprises, notamment celles membres du DASH Industry Forum.