Les codes Low-Density Parity-Check (LDPC) sont au coeur de larecherche des codes correcteurs d'erreurs en raison de leur excellenteperformance de décodage en utilisant un algorithme de décodageitératif de type propagation de croyances (Belief Propagation - BP).Cet algorithme utilise la représentation graphique d'un code, ditgraphe 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 marginalessur les graphes cycliques, et les codes LDPC peuvent asymptotiquementapprocher la capacité de Shannon avec cet algorithme.Cependant, sur des codes de longueurs finies dont la représentationgraphique contient des cycles, l'algorithme BP est sous-optimal etdonne lieu à l'apparition du phénomène dit de plancher d'erreur. Leplancher d'erreur se manifeste par la dégradation soudaine de la pentedu taux d'erreur dans la zone de fort rapport signal à bruit où lesstructures néfastes au décodage sont connues en termes de TrappingSets présents dans le graphe de Tanner du code, entraînant un échec dudécodage. De plus, les effets de la quantification introduite parl'implémentation en hardware de l'algorithme BP peuvent amplifier ceproblème de plancher d'erreur.Dans cette thèse nous introduisons un nouveau paradigme pour ledécodage itératif à précision finie des codes LDPC sur le canalbinaire symétrique. Ces nouveaux décodeurs, appelés décodeursitératifs à alphabet fini (Finite Alphabet Iterative Decoders – FAID)pour préciser que les messages appartiennent à un alphabet fini, sontcapables de surpasser l'algorithme BP dans la région du plancherd'erreur. Les messages échangés par les FAID ne sont pas desprobabilités ou vraisemblances quantifiées, et les fonctions de miseà jour des noeuds de variable ne copient en rien le décodage par BP cequi contraste avec les décodeurs BP quantifiés traditionnels. Eneffet, les fonctions de mise à jour sont de simples tables de véritéconçues pour assurer une plus grande capacité de correction d'erreuren utilisant la connaissance de topologies potentiellement néfastes audécodage présentes dans un code donné. Nous montrons que sur demultiples codes ayant un poids colonne de trois, il existe des FAIDutilisant 3 bits de précision pouvant surpasser l'algorithme BP(implémenté en précision flottante) dans la zone de plancher d'erreursans aucun compromis dans la latence de décodage. C'est pourquoi lesFAID obtiennent des performances supérieures comparées au BP avecseulement une fraction de sa complexité.Par ailleurs, nous proposons dans cette thèse une décimation amélioréedes FAID pour les codes LDPC dans le traitement de la mise à jour desnoeuds de variable. La décimation implique de fixer certains bits ducode à une valeur particulière pendant le décodage et peut réduire demanière significative le nombre d'itérations requises pour corriger uncertain nombre d'erreurs fixé tout en maintenant de bonnesperformances d'un FAID, le rendant plus à même d'être analysé. Nousillustrons cette technique pour des FAID utilisant 3 bits de précisioncodes de poids colonne trois. Nous montrons également comment cettedécimation peut être utilisée de manière adaptative pour améliorer lescapacité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 unFAID donné. Sur certains codes à haut rendement, nous montrons que ladécimation adaptative des FAID permet d'atteindre des capacités decorrection d'erreur proches de la limite théorique du décodage au sensdu maximum de vraisemblance. / At the heart of modern coding theory lies the fact that low-density parity-check (LDPC) codes can be efficiently decoded by message-passing algorithms which are traditionally based on the belief propagation (BP) algorithm. The BP algorithm operates on a graphical model of a code known as the Tanner graph, and computes marginals of functions on the graph. While inference using BP is exact only on loop-free graphs (trees), the BP still provides surprisingly close approximations to exact marginals on loopy graphs, and LDPC codes can asymptotically approach Shannon's capacity under BP decoding.However, on finite-length codes whose corresponding graphs are loopy, BP is sub-optimal and therefore gives rise to the error floor phenomenon. The error floor is an abrupt degradation in the slope of the error-rate performance of the code in the high signal-to-noise regime, where certain harmful structures generically termed as trapping sets present in the Tanner graph of the code, cause the decoder to fail. Moreover, the effects of finite precision that are introduced during hardware realizations of BP can further contribute to the error floor problem.In this dissertation, we introduce a new paradigm for finite precision iterative decoding of LDPC codes over the Binary Symmetric channel (BSC). These novel decoders, referred to as finite alphabet iterative decoders (FAIDs) to signify that the message values belong to a finite alphabet, are capable of surpassing the BP in the error floor region. The messages propagated by FAIDs are not quantized probabilities or log-likelihoods, and the variable node update functions do not mimic the BP decoder, which is in contrast to traditional quantized BP decoders. Rather, the update functions are simple maps designed to ensure a higher guaranteed error correction capability by using the knowledge of potentially harmful topologies that could be present in a given code. We show that on several column-weight-three codes of practical interest, there exist 3-bit precision FAIDs that can surpass the BP (floating-point) in the error floor without any compromise in decoding latency. Hence, they are able to achieve a superior performance compared to BP with only a fraction of its complexity.Additionally in this dissertation, we propose decimation-enhanced FAIDs for LDPC codes, where the technique of decimation is incorporated into the variable node update function of FAIDs. Decimation, which involves fixing certain bits of the code to a particular value during the decoding process, can significantly reduce the number of iterations required to correct a fixed number of errors while maintaining the good performance of a FAID, thereby making such decoders more amenable to analysis. We illustrate this for 3-bit precision FAIDs on column-weight-three codes. We also show how decimation can be used adaptively to further enhance the guaranteed error correction capability of FAIDs that are already good on a given code. The new adaptive decimation scheme proposed has marginally added complexity but can significantly improve the slope of the error floor performance of a particular FAID. On certain high-rate column-weight-three codes of practical interest, we show that adaptive decimation-enhanced FAIDs can achieve a guaranteed error-correction capability that is close to the theoretical limit achieved by maximum-likelihood decoding.

No description available.

Dans cette thèse, nous étudions le problème de l'inférence bayésienne dans les graphes factoriels, en particulier les codes LDPC, quasiment résolus par les algorithmes de message-passing. Nous réalisons en particulier une étude approfondie du Belief Propagation (BP) dont la question de la sous-optimalité est soulevée dans le cas où le graphe factoriel présente des boucles. A partir de l'équivalence entre le BP et l'approximation de Bethe en physique statistique qui se généralise à l'approximation basée régions, nous détaillons le Generalized Belief Propagation (GBP), un algorithme de message-passing entre des clusters du graphe factoriel. Nous montrons par des expériences que le GBP surpasse le BP dans les cas où le clustering est réalisé selon les structures topologiques néfastes qui empêchent le BP de bien décoder, à savoir les trapping sets. Au-delà de l'étude des performances en termes de taux d'erreur, nous confrontons les deux algorithmes par rapport à leurs dynamiques face à des événements d'erreur non triviaux, en particulier lorsqu'ils présentent des comportements chaotiques. Par des estimateurs classiques et originaux, nous montrons que l'algorithme du GBP peut dominer l'algorithme du BP. / This thesis addresses the problem of inference in factor graphs, especially the LDPC codes, almost solved by message-passing algorithms. In particular, the Belief Propagation algorithm (BP) is investigated as a particular message-passing algorithm whose suboptimality is discussed in the case where the factor graph has a loop-like topology. From the equivalence between the BP and the Bethe approximation in statistical physics that is generalized to the region-based approximation, is detailed the Generalized Belief Propagation algorithm (GBP), a message-passing algorithm between clusters of the factor graph. It is experimentally shown to surpass the BP in the cases where the clustering deals with the harmful topological structures that prevents the BP from rightly decoding any LDPC code, namely the trapping sets. We do not only confront the BP and the GBP algorithms according to their performance from the point of view of the channel coding with the error-rate, but also according to their dynamical behaviors for non-trivial error-events for which both algorithms can exhibit chaotic beahviors. By means of classical and original dynamical quantifiers, it is shown that the GBP algorithm can overcome the BP algorithm.

Σήμερα οι απαιτήσεις τόσο σε όγκο πληροφορίας προς μετάδοση όσο και της αξιόπιστης μετάδοσης και προστασίας της πληροφορίας είναι ιδιαίτερα υψηλές. Καθοριστικό ρόλο σε αυτό παίζει το αντικείμενο της Αναγνώρισης και Διόρθωσης Λαθών με τους κώδικες διόρθωσης λαθών που βρίσκονται σε κάθε πλευρά της καθημερινής και όχι μόνο ζωής οι οποίοι προστατεύουν από την αλλοίωση των δεδομένων και χρησιμοποιούνται για παράδειγμα σε συσκευές αποθήκευσης, κινητή τηλεφωνία, ασύρματα δίκτυα και επεκτείνονται μέχρι και στην δορυφορική επικοινωνία. Οι κώδικες LDPC είναι μια τέτοια κατηγορία κωδίκων με ποικίλες εφαρμογές και συγκαταλέγονται ανάμεσα στους καλύτερους του πεδίου της Αναγνώρισης και Διόρθωσης Λαθών. Όμως για να προστατευθεί το αναλλοίωτο της πληροφορίας είναι απαραίτητη η αξιόπιστη και επιτυχής αποκωδικοποίηση μετά τη λήψη των δεδομένων. Το πρόβλημα στην επαναληπτική αποκωδικοποίηση κωδίκων LDPC εμφανίζεται όταν έχουμε κύκλους στον πίνακα ελέγχου ισοτιμίας και στο γράφημα Tanner και εμφανίζονται κάποιες δομές που ονομάζονται trapping sets, οι οποίες οδηγούν σε διαφορετική από την αναμενόμενη συμπεριφορά της καμπύλης που δίνει το ρυθμό σφάλματος ανά bit. Σε αυτές τις περιπτώσεις η καμπύλη εμφανίζει από ένα σημείο και μετά διαφορετική κλίση από την αναμενόμενη και επηρεάζεται το κατώτατο σφάλμα το οποίο τώρα είναι υψηλότερο. Η μέθοδος που ακολουθήθηκε στη παρούσα εργασία ήταν για την μελέτη των χαρακτηριστικών κωδίκων μέσω της καταμέτρησης των trapping sets. / Today our requirements for reliable transmission of huge amounts of information are very high. The objective of Error Identification and Correction plays an important role in this effort with the use of error correction codes which are present in every aspect of everyday life and beyond for keeping information unchanged. Such examples of their use are storage devices, mobile communication, wireless networks and even satellite communication. LDPC codes are such a category of error correction codes, have many applications and constitute of some of the greatest codes of the field of Error Identification and Correction. But in order to achieve unchanged information after transmission, it is essential that decoding problems which appear must be resolved. The problem with iterative decoding of LDPC codes appears when cycles exist inside the parity check matrix and the Tanner graph and as a result some other structures appear, which are called trapping sets. These trapping sets are responsible for the deviation of the bearing of the graph of bit error rate and error floor. In these cases the graph has a suddenly change in gradient. So the error floor is much higher now. The method used here was the study of characteristics of some codes from counting the trapping sets.

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.

Ever since the publication of Shannon's seminal work in 1948, the search for capacity achieving codes has led to many interesting discoveries in channel coding theory. Low-density parity-check (LDPC) codes originally proposed in 1963 were largely forgotten and rediscovered recently. The significance of LDPC codes lies in their capacity approaching performance even when decoded using low complexity sub-optimal decoding algorithms. Iterative decoders are one such class of decoders that work on a graphical representation of a code known as the Tanner graph. Their properties have been well understood in the asymptotic limit of the code length going to infinity. However, the behavior of various decoders for a given finite length code remains largely unknown.An understanding of the failures of the decoders is vital for the error floor analysis of a given code. Broadly speaking, error floor is the abrupt degradation in the frame error rate (FER) performance of a code in the high signal-to-noise ratio domain. Since the error floor phenomenon manifests in the regions not reachable by Monte-Carlo simulations, analytical methods are necessary for characterizing the decoding failures. In this work, we consider hard decision decoders for transmission over the binary symmetric channel (BSC).For column-weight-three codes, we provide tight upper and lower bounds on the guaranteed error correction capability of a code under the Gallager A algorithm by studying combinatorial objects known as trapping sets. For higher column weight codes, we establish bounds on the minimum number of variable nodes that achieve certain expansion as a function of the girth of the underlying Tanner graph, thereby obtaining lower bounds on the guaranteed error correction capability. We explore the relationship between a class of graphs known as cage graphs and trapping sets to establish upper bounds on the error correction capability.We also propose an algorithm to identify the most probable noise configurations, also known as instantons, that lead to error floor for linear programming (LP) decoding over the BSC. With the insight gained from the above analysis techniques, we propose novel code construction techniques that result in codes with superior error floor performance.

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.

This thesis addresses the problem of inference in factor graphs, especially the LDPC codes, almost solved by message-passing algorithms. In particular, the Belief Propagation algorithm (BP) is investigated as a particular message-passing algorithm whose suboptimality is discussed in the case where the factor graph has a loop-like topology. From the equivalence between the BP and the Bethe approximation in statistical physics that is generalized to the region-based approximation, is detailed the Generalized Belief Propagation algorithm (GBP), a message-passing algorithm between clusters of the factor graph. It is experimentally shown to surpass the BP in the cases where the clustering deals with the harmful topological structures that prevents the BP from rightly decoding any LDPC code, namely the trapping sets. We do not only confront the BP and the GBP algorithms according to their performance from the point of view of the channel coding with the error-rate, but also according to their dynamical behaviors for non-trivial error-events for which both algorithms can exhibit chaotic beahviors. By means of classical and original dynamical quantifiers, it is shown that the GBP algorithm can overcome the BP algorithm.

Fountain codes have demonstrated great results for the binary erasure channel and have already been incorporated into several international standards to recover lost packets at the application layer. These include multimedia broadcast/multicast sessions and digital video broadcasting on global internet-protocol. The rateless property of Fountain codes holds great promise for noisy channels. These are more sophisticated mathematical models representing errors on communications links rather than only erasures. The practical implementation of Fountain codes for these channels, however, is hampered by high decoding cost and delay. In this work we study trapping sets in Fountain codes over noisy channels and their effect on the decoding process. While trapping sets have received much attention for low-density parity-check (LDPC) codes, to our knowledge they have never been fully explored for Fountain codes. Our study takes into account the different code structure and the dynamic nature of Fountain codes. We show that 'error-free' trapping sets exist for Fountain codes. When the decoder is caught in an error-free trapping set it actually has the correct message estimate, but is unable to detect this is the case. Thus, the decoding process continues, increasing the decoding cost and delay for naught. The decoding process for rateless codes consists of one or more decoding attempts. We show that trapping sets may reappear as part of other trapping sets on subsequent decoding attempts or be defeated by the reception of more symbols. Based on our observations we propose early termination methods that use trapping set detection to obtain improvements in realized rate, latency, and decoding cost for Fountain codes. / Thesis (Master, Electrical & Computer Engineering) -- Queen's University, 2009-10-29 14:33:06.548