Codes AL-FEC hautes performances pour les canaux à effacements : variations autour des codes LDPC

Version du 30 juin 2010Content distribution systems are developping quickly. In these systems, in addition to the traditionnal information corruptions, arises the problem of packet losses. The need of reliability in this context has lead to the emergence of erasure correcting codes. Thanks to the addition of redundant information, they are able to recover the lost information. In this thesis we address the problem of designing erasure codes having good correction capabilities while having a complexity enabling to reach high throughput. For this, we have chosen to work jointly on the codes and there implementations inside a software codec, and more specificaly on the decoding algorithms. The first part of our work shows that solutions based on Low Density Parity Check (LDPC) codes enable us to get excellent results. In particular, when these codes are decoded with an hybrid Iterative (IT)/Maximum Likelihood (ML) decoder, that enables to obtain correction capabilities close to the optimal whilst keeping an acceptable complexity. Furthemore, we show that thanks to the use of structured LDPC codes, the complexity of the ML decoding can be largely reduced. We then sudy the design of schemes combining both erasure correction and cryptographic features. These systems allow to reduce the global complexity while keeping a high security level. Finaly, we present a fault tolerant scheme for matrix multiplication, based on error correcting codes. This approach allows to build a distributed system on P2P platforms that can tolerate efficiently fail stop and malicious errors.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