Codes LDPC multi-binaires hybrides et méthodes de décodage itératif

Description

This thesis is dedicated to the analysis and the design of sparse-graph codes for channel coding. The aim is to construct coding schemes having high performance both in the waterfall and in the error-floor regions under iterative decoding. In the first part, a new class of LDPC codes, named hybrid LDPC codes, is introduced. Their asymptotic analysis for memoryless symmetric channel is performed, and leads to code parameter optimization for the binary input Gaussian channel. Additionally to a better waterfall region, the resulting codes have a very low error-floor for code rate one- half and codeword length lower than three thousands bits, thereby competing with multi- edge type LDPC. Thus, hybrid LDPC codes allow to achieve an interesting trade-off between good error-floor performance and good waterfall region with non-binary coding techniques. In the second part of the thesis, we have tried to determine which kind of machine learning methods would be useful to design better LDPC codes and better decoders in the short code length case. We have first investigated how to build the Tanner graph of a code by removing edges from the Tanner graph of a mother code, using a machine learning algorithm, in order to optimize the minimum distance. We have also investigated decoder design by machine learning methods in order to perform better than BP which is suboptimal as soon as there are cycles in the graph. In the third part of the thesis, we have moved towards quantized decoding in order to address the same problem: finding rules to decode difficult error configurations. We have proposed a class of two-bit decoders. We have derived sufficient conditions for a column-weight four code with Tanner graph of girth six to correct any three errors. These conditions show that decoding with the two-bit rule allows to ensure weight-three error correction capability for higher rate codes than the decoding with one bit.

Abstract (French)

Cette thèse porte sur l'analyse et le design de codes de canal définis par des graphes creux. Le but est de construire des codes ayant de très bonnes performances sur de larges plages de rapports signal à bruit lorsqu'ils sont décodés itérativement. Dans la première partie est introduite une nouvelle classe de codes LDPC, nommés code LDPC hybrides. L'analyse de cette classe pour des canaux symétriques sans mé- moire est réalisée, conduisant à l'optimisation des paramètres, pour le canal gaussien à entrée binaire. Les codes LDPC hybrides résultants ont non seulement de bonnes proprié- tés de convergence, mais également un plancher d'erreur très bas pour des longueurs de mot de code inférieures à trois mille bits, concurrençant ainsi les codes LDPC multi-edge. Les codes LDPC hybrides permettent donc de réaliser un compromis intéressant entre ré- gion de convergence et plancher d'erreur avec des techniques de codage non-binaires. La seconde partie de la thèse a été consacrée à étudier quel pourrait être l'apport de méthodes d'apprentissage artificiel pour le design de bons codes et de bons décodeurs itératifs, pour des petites tailles de mot de code. Nous avons d'abord cherché comment construire un code en enlevant des branches du graphe de Tanner d'un code mère, selon un algorithme d'apprentissage, dans le but d'optimiser la distance minimale. Nous nous sommes ensuite penchés sur le design d'un décodeur itératif par apprentissage artificiel, dans l'optique d'avoir de meilleurs résultats qu'avec le décodeur BP, qui devient sous- optimal dès qu'il y a des cycles dans le graphe du code. Dans la troisième partie de la thèse, nous nous sommes intéressés au décodage quan- tifié dans le même but que précédemment : trouver des règles de décodage capables de décoder des configurations d'erreur difficiles. Nous avons proposé une classe de déco- deurs utilisant deux bits de quantification pour les messages du décodeur. Nous avons prouvé des conditions suffisantes pour qu'un code LDPC, avec un poids de colonnes égal à quatre, et dont le plus petit cycle du graphe est de taille au moins six, corrige n'importe quel triplet d'erreurs. Ces conditions montrent que décoder avec cette règle à deux bits permet d'assurer une capacité de correction de trois erreurs pour des codes de rendements plus élevés qu'avec une règle de décodage à un bit.

Additional details