Codes correcteurs d'erreurs pour une transmission de vidéos H.264 / AVC sur IP:Rapport étude bibliographique

De Wiki de Romain RUDIGER
Aller à : navigation, rechercher

Revenir sur la page d'accueil du projet.

Introduction

Actuellement, le monde de l'Internet fleurit de nouveaux services qui se multiplient de plus en plus rapidement. Depuis peu, on voit apparaître des services à la demande tel que les radios, la vidéo (VoD, Streaming,IPTV) qui sont consommateurs en ressources et bande passante. Malheureusement, Internet, de par sa conception est un réseau incontrôlable, les applications de services à la demande doivent s'adapter au réseau. Face à ce problème, de nouvelles idées sont apparues et permettent de trouver des moyens palliant le manque voir l'absence de qualité de service (QoS).

Face à la perte de paquets sur les réseaux IP, des solutions sont apparues, ce sont les codes détecteurs et correcteurs d'erreurs. Ils sont intégrés au niveau du codage canal dans le schéma classique de transmission décrit sur la figure 1. Ces codes agissent lors du codage canal après le codage source qui a pour but de compresser l'information à transmettre. Le but de ces codes est d'ajouter de la redondance d'information aux données sources. De par la redondance, on retrouvera plusieurs fois la même information sur plusieurs paquets, ce qui permet de reconstruire d'éventuel paquet perdu. Cette technique permet de faire de la correction de perte sur une liaison sans retransmission des paquets (i.e. : transmission d'une vidéo en temps réel).

Figure 1 : Chaîne de transmission de données sur un support de communication quelconque.

De ces problématiques, notre projet s'inscrit dans l'étude de codes correcteurs d'erreurs orientés dans la transmission de vidéo à la demande sur les réseaux IP. Ce projet se découpe en deux grandes parties: la bibliographie et l'implémentation. La bibliographie est délivrée dans ce rapport et l'implémentation des codes correcteurs dont nous faisons l'étude sera l'objet d'un second rapport.

Cette bibliographie se décompose en trois grande parties :

  • Une première partie contient les grandes définitions nécessaires à la compréhension des codes correcteurs avec : les notions de classes et de familles de codes correcteurs d'erreurs ainsi que des exemples de codes.
  • Une deuxième partie présente en détail trois codes qui seront implémentés puis testés : Raptor, Reed-Salomon ainsi que la transformation Mojette.
  • Une dernière partie détaille la phase d'implémentation ainsi que les tests qui seront réalisés.

Ce rapport marque la fin de l'étude bibliographique et le début de l'implémentation des codes retenus et des tests comparatifs.

But et contexte du projet

Codes correcteurs d'erreurs pour une transmission de vidéos H.264/AVC sur IP

Encadrement : Fadi Boulos

Introduction

La transmission de vidéos sur les réseaux IP (Internet Protocol) connaît un grand essor depuis quelques années grâce à la multiplication et à la diversification des services vidéos disponibles aux utilisateurs : chaînes de télévision sur IP (IPTV), vidéos à la demande (VOD) et les services de visioconférence. Pourtant, Internet n'a pas été conçu initialement pour ce genre de services et ces services souffrent ainsi d'une fluctuation de la qualité d'usage. Cette variation est essentiellement due à la perte de paquets, elle-même causée par les congestions sur le réseau. Pour remédier au problème de perte de paquets, il a été proposé d'utiliser les codes correcteurs d'erreurs (FEC). Ces codes ajoutent de la redondance aux données initiales de façon à compenser les paquets perdus pendant la transmission. Dans la littérature, nous retrouvons plusieurs codes correcteurs adaptés aux transmissions vidéos (Reed-Solomon, Turbo, Raptor...). D'autre part, la transformation Mojette développée au sein de l'équipe Image et Vidéocommunication du laboratoire IRCCyN a des propriétés intéressantes pour de la protection canal.

Objectif du projet

L'objectif est de comparer les performances de codes correcteurs extraits de la littérature à celles de la transformation Mojette.

Travail à réaliser

Un travail de mise en œuvre des différentes étapes de protection canal dans une chaîne de transmission vidéo est à réaliser. Il comporte deux grandes parties :

  1. Recherche bibliographique : la recherche portera sur les codes correcteurs les plus utilisés dans le cadre d'une transmission vidéo sur IP. Les avantages et les inconvénients de chaque code seront exposés.
  2. Développement :
  • Implémentation (codage/décodage) des codes identifiés comme étant les plus intéressants à tester.
  • Implémentation du module "simulateur de pertes" qui contrôlera plus ou moins rigidement l'introduction des pertes dans les flux vidéos.

Compétences

Une bonne connaissance des langages C/C++ est requise. Une familiarité avec les normes de codage vidéo (en particulier H.264/AVC) serait un plus.

Les codes correcteurs

Cette première partie se propose d'établir une définition des codes correcteurs d'erreurs. Les codes correcteurs d'erreurs sont des codes utilisés au niveau du codage canal lors d'une transmission d'informations sur un support de communication quelconque. Ils sont plus élaborés que les codes détecteurs d'erreurs qui permettent uniquement de déceler le nombre d'erreurs au niveau du récepteur pour signaler que l'intégrité du message n'est pas arrivé mais ne permettent pas de corriger ces erreurs.

Définitions des codes correcteurs

Selon les principaux domaines d'utilisation des codes correcteurs d'erreurs à savoir les mathématiques, l'informatique, la théorie de l'information et la télécommunication; nous retrouvons l'idée principale qui est qu'un code correcteur d'erreurs doit assurer l'intégrité des données au travers d'un canal bruité où au sein d'un média de stockage peu fiable.

Un autre trait des codes correcteurs d'erreurs est qu'ils sont capables au niveau du récepteur de détecter et de corriger les erreurs survenues durant la transmission. Nous verrons que certains codes ne peuvent corriger qu'une seule erreur et d'autres plusieurs.

Au cours de notre étude, nous allons voir qu'il est possible de regrouper ces codes sous la forme de classes et au sein même de ces classes distinguer différentes familles. Nous verrons aussi que certains codes sont plus appropriés à certains domaines d'utilisation. Les performances des codes dépendent très souvent des réglages de paramètres choisis.

Les classes

Lors de cette étude, nous avons découvert qu'il existe plusieurs catégories (classes) de codes. Selon les thèses de Benoît Parrein et Pierre Verbert, il existe trois grandes classes sur lesquelles nous avons approfondi nos recherches: les codes linéaires, les codes cycliques et les codes par anticipation.

Codes correcteurs linéaires

Les codes en blocs linéaires trouvent leurs origines dans les codes de parité (Hamming, années 1950) qui consistent à ajouter un bit supplémentaire aux bits d'information à vérifier. Une définition plus mathématique des codes linéaires donnée par P. Verbert est: "Un code est dit linéaire si la loi de formation du code se réduit à des combinaisons linéaires permettant de déterminer les éléments à placer en positions de contrôle, à partir des positions d'information."

Dans cette classe de code, nous retrouvons plusieurs familles de codes. Notre étude nous a mené à deux grandes familles de codes connus: les codes de Hamming et Reed-Muller.

  • Code de Hamming

Le code de Hamming doit son nom à Richard Wesley HAMMING son inventeur. Il peut être utilisé en tant que code correcteur d'erreurs. En théorie de l'information, l'illustration connue des codes correcteurs est la matrice Hamming (7,4) qui permet de détecter des erreurs lors d'une transmission d'information. Plus généralement, les codes de Hamming dépendent de 3 variables: le mot d'information (m), le mot code (n) et le mot de contrôle (k). On évalue chacun des codes de Hamming selon 2 mesures: la redondance ((n-m)/n) et le rendement (m/n). Ces critères se retrouvent dans un grand nombre de codes correcteurs et permettent de les comparer. Le rendement doit être le plus élevé possible (proche de 1) lorsque le mot code (n) est grand.

Une faiblesse de cette famille de codes est que l'on ne peut détecter qu'une seule erreur. C'est une très grosse limite lorsque l'on sait que d'autres codes peuvent corriger plusieurs erreurs. Un second point néfaste est qu'ils ne sont pas utilisés dans le domaine de la transmission vidéo sur IP. La conclusion est que les codes de Hamming possèdent trop d'inconvénients pour faire l'objet d'une étude plus approfondie.

  • Code de Reed-Muller

Les codes de I.S REED et D.E Muller appartiennent à la catégories des codes correcteurs linéaires. Ils forment une famille car comme les codes de Hamming, ils dépendent de plusieurs paramètes: l'ordre du code (r) et le nombre de variables (m). On parle des codes binaires Reed-Muller (r,m). Un code Reed-Muller est défini mathématiquement par l'ensemble des tables de vérité des fonctions booléennes en m variables dont la forme algébrique normale est de degré au plus r. Lorsque l'alphabet est le corps fini à q éléments, il suffit de considérer les fonctions q-aires.

Sur le principe de fonctionnement, lorsque le nombre d'erreurs dans le mot code est égal à 1, on retrouve alors le code de Hamming (n+1,m). La matrice Reed-Muller est formée de la même manière que celle des codes de Hamming (n+1,m) à la seule différence que ses lignes sont disposées différemment. L'intérêt du code Reed-Muller est la simplicité du décodage des mots code reçus. Il suffit de fixer le nombre de lignes de la matrice et le nombre d'erreurs dans le mot code.

C'est une famille de codes qui n'est pas utilisée dans le domaine de la vidéo sur IP et qui donc ne retient pas notre attention pour cette étude. Malgré cela, historiquement, le code Reed-Muller d'ordre 1 en 5 variables, qui a 64 mots de longueur 32 et corrige 7 erreurs, a été utilisé par les sondes Mariner lancées par la NASA entre 1969 et 1973 pour assurer une transmission numérique correcte des photos de Mars.

Codes correcteurs cycliques

Les codes cycliques sont une sous-famille des codes linéaires. Ils sont donc plus compliqués et reposent sur l'utilisation de propriétés des polynômes. Une définition mathématique de cette famille est donnée par P. Verbert sous la forme: "Un code linéaire est dit cyclique si et seulement si le mot formé par toute permutation circulaire sur les symboles d'un mot de code appartient au code."

Dans cette famille de codes, on retrouve le plus souvent le code Reed-Salomon et les codes de contrôle de redondance cyclique (CRC). Un nouveau code vient s'inclure dans cette famille: la transformation Mojette.

  • Codes CRC

Le contrôle de redondance cyclique (Cyclic Redundancy Check) consiste à considérer un bloc de données comme la représentation des coefficients d'un polynôme que l'on divise ensuite par un polynôme fixe et prédéterminé. Les coefficients issus de cette division constituent le CRC et servent de code correcteur d'erreur au récepteur. La vérification des données se fait en multipliant le polynôme fixe par les coefficients du CRC et en comparant le résultat avec les données. On peut également calculer le CRC des données reçues et comparer avec le CRC reçu.

L'utilisation de ces codes est grande mais reste dans des domaines non appliqués à la vidéo sur IP. Ces codes sont tout de même très référencés et considérés comme efficaces.

  • Codes Reed-Salomon

Les codes Reed-Salomon, très intéressants, sont largement utilisés dans le domaine de la transmission de vidéo sur IP. Ce code est détaillé dans une partie suivante.

  • La transformation Mojette

La transformation Mojette semble appartenir à cette famille de codes. De même que pour le code Reed-Salmon, une partie entière lui est consacrée dans la suite de ce rapport.

Codes correcteurs par anticipation (FEC)

Les codes correcteurs par anticipation (Forward Error Correction) ont pour but d'introduire de la redondance dès l'envoi pour éviter que l'émetteur ne soit solliciter pour retransmettre le message. Ses codes sont très utilisés sur des canaux bruités tel qu'Internet par exemple. Les codes FEC ont pour principe de ne pas mélanger les paquets de corrections et les paquets contenant les données sources.

L'un des inconvénients de ces codes est que le gain de temps est contestable devant la suppression des allers et retours des données et des acquittements. A l'opposé un avantage sérieux est le gain de débit. La plupart des codes utilsés dans le domaine de la vidéo sur IP appartiennent à cette famille.

Fonctionnement d'un code FEC.
  • Codes MDS

Les codes MDS (Maximum Distance Separate) utilisent la distance de Hamming. Ces codes sont les plus efficaces des codes correcteurs FEC et sont parfois appelés "code parfait". Ce terme s'explique par le fait qu'il n'ajoute aucune redondance inutile. La propriété la plus intéressante est: si en sortie du codeur, (s) paquets sources et (r) paquets répartions sont émis alors les données initiales pourrons être reconstruites par le décodeur en ne recevant que s paquets parmi les (s+r) envoyés. Cette propriété justifie le fait qu'aucune redondance ajoutée n'est inutile.

Des codes FEC, le code Raptor est l'un des plus récent et selon le marché de la vidéo sur IP: le plus performant. Il est présenté plus en détail dans la suite de ce rapport.

Généralités

Dans cette partie, nous présentons des généralités communes aux deux codes que nous avons retenus pour notre étude: Raptor et Reed-Salomon.

Protection inégale des données

"Unequal Error Protection" (UEP) traduisible par "protection contre les erreurs inégales" est une technique de protection des données qui consiste à protéger plus moins certaines données. Pour mettre en pratique ce type de protection, il faut absolument un moyen de savoir ce qu'est une information importante et donc il faut regarder le codeur source.

Appliqué à ce projet, il est possible de détecter l'importance d'un paquet RTP en dans l'en-tête de chaque NAL (NALU) le champ NAL Storage IDC (NSI). Ce champ est codé sur 2 bits, une valeur 11 indique que cette NAL est importante pour reconstruire l'image, une valeur de 00 indique que cette NAL peut être perdue sans risquer d'empêcher le décodeur source de décoder l'image.

Protection inégale de l'information en utilisant le champ NSI de l'en-tête des NALU (Network Abstraction Layer Packet).

Donc pour un taux d'importance élevé, il faudra utiliser plus de redondance que pour un taux faible. Ainsi, nous améliorerons considérablement la qualité de la vidéo reçue.

Code d'effacement

Un code d’effacement (Erasure Code) transforme un message de k blocs en un message plus long que k blocks ainsi le message original peut être recouvert par un sous ensemble de ces blocks. Le taux de fractionnement des ces blocs est appelé r. Les codes d’effacement sont utilisés dans certaines formes des codes appartenant à la famille des codes correcteurs d’erreurs par anticipation (FEC). Les codes d’effacements optimaux sont définis par le fait qu’il suffit d’avoir le même nombre de symboles encodés que le nombre de symboles du message original. Ils sont malheureusement coûteux en terme de consommation mémoire et d’utilisation CPU lorsque n s’accroît. Les codes Fountain sont connus pour être les plus efficaces des codes d’effacement (Rateless Erasure Codes); ils ne sont pas optimaux mais s’en rapprochent le plus parmi tous les codes de cette famille. Il est important de préciser que les codes d’effacement sont généralement implémentés en utilisant des mots codes construits dans un domaine fini utilisant les matrices de Vandermonde.

Une implémentation de Reed Solomon est décrite dans l'article numéro 01409539 de l'IEEE ainsi que dans les deux codes Reed-Solomon Cauchy-RS et Vandermonde-RS.

Efficacité du code

Le "code rate" est un réel entre 0 et 1, il représente le ratio entre le nombre de symboles informations (k)et le nombre total de symboles envoyés (informations + parités = n ). Il peut être traduit par "Rendement du code". Par exemple, un code RS(7,5) a un taux de 5/7, autrement dit, 2 symboles de redondances sont nécessaires tous les 5 symboles d'informations.

Certains codes comme les codes Raptor, LT sont dit : "rateless erasure codes" ; c'est à dire qu'ils n'utilisent un nombre fixe de symboles parités, et n'ont donc pas un taux fixe.

Les codes étudiés

Nous avons étudié trois codes dans ce rapport, les deux premiers ont été élus de par leurs grande utilisation dans le domaine de la vidéo sur IP. Le dernier, la transformée Mojette, est imposé dans le sujet de recherche.

Reed-Solomon

Les codes de Reed-Solomon sont des codes de correction et de détection d'erreurs qui se basent sur le sur échantillonnage des données sources par l'application d'un polynôme. Ces codes sont largement utilisés dans des applications commerciales : CDs, DVDs , Blu-ray et transmission de données (xDSL, WiMAX, DVB).

Origine

Les codes RS ont été inventés en 1960 par Irving S. Reed et Gustave Solomon au MIT Lincoln Laboratory. L'article parlait d'un code polynomiale d'un champ fini. La première application date de 1982 lors de son utilisation massive dans les lecteurs de disque compact.

Propriétés

Les codes RS (Reed-Solomon) ont les propriétés suivantes :

  • Ils sont linéaires ;
  • Ils sont cycliques, anciennement contrôle de redondance cyclique (CRC) ;
  • Ils font partie des codes BCH (Bose, Ray-Chaudhuri, Hocquenghem) ;
  • Ils font partie des codes Maximum Distance Separable (MDS) ce qui signifie que si il n'y a pas eu trop de symboles perdus, la correction est possible quelque soit l'ordre des symboles perdus (voir l'article de Wikipédia).

Un code RS se définit par RS(n,k) avec n indiquant le nombre de symboles au total du bloc final et k le nombre de symboles sources en entrée du codeur. Ainsi le nombre de symbole de parité se définit par n-k. Un symbole est représenté par m-bits, m étant un entier positif.

Un code RS existe si cette équation est respectée :

0<k<n<2^m+2

En général, n et k sont définis par cette équation :

(n,k)=( 2^m - 1,2^m - 1 - 2t)

, avec 2t représentant le nombre de symbole de correction. t définit la capacité de correction du code (i.e., le nombre de symboles pouvant être corrigés), la capacité de correction quelle que soit la combinaison de symboles perdus et/ou altérés est donc :

t = (\frac{n-k}{2})

, on garde le plus grand entier. Donc pour corriger t erreurs, il faut 2t symboles de parité. Pour chaque erreur, un symbole redondant sert à localiser l'erreur et un deuxième pour corriger cette erreur.

La capacité p de correction en tant que code d'effacement est :

p=n-k

Le fait que RS n'est pas un code correcteur binaire est pratique car avec un code binaire classique (7,3) le nombre de tuples n vaut : 2^n=2^7=128 tuples et celui de k : 2^k=2^3=8. Le code de parité représente donc 1/16 du message. Prenons maintenant un code non binaire (7,3) pour lequel chaque symbole est sur 3 bits (m=3), on aura 2^{nm}=2^21=2 097 152 tuples n et 2^{km}=2^9=512 tuples k soit un ratio de 1/4096 bien plus inférieur avec un code binaire. De plus ce ratio décroît plus m est grand.

Attention cependant plus la redondance augmente plus la complexité et donc le temps de calcul augmente ! Les code RS les plus performants sont ceux qui obtiennent un fort taux de "code rates" donc une faible redondance.

Principe de fonctionnement

Cette partie traite de la théorie du codage et du décodage des codes Reed-Solomon.

Codage

Ces sous parties détaillent les étapes du codage. En résumé : le codeur lit k symboles de données, calcule n-k symboles de parités (n correspond à la longueur totale du message, donnée + parité) et ajoute ces symboles de parités à la suite des symboles de données.

Le codage avec un code RS se fait comme celui d'un code CRC mais comme les codes RS sont non-binaires, il y a tout de même une différence.

Principe

Avec s le vecteur source de k symboles appartenant au champs de Galois GF(2^m) et e le vecteur encodé de n symboles. Pour être un code linéaire, l'encodage est effectué par la multiplication du vecteur source à une matrice génératrice, GM, de k lignes et n colonnes. Ce qui nous donne comme équation :

e=s*GM

Ce qui fait qu'un code RS, c'est la matrice GM. En utilisant une matrice de Vandermonde noté V_{k,n} construite à partir d'un polynôme (noté \Alpha) choisi en fonction de m (m étant le nombre de bits par symbole) dans le tableau suivant :

Liste des polynomes représentant les champs de Galois selon la valeur de m :
m = 2 "111" 1+x+x^2
m = 3 "1101" 1+x+x^3
m = 4 "11001" 1+x+x^4
m = 5 "101001" 1+x^2+x^5
m = 6 "1100001" 1+x+x^6
m = 7 "10010001" 1+x^3+x^7
m = 8 "101110001" 1+x^2+x^3+x^4+x^8
m = 9 "1000100001" 1+x^4+x^9
m = 10 "10010000001" 1+x^3+x^10
m = 11 "101000000001" 1+x^2+x^11
m = 12 "1100101000001" 1+x+x^4+x^6+x^12
m = 13 "11011000000001" 1+x+x^3+x^4+x^13
m = 14 "110000100010001" 1+x+x^6+x^10+x^14
m = 15 "1100000000000001" 1+x+x^15
m = 16 "11010000000010001" 1+x+x^3+x^12+x^16

Pour obtenir la matrice V_{k,n} : V_{k,n}=\Alpha^{kn}. Avec une génération par la matrice de Vandermonde on obtient bien un code MDS (maximum distance séparable) mais pas systématique. Un code systématique est un code qui génère un mot code contenant en premier le code source sans aucune modification. Il faut donc utiliser une matrice identité d'ordre k, comme le fait la formule ci-dessous :

GM=V_{k,n}^{-1}*V_{k,n}

, la première partie génère une matrice identité d'ordre k, la seconde permet de générer les symboles de parités.

Complexité

La complexité peut être décomposée en deux parties :

  1. Le calcul de la matrice génératrice GM (k lignes et n colonnes).
  2. La multiplication du vecteur source avec la matrice GM.

Le calcul de la matrice génératrice GM de Vandermonde nécessite : 0(k * (\log{k})^2) opérations. En ajoutant le coût de la multiplication, on obtient une complexité de 0((n-k) * k * (\log{k})^2) opérations. Si les matrices sont pré calculées, la complexité ne sera que de k opérations par élément de redondance.

Décodage

Ces sous parties détaillent comment le décodeur détecte puis répare les erreurs ou pertes de symboles. En résumé un syndrome est calculé à partir du mot reçu, ce syndrome donne le nombre d'erreur, s'il y a une erreur : le décodeur localise l'erreur puis la corrige.

Principe

Voici les grandes étapes du décodage des codes de Reed-Solomon :

  1. Calcul du syndrome
  2. Calcul des polynômes permettant de localiser les erreurs ainsi que l'amplitude
  3. Évaluation des deux polynômes
  4. Soustraction du polynôme reconstitué par le polynôme reçu pour obtenir la source sans erreur.
Schéma de principe du décodage des codes Reed-Solomon.
- r(x) vecteur reçu,
- S(x) syndrome,
- \omega(x) polynôme d'amplitude,
- \omega(x^i) polynôme d'amplitude dans GF(2^m),
- \sigma(x) polynôme de localisation,
- \sigma(\alpha^i) polynôme de localisation dans GF(2^m),
- \sigma'(\alpha^i) dérivée du polynôme de localisation dans GF(2^m)
- \omega(\alpha^i) / \sigma'(\alpha^i) division du polynôme d'amplitude et la dérivée de celui de localisation,
- c(x) vecteur source corrigé.
Source : Rapport du projet de fin d'étude de Samuele Dietler du 24 janvier 2006.

En utilisant le principe de codage décrit précédemment, ces étapes se simplifient grâce à l'utilisation de la matrice de génération. Il faudra donc faire : La première étape consiste à extraire une sous matrice V_{k,k} de la matrice génératrice en utilisant les colonnes correspondants au vecteur reçu (r). On obtient donc le vecteur source s de k symboles par la multiplication de la matrice reçue et de cette sous matrice de taille (k,k) :

s=V_{k,k}*r

La seconde étape consiste à inverser cette sous matrice et à la multiplier au vecteur reçu (r) pour corriger le vecteur source.

Complexité

Le décodeur effectue une inversion de matrice ainsi qu'une multiplication matrice-vecteur. L'inversion est simplifiée car elle peut être calculée par la multiplication de l'inverse de la matrice de Vandermonde avec une autre matrice de Vandermonde. La complexité finale est de O((\log{k})^2)

Implémentation en tant que code d'effacement

Dans le cas d'un canal de transmission à suppression de paquets, un paquet est soit bien reçu, soit supprimé.

Canal de transmission à suppression de paquets.

L'utilisation d'un code Reed-Solomon en tant que code correcteur d'erreur par anticipation permet, en encodant k paquets source et en envoyant n paquets, d'être capable de restituer les k paquets source à partir du moment ou l'on reçoit au moins k paquets (source ou parité).

Principe d'un code Reed-Solomon en Forward Error Correction.
(k paquets source, n paquet envoyés (n≥k, au moins k paquets reçus pour décoder les k paquets source)

Un paquet contient au moins S > 0 symboles, un symbole est composé de m éléments binaires. Nous avons donc k paquets sources de S symboles, si certain paquet possède moins de S symboles, des éléments nuls seront ajoutés. En sortie du processus de codage, nous aurons n paquets : k paquets sources et n-k paquets d'encodages.

Illustration des paquets d'un code Reed-Solomon en Forward Error Correction.
(k paquets source + n-k paquets FEC, k paquets reçu donc k paquets décodés pour le récepteur.)

Exemple d'encodage de paquets

Voici un schéma explicatif de l'encodage des paquets avec un code RS(7,4) qui est utilisé dans la VoIP :

\begin{bmatrix} I_11 & I_12 & I_13 & \cdots & I_1n \\ I_21 & I_22 & I_23 & \cdots & I_2n \\ I_31 & I_32 & I_33 & \cdots & I_3n \\ I_41 & I_42 & I_43 & \cdots & I_4n \end{bmatrix} Paquets d'informations
4 par n
\Downarrow Encodage
\begin{bmatrix} P_11 & P_12 & P_13 & \cdots & P_1n \\ P_21 & P_22 & P_23 & \cdots & P_2n \\ P_31 & P_32 & P_33 & \cdots & P_3n \\ I_11 & I_12 & I_13 & \cdots & I_1n \\ I_21 & I_22 & I_23 & \cdots & I_2n \\ I_31 & I_32 & I_33 & \cdots & I_3n \\ I_41 & I_42 & I_43 & \cdots & I_4n \end{bmatrix} Paquets encodés
7 par n
Encodage de paquets

Nous avons donc I_ij symboles d'informations et P_ij symboles de parités. Au lieu d'envoyer 4 paquets d'informations, nous en enverrons 7. Quelque soit les 4 paquets reçus, nous serons capable de restituer les 4 paquets d'informations.

Exemples d'utilisation dans le domaine de la vidéo sur IP

Cet article détaille une amélioration de la partie décodage d'un code Reed-Solomon dans le cadre de son intégration dans la puce effectuant la démodulation d'une transmission HDTV d'un satellite.

Si cette article ne nous intéresse pas vraiment de par son contenu, il démontre bien que Reed-Solomon est un code utilisé dans de la transmission vidéo HD par satellite.

Ce document détaille une implémentation d'un code Reed-Solomon de type RS(207,187) dans une puce de type VLSI qui est utilisée dans une chaîne de décodage HDTV.

Cet article démontre l'intérêt porté au code Reed-Solomon dans une transmission vidéo HDTV par câble et satellite.

  • Entreprise Amethyst Communication Technologies Ltd.

Cet entreprise propose une solution de protection d'une "transmission multimédia en continu" par un codeur/décodeur Reed-Solomon. Référence : design-reuse.com.

Codes Raptor

Origine

Les codes Raptor ont été inventés par Amin Shokrollahi dans les années 2000, 2001 et furent publiés en 2004. Cette famille de codes est l’une des premières des codes fontaines (Fountain code). Nous allons dans un premier temps décrire la famille des codes fontaines puis revenir sur les caractéristiques particulières des codes Raptors.

Les codes fontaines sont une famille de codes sans rendement. Le terme "fontaine" trouve son explication dans le fait que des symboles de parité sont émis de façon ininterrompue. Ces codes ont la capacité de transmettre efficacement des données sur un canal bruité ou canal à effacement. Ils ne sont pas supposés connaître les paramètres du canal de transmission et ne sont pas supposés recevoir d'information du récepteur concernant la réception ou non des données. Au sein de cette famille, nous retrouvons les codes LT (Luby Transform) qui sont considérés comme les premiers codes fontaines efficaces. Leur efficacité se fait au détriment d’une complexité d’encodage et de décodage croissant en O(K log(K)) ou K représente la taille du message à transmettre. Ce problème fait qu'ils sont trop contraignant pour une implantation matérielle.

Les codes Raptor sont une extension des codes LT. Ils sont construits en concaténant un code LT et un code appelé “pré-code” (étape de precoding) qui est un code bloc correcteur d’erreur. L'utilisation du pré-code permet de réduire la complexité d'encodage et de décodage. La complexité d'un code Raptor est linéaire en la taille du mot code O(K).

Principe de fonctionnement

Selon la RFC 5053, “Raptor Forward Error Correction Scheme for Object Delivery”, le « Systematic Raptor Code » est mis en œuvre au travers de différentes étapes inclues dans la chaîne de codage. Le choix du « Systematic Raptor Code » peut être expliqué par le fait que les codes Raptor possèdent un désavantage, ils ne sont pas systématiques. Cela signifie que les symboles d'entrée ne sont pas nécessairement reproduits par l'encodeur. Étant donné que beaucoup d'applications requièrent des codes systématiques pour plus de performance, nous allons nous intéresser au « Systematic Raptor Code ».

Figure X : Une chaîne de transmission incluant le codage et le décodage d'un code Raptor Systèmatique.

Codage

Le codage se divise en 3 grandes phases que sont: la construction de blocs, le pré-codage et l'encodage. La phase de construction des blocs est commune à beaucoup de codes correcteurs et tous les codes Raptor.

  • Construction des blocs sources

Dans un premier temps, on considère que l’encodeur doit traiter une quantité de données (les données sources) qu’il va falloir découper sous la forme de blocs pour facilité l’encodage. On considère que l'encodeur connaît la taille des données entrées.

La première étape consiste à découper cet ensemble de données en blocs de même taille que l’on nomme des blocs sources. Chacun des blocs sources est identifié par un SBN (Source Block Number) qui est un entier correspondant au numéro du bloc sur l'ensemble de Z blocs (la totalité des données à transférer). Le SBN du premier bloc est 0 et par conséquent le dernier sera (Z-1).

Chacun des blocs sources est ensuite découpé en K symboles sources de même taille T. Chacun des symboles sources du bloc est identifié par un ESI (Encoding Symbol Identifier). Le ESI du premier symbole source d’un bloc est fixée à 0 et par conséquent l'ESI du dernier symbole source est (K-1).

Les étapes suivantes consistent à diviser un bloc source en sous-blocs qui seront de taille plus petite que la taille du bloc source. Chacun des sous-blocs se verra découpé en sous-symboles. Le but de cette opération est de découper les blocs sources en sous-blocs assez petits pour facilité le travail du processeur lors du décodage. Cette étape est facultative si l'on considère que la taille T des blocs sources est assez petite.

En pratique, il est nécessaire de créer une fonction Partition(I,J) qui partitionnera un bloc de taille I en J blocs de tailles égales. Cette fonction est utilisée pour chaque partitionnement (des données en blocs sources, des blocs sources en symboles sources, ...). Cette étape étant réalisée, l'encodeur peut procédé à l'encodage de chacun des blocs sources indépendamment les uns des autres.

Figure X : Système de partitionnement d'un code Raptor.
  • Construction des paquets encodés

Lors de l'étape d'encodage, nous distinguons deux types de paquets pouvant être générés: les paquets sources et les paquets de réparation (repair packet). Les deux types de paquets possèdent des similitudes dans leurs constructions.

Un paquet est défini par deux champs: SBN et ESI. Le SBN indique le numéro de bloc source auquel se réfère le paquet. Le champ ESI indique le numéro du premier symbole contenu dans le paquet. Selon le schéma de composition des paquets, le reste de la place est alloué aux symboles.

Les paquets sources contiennent uniquement des symboles sources rattachés au bloc source traité par l'encodeur. Ils sont faciles à générer lorsque l'étape de découpage du bloc source en symboles est effectuée. Ces paquets permettent de justifier le fait que le code Raptor appartienne à classe des codes correcteurs par anticipation, l'envoi des symboles n'est pas encodé. Les paquets de réparation sont générés par l'encodeur systématique de notre code Raptor. Nous allons nous intéresser à la génération de ces paquets en étudiant le procédé utilisé: le pré-codage (precoding).

L'étape de pré-codage consiste à créer un nombre L de symboles intermédiaires (intermediate symbol) plus long que le nombre de symboles sources K (L>K). Elle permet ensuite de créer des symboles de réparation qui seront isolés et mis dans des paquets de réparation pour finalement être transmis sur le canal de diffusion.

Figure X : Étapes de codage du code Raptor Systèmatique.
  • Génération des symboles intermédiaires

La génération de L symboles intermédiraires est issue d'un travail de plusieurs algorithmes sur les K blocs sources. Parmi ces étapes, nous retrouvons la génération d'un triple de valeurs entières associé à chacun des symboles sources. La génération de ces triples est une fonction utilisant le numéro du symbole ainsi que le nombre total de symboles sources traités. Plus en détail, le générateur de triple utilise deux méthodes pour générer un triple: RAND et DEG. La méthode RAND permet de générer un nombre aléatoire et la méthode DEG permet de générer un degré, les deux résultats étant utilisés pour attribuer un triple de valeur à chacun des symboles sources.

Le triple associé à chacun des symboles sources est ensuite utilisé pour créer les L symboles intermédiaires. Auparavant, l'encodeur doit déterminer la longueur supplémentaire (L-K) qui sera ajouté. Ce calcul repose sur un système d'équations utilisant le nombre total de symboles sources traités dans le bloc. Les (L-K) symboles ajoutés sont générés par concaténation de deux algorithmes que sont LDPC (Low-Density Parity-Check) et Half. Ces deux algorithmes effectuent des calculs de "OU EXCLUSIF" entre différents symboles et stock le résultat dans les (L-K) symboles ajoutés. On dit que ces algorithmes permettent de lier les symboles les uns entre les autres (liaisons inter-symboles).

La génération des symboles de réparation, qui seront placés dans les paquets de réparation, est calculée sur la base de triples, des L symboles intermédiaires qui ont été générés et l'algorithme du LT (Luby Transform) encodeur. Le codeur LT constitue la deuxième phase de traitement des données.

  • Utilisation du LT Encodeur

Le Systematic Raptor Code utilise un algorithme noté "LTenc" qui reprend le principe d'encodage définit par le code LT. Il est important de préciser que cette étape repose avant tout sur une réorganisation des données. On considère que les L symboles intermédiaires obtenus peuvent être représentés sous la forme d'un vecteur colonne C de taille (L,1) et qu'il est possible de former une matrice nommée A de taille (L,L) découpée en zones contenant des informations des symboles intermédiaires et des vides. Le codage LT va procédé à des calculs et placer ses résultats dans les zones vides de la matrice A. Une autre matrice colonne D de taille (L,1) peut être formée en réorganisant les symboles intermédiaires d'une manière différente de C. Le résultat de ces réorganisation est que les trois matrices sont liées par une relation: A * C = D.

Le processus de LTenc prend en paramètre le nombre de symboles que l'on traite ainsi que les valeurs des L symboles intermédiaires et un triple associé au symbole de réparation. Cette fonction permet de compléter la matrice A en effectuant des opérations de OU EXCLUSIF sur les symboles. Les symboles de réparation sont ensuite mis dans un paquet de réparation et transmis.

Decodage

Il existe différents algorithmes permettant de procéder au décodage du flux issu d'un encodeur Raptor. Pour le "systematic Raptor code", il préférable d'utiliser un approche combinatoire. Cette approche consiste à utiliser les symboles transmis dans les paquets sources et les paquets de réparation pour recréer la matrice A qui est elle même issue de la transformation des symboles sources.

En sachant que dans les étapes de codage, les opérations effectuées étaient des OU EXCLUSIF, il est possible de retrouver un système d'équations qui permet de vérifier si la combinaison des OU EXCLUSIF donne le même résultat que celui trouvé lors de l'encodage. Dans le cas où des erreurs sont détectées, il est possible par une combinaison de plusieurs résultats de OU EXCLUSIF de retrouver les erreurs et les corriger. Ceci implique d'utiliser le même générateur aléatoire que celui utilisé lors de l'encodage pour retrouver les symboles sources inclus dans l'opération de OU EXCLUSIF qui donne le résultat de l'opération. On comprend que ce raisonnement est possible si et seulement si un nombre suffisant de symboles est présent. Il est nécessaire de posséder au moins N symboles (nombre de symboles sources) parmi les L symboles comprenant les symboles sources et les symboles de redondance.

En pratique, l'algorithme réutilise le générateur aléatoire RAND utilisé à l'encodage ainsi que le générateur DEG. Plusieurs solutions existent pour résoudre les combinaisons d'équations mais lors de l'implémentation, nous utiliserons le système proposé par la RFC5053 prétendant être efficace en terme de coût de calcul processeur pour le "systematic Raptor code".

Complexité

En terme de complexité, Michael LUBY de la société DIGITAL FOUNTAIN estime que la complexité à l'encodage se résume aux opérations faites durant le pré-codage et le codage. Les opérations se résument à des OU EXCLUSIF pour les algorithmes LDPC et Half. En sachant que l'on effectue 3 opérations de OU EXCLUSIF pour chaque symbole source dans chaque algorithme et que selon la RFC, l'étape de codage est estimée en moyenne à 4,64 opérations de OU EXCLUSIF par symboles soit au total un peu plus de 10 opérations binaires. En décodage, il est estimé qu'un bon algorithme de décodage fait en moyenne une dizaine d'opérations binaires pour chaque symboles sources donnés en sortie du décodeur.

Exemples d'utilisation dans le domaine de Vidéo sur IP

Cet article présente le DF Raptor utilisé par la société américaine Digital Foutain. Elle est investie dans l'avancée des codes correcteurs par anticipation et s'intéresse aux codes Raptor par le biais de DF Raptor.

Cet article présente un nouvel article de la société Californienne Digital Foutain, ToughStream™ Engine, qui permet d'incorporer facilement dans des applications IPTV ou Internet TV de la correction d'erreur par anticipation (FEC). Cette application contient une technologie "DF Raptor".

Cet article rapporte les essais de 4 sociétés de télévision nippone (dont Sumitomo Electric Networks) qui ont effectué un test entre le 12/2003 et le 31/2004 au Japon pour diffuser à près de 300 personnes de la vidéo Haute Définition (HD) en utilisant la correction par anticipation (FEC).

Cet article présente le résumé d'un article sur HandVoD. C'est une solution qui répond au problème de la diffusion de Vidéo à la Demande (VoD) sur le réseau GPRS en intégrant une correction par anticipation (FEC) et les codes "Raptor".

transformation Mojette

La transformation Mojette est un élément nouveau dans les codes correcteurs d'erreurs. Elle peut générer de la redondance d'information ce qui laisse présumer qu'elle puisse être utilisée en tant que code correcteur d'erreur.

Origine

La transformation Mojette est issue du laboratoire IRCCyN de Nantes dont les principaux concepteurs sont Jean Pierre GUEDON et Nicolas NORMAND. Elle peut être utilisée dans de nombreux domaines tel que : le multimédia, les codes correcteurs d'erreurs, la cryptographie…

Principe de fonctionnement

En résumé, la transformée Mojette repose sur l'idée que des données représentées sous la forme d'une matrice peuvent être projetées sur différents axes de projection. La Mojette transforme un ensemble de données 2D en des suites de données 1D (une par projection).

Exemple de trois projections de la transformation Mojette

Utilisation en tant que code correcteur d'erreur

L'idée du code correcteur utilisant la transformation Mojette serait de mettre les informations source en matrice et ainsi transmettre, en tant que données redondantes, les axes de projection.

Le nombre N d'axes est à fixer tout en sachant que si les données sont représentées sur une matrice de taille (I,J), il est nécessaire d'avoir un nombre d'axes supérieur ou égal au nombre le plus petit I ou J ( N \ge min(I,J) ). La redondance serait alors mesurée par le nombre d'axes générés. Plus un grand nombre d'axes est généré, plus il sera facile de reconstituer les données manquantes.

En tant que code FEC, la transmission utilisera deux types de paquets: des paquets de données sources et des paquets de réparation (paquet FEC). Les paquets de données sources contiennent les données sources sans modification (comme le décrit la spécification FEC). Les paquets de réparation contiendraient un axe de projection et un seul associé. Chacun des paquets réparation feront références au paquet source qu'ils permettent de corriger.

Actuellement, aucune tentative d'implémentation de cette solution n'a été réalisée. L'objet de ce projet est de réaliser une première version et de comparer l'efficacité de la transformation Mojette par rapport aux autres deux codes correcteurs d'erreur (Reed-Salomon et Raptor).

Conception

Implémentation générale d'un code

schéma complet avec :

  • le codeur source qui générera des paquets rtp contenant des NAL (entrée : vidéo, sortie : k paquets)
  • le codeur canal qui sera l'un des trois codes (sortie : n paquets)
  • le simulateur de perte avec probabilité p (sortie : <=n paquets)
  • le décodeur canal (sortie : <=k)
  • le décodeur source (sortie : une vidéo)

Méthode de test

La finalité de cette partie de pouvoir comparer l'efficacité de chaque code correcteur implémenté. Pour cela, nous allons décrire un jeux de test qui servira de référence pour les trois codes. Les paramètres :

  1. Taux de redondance (r) défini par le nombre de bits transmis (k) divisé par le nombre total de bits d'information source (n) soit : r = k/n.
  2. La probabilité de perte d'un paquet (p), ce paramètre sera défini sur le simulateur de perte.

Les critères de comparaisons :

  1. Le taux de correction qui correspond au nombre de paquet source reçu par rapport au nombre de paquet source à émis.
  2. La complexité d'encodage et de décodage qui pourra s'exprimer en nombre de cycles par bloc.

Conclusion

Cette étude bibliographique nous a permis de mieux appréhender le sujet de recherche et développement. Nous avons appris énormément d'information sur les codes correcteurs en général pour ensuite étudier précisément ceux choisis dans cette étude. Cela va des grandes théories aux théorèmes mathématiques utilisés. Puis nous avons étudié comment se protéger de la perte de paquets en lisant différentes RFC.

L'étude portait également sur une partie de conception qui nous a permis de comprendre l'utilisation des codes dans le domaine de la transmission de données sur IP. Cette partie nous permet de commencer sereinement la prochaine phase de ce projet qui est l'implémentation des codes en tant que code correcteur d'erreurs par anticipation.

D'un point de vue éducatif, cette étude nous a aidé à améliorer nos techniques de recherche et aller plus facilement vers de la documentation technique comme les RFC qui étaient, auparavant, des documents redoutés.

Références

Reed-Solomon

  1. An RTP Payload Format for Reed Solomon Codes.
    Ce document décrit un format de paquet RTP pour appliquer du FEC avec le code Reed-Solomon.
  2. Reed-Solomon Forward Error Correction (FEC) Schemes
    Ce document décrit un schéma d'implémentation d'un code Reed-Solomon FEC.
  3. Rapport du projet de fin d'étude de Samuele Dietler du 24 janvier 2006.
  4. Cours Internet et Multimédia de Benoît Parrein - Polytech'Nantes - Laboratoire IRCCyN/Image Vidéo Communication
  5. Reed-Solomon by Bernard Sklar.
    Ce document décrit les principes des codes Reed-Solomon.
  6. Article de wikipedia : Reed-Solomon : error correction
  7. Article de wikipedia : Cross-interleaved Reed-Solomon coding
  8. Article IEEE numéro 01409539 : "Recovery of voice packets using combined R-S Erasure code with adaptive decoding and packet repetition concealment technique" de K.M.S. Soyjaudah et S. Jharee.
  9. HDTV Error Correction using Reed-Solomon Code

Une bibliothèque implémentant le code correcteur Reed-Solomon pour les logiciels et applications IP. Cette bibliothèque est sous licence GNU GPL v2 (voir schifra_license).

Page d'accueil du projet : schifra.

Codes Raptor

  1. La RFC 5053 décrit le fonctionnement du "Systematic Raptor Code".
  2. Le diaporama "Raptor codes for reliable multicast object delivery" de Michael LUBY explique la RFC 5053.
  3. "Analyse asymptotique et conception robuste de codes Raptor pour le décodage conjoint" de Auguste VENKIAH rappelle le fonctionnement des codes Raptor et en propose une analyse,
  4. "Summary of Raptor Codes" de Tracey HO
  5. "Raptor Codes" de Amin SHOKROLLAHI l'inventeur des codes Raptor.
  6. "Implementation and performance evaluation of LT and Raptor codes for multimedia applications" de Pasquale CATALDI présente une évaluation des performances des codes Raptor.
  7. Article IEEE numéro 4536800 relatant l'utilisation des codes Raptor dans le cadre d'un service de VoD sur un réseau GPRS/EDGE : HandVoD: A Robust and Scalable VoD Solution with Raptor Codes over GPRS/EDGE Network.

Transformée Mojette

  1. Thèse de Benoît Parrein (2001), "Description multiple de l'information par la transformée Mojette"
  2. Thèse de Pierre Verbert (2004), "Sur la redondance des transformations Mojette en dimension n et en ligne"

Transmission de l'information

  1. Options for Repair of Streaming Media
    Ce mémo résume les différentes techniques de correction des flux multimédia sujet à la perte de paquet.
  2. RTP Payload format for Interleaved Media
    Description d'un format de paquets RTP avec redondance.
  3. RTP Payload Format for MPEG1/MPEG2 Video
  4. RTP Payload Format for H.264 Video
  5. Real Time Streaming Protocol (RTSP)

Autre code et généralités sur les codes

  1. Article de wikipedia : Code correcteur
  2. Article de wikipedia : BCH code
  3. Article de wikipedia : Cyclic code ou en français : Code cyclique
  4. Article de wikipedia : Cyclic redundancy check
  5. Article de wikipedia : Maximum Distance Separable
  6. Article de wikipedia : Code rate
  7. Introduction to Coding Theory de Nikolai Yakovenko and Justin Cranshaw.