The growing popularity of a class of linear block codes called the low-density parity-check (LDPC) codes can be attributed to the low complexity of the iterative decoders, and their potential to achieve performance very close to the Shannon capacity. This makes them an attractive candidate for ECC applications in communication systems. This report proposes methods to systematically construct regular and irregular LDPC codes.A class of regular LDPC codes are constructed from incidence structures in finite geometries like projective geometry and affine geometry. A class of irregular LDPC codes are constructed by systematically splitting blocks of balanced incomplete block designs to achieve desired weight distributions. These codes are decoded iteratively using message-passing algorithms, and the performance of these codes for various channels are presented in this report.The application of iterative decoders is generally limited to a class of codes whose graph representations are free of small cycles. Unfortunately, the large class of conventional algebraic codes, like RS codes, has several four cycles in their graph representations. This report proposes an algorithm that aims to alleviate this drawback by constructing an equivalent graph representation that is free of four cycles. It is theoretically shown that the four-cycle free representation is better suited to iterative erasure decoding than the conventional representation. Also, the new representation is exploited to realize, with limited success, iterative decoding of Reed-Solomon codes over the additive white Gaussian noise channel.Wiberg, Forney, Richardson, Koetter, and Vontobel have made significant contributions in developing theoretical frameworks that facilitate finite length analysis of codes. With an exception of Richardson's, most of the other frameworks are much suited for the analysis of short codes. In this report, we further the understanding of the failures in iterative decoders for the binary symmetric channel. The failures of the decoder are classified into two categories by defining trapping sets and propagating sets. Such a classification leads to a successful estimation of the performance of codes under the Gallager B decoder. Especially, the estimation techniques show great promise in the high signal-to-noise ratio regime where the simulation techniques are less feasible.

Les codes Low-Density Parity-Check (LDPC) sont au coeur de la recherche des codes correcteurs d'erreurs en raison de leur excellente performance de décodage en utilisant un algorithme de décodage itératif de type propagation de croyances (Belief Propagation - BP). Cet algorithme utilise la représentation graphique d'un code, dit graphe de Tanner, et calcule les fonctions marginales sur le graphe. Même si l'inférence calculée n'est exacte que sur un graphe acyclique (arbre), l'algorithme BP estime de manière très proche les marginales sur les graphes cycliques, et les codes LDPC peuvent asymptotiquement approcher la capacité de Shannon avec cet algorithme. Cependant, sur des codes de longueurs finies dont la représentation graphique contient des cycles, l'algorithme BP est sous-optimal et donne lieu à l'apparition du phénomène dit de plancher d'erreur. Le plancher d'erreur se manifeste par la dégradation soudaine de la pente du taux d'erreur dans la zone de fort rapport signal à bruit où les structures néfastes au décodage sont connues en termes de Trapping Sets présents dans le graphe de Tanner du code, entraînant un échec du décodage. De plus, les effets de la quantification introduite par l'implémentation en hardware de l'algorithme BP peuvent amplifier ce problème de plancher d'erreur. Dans cette thèse nous introduisons un nouveau paradigme pour le décodage itératif à précision finie des codes LDPC sur le canal binaire symétrique. Ces nouveaux décodeurs, appelés décodeurs itératifs à alphabet fini (Finite Alphabet Iterative Decoders - FAID) pour préciser que les messages appartiennent à un alphabet fini, sont capables de surpasser l'algorithme BP dans la région du plancher d'erreur. Les messages échangés par les FAID ne sont pas des probabilités ou vraisemblances quantifiées, et les fonctions de mise à jour des noeuds de variable ne copient en rien le décodage par BP ce qui contraste avec les décodeurs BP quantifiés traditionnels. En effet, les fonctions de mise à jour sont de simples tables de vérité conçues pour assurer une plus grande capacité de correction d'erreur en utilisant la connaissance de topologies potentiellement néfastes au décodage présentes dans un code donné. Nous montrons que sur de multiples codes ayant un poids colonne de trois, il existe des FAID utilisant 3 bits de précision pouvant surpasser l'algorithme BP (implémenté en précision flottante) dans la zone de plancher d'erreur sans aucun compromis dans la latence de décodage. C'est pourquoi les FAID obtiennent des performances supérieures comparées au BP avec seulement une fraction de sa complexité. Par ailleurs, nous proposons dans cette thèse une décimation améliorée des FAID pour les codes LDPC dans le traitement de la mise à jour des noeuds de variable. La décimation implique de fixer certains bits du code à une valeur particulière pendant le décodage et peut réduire de manière significative le nombre d'itérations requises pour corriger un certain nombre d'erreurs fixé tout en maintenant de bonnes performances d'un FAID, le rendant plus à même d'être analysé. Nous illustrons cette technique pour des FAID utilisant 3 bits de précision codes de poids colonne trois. Nous montrons également comment cette décimation peut être utilisée de manière adaptative pour améliorer les capacités de correction d'erreur des FAID. Le nouveau modèle proposé de décimation adaptative a, certes, une complexité un peu plus élevée, mais améliore significativement la pente du plancher d'erreur pour un FAID donné. Sur certains codes à haut rendement, nous montrons que la décimation adaptative des FAID permet d'atteindre des capacités de correction d'erreur proches de la limite théorique du décodage au sens du maximum de vraisemblance.

No description available.