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

De Wiki de Romain RUDIGER
Aller à : navigation, rechercher

Revenir sur la page d'accueil du projet.


Rapport d'implémentation Codes correcteurs d'erreurs pour une transmission de vidéos H.264/AVC sur IP Benoît Farré Romain Rüdiger Supervisor:Fadi Boulos IRCCyN

Abstract

Ce rapport présente la partie implémentation du projet recherche et développement reposant sur l'étude de la transformation Mojette en tant que code correcteur d'erreurs. Il présente de manière simple la partie implémentation du logiciel réalisé en utilisant le langage de programmation C++. Cette présentation décrit le fonctionnement des codeurs et décodeurs Reed-Salomon et Transformation Mojette.

Une phase de tests a permis de comparer les deux codes sur leurs performances et une suite de critères définis lors de cette étape. Tout au long de ce rapport, il est expliqué les démarches effectuées ainsi que les résultats obtenus (réussites/échecs).

Des conclusions définissent les apports personnels de chacun des membres du projet ainsi qu'un bilan global du déroulement de ce projet.

Remerciements

Nous tenons à remercier toutes les personnes du laboratoire IRCCyN qui nous ont aidées dans le développement de ce projet et plus particulièrement Benoît Parrein et Fadi Boulos qui nous ont fourni des informations essentielles durant la phase d'implémentation de ce projet.

Nous remercions aussi Jean Pierre Guédon, notre examinateur pour ce projet, et tous nos camarades qui nous ont soutenus lors de ce projet.

Préambule

Notre projet s'inscrit dans une recherche comparative des codes correcteurs d'erreurs appliqués au domaine de la transmission vidéo sur les réseaux TCP/IP. Nous avons dans un premier dossier effectué une bibliographie rapportant les codes correcteurs d'erreurs les plus connus du monde des transmissions. Notre objectif était de trouver deux codes populaires que l'on puisse implémenter pour ensuite les comparer à la Transformation Mojette issue du travail du laboratoire IRCCyN de Polytech'Nantes. Nous avions sélectionné les codes Reed-Salomon et les codes Raptors.

Ce rapport présente les implémentations que nous avons réalisées durant cette seconde période. A la suite de ces implémentations, nous avons effectué différents tests pour lesquels nous avons obtenus des résultats que nous présentons à la fin de ce rapport. Tout au long de ce rapport, il est présenté les problèmes que nous avons rencontrés. Parfois, ces problèmes nous ont amené à faire des changements par rapport à la conception que nous avions faite.

Un problème qui illustre nos changements est certainement celui de notre tentative d'implémentation d'un code Raptor. Nous n'avons pas réussi à obtenir de bibliothéques libres pour les codes Raptors \cite{Rfc5053, ce qui nous a fait abandonner l'implémentation de ce code (Malgré des prises de contacts par courier électronique avec Mohammad Amin Shokrollahi, inventeur des codes Raptors et de la société Digital Fountain, principale utilisatrice de ces codes). Pour les codes Reed-Salomon et Transformation Mojette, Benoît Parrein et Fadi Boulos nous ont fourni des bibliothèques libres que nous avons pu réutiliser.

Nous présentons dans une dernière partie les tests effectués et les résultats que nous avons obtenus. Un manuel utilisateur de notre application est fourni avec ce rapport. Une archive contenant le code source ainsi qu'un exécutable de notre application est disponible en contactant l'un des participants du projet par courriel électronique:

  • benoitfarre@gmail.com
  • romain.rudiger@novalan.fr

Introduction

Cette introduction est un rappel du sujet et des objectifs de notre projet de recherche et développement. Elle fait état de présentation du contexte et de l'environnement dans lequel nous avons travaillé durant cette seconde phase de projet.

Présentation de la problématique

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 \cite{Rfc3452). 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.

Objectifs poursuivis

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

Travail demandé

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

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

Travail réalisé

Nous avons réalisé durant cette phase d'implémentation et de tests, une application capable d'encoder et de décoder une vidéo dans différents formats et selon deux codes différents (Reed-Salomon et Transformation Mojette). Cette application est un fichier exécutable auquel l'utilisateur doit passer des arguments pour spécifier l'emplacement de la vidéo à traiter, le code à utiliser ainsi que l'opération à effectuer (Encoder/Décoder). Cette application est livrée sous la forme d'un fichier exécutable à lancer dans un environnement en ligne de commandes.

Contribution

Ce projet a contribué à l'étude des performances de la transformation Mojette en tant que code correcteur d'erreurs. Il nous a permi de comprendre et de comparer ce code au code Reed-Salomon actuellement très utilisé. Malheureusement, nous n'avons pas été en mesure de réaliser l'implémentation d'un troisième code (Raptor, initialement prévu ou Turbo Code comme suggérer durant l'implémentation) qui aurait permis d'élargir l'espace de comparaison.

Plan de l'étude

Dans la partie 1, ce rapport livre des détails sur notre manière d'implémenter les codeurs/décodeurs de chacun des codes (Reed-Salomon et Transformation Mojette). Nous présentons dans cette partie des explications sur les problèmes rencontrés lors de notre tentative d'implémentation d'un troisième code.

Une partie présentant le simulateur de pertes est exposée dans le chapitre 2. Elle reprend le fonctionnement d'un outil existant (RTPloss) que nous avons utilisé et modifié.

La partie 3 traite l'organisation globale de la phase de développement. Des explications sont fournies pour chaque réussite et chaque échec sur ce projet. Nous expliquons aussi, en parallèle, les changements que nous avons effectués tout au long de cette période par rapport à la conception établie lors du rapport précédant.

Une partie 4 présente les tests effectués sur les parties de l'application qui fonctionnent. Ces résultats permettent d'analyser et de comparer les deux codes implémentés. Des détails sont apportés sur la réalisation des tests et les objectifs attendus de chacun d'eux.

Des conclusions sont finalement présentées dans le chapitre 5. Elles synthétisent les résultats obtenus et livrent les réponses permettant de répondre à la problématique du projet. Cette partie présente aussi les connaissances que nous avons acquises durant ce projet.

Les annexes présentent un ensemble d'outils que nous avons utilisés et des normes que nous avons utilisés telles que les en-têtes des paquets RTP...

Fonctionnement de l'application

L'objectif de cette partie est de présenter le fonctionnement générale de l'application ainsi que chacune des ces fonctionnalités. La présentation des fonctionnalités fait l'objet de chacune des sous-parties de ce chapitre. Elles se découpent en deux parties abordant chacune l'un des deux codes correcteurs que nous avons implémentés (Reed-Salomon et Transformation Mojette). Chacun des codes est décrit par le fonctionnement de son codeur et de son décodeur. Une dernière section présente les tentatives d'implémentations d'un troisième code correcteur d'erreurs.

Fonctionnement global

L'application a été réalisée en utilisant le langage de programmation C++. Le fonctionnement global de cette application est décrit dans cette partie par un schéma représentant les fonctionnalités et ressources nécessaires pour une bonne utilisation du programme.

Présentation de l'application

Le logiciel réalisé est décrit par quatre fonctionnalités:

  • Codage Reed-Salomon
  • Décodage Reed-Salomon
  • Codage Transformation Mojette
  • Décodage Transformation Mojette


Description simple du fonctionnement de l'application

Paramètres de l'application

On s'aperçoit que l'application nécessite quatre paramètres d'entrée que l'utilisateur doit fournir sur la ligne de commande lors de l'exécution du programme:

  • Nom du fichier source
  • Nom du fichier destination
  • Nom du code correcteur d'erreurs
  • Type d'opération (codage/décodage)


Le << nom de fichier source >> est une chaîne de caractère que l'on passe en tant que premier paramètre de l'application. Il est nécessaire qu'il soit dans le même dossier que l'exécutable de l'application.

Le << nom du fichier destination >> est utilisé par le programme pour créer un fichier de sortie que l'on retrouve dans le répertoire où le programme s'exécute. C'est le deuxième paramètre du programme.

Le << nom du code correcteur d'erreurs>> est définit sur trois caractères et doit correspondre à l'une de ces deux possibilités:

  • moj : utilisation de la Transformation Mojette
  • cau : utilisation de Reed-Salomon (matrice de Cauchy)

Le code correcteur est donné en troisième paramètre de la ligne de commande.

Le << type d'opération >> est lui aussi défini sur trois caractères et n'appartient qu'à l'une de ces deux possibilités:

  • enc : opération de codage
  • dec : opération de décodage

Le type d'opération est fourni en quatrième paramètre de la ligne de commande.

Dans les cas où tous les paramètres sont valides, le programme commence par analyser le nom du code à utiliser et détermine ensuite quelle opération il doit effectuer. Le nom du fichier d'entrée (fichier source) et du fichier de sortie (fichier destination) doivent être cohérents sinon le programme annonce qu'il ne peut pas les utiliser pour lire ou écrire et s'arrête.

Dans tous les autres cas de figure, le programme n'affichera pas de commentaire et se terminera sans que l'utilisateur ait été prévenu que l'exécution a échoué.

Contraintes

Le programme implémenté est limité par différentes contraintes dont la première est le format des données du fichier source.

Il existe deux types de format pour les fichiers source (et destination) de l'application:

  • RTP : le fichier contient des paquets de type RTP
  • Annex-B : le fichier contient des paquets de type Annex-B


Lorsque le fichier source est format Annex-B, les données ne peuvent être encodées que par le codeur utilisant la Transformation Mojette. De même, lorsque les données d'entrées sont au format RTP, elles ne peuvent être encodées que par le codeur Reed-Salomon. Un premier inconvénient apparaît, notre application ne gére pas tous les types pour tous les codeurs.

Les quatres opérations possibles sont décrites par le tableau des formats de fichier en fonction des opérations. Toutes les opérations exposées ne sont possibles que dans ces conditions.

Format du fichier source Format du fichier destination

Encode Reed-Salomon

RTP

RTP

Décode Reed-Salomon RTP RTP
Encode Transformation Mojette Annex-B RTP
Décode Transformation Mojette RTP Annex-B

Tableau des formats de fichier en fonction des opérations

Exemple d'utilisation

Le logiciel se lance en ligne de commande dans une fenêtre d'invite de commande. Il est nécessaire de se positionner dans le dossier où se situe l'application. Il est obligatoire de placer le fichier source dans le même répertoire que le fichier exécutable permettant de lancer l'application.

Lorsque toutes les conditions sont réunies, il est alors possible de lancer le programme en exécutant une ligne de commande semblable à celle-ci:

boboha.exe FichierSource FichierDestination cau enc

(boboha est le nom que nous avons donné à notre projet lors de cette phase d'implémentation)

Le programme utilise le FichierSource pour extraire des paquets RTP qu'il encode (opération :enc) avec le codeur Reed-Salomon (cau). Il copie l'ensemble des paquets RTP source et paquets RTP de redondance dans le fichier de sortie dont le nom est FichierDestination.

Reed-Salomon

Cette partie présente les opérations effectuées lorsque l'utilisateur a choisi un traitement des données en utilisant le code Reed-Salomon. Deux opérations sont alors possibles : le codage et le décodage.

Il est important de rappeler que lorsque nous avons rédigé le précédant rapport, nous avions souligné le fait qu'il existe plusieurs codes Reed-Salomon. Ils sont basés sur les même principes et ne diffèrent que par la valeur de leurs paramètres globaux des fonctions de codage et de décodage. Plus concrétement, nous avons obtenu deux bibliothèques C++ (avec l'aide de Benoît Parrein) dont l'une utilise la matrice de Cauchy et l'autre la matrice de Vandermonde.

Dans ce programme, nous avons choisi d'implémenter la version utilisant la matrice de Cauchy. Ce choix s'explique par le fait que cette bibliothèque est plus complète et plus simple à réutiliser que la seconde.

Codeur Reed-Salomon

Le codeur Reed-Salomon que nous avons implémenté utilise la matrice de Cauchy. Il utilise une bibliothèque libre qui nous a fourni la fonction de codage. Cette fonction nécessite de présenter les données sous une forme organisée de paquets (dans notre cas, des paquets RTP). Le fonctionnement de ce codeur peut être illustré par le schéma de fonctionnement du codeur Reed-Salomon.


Fonctionnement du codeur Reed-Salomon (utilisant la matrice de Cauchy)


Ce codeur est paramètré lors de l'implémentation du logiciel (dans le code source par des variables globales). Le codeur Reed-Salomon est défini pour encoder une série de N paquets média (paquets source) et générer R paquets de redondance (paquet FEC\footnote{Forward Error Correction, information de redondance pour les codes correcteurs d'erreurs par anticipation) soit un total de N + R = M paquets.

Pour ce faire, le codeur lit le fichier source contenant les paquets média et stocke ces paquets jusqu'à avoir N paquets média dans sa mémoire tampon (buffer). Le programme encode ensuite les N paquets grâce à la fonction fournie par la bibliothèque et délivre en sortie R paquets FEC. Les M paquets sont ensuite écrits dans le fichier destination. Ces étapes sont répéter en boucle jusqu'à la fin de lecture du fichier source.

Techniquement, les valeurs de N et R peuvent être modifiées dans le fichier parameters.h avant compilation du projet.

En entrée du codeur, il est nécessaire d'avoir des paquets RTP. Dans le cas contraire, l'application renvoie une erreur et arrête son exécution. En sortie du programme, le fichier destination contient tous les paquets RTP média et de redondance sous une forme ordonnée: N paquets, R paquets, N paquets, R paquets, ...

Les paquets RTP de redondance sont créés par le programme en respectant la RFC\footnote{Request For Comment: http://www.ietf.org/rfc.html 2733 \cite{Rfc2733. Cette recommendation normalise la valeur du champ Payload de l'en-tête RTP des paquets FEC égale à la valeur 127. Les paquets média ont alors une valeur comprise en 0 et 126 pour ce même champ. Ce signe permet d'identifier le type du paquet lors du décodage.

  • Conditions de codage

Il n'existe aucune condition particulière pour procéder à l'encodage. Le fichier source doit seulement posséder des paquets au format RTP. L'encodage s'effectue lorsque le codeur possède suffisament de paquets (N paquets média). Lorsque la lecture du fichier source est terminée, il est possible qu'il manque des paquets pour procéder à l'encodage. Ce cas est résolu en simulant le nombre de paquets manquants comme des paquets RTP vide. Ces paquets vides ne sont pas recopiés dans le fichier destination.

  • Inconvénients

Ce codeur possède des inconvénients:

  • Peu paramètrable
  • Optimisé?
  • Format d'entrée uniquement RTP


En solution à ces inconvénients, nous proposons une liste de modifications à effectuer:

  • Création d'un fichier de configuration <<RS.conf>> contenant les valeurs des paramètres tel que le nombre de paquets source N, nombre de paquets FEC R.
  • Possibilité d'améliorer le codeur (Nous n'avons pas accordé de temps à l'optimisation de l'application)
  • Spécification dans le fichier <<RS.conf>> du format du fichier source (RTP/Annex-B) et de gérer chaque format (actuellement que RTP).

Décodeur Reed-Salomon

Le décodeur Reed-Salomon utilise, comme le codeur, la matrice de Cauchy. Il permet de corriger les erreurs apparues durant la transmission. Ce phénomène se produit régulièrement si on prend l'exemple d'un réseau tel que Internet. Dans notre cas, la perte de paquets est simulé par l'éffacement d'un nombre aléatoire de paquets déterminé en fonction d'un pourcentage voulu. Ce procédé est expliqué dans le chapitre~\ref{chap:Simulateur de pertes.

Ce décodeur se découpe en plusieurs parties dont certaines sont communes au codeur (lecture de paquet RTP, écriture de paquets dans un fichier...).


Fonctionnement du décodeur Reed-Salomon (utilisant la matrice de Cauchy)



Le décodeur n'accepte que des paquets au format RTP en entrée. Il lit les paquets RTP du fichier source et les stocke dans une mémoire tampon. Lorsqu'il n'y a pas de paquets perdus, le décodeur lit M paquets dont N paquets média et R paquet FEC puis procède au décodage.

Dans le cas où les paquets sont perdus, le décodeur attend M paquets mais n'en reçoit que P où P est inférieur à M (P < M). Dans ces conditions, l'application doit procéder au décodage dès qu'elle posséde les P paquets reçus et ne plus attendre d'avoir M paquets en mémoire tampon.

Ce problème est résolu dans notre application en créant deux compteurs distincts. L'un s'incrémente lorsque l'on reçoit un paquet média et l'autre compte les paquets FEC. Ces incrémentations se basent sur la lecture du champ SN\footnote{Sequence Number: Numéro de séquence d'un paquet RTP. de l'en-tête des paquets RTP.

Lorsque le SN du paquet courant n'est pas égale au SN du paquet précédant plus 1, des paquets ont été perdus. \[Si (\underset{cour{SN - \underset{prec{SN) > 1 \] \[ alors (\underset{cour{SN - \underset{prec{SN) paquets perdus \]

Tout ceci n'est valable que si l'on respecte l'hypothèse effectuée lors de la bibliographique qui est : << Les paquets arrivent toujours dans le bon ordre >>. Nous incrémentons les compteurs du nombre de paquets perdus. Ils permettent de déclencher le décodage malgré la perte de paquets.

Lorsque le décodage est lancé, il se peut que le décodeur ne puisse pas réparer les paquets perdus (trop de paquets perdus). Dans ce cas là, le programme continue son exécution et affiche dans la sortie standart un message signalant qu'il n'a pas pu procéder au décodage d'une série de M paquets source à cause d'un manque de paquets après transmission (moins de M paquets reçus).

  • Conditions de décodage

L'étape de décodage ne s'effectue que lorsque l'on passe d'un paquet FEC à un paquet média. Le décodeur ne décode que s'il possède plus de M paquets parmi les N paquets émis par la source.

  • Inconvénients

Ce décodeur possède, tout comme le codeur exposé précédemment, des inconvénients:

  • Optimisé?
  • Format de sortie uniquement RTP
  • Améliorer le décodeur lorsqu'il n'y a pas assez de paquets pour reconstuire partiellement les données initiales


Pour ces problèmes, nous avons proposé des solutions:

  • Il est probablement possible d'optimiser le décodeur (Regarder plus en détail la fonction décodage de la bibliothèque)
  • Pour une plus large utilisation de l'application, il serait appréciable de reconstruire des flux de données au format RTP ou Annex-B (Actuellement, seul le format RTP est géré)
  • Le programme ne procéde pas au recopiage des paquets sources reçus dans le fichier destination du décodeur lorsque l'étape de décodage n'a pas été effectuée. Par hypothèse, les paquets reçus ne sont pas modifiés. Il serait donc intéressant de recopier les paquets média reçus dans le fichier de sortie du décodeur lorsqu'il manque trop de paquets pour décoder (Restitution partielle de l'information plutôt que tout ou rien)

Transformation Mojette

Ce chapitre aborde l'implémentation du codeur et du décodeur utilisant les propriètés de la Transformation Mojette. Cette implémentation a été réalisée sur la base de notre conception établie lors du premier rapport. Sur le plan technique, Fadi Boulos nous a fourni une bibliothèque de fonctions qui nous a facilité l'implémentation du codeur et le début du décodeur. Dans ce rapport, nous nommons << codeur Transformation Mojette >> et << décodeur Transformation Mojette >> les opérations utilisant les propriétés Transformation Mojette (codeur) et Transformation Mojette Inverse (décodeur).

Codeur Transformation Mojette

Le codeur Transformation Mojette repose sur les propriétés de la Transformation Mojette. Le fonctionnement de ce codeur est résumé par le schéma de fonctionnement du codeur utilisant la Transformation Mojette.


Fonctionnement du codeur utilisant la Transformation Mojette



Le codeur TM\footnote{TM: Transformation Mojette requière en entrée un flux de paquets au format Annex-B. Ce format est imposé par la bibliothèque nous avons repris. Le principe du codeur TM repose sur la lecture de paquets Annex-B que l'on traite un par un. Chaque paquet Annex-B est transposé en une matrice dont la bibliothèque calcule automatiquement les dimensions en fonction des réglages prédéfinis. Un ensemble de paramètres est modifiable dans un fichier de configuration fourni à la racine du programme.

La matrice de données peut ensuite être encodée. L'encodeur effectue un calcul permettant de déterminer le nombre de projections nécessaires pour décrire la matrice de données en fonction du taux de redondance souhaité par l'utilisateur. Ce taux de redondance est spécifié dans le code source de l'application (doit être modifié avant la complilation). Les projections sont ensuite calculées et copiées dans le fichier de sortie au format RTP.

Chaque projection représente un paquet RTP dans le fichier de sortie du codeur. Il est à noter que la taille de ces projections est variable et dépend de la taille du paquet Annex-B source.

Contrairement au codage Reed-Salomon, le codeur TM ne recopie pas les paquets média dans le fichier destination. Seul les projections calculées lors de l'encodage sont écrites dans le fichier de sortie. Les projections seules permettent de reconstruire l'ensemble de l'information originale ce qui évite d'envoyer les paquets média.

Les paquets RTP écrits dans le fichier de sortie possèdent tous le même Payload: 127. Payload est champ de l'en-tête RTP et la valeur 127 est réservée pour signaler que le paquet RTP contient des données de redondance (RFC 2733 \cite{Rfc2733). Seul le champ SN est différent d'un paquet à l'autre. La variable SN du programme est incrémenté de un en un pour chaque projection écrite dans le fichier destination du codeur.

L'en-tête RTP que nous avons créé n'est pas utilisée par le décodeur TM. Ceci peut s'expliquer par le fait que chacune des projections comporte un en-tête spécifique utilisé par le décodeur TM (créé par Fadi Boulos et donné en Annexe).

  • Conditions de codage

Le codage n'est possible que si le flux de données en entrée est au format Annex-B. Le codage s'effectuant paquet par paquet, il n'existe aucune limite concernant le nombre de paquets contenu dans le fichier source.

  • Inconvénients

Le codeur TM possède des inconvénients:

  • Format des données d'entrée uniquement Annex-B
  • Pas d'envoi des données sources (uniquement de la redondance)
  • Possibilités d'optimisation


Face à ces problèmes, nous proposons des solutions:

  • Possiblité de rendre ce codeur compatible avec le format RTP pour les données d'entrée
  • Pour une meilleur comparaison de ce codeur avec le codeur Reed-Salomon, il serait intéressant que le codeur recopie les paquets média dans le fichier de sortie (techniquement, avec un Payload inférieur à 127)
  • Nous avons procédé à une optimisation du codeur TM lors de l'implémentation (libération de pointeurs d'objet non utilisés). Il reste certainement des optimisations possibles.


Décodeur Transformation Mojette

Le décodeur TM utilise les propriétés de la Transformation Mojette Inverse. Il ne fonctionne que partiellement dans notre application. Pour faute de temps, nous n'avons pas pu résoudre des problèmes liés au décodage. Ce décodeur n'a donc pas pu être testé et comparé au décodeur Reed-Salomon. Il reste donc une partie du travail à effectuer sur le plan de l'implémentation.

Nous allons tout de même voir dans cette partie les ajouts de notre travail ainsi que ce qu'il reste à faire. Le schéma de fonctionnement du décodeur TM décrit les grandes phases du décodage.


Fonctionnement du décodeur utilisant la Transformation Mojette



Ce décodeur requière des données d'entrée au format RTP. La première étape du décodage est de désencapsuler les paquets RTP et d'analyser l'en-tête de chaque projection\footnote{Rappel: Une seule projection par paquet RTP. Le décodeur stocke les projections permettant de reconstruire un paquet Annex-B source.

Lorsque le paquet lu posséde un NALU\footnote{NALU: Numéro de l'unité Network Abstraction Layer(NAL) différent des paquets stockés dans la mémoire tampon (Buffer), le décodeur vérifie qu'il possède assez de projections et procéde au décodage (si l'opération est possible). Dans le cas ou le décodage ne peut pas s'effectuer, un message d'erreur est affiché sur la sortie standart.

Le décodage n'est possible que si le nombre de projections reçues est supérieur ou égale au minimum de la hauteur ou de la largeur de la matrice contenant les données sources. Lorsque le décodage est terminé, l'information restituée est écrite dans le fichier destination au format Annex-B (du fait que le codeur travaille sur des données d'entrée au format Annex-B).

Actuellement, la fonction de décodage désencapsule l'en-tête RTP, procéde à la vérification des conditions minimum pour le décodage et décode l'information lorsque s'est possible. Notre programme ne gére pas l'écriture de l'information décodée dans le fichier de sortie.

  • Conditions de décodage

L'étape de décodage impose que le flux de données d'entrée soit au format RTP. La contrainte majeure pour procéder au décodage est que l'on recoive au minimum un nombre de projections N supérieur ou égale au minimum de valeur de la hauteur h ou de la largeur l de la matrice des données sources. [ N > min(h,l) ]

Lorsque cette régle n'est pas respectée, le décodage de information n'est pas possible.

  • Inconvénients

Le décodeur TM possède des inconvénients:

  • Format de sortie uniquement Annex-B
  • Ne fonctionne pas


Nous proposons diverses solutions:

  • L'application pourrait redonner l'information selon deux formats de sortie: RTP et Annex-B
  • Pour que le décodage fonctionne, il est nécessaire d'implémenter une méthode nommée << writeAnnexbPacket() >>. Cette méthode serait appellée par la fonction << demojettizeData() >> de la bibliothèque qui permet de décoder les données reçues.


Tentative d'implémentation d'un troisième code

Durant la phase d'implémentation, nous nous sommes apperçus qu'il n'était pas possible d'implémenter un code Raptor. Nous avons donc réfléchi et cherché des informations sur d'autres codes tel que Reed-Salomon utilisant la matrice de Vandermonde ou les codes Turbo.

Codes Raptors

Initialement prévu lors de notre premier rapport, nous avions choisi d'implémenter un code Raptor pour comparer la Transformation Mojette à un deuxième code (le premier étant le code Reed-Salomon).

Nous nous sommes aperçus durant nos recherches d'une bibliothèque libre qu'il n'existait pas de telles bibliothèques pour ces codes. En prenant contact par courrier électronique avec l'inventeur des codes Raptors Mohammad Amin Shokrollahi, nous avons constaté qu'il existait une bibliothèque mais qu'elle n'était pas libre. Elle appartient à la société Digital Fountain\footnote{Digital Fountain: Société californienne principale utilisatrice des codes Raptors.

En contactant par la suite cette socièté, nous n'avons pas obtenus de réponses favorables à notre demande d'utilisation de cette bibliothèque. Nous nous sommes alors orientés vers l'implémentation d'un nouveau code.

Codes Turbo

Suite à notre échec face aux codes Raptors, nous avons décidé de nous orienter vers les codes Turbo inventés par un labortatoire de recherche français basé en Bretagne. Ces codes ont la particularité d'utiliser une combinaison de deux codes correcteurs d'erreurs comme les codes Raptors. Ils ressemblent de près aux codes Raptors ce qui a attiré notre attention.

Nous avons trouvé une bibliothèque libre pour ces codes. Cette bibliothèque était trop conséquente et nous ne sommes pas parvenus à comprendre son fonctionnement avant la fin de notre projet. En parallèle de cette recherche, nous nous sommes intéressés à une autre bibliothèque qui permettait l'implémentation d'un code Reed-Salomon utilisant la matrice de Vandermonde que Benoît Parrein nous avait fournie.

Reed-Salomon utilisant la matrice de Vandermonde

Nous ne sommes pas parvenus à comprendre le fonctionnement de cette bibliothèque libre dans le temps accordé à ce projet. Cette bibiothèque est moins intuitive que celle des codes Reed-Salomon utilisant la matrice de Cauchy que nous avons implémentée.

Conclusion

Les différentes voies vers lesquelles nous nous sommes orientées ne nous ont pas permises de choisir et d'implémenter un troisième code correcteur d'erreurs. L'un des défauts de notre projet est que nous n'avons pas assez insistés sur la conception ce qui nous a mené à des erreurs. Principalement, nous aurions dû nous renseigner quant à la faisabilité d'implémentation des codes Raptors.

Résumé des caractéristiques

Voici deux tableaux résumant les caractéristiques du programme réalisé :

Code Reed-Salomon Code Transformation Mojette
Utilisable Oui Oui
Format d'entrée codeur RTP Annex-B
Format de sortie codeur RTP RTP
Recopie des paquets médias Oui Non
Type de codage Par lot de paquets Paquet par paquet
Taille des paquets sources Variable Variable
Taille des paquets de redondance générés Fixe Variable
Type de protection Protecion égale contre les erreurs Protection inégale contre les erreurs

Tableau comparatif des codeurs Reed-Salomon et Transformation Mojette

Code Reed-Salomon Code Transformation Mojette
Utilisable Oui Non
Format d'entrée décodeur RTP RTP
Format de sortie décodeur RTP Annex-B
Limites du décodage P reçu >= N Proj reçues >= min(h,l)

Tableau comparatif des décodeurs Reed-Salomon et Transformation Mojette

Simulateur de pertes

Une partie de notre projet a été de mettre en place un simulateur de perte de paquets. Cette opération a pour but de mettre en place des tests pour vérifier l'efficacité et le bon fonctionnement de nos codes. Nous avons décidé de réutiliser le simulateur RTPloss fourni avec le code source du codeur vidéo H264/AVC. Cet outil permet de supprimer des paquets RTP dans un fichier binaire fourni en paramètre. Un nombre aléatoire de paquets est supprimé en fonction d'une valeur passée en argument de la ligne de commande indiquant le taux de pertes voulu en pourcentage. Nous présentons dans ce chapitre le fonctionnement du simulateur de pertes RTPloss puis les modifications que nous avons effectuées.

Fonctionnement de RTPloss

RTPloss est un outil livré avec le codeur H264/AVC que nous avons utilisé lors de nos tests. Ce programme est utilisé en ligne de commande de cette manière:

rtploss.exe fichierSource fichierDestination 10

Le premier paramètre est le nom du fichier source sur lequel les pertes de paquets RTP vont être effectuées. Le deuxième argument spécifie le nom du fichier destination dans lequel le programme recopie les paquets RTP qui n'ont pas été effacés. Le dernier argument est un nombre compris en 0 et 100 qui indique le pourcentage de pertes aléatoire à effectuer sur le fichier source.


Fonctionnement du simulateur de pertes RTPloss



Dans cet exemple, << fichierSource >> est le fichier source sur lequel 10\% de pertes aléatoires vont être effectuées. << fichierDestination >> est le nom du fichier de sortie qui contient les paquets RTP qui n'ont pas été supprimés par le programme. Le numéro de chaque paquet RTP supprimé est affiché dans la sortie standard.

Modification de RTPloss

Pour nos tests, nous avons repris et modifié le fonctionnement de RTPloss. Nous avons donc créé un nouveau simulateur permettant d'appliquer une perte maximale à un fichier codé par RS Cauchy. Ce simulateur se nomme: BobohaLoss.

  • BobohaLoss

Ce simulateur fonctionne de la façon suivante :

bobohaLoss.exe <fichier d'entrée> <fichier de sortie> <taille d'un cycle> <paquets à supprimer en début de cycle> <paquets à supprimer en fin de cycle>

Il n'y a donc plus de facteur aléatoire mais par exemple pour un codage Reed-Salomon de type 20/30 (pour 20 paquets media, génération de 10 paquets FEC), il nous est possible de supprimer 10 paquets tous les 30 grâce à ce simulateur en exécutant la ligne de commande suivante:

bobohaLoss.exe fichierSrc fichierDest 30 5 5

Cet exemple permettra de supprimer les 5 premiers paquets média et les 5 derniers paquets FEC d'un lot de 30 paquets. Il est important de connaître le nombre de paquets traités par le codeur (30).

Organisation

Ce chapitre présente les grandes étapes de cette période d'implémentation. Nous nous sommes accordés des temps de réflexion pour effectuer des choix et prendre des décisions. Le travail s'est effectué parfois en binôme et d'autre fois nous avons parallélisé certaines tâches. Globalement, nous pouvons divisé cette période en deux phases:

  • phase d'implémentation
  • phase de test


Les phases d'implémentation

Dans le temps qui a suivi la rédaction de notre premier rapport et la préparation de notre présentation, nous nous sommes intéressés à l'environnement de travail de ce projet.

  • Environnement de travail

Nous avons utilisé les systèmes d'exploitation Windows XP et Windows Vista et l'environnement de travail de Microsoft: Visual Studio 2008. Ce choix est dû au fait que nous n'avions jamais utilisé ce cadre de travail pour nos précédents projets et nous souhaitions le découvrir.

  • Serveur de versions?

Ce projet s'est effectué en binôme et nous souhaitions travailler selon la méthode Extreme programming \cite{extProg ainsi nous avons fait le choix de ne pas utiliser de serveur de versions. Le choix de travailler selon la méthode Extreme programming s'explique par le fait que nous voulions être réactifs face aux changements de l'environnement et des besoins du client.

  • Début d'implémentation

Nous avons commencé par implémenter le code Reed-Salomon en utilisant une bibliothèque libre que nous avions trouvée sur Internet. Ce début d'implémentation s'est avéré être un échec. Benoît Parrein nous a indiqué qu'il existait différents types de bibliothèques pour l'implémentation des codes Reed-Salomon. Notre attention s'est alors portée sur les codes Reed-Salomon par traitement de paquets (exemple: RTP). Nous avons donc changé de bibliothèque et repris le projet depuis le début.

  • Utilisation de la bibliothèque de Benoît Parrein

Lors de notre première soutenance, Benoît Parrein nous a conseillé de changer de bibliothèque. Il nous proposa deux bibliothèques pour les codes Reed-Salomon par traitement de paquets:

  • CauchyCode (matrice de Cauchy)
  • Vandermonde (matrice de Vandermonde)

Nous avons choisi d'implémenter le code Reed-Salomon utilisant la matrice de Cauchy. Cette bibliothèque nous facilita le travail en nous fournissant des fonctions de base telles que le codage et le décodage de flots de paquets. Notre travail consista à créer des méthodes qui permettent de lire des paquets RTP provenant d'un fichier binaire pour ensuite les présenter à la fonction de codage de la bibliothèque.

En sortie du codeur, les fonctions ajoutées permettent d'écrire des paquets RTP dans un fichier de sortie. Certains paquets contiennent de la redondance (paquet FEC) et d'autres sont identiques aux paquets sources (paquets média). L'étape suivante fut de reprendre ces fonctions pour les rendre utilisable dans les fonctions de décodage. Ces étapes se sont réalisées à deux sans division du travail.

  • Implémentation de la Transformation Mojette

L'un de nous continua en implémentant la Transformation Mojette. L'autre continua à ressoudre les problèmes détectés lors des tests. En relation avec Fadi Boulos, nous avions décidé de commencer l'implémentation de la Transformation Mojette. Le travail consista à réutiliser la bibliothèque fournie en modifiant des fonctions de manière à encapsuler les données de sortie du codeur dans des paquets RTP.

  • Tentative d'un troisième codeur/décodeur

Lorsque les tests du code Reed-Salomon se sont terminés, nous avons cherché un troisième code correcteur d'erreurs que nous pourrions implémenter. Lors de la conception, nous souhaitions implémenter un code Raptor mais ce ne fut pas possible car il n'existait pas de bibliothèque libre. Nous nous sommes alors intéressés aux codes Turbo (très similaires aux codes Raptors). Pour des problèmes d'incompréhension des bibliothèques trouvées, nous avons décidé d'abandonner cette voie en nous consacrant à la phase de tests des éléments implémentés. Ce même choix fut effectué lorsque nous avons tenté de comprendre la deuxième bibliothèque des codes Reed-Salomon utilisant la matrice de Vandermonde.

Les phases de tests

  • Tests Reed-Salomon

Lorsque le codeur et le décodeur Reed-Salomon fonctionnèrent, nous avons choisi de continuer en effectuant des tests de performance. Ces tests se sont avérés négatifs et nous ont amené à faire des changements et des réparations. Les erreurs étaient dûes à des cas non-gérer par nos tests dans le code ou des sorties de boucles non-prévues. La plupart des erreurs étaient des cas non-déterminer lors de la conception. Notre conception n'était donc pas suffisante et s'avèrait être l'un des points négatifs de notre travail.

Durant cette phase, nous avons utilisé des outils tels que RTPdump, FC, HexEdit... RTPdump nous a permi de lire les fichiers binaires contenant les paquets RTP et de vérifier que les en-têtes de paquet étaient correctes. FC est une commande Windows qui permet de comparer deux fichiers binaires octet à octet. D'autres outils sont présentés en annexe de ce rapport.

  • Tests Transformation Mojette

Le décodeur TM n'étant pas fini, nous n'avons pas pû effectuer les même tests que pour le code Reed-Salomon. Néanmoins, nous avons testé le codeur qui fonctionne et transforme un paquet Annex-B en plusieurs projections encapsulées dans des paquets RTP. Ces tests sont expliqués en détail dans le chapitre suivant.

  • Mesures comparatives

Notre objectif principal était de comparer les performances du code Transformation Mojette à deux autres codes correcteurs d'erreurs. Nous avons finalement comparé les codeurs Reed-Salomon et Transformation Mojette. La partie suivante présente les tests et mesures que nous avons effectué.

Tests et résultats

Cette partie présente les tests et les mesures que nous avons effectué sur les deux codes correcteurs que nous avons implémentés: Reed-Salomon et Transformation Mojette. Le but de cette étude est de dégager les avantages et les inconvénients de chacun des codes. Une première partie présente les mesures que nous avons conçus. La deuxième partie partie présente les résultats de ces tests sous la forme de tableaux comparatif.

Présentation des mesures

Nous avons mesurer les informations pertinantes permetants de comparer les deux codeurs. Nous avons donc le nombre d'opérations CPU necessaire pour coder, décoder sans pertes et avec pertes. Nous avons également mesuré le temps de codage, décodage sans pertes et avec pertes. La moyenne de ces mesures par paquet est pertinente.

La mesure du nombre d'opération CPU, n'est pas une mesure fiable. Il est intéressant d'en étailler les différentes raisons :

  • Une seule mesure n'est pas fiable, une grande majorité des logiciels de test de performance appellent plusieurs fois la même fonction pour ensuite garder la valeur moyenne.
  • Le compteur de cycle CPU continue d'augmenter même si le programme est en pause puisque le système d'exploitation peut devoir traiter des interruptions (arrivé d'un paquet, action sur son interface homme machine...) ou encore un programme concurrent s'exécute. Ce problemme n'affectera cependant que très peu la mesure moyenne d'une fonction rapide qui ne subira probablement pas d'interuption.
  • Le problème des processeurs double coeur ou encore des machines multi-processeur se pose également puisqu'il y aura un compteur de cycle par unité de calcul. Un programme pouvant commencer son exécution sur une unité et finir sur une autre va voir son compteur de cycle CPU changé.
  • Il existe de plus en plus de systèmes capable de réduire leur consommation électrique en réduisant la vitesse du CPU. Cependant la vitesse du compteur du nombre d'opérations ne change pas. Heureusement lors du codage ou du décodage, aucune éconnomie d'énergie n'est possible puisque l'unité de contrôle est utilisée à 100\%.


Ayant fait les tests sous Microsoft Windows, nous avons utisés une bibliothèque Windows : QueryPerformance\cite{QueryPerformance, cette bibliothèque permet de connaître le compteur CPU et donc d'avoir une approximation du nombre d'opérations CPU "consommées" par une fonction.

La mesure du temps s'est faite en utilisant la bibliothèque Windows : GetSystemTimeAsFileTime\cite{GetSystemTimeAsFileTime. Cette bibliothèque permet d'avoir un compteur de temps avec une précision de l'ordre de la nanoseconde. On peut donc calculer le temps mis par une fonction à s'exécuter.

Résultats des tests

Lors de nos différents tests, nous avons pu comparer les codeurs Reed-Salomon et Transformation Mojette.

Code RS Code TM Comparaison TM / RS
Paquets Média
Nombre de paquets 6891 6970
Taille du fichier d'entrée 9MB (9513kB) 9MB (9770kB)
Taille moyenne d'un paquet 1413B 1401B
Paquets FEC
Nombre de paquets 3450 48509
Taille du fichier de sortie 13MB (14553kB) 12MB (13398kB)
Taille moyenne d'un paquet 1496B 276B
Temps
Temps moyen par paquet média (ms) 0,21 1,61 -7 fois
Temps total (s) 1,43 11,2 -8 fois
Cycles d'horloge CPU\footnote{CPU: Central Processing Unit, unité centrale de traitement.
Moyenne par paquet média 506 5738 -11 fois
Total (M) 3M 39M -13 fois
Efficacité du code (Code Rate) 0.65 0.82

Résultats des codeurs des codeurs Reed-Salomon et Transformation Mojette

Code RS Code TM
sans pertes avec pertes* sans pertes avec pertes*
Paquets Média
Nombre de paquets décodés 6891 6891 6968 6968
Nombre de paquets non décodés 0 0 0 0
Taux de décodage 100\% 100\% 100\% 100\%
Temps
Temps moyen par paquet média décodés (ms) 0,068 0,206 0,078** 0,078**
Temps total (s) 0,47 1,42 0,55** 0,55**
Cycles d'horloge CPU***
Moyenne par paquet média 244 735 286** 286**
Total (M) 1,7 5 2** 2**
*Le taux de perte simulé est maximal.
**Le décodage TM n'est pas pris en compte.
***CPU: Central Processing Unit, unité centrale de traitement.

Résultats des décodeurs Reed-Salomon et Transformation Mojette

Conclusion

Notre étude nous permet non seulement de comparer les performances de chacun des codes lorsque aucune perte n'est simulée mais également lorsque qu'une perte maximale est simulée. Pour la partie codage, on voit clairement que le codage de TM est environ dix fois (Voir le tableau de la partie précédente) plus couteux que celui de Cauchy. Cette lenteur peut être problématique sur un flux que l'on doit protéger en temps réel, cependant le codeur TM peut être amélioré. De plus, le codeur TM effectue une protection inégale (UEP\footnote{UEP: Unequal Error Protection, Protection inégale contre les erreurs) des données ce qui représente un coût de calcul supplémentaire. Pour le décodage, nous n'avons pas réussi à implémenter le décodeur TM ; le coût du décodage n'est donc pas calculable. Cependant la sortie du codeur TM envoyant beaucoup de petits paquets (les projections), offre une plus grande résistance aux pertes. D'autre part, le décodeur TM devrait être moins coûteux que le codage.

Conclusions

Ce dernier chapitre présente les conclusions de ce rapport. Une première partie présente un bilan général de la gestion de ce projet et les réponses à la problématique dégagée lors du premier rapport. La seconde partie présente les conclusions personnelles et les apports de ce projet pour notre binôme.

Bilan du projet

Ce projet a contribué à l'évaluation du code correcteur d'erreurs construit en utilsant la Transformation Mojette. Il se proposait de comparer sur plusieurs points le code Transformation Mojette à d'autres codes correcteurs d'erreurs actuellement utilisé dans les domaines de la transmission sur canal avec perte. Nous avons pu comparer le code TM avec le code Reed-Salomon. Nous nous sommes aperçus que le code TM utilisé lors de notre projet est moins performant que le code Reed-Salomon si on se référe aux tests présentés dans le chapitre prédédent (~\ref{chap:Tests et résultats).

Notre conclusion est que le code Transformation Mojette n'est pas, comparé au code Reed-Salomon, le plus performant. Ce résultat peut être expliqué par le fait que les codes ne fonctionnent pas de la même façon. Reed-Salomon recopie les paquets média et ajoute de la redondance tandis que le code TM ne génére que des nouvelles informations (les projections). Notre implémentation de chacun des codes n'est peut être pas la plus optimale ce qui expliquerait ces résultats.

Pour une grande fiabilité, il serait intéressant de comparer la Transformation Mojette à d'autres codes correcteurs (plus que le code Reed-Salomon) et étudier les résultats obtenus. Ce projet est donc une ouverture sur un futur projet qui permettrait une meilleure comparaison possible.

Conclusions personnelles

  • Benoît Farré

Ce projet m'a beaucoup apporté sur le plan technique. J'ai découvert plus précisément le langage C++ ainsi que l'environnement de travail Visual Studio de Microsoft. L'organisation est un élément important dans la gestion de projet comme nous l'avons revu dans ce projet. Nous avons appris à partager nos méthode de travail car nous n'avions jamais réalisé de projet ensemble. L'aide du Laboratoire IRCCyN a permis en grande partie de réaliser dans de bonnes conditions ce projet de recherche et développement. Je retiends aussi que la lecture de document en anglais reste un élément non-négligeable dans l'amélioration de l'anglais technique.

  • Romain Rüdiger

Sur le plan relationnel, j'ai amélioré ma capacité de travail en équipe. D'autre part, j'ai pu, grâce à ce projet, améliorer mon expérience technique en C++. Travailler sur un projet de recherche et développement permet de créer quelque chose de nouveau mais aussi d'améliorer son anglais technique lors de la lecture d'articles scientifiques.

Annexes

En-tête RTP

En-tête de paquet RTP utilisé dans notre application


En-tête des projections en Transformation Mojette

En-tête des projections en Transformation Mojette


HexEdit

HexEdit est un logiciel utilisé pour comparer deux fichiers binaires. Chaque fichier est présenté au format hexadécimal. Il est ainsi plus facile de comparer octet par octet visuellement les deux fichiers. Ce logiciel est disponible sur Internet: http://www.megagiciel.com/logiciels/fiches/logi4467.html.

RTPdump

RTPdump est un programme livré avec le codeur H264/AVC que nous avons utilisé en tant que codeur source pour nos vidéos de test. Ce logiciel permet d'afficher sur la sortie standard les en-têtes de paquet RTP contenus dans le fichier source. Le code source de ce logiciel nous a permi de comprendre le fonctionnement de la lecture des fichiers binaires et des paquets RTP. Nous avons réutilisé plusieurs de ces principes dans notre application.

H264/AVC

H264/AVC est un codeur vidéo de dernière génération. Il permet d'encoder des vidéos au format YUV en fichier binaire contenant des paquets RTP ou Annex-B. Il est disponible sur Internet: http://iphome.hhi.de/suehring/tml/.

Revenir sur la page d'accueil du projet.