Globecom

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

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

Published Dec 1, 2010• 2 citations

Abstract

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.

DOI: 10.1109/glocom.2010.5684185

Related papers

Analysis of Generalized LDPC Codes with Random Component Codes for the Binary Erasure Channel

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

In this paper, a method for the asymptotic analysis of generalized low-density parity-check (GLDPC) codes on the binary erasure channel (BEC) is proposed. The considered GLDPC codes have block linear codes as check nodes. Instead of considering specific check com-ponent codes, like Hamming or BCH codes, random codes are considered, and a technique is developed for obtaining the expected check EXIT function for the overall GLDPC code. Each check component code is supposed to belong to an expurgated ensemble. Some GLDPC thresholds obtained by this technique are com-pared with those of GLDPC codes, with the same dis-tribution and component codes lengths, using specific codes. Results obtained by combining our analysis with differential evolution tool are also presented. 1.

International Symposium on Information Theory and its ApplicationsJan 1, 200612 citations

Generalized constructions, decoding and implementation of LDPC codes

Yige Wang

Low-density parity-check (LDPC) codes have received significant attention due to their near-Shannon-limit error performance. The belief propagation (BP) algorithm is the best-known decoding algorithm for LDPC codes. However it often needs several tens or hundreds of iterations to converge. Although fast convergence BP algorithms have been proposed, there is neither an easy tool to analyze their performance nor a standard VLSI architecture to implement them. Moreover, there exists a trade-off between waterfall (i.e., threshold) and error floor (i.e., minimum pseudo distance) performances for LDPC codes. For generalized LDPC (GLDPC) codes, better minimum distance properties can be achieved but at the expense of a rate loss. This research investigates performance analysis and hardware implementation of LDPC codes using fast convergence algorithms. Closed-form extrinsic mutual information transfer (EXIT) functions for several fast convergence BP decoding algorithms are proposed. It is shown theoretically that these algorithms converge faster than standard BP, while the corresponding thresholds remain unchanged. Since these algorithms are of serial nature, their parallelization without compromising convergence speed and error performance is also investigated. This result is useful in hardware implementation because in practice partly parallel decoding schemes are often used. This result also sheds some light on how to group nodes in order to preserve performance. The VLSI architecture of a particular decoding algorithm for LDPC codes is proposed. This approach can be adopted in many standards to achieve a large throughput. Doubly GLDPC (DGLDPC) codes are proposed to compensate the rate loss of GLDPC codes. EXIT charts are used to analyze DGLDPC codes and EXIT functions for variable component codes are thoroughly discussed. Based on EXIT charts, differential evolution is used to optimize their threshold. Ensemble weight enumerators are generalized to protograph-based DGLDPC codes. Simulation results show that DGLDPC codes constructed based on these results can improve the performance of their LDPC and GLDPC counterparts in both the waterfall region and the error floor region.

Jan 1, 20083 citations

Doubly Generalized LDPC Codes over the AWGN Channel

Yige Wang, M.P.C. Fossorier

In this paper, the design of doubly generalized low-density parity-check (DGLDPC) codes is proposed. This approach generalizes the structure of LDPC codes at both check and variable nodes. The performance of DGLDPC codes over the AWGN channel is analyzed using EXIT charts. Combined with differential evolution optimization, this analysis provides thresholds for DGLDPC codes that are better than that of LDPC and GLDPC codes with the same maximum variable degree. These theoretical thresholds are verified via simulations. Furthermore DGLDPC codes exhibit a lower error floor compared with their LDPC and GLDPC counterparts.

IEEE Transactions on CommunicationsMay 1, 200926 citations

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

Enrico Paolini, Mark F. Flanagan, Marco Chiani +1 more

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.

arXiv:1112.3730GlobecomDec 1, 20111 citation

Near-capacity protograph doubly-generalized LDPC codes with block thresholds

Asit Kumar Pradhan, Andrew Thangaraj

Protograph doubly-generalized low-density parity-check (DGLDPC) codes, which allow for arbitrary component codes at the variable and check nodes of a protograph, are considered. Exact density evolution is derived over the binary erasure channel. Conditions on the protograph and component codes to ensure equality of block-error threshold and density evolution threshold for large-girth ensembles are established. Conditions for stability of density evolution are derived, and block-error threshold property is extended to binary-input symmetric channels. Optimized low-rate protographs for DGLDPC codes over the erasure channel are presented.

IEEE International Symposium on Information Theory (ISIT)Jul 1, 20165 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