arXiv:1112.3730 · Globecom

Stability of Iterative Decoding of Multi-Edge Type Doubly-Generalized LDPC Codes over the BEC

Enrico Paolini, Mark F. Flanagan, Marco Chiani, M.P.C. Fossorier

Published Dec 1, 2011• 1 citation

Abstract

Using the EXIT chart approach, a necessary and sufficient condition is developed for the local stability of iterative decoding of multi-edge type (MET) doubly-generalized low-density parity-check (D-GLDPC) code ensembles. In such code ensembles, the use of arbitrary linear block codes as component codes is combined with the further design of local Tanner graph connectivity through the use of multiple edge types. The stability condition for these code ensembles is shown to be succinctly described in terms of the value of the spectral radius of an appropriately defined polynomial matrix.

DOI: 10.1109/glocom.2011.6134025

Related papers

Generalized Stability Condition for Generalized and Doubly-Generalized LDPC Codes

Enrico Paolini, M.P.C. Fossorier, Marco Chiani

In this paper, the stability condition for low-density parity-check (LDPC) codes on the binary erasure channel (BEC) is extended to generalized LDPC (GLDPC) codes and doubly-generalized LDPC (D-GLDPC) codes. It is proved that, in both cases, the stability condition only involves the component codes with minimum distance 2. The stability condition for GLDPC codes is always expressed as an upper bound to the decoding threshold. This is not possible for D-GLDPC codes, unless all the generalized variable nodes have minimum distance at least 3. Furthermore, a condition called derivative matching is defined in the paper. This condition is sufficient for a GLDPC or D- GLDPC code to achieve the stability condition with equality. If this condition is satisfied, the threshold of D-GLDPC codes (whose generalized variable nodes have all minimum distance at least 3) and GLDPC codes can be expressed in closed form.

arXiv:0704.3199IEEE International Symposium on Information Theory (ISIT)Jun 1, 20077 citations

On Design of Doubly-Generalized LDPC Codes Based on Multi-Type Information Functions

Enrico Paolini, Marco Chiani, M.P.C. Fossorier

Ensemble design of low-density parity-check (LDPC) codes and their generalizations is usually performed via numerical optimization techniques, such as differential evolution, in which a threshold analysis tool is always necessary. Threshold analysis of unstructured doubly-generalized LDPC (D-GLDPC) code ensembles over the binary erasure channel (BEC) can be performed via extrinsic information transfer (EXIT) chart, exploiting the information functions and split information functions of the check and variable component codes, respectively. In this paper, multi-type information functions of linear block codes are introduced as an extension of the concept of information functions, when the bit positions are assumed to be associated with different types. It is shown how multi-type information functions (together with their split counterparts) can be exploited within an EXIT analysis approach to perform threshold analysis over the BEC of multi-edge type D-GLDPC code ensembles. The proposed technique for threshold analysis captures D-GLDPC codes based on protographs as a special case.

GlobecomDec 1, 20102 citations

Doubly-Generalized LDPC Codes: Stability Bound Over the BEC

Enrico Paolini, M.P.C. Fossorier, Marco Chiani

The iterative decoding threshold of low-density parity-check (LDPC) codes over the binary erasure channel (BEC) fulfills an upper bound depending only on the variable and check nodes with minimum distance 2. This bound is a consequence of the stability condition, and is here referred to as stability bound. In this paper, a stability bound over the BEC is developed for doubly-generalized LDPC codes, where variable and check nodes can be generic linear block codes, assuming maximumaposteriorierasure correction at each node. It is proved that also in this generalized context the bound depends only on the variable and check component codes with minimum distance 2. A condition is also developed, namely, the derivative matching condition, under which the bound is achieved with equality. The stability bound leads to consider single parity-check codes used as variable nodes as an appealing option to overcome common problems created by generalized check nodes.

arXiv:0802.0823IEEE Transactions on Information TheoryFeb 26, 200928 citations

Generalized LDPC codes and generalized stopping sets

N. Miladinovic, M.P.C. Fossorier

A generalized low-density parity check code (GLDPC) is a low-density parity check code in which the constraint nodes of the code graph are block codes, rather than single parity checks. In this paper, we study GLDPC codes which have BCH or Reed-Solomon codes as subcodes under bounded distance decoding (BDD). The performance of the proposed scheme is investigated in the limit case of an infinite length (cycle free) code used over a binary erasure channel (BEC) and the corresponding thresholds for iterative decoding are derived. The performance of the proposed scheme for finite code lengths over a BEC is investigated as well. Structures responsible for decoding failures are defined and a theoretical analysis over the ensemble of GLDPC codes which yields exact bit and block error rates of the ensemble average is derived. Unfortunately this study shows that GLDPC codes do not compare favorably with their LDPC counterpart over the BEC. Fortunately, it is also shown that under certain conditions, objects identified in the analysis of GLDPC codes over a BEC and the corresponding theoretical results remain useful to derive tight lower bounds on the performance of GLDPC codes over a binary symmetric channel (BSC). Simulation results show that the proposed method yields competitive performance with a good decoding complexity trade-off for the BSC.

IEEE Transactions on CommunicationsFeb 1, 200852 citations

On the Error Correction of Iterative Bounded Distance Decoding of Generalized LDPC Codes

David Burshtein

Consider an ensemble of regular generalized LDPC (GLDPC) codes and assume that the same component code is associated with each parity check node. To decode a GLDPC code from the ensemble, we use the bit flipping bounded distance decoding algorithm, which is an extension of the bit flipping algorithm for LDPC codes. Previous work has shown conditions, under which, for a typical code in the ensemble with blocklength sufficiently large, a positive constant fraction of worst case errors can be corrected. In this work we first show that these requirements can be relaxed for ensembles with small left degrees. While previous work on GLDPC codes has considered expander graph arguments, our analysis formulates a necessary condition that the Tanner graph needs to satisfy for a failure event and then shows that the probability of this event vanishes for a sufficiently large blocklength. We then extend the analysis to random error correction and derive a lower bound on the fraction of random errors that can be corrected asymptotically. We discuss the extension of our results to non-binary GLDPC codes and present numerical examples.

arXiv:2507.12073IEEE Transactions on Information TheorySep 16, 20250 citations

Design of LDPC Code Ensembles with Fast Convergence Properties

Ian P. Mulholland, Enrico Paolini, Mark F. Flanagan

The design of low-density parity-check (LDPC) code ensembles optimized for a finite number of decoder iterations is investigated. Our approach employs EXIT chart analysis and differential evolution to design such ensembles for the binary erasure channel and additive white Gaussian noise channel. The error rates of codes optimized for various numbers of decoder iterations are compared and it is seen that in the cases considered, the best performance for a given number of decoder iterations is achieved by codes which are optimized for this particular number. The design of generalized LDPC (GLDPC) codes is also considered, showing that these structures can offer better performance than LDPC codes for low-iteration-number designs. Finally, it is illustrated that LDPC codes which are optimized for a small number of iterations exhibit significant deviations in terms of degree distribution and weight enumerators with respect to LDPC codes returned by more conventional design tools.

Aug 14, 20169 citations