Faculté informatique et communications IC, Section des systèmes de communication (Laboratoire de théorie des communications LTHC)

Asymptotic and finite-length optimization of LDPC codes

Amraoui, Abdelaziz ; Urbanke, Rüdiger (Dir.)

Thèse sciences Ecole polytechnique fédérale de Lausanne EPFL : 2006 ; no 3558.

Ajouter à la liste personnelle
    Summary
    This thesis addresses the problem of information transmission over noisy channels. In 1993, Berrou, Glavieux and Thitimajshima discovered Turbo-codes. These codes made it possible to achieve a very good performance at low decoding complexity. In hindsight, it was recognized that the underlying principle of using sparse graph codes in conjunction with message-passing decoding was the same as the one proposed in Gallager's remarkable thesis of 1963, although Gallager's work had all but been forgotten in the intervening 30 years. In 1997, there occurred a breakthrough in the analysis of this type of codes. Luby, Mitzenmacher, Shokrollahi, Spielman and Stemann were able to give a complete characterization of the behavior of Low-Density Parity-Check code ensembles in the infinite blocklength case when used over the binary erasure channel. Soon thereafter, Richardson and Urbanke extended their results to binary-input memoryless symmetric channels. In this thesis we present tools to analyze the performance of these types of codes and ways to optimize their parameters. The optimization for the infinite blocklength case is relatively straightforward and we give a simple and efficient method of doing so. However, this does not really solve the problem in practice, since the asymptotic analysis has only limited relevance for the short or moderate blocklengths that are typically used in practice. This brings us to the main objective of this thesis, which is to bridge the gap between the asymptotic case and the practical finite-length case. We follow the lead of Luby et al. by considering the binary erasure channel. We show that the performance of LDPC codes obeys a well-defined scaling law as the blocklength increases. This scaling law refines the asymptotic analysis and provides a good way to understand and approximate the behavior of LDPC codes of short to moderate length. We show how to compute the scaling parameters involved and demonstrate how to use the resulting approximation as a design and optimization tool.
    Résumé
    Cette thèse traite l'analyse des transmissions sur des canaux bruités. En 1993, Berrou, Glavieux et Thitimajshima découvrirent les Turbo-codes qui rendirent possible d'atteindre de très bonnes performances au prix d'une complexité de décodage réduite. A posteriori, il fut reconnu que les principes sous-jacents au fonctionnement des Turbo-codes étaient identiques à ceux introduits par Gallager dans sa thèse en 1963. Ces principes, oubliés entre-temps, reposent sur l'utilisation de codes aux matrices de parité à faible densité en combinaison avec un décodage itératif se basant sur un échange de messages. En 1997, une percée dans l'analyse de ce type de codes permit à Luby, Mitzenmacher, Shokrollahi, Spielman et Stemann de caractériser de façon très précise le comportement des ensembles de codes "Low-Density Parity-Check" de longueur infinie et ce, lors de leur utilisation sur des canaux à effacement. Richardson et Urbanke étendirent ces résultats aux canaux à entrée binaire, sans mémoire et symétriques. Dans cette thèse, nous présentons une analyse de la performance des codes LDPC. Nous commençons par étudier le cas des codes de longueur infinie, pour lequel nous exposons une méthode d'optimisation simple et efficace. Néanmoins, cela ne résout pas complètement le problème, puisqu'en pratique sont utilisés des codes courts ou de longueur moyenne. L'intérêt des résultats obtenus au moyen de l'analyse asymptotique s'en retrouve réduit, ce qui nous amène à l'objectif principal de cette thèse qui est de faire le lien entre le cas asymptotique et le cas pratique de longueur finie. Nous suivons l'approche de Luby et al. en utilisant des canaux à effacement et nous montrons que la performance des codes LDPC suit une loi d'échelle bien définie lorsque la longueur augmente. Ceci nous permet d'affiner l'analyse asymptotique et de mieux comprendre le comportement des codes LDPC courts et de longueur moyenne. Nous expliquons comment calculer les paramètres régissant cette loi d'échelle et montrons comment l'approximation qui en découle peut être utilisée pour optimiser les performances des codes LDPC.