Ce travail est consacré à la conception, l'analyse et l'optimisation des codes correcteurs d'effacements de niveau applicatif (AL-FEC). Nous nous intéressons à une famille des codes LDPC généralisés (GLDPC), nommés les codes GLDPC-Staircase, qui sont composé d'un code LDPC-Staircase code de base ainsi que des codes Reed-Solomon (RS) (codes externes). Dans la première partie de cette thèse, nous commençons par montrer que les codes RS ayant une construction basée sur la matrice "quasi" Hankel sont les codes MDS les plus appropriés pour obtenir la structure des codes GLDPC-Staircase. Ensuite, nous proposons un nouveau type de décodage à ces codes, baptisé décodage hybride (IT/RS/ML), pour atteindre les capacités de correction du décodage par maximum de vraisemblance (ML) avec de faible complexité. Afin d'étudier l'impact de la structure des codes GLDPC-Staircase sur le décodage, nous proposons une autre construction : ils diffèrent sur la nature des symboles de redondance LDPC générés. Puis, pour prédire le seuil de décodage et les écarts par rapport à la limite de Shannon des codes GLDPC-Staircase, nous élaborons une analyse asymptotique en fonction de la technique d'évolution de densité (DE), les technique EXIT (Extrinsic Information Transfer) et la théorème d'air. Finalement, en se basant sur l'analyse à taille finie et l'analyse asymptotique, nous réglons les importants paramètres internes de ces codes pour obtenir la configuration optimale sous le décodage hybride (IT/RS/ML). La deuxième partie de la thèse est consacrée à l'étude des codes GLDPC-Staircase dans diverses situations. Tout d'abord, nous montrons que ces codes ont des performances asymptotiquement très proches des limites théoriques de Shannon. En plus, à taille fini, ils permettent d'atteindre d'excellentes capacités de correction d'effacements (i.e., très proches de celle des codes MDS idéal) peu importe la taille des objets : très faible overhead de décodage, faible plancher d'erreur, et une zone ``waterfull'' raide. Nous montrons aussi que ces codes surpassent les codes Raptor, les codes LDPC-Staircase, et un autre code GLDPC avec une construction differente. Finallement, nous proposons une méthodologie générale pour régler le problème de l'impact de l'ordonnancement des paquets sur les performance des codes GLDPC-Staircase sur un grand nombre des canaux à effacements (avec perte en rafale ou pas). Cette étude montre le meilleur ordonnancement de paquets. Tous les résultats mentionnés ci-dessus montrent que les codes GLDPC-Staircase peuvent considérés comme des codes FEC de niveau applicatif (AL-FEC) universelle. / This work is dedicated to the design, analysis and optimization of Application-Level Forward Erasure Correction (AL-FEC) codes. In particular, we explore a class of Gen- eralized LDPC (GLDPC) codes, named GLDPC-Staircase codes, involving the LDPC- Staircase code (base code) as well as Reed-Solomon (RS) codes (outer codes). In the first part of this thesis, we start by showing that RS codes having “quasi” Han- kel matrix-based construction are the most suitable MDS codes to obtain the structure of GLDPC-Staircase codes. Then, we propose a new decoding type, so-called hybrid (IT/RS/ML) decoding, for these codes to achieve Maximum Likelihood (ML) correction capabilities with a lower complexity. To investigate the impact of the structure of GLDPC- Staircase codes on decoding, we propose another construction: they differ on the nature of generated LDPC repair symbols. Afterwards, to predict the capacity approaching GLDPC- Staircase codes, we derive an asymptotic analysis based on DE, EXIT functions, and area theorem. Eventually, based on finite length analysis and asymptotic analysis, we tune important internal parameters of GLDPC-Staircase codes to obtain the best configuration under hybrid (IT/RS/ML) decoding. The second part of the thesis benchmarks GLDPC-Staircase codes in various situations. First, we show that these codes are asymptotically quite close to Shannon limit performance and achieve finite length excellent erasure correction capabilities very close to that of ideal MDS codes no matter the objects size: very small decoding overhead, low error floor, and steep waterfall region. Second, we show that these codes outperform Raptor codes, LDPC- Staircase codes, other construction of GLDPC codes, and have correction capabilities close to that of RaptorQ codes. Last but not least, we propose a general-methodology to address the problem of the impact of packet scheduling on GLDPC-Staircase codes for a large set of loss channels (with burst loss or not). This study shows the best packet scheduling. All the aforementioned results make GLDPC-Staircase codes an ubiquitous Application-Level FEC (AL-FEC) solution.

L’objectif de la thèse est l’étude des codes correcteurs d’erreurs au niveau applicatif (Application Layer – Forward Error Correction, ou AL-FEC) pour les communications par satellite. Dans ce contexte, pendant les deux première années de thèse, nous avons proposé de nouvelles méthodes d’analyse, de construction et d’optimisation des codes à effacements définis par des matrices de parité à faible densité (code LDPC, pour « Low Density Parity Check » en anglais). La troisième année de la thèse a été consacrée à : (1) La suite des études portant sur de nouvelles méthodes de construction des codes LDPC non-binaires. D’une part, nous avons développé un nouvel algorithme (Scheduled-PEG) qui permet d’optimiser la construction des codes LDPC non-binaires pas rapport aux métriques de performance spécifiques à la couche application, notamment dans le cadre des systèmes de diffusion de contenu (broadcasting). D’autre part, nous avons proposé une nouvelle méthode de construction de codes à faible rendement, qui utilise l’image binaire étendue d’un code LDPC non-binaire. Ces études ont fait l’objet de deux publications dans deux conférences internationales : (a) “Scheduled-PEG construction of LDPC codes for Upper-Layer FEC”, International Workshop on Coding and Cryptography, April 2011, Paris, France. (b) “Extended Non-Binary Low-Density Parity-Check Codes over Erase Channels”, IEEE International Symposium on Wireless Communication Systems, November 2011, Aachen, Germany. (2) Une étude portant sur l’analyse asymptotique de codes cluster-LDPC non-binaires. Cette nouvelle classe de codes – introduite récemment (ISIT’2011) – se distingue par ses excellentes propriétés en termes de distance minimale. Notre étude a permis de déterminer de manière analytique la capacité de correction des codes cluster-LDPC non-binaires, aussi bien pour le décodage itératif par propagation de croyances (BP, pour « Belief Propagation ») que pour le décodage par maximum de vraisemblance (ML, pour « Maximum Likelihood »). Ces résultats seront intégrés à une publication scientifique sur les codes cluster-LDPC, en cours de rédaction, qui sera soumise à « IEEE Transactions on Information Theory », avant la fin de l’année 2011. (3) Une étude portant sur une méthode de construction des codes LDPC qui permet de réduire de manière significative le plancher d’erreur (« error floor ») du code, sans dégrader ses performances dans la région de « waterfall ». Ainsi, nous avons proposé la structuration de la matrice de parité du code, de manière à intégrer une partie irrégulière, optimisée pour la partie « waterfall », et une partie régulière, qui permet de réduire le plancher d’erreur du code. Cette étude fera l’objet d’une publication dans une conférence internationale (à déterminer), à soumettre début 2012. / The advent of content distribution, IPTV, video-on-demand and other similar services accelerate the demand for reliable data transmission over highly heterogeneous networks and toward terminals potentially heterogeneous too. In this context, Forward Error Correction (FEC) codes that operate at the transport or the Application Layer (AL-FEC) are used in conjunction with the FEC codes implemented at the physical layer, in order to improve the overall performance of the communication system. AL-FEC codes are aimed at recovering erased data packets and they are essential in many multicast/broadcast environments, no matter the way the information is transported, for instance using a wired or wireless link, and a terrestrial, satellite-based or hybrid infrastructure.This thesis addresses the design of Low Density Parity Check (LDPC) codes for AL-FEC applications. One the one hand, we provide an asymptotical analysis of non-binary LDPC codes over erasure channels, as well as waterfall and error-floor optimization techniques for finite-length codes. On the other hand, new concepts and coding techniques are developed in order to fully exploit the potential of non-binary LDPC codes.The first contribution of this thesis consists of the analysis and optimization of two new ensembles of LDPC codes. First, we have derived the density evolution equations for a very general ensemble of non-binary LDPC codes with rank-deficient coefficients. This allows improving the code performance, as well as designing ensembles of LDPC codes that can be punctured in an effective manner. The second approach allows the asymptotical optimization of a particular ensemble of LDPC codes, while ensuring low error-floors at finite lengths.The second contribution is the construction of finite length LDPC codes with good waterfall and error floor performance. Two approaches were investigated, according to the metric used to evaluate the code. The “Scheduled” Progressive Edge Growth (SPEG) algorithm is proposed, in order to optimize the waterfall performance of the code. Another method is proposed which consists in optimizing a specific structure of the parity check matrix. This approach gives low error-floors.The third contribution investigates a new technique of rate adaptability for non-binary LDPC codes. We propose a new method to generate “on-the-fly” incremental redundancy, which allows designing codes with flexible coding rates, in order to cope with severe channel conditions or to enable Fountain-like distribution applications.The fourth contribution focuses on a new class of LDPC codes, called non-binary cluster-LDPC codes. We derive exact equations of the density evolution for the iterative decoding and an upper bound for the maximum-likelihood decoding.Finally, we propose a practical solution to the problem of reliable communication via satellite to high-speed trains. Here, the challenge is that obstacles present along the track regularly interrupt the communication. Our solution offers optimal performance with a minimum amount of redundancy.

One of the most important emerging aspects of Third Generation Partnership Project (3GPP) is the Multimedia Broadcast/Multicast Service (MBMS) aiming to deliver multimedia contents to mobile users more efficiently in point-to-multipoint way. 3GPP also recommends an Application Layer Forward Error Correction (AL-FEC) scheme, especially for MBMS, in order to provide reliable transmission over mobile networks. Due to many emerging FEC schemes, the existing 3GPP standardized systematic fountain Raptor code FEC scheme is considered to be outdated. One of the newly emerged codes, namely RaptorQ, has enhanced an AL-FEC scheme by providing higher protection against packet loss and superior flexibility to meet the growing demand in mobile multicast services. In this work, we provide an extensive device based performance evaluation of RaptorQ FEC codes, specified as RFC 6330 in Internet Engineering Task Force (IETF), and notice that the performance always outperforms that of the existing Raptor (RFC 5053) codes in terms of decoding speed, latency and memory. We also include the device based performance comparison of RaptorQ FEC codes in a comparison with other FEC schemes like Supercharged codes and Reed Solomon + Low Density Parity Check codes (RS+ LDPC). Finally, we conduct simulation carried out in the mobile devices for several network parameters like latency, decoding speed and memory in combination with FEC encoding and decoding parameters and investigate that RaptorQ is the best code that suits multicast services. / +46723185198, +4917626686238,+4915166808450

Este trabajo de tesis presenta los servicios de descarga de contenido en modo push como un mecanismo eficiente para el envío de contenido de televisión pre-producido sobre redes de difusión. Hoy en día, los operadores de red dedican una cantidad considerable de recursos de red a la entrega en vivo de contenido televisivo, tanto sobre redes de difusión como sobre conexiones unidireccionales. Esta oferta de servicios responde únicamente a requisitos comerciales: disponer de los contenidos televisivos en cualquier momento y lugar. Sin embargo, desde un punto de vista estrictamente académico, el envío en vivo es únicamente un requerimiento para el contenido en vivo, no para contenidos que ya han sido producidos con anterioridad a su emisión. Más aún, la difusión es solo eficiente cuando el contenido es suficientemente popular. Los servicios bajo estudio en esta tesis utilizan capacidad residual en redes de difusión para enviar contenido pre-producido para que se almacene en los equipos de usuario. La propuesta se justifica únicamente por su eficiencia. Por un lado, genera valor de recursos de red que no se aprovecharían de otra manera. Por otro lado, realiza la entrega de contenidos pre-producidos y populares de la manera más eficiente: sobre servicios de descarga de contenidos en difusión. Los resultados incluyen modelos para la popularidad y la duración de contenidos, valiosos para cualquier trabajo de investigación basados en la entrega de contenidos televisivos. Además, la tesis evalúa la capacidad residual disponible en redes de difusión, por medio de estudios empíricos. Después, estos resultados son utilizados en simulaciones que evalúan las prestaciones de los servicios propuestos en escenarios diferentes y para aplicaciones diferentes. La evaluación demuestra que este tipo de servicios son un recurso muy útil para la entrega de contenido televisivo. / This thesis dissertation presents background push Content Download Services as an efficient mechanism to deliver pre-produced television content through existing broadcast networks. Nowadays, network operators dedicate a considerable amount of network resources to live streaming live, through both broadcast and unicast connections. This service offering responds solely to commercial requirements: Content must be available anytime and anywhere. However, from a strictly academic point of view, live streaming is only a requirement for live content and not for pre-produced content. Moreover, broadcasting is only efficient when the content is sufficiently popular. The services under study in this thesis use residual capacity in broadcast networks to push popular, pre-produced content to storage capacity in customer premises equipment. The proposal responds only to efficiency requirements. On one hand, it creates value from network resources otherwise unused. On the other hand, it delivers popular pre-produced content in the most efficient way: through broadcast download services. The results include models for the popularity and the duration of television content, valuable for any research work dealing with file-based delivery of television content. Later, the thesis evaluates the residual capacity available in broadcast networks through empirical studies. These results are used in simulations to evaluate the performance of background push content download services in different scenarios and for different applications. The evaluation proves that this kind of services can become a great asset for the delivery of television content / Fraile Gil, F. (2013). Evaluation of unidirectional background push content download services for the delivery of television programs [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/31656

Ce travail est consacré à la conception, l'analyse et l'optimisation des codes correcteurs d'effacements de niveau applicatif (AL-FEC). Nous nous intéressons à une famille des codes LDPC généralisés (GLDPC), nommés les codes GLDPC-Staircase, qui sont com- posés d'un code LDPC-Staircase (code de base) ainsi que des codes Reed-Solomon (RS) (codes externes). Dans la première partie de cette thèse, nous commençons par montrer que les codes RS ayant une construction basée sur la matrice "quasi" Hankel sont les codes MDS les plus appropriés pour obtenir la structure des codes GLDPC-Staircase. Ensuite, nous proposons un nouveau type de décodage à ces codes, baptisé le décodage hybride (IT/RS/ML), pour atteindre les caspacités de correction du décodage par maximum de vraisemblance (ML) avec de faible complexité. Afin d'étudier l'impact de la structure des codes GLDPC- Staircase sur le décodage, nous proposons une autre construction : ils se diffèrent sur la nature des symboles de redondance LDPC générés. Puis, pour prédire le seuil de décodage et les écarts par rapport à la limite de Shannon des codes GLDPC-Staircase, nous élaborons une analyse asymptotique en fonction de la technique d'évolution de densité (DE), la technique EXIT (Extrinsic Information Transfer) et le théorème d'air. Finalement, en se basant sur l'analyse à taille finie et l'analyse asymptotique, nous ajustons les différentes paramètres internes de ces codes pour obtenir la configuration optimale sous le décodage hybride (IT/RS/ML). La deuxième partie de la thèse est consacrée à l'étude des codes GLDPC-Staircase dans diverses situations. Tout d'abord, nous montrons que ces codes ont des performances asymptotiquement très proches de la limite de Shannon. En plus, à taille finie, ils permet- tent d'atteindre d'excellentes capacités de correction d'effacements (i.e., très proches de celles des codes MDS) peu importe la taille des objets : très faible overhead de décodage, faible plancher d'erreur, et une zone "waterfall" raide. Nous montrons aussi que les performances de ces codes sont trés proches des codes RaptorQ et surpassent celles des codes Raptor, les codes LDPC-Staircase, et un autre code GLDPC avec une construction différente. Finalement, nous proposons une méthodologie générale pour étudier l'impact de l'ordonnancement des paquets envoyés sur les performances des codes GLDPC-Staircase sur un grand nombre des canaux à effacements (avec des pertes en rafale ou pas). Cette étude montre le meilleur ordonnancement de paquets. Tous les résultats mentionnés ci-dessus montrent que les codes GLDPC-Staircase peuvent considérés comme des codes AL-FEC universels.

Nous assistons au développement rapide des solutions de diffusion de contenus sur des systèmes, où en plus des traditionnelles corruptions de l'information dans les couches basses, se pose le problème des pertes de paquets d'informations. Le besoin de fiabiliser ces systèmes de transmission a conduit à l'émergence de codes correcteurs d'effacements, qui grâce à l'ajout d'informations redondantes, permettent de reconstruire l'information perdue. Dans cette thèse nous abordons le problème de la conception de codes à effacements ayant de bonnes capacités de correction et dont les algorithmes de décodage possèdent une complexité permettant d'atteindre des débits élevés. Pour cela, nous avons choisi de travailler conjointement sur les codes et sur leur implémentation au sein d'un codec logiciel, et plus particulièrement sur les algorithmes de décodage. La première partie de nos travaux montre que des solutions basées sur les codes “Low-Density Parity-Check” (LDPC) permettent d'obtenir d'excellents résultats. En particulier lorsque ces codes sont décodés avec un décodeur hybride IT/ML qui permet d'obtenir des capacités de corrections proches de l'optimal, tout en conservant une complexité acceptable. De plus, nous montrons que grâce à l'utilisation de codes LDPC structurés la complexité du décodage ML peut être largement réduite. Nous étudions ensuite le développement de systèmes combinant un code à effacements et des fonctionnalités cryptographiques. Les systèmes résultants permettent de réduire la complexité globale du système tout en garantissant un niveau de sécurité élevé. Finalement, nous présentons une technique de tolérance aux fautes basée sur des codes correcteurs pour des applications de multiplications matricielles. Cette technique nous permet de construire un système de calcul distribué sur plateforme P2P tolérant efficacement aussi bien les pannes franches que les erreurs malicieuses.

Esta tesis estudia la distribución de ficheros en redes inalámbricas, analizando diferentes mecanismos que permiten optimizar la transmisión en términos de ancho de banda y calidad de experiencia. Concretamente, la tesis se centra en la transmisión de ficheros en canales multicast. Dicha transmisión resulta adecuada en ciertos entornos y tiene múltiples aplicaciones, algunas de las cuales se presentan en este trabajo. La tesis analiza en profundidad FLUTE (File Delivery over Unidirectional Transport), un protocolo para el envío fiable de ficheros en canales unidireccionales, y presenta algunas propuestas para mejorar la transmisión a través de dicho protocolo. En este sentido, una de las bases de este protocolo es el uso de un mecanismo llamado Tabla de Envío de Ficheros (FDT), que se utiliza para describir los contenidos transmitidos. Este trabajo analiza cómo la transmisión de la FDT afecta al funcionamiento del protocolo FLUTE, y proporciona una metodología para optimizar el envío de contenido mediante FLUTE. Por otro lado, en la transmisión de ficheros por multicast resulta esencial ofrecer un servicio fiable. Entre los distintos mecanismos utilizados por FLUTE para ofrecer fiabilidad, este trabajo analiza principalmente los códigos de corrección AL-FEC (Application Layer ¿ Forward Error Correction), los cuales añaden redundancia a la transmisión para minimizar los efectos de las pérdidas en el canal. Al respecto, esta tesis evalúa los códigos LDPC Staircase y LDPC Triangle, comparando su funcionamiento bajo diferentes condiciones de transmisión. Además, en el caso de tener un canal de retorno, una de las principales contribuciones de esta tesis es la propuesta de códigos LDPC adaptativos para servicios de descarga de ficheros. En esta clase de códigos, el servidor de contenidos cambia dinámicamente la cantidad de protección FEC proporcionada en función de las pérdidas que detectan los usuarios. La evaluación demuestra el buen funcionamiento de estos códigos en distintos entornos. / De Fez Lava, I. (2014). Evaluation of a content download service based on FLUTE and LDPC for improving the Quality of Experience over multicast wireless networks [Tesis doctoral]. Editorial Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/37051 / Premios Extraordinarios de tesis doctorales

Ce document discute de la fourniture de services de diffusion où des contenus de toute nature doivent être transmis efficacement à un ensemble de récepteurs. Plusieurs problèmes se posent : - la robustesse face aux problèmes de transmission, qu'il s'agisse d'erreurs (inversion de bits) ou de pertes (de paquets); - l'efficacité du service fourni, en termes de performances de correction d'erreurs et/ou effacements, et de faible complexité algorithmique; - le respect d'éventuelles contraintes temps réelles de certains contenus; - et enfin le passage à l'échelle lorsque le nombre de récepteur augmente significativement. La problématique est assez large et nous nous "limitons" à deux aspects et composants essentiels que sont : - les codes correcteurs de niveau applicatif, ou AL-FEC, pour le canal à effacements, sans lesquels l'efficacité du service serait fortement compromise, et - les protocoles de transport qui définissent les règles d'échanges d'informations entre soure(s) et récep- teur(s) et garantissent le niveau de fiabilité nécessaire. Tout au long de ce document, nous détaillons ces deux axes et positionnons nos contributions et leur usage effectif dans le panorama actuel.