IEEE Transactions on Communications

Selective Avoidance of Cycles in Irregular LDPC Code Construction

T. Tian, C.R. Jones, John D. Villasenor, Richard D. Wesel

Published Aug 1, 2004• 396 citations

Abstract

This letter explains the effect of graph connectivity on error-floor performance of low-density parity-check (LDPC) codes under message-passing decoding. A new metric, called extrinsic message degree (EMD), measures cycle connectivity in bipartite graphs of LDPC codes. Using an easily computed estimate of EMD, we propose a Viterbi-like algorithm that selectively avoids small cycle clusters that are isolated from the rest of the graph. This algorithm is different from conventional girth conditioning by emphasizing the connectivity as well as the length of cycles. The algorithm yields codes with error floors that are orders of magnitude below those of random codes with very small degradation in capacity-approaching capability.

DOI: 10.1109/tcomm.2004.833048

Related papers

Construction of irregular LDPC codes with low error floors

Tao Tian, C. Jones, John D. Villasenor +1 more

This work explains the relationship between cycles, stopping sets, and dependent columns of the parity check matrix of low-density parity-check (LDPC) codes. Furthermore, it discusses how these structures limit LDPC code performance under belief propagation decoding. A new metric called extrinsic message degree (EMD) measures cycle connectivity in bipartite graph. Using an easily computed estimate of EMD, we propose a Viterbi-like algorithm that selectively avoids cycles and increases stopping set size. This algorithm yields codes with error floors that are orders of magnitude below those of girth-conditional codes.

International Conference on CommunicationsMar 30, 2004196 citations

Design of LDPC Codes Based on Multipath EMD Strategies for Progressive Edge Growth

Cornelius T. Healy, Rodrigo C. de Lamare

Low-density parity-check (LDPC) codes are capable of achieving excellent performance and provide a useful alternative for the high-performance applications. However, at medium to high signal-to-noise ratios, an observable error floor arises from the loss of independence of messages passed under iterative graph-based decoding. In this paper, the error floor performance of the short block length codes is improved by the use of a novel candidate selection metric in code graph construction. The proposed multipath extrinsic message degree (EMD) approach avoids harmful structures in the graph by evaluating certain properties of the cycles introduced in each edge placement. We present multipath EMD-based designs for several structured LDPC codes, including quasi-cyclic and the irregular repeat accumulate codes. In addition, an extended class of the diversity-achieving codes on the challenging block fading channel is proposed and considered with the multipath EMD design. This combined approach is demonstrated to provide the gains in decoder convergence and error rate performance. A simulation study evaluates the performance of the proposed and existing state-of-the-art methods.

IEEE Transactions on CommunicationsJun 10, 201652 citations

Design of LDPC Codes using Multipath EMD Strategies and Progressive Edge Growth

Cornelius T. Healy, Rodrigo C. de Lamare

Low-density parity-check (LDPC) codes are capable of achieving excellent performance and provide a useful alternative for high performance applications. However, at medium to high signal-to-noise ratios (SNR), an observable error floor arises from the loss of independence of messages passed under iterative graph-based decoding. In this paper, the error floor performance of short block length codes is improved by use of a novel candidate selection metric in code graph construction. The proposed Multipath EMD approach avoids harmful structures in the graph by evaluating certain properties of the cycles which may be introduced in each edge placement. We present Multipath EMD based designs for several structured LDPC codes including quasi-cyclic and irregular repeat accumulate codes. In addition, an extended class of diversity-achieving codes on the challenging block fading channel is proposed and considered with the Multipath EMD design. This combined approach is demonstrated to provide gains in decoder convergence and error rate performance. A simulation study evaluates the performance of the proposed and existing state-of-the-art methods.

arXiv:1607.05647Jul 19, 20160 citations

Fast estimation of error floor effect for irregular low-density parity-check codes

Aleksei Ovinnikov, Vladimir V. Vityazev

The article summarizes a comparison of numerous irregular low-density parity-check codes using a set of metrics such as girth, number of short cycles in Tanner graph and extrinsic message degree (EMD). Based on this these metrics, we analyze how to decrease error floor for such codes with no negative effect to threshold.

International Siberian Conference on Control and CommunicationsMay 1, 20150 citations

Fast Identification of Error-Prone Patterns for LDPC Codes under Message Passing Decoding

Jing Lei, Wen Gao

Although density evolution accurately predicts the asymptotic performance of LDPC codes, it provides limited information for codes of short or moderate block length. For this reason, combinatorial methods have been employed to analyze the performance of finite-length LDPC codes under message passing decoding. The error floor phenomenon is a key issue of finite-length effects, which is caused largely by poorly connected subgraphs residing in the LPDC codes structure. Because of the unequal noise immunity of different bit levels, error floors become more pronounced for LDPC-coded high-order modulation. Nevertheless, the enumeration of error-prone patterns that lead to error floors has been proven to be NP-hard, which motivates us to find substitute metrics with manageable complexity. Considering trapping sets always comprise loops of low extrinsic message degree (EMD) and the connectivity of a loop with the residual graph can be characterized by its approximate EMD (ACE), in this paper we propose a fast method to identify loops with low ACE for a given code. In light of this, the vulnerable variable nodes residing on low-ACE loops are judiciously mapped to bit levels benefitting from stronger error protection. As a result, the error floor can be significantly improved at the cost of a minor increase of hardware complexity.

GlobecomJan 1, 20084 citations

On Lowering the Error Floor of Short-to-Medium Block Length Irregular Low Density Parity Check Codes

Umar-Faruk Abdu-Aguye

Gallager proposed and developed low density parity check (LDPC) codes in the early 1960s. LDPC codes were rediscovered in the early 1990s and shown to be capacity approaching over the additive white Gaussian noise (AWGN) channel. Subsequently, density evolution (DE) optimized symbol node degree distributions were used to significantly improve the decoding performance of short to medium length irregular LDPC codes. Currently, the short to medium length LDPC codes with the lowest error floor are DE optimized irregular LDPC codes constructed using progressive edge growth (PEG) algorithm modifications which are designed to increase the approximate cycle extrinsic message degrees (ACE) in the LDPC code graphs constructed. The aim of the present work is to find efficient means to improve on the error floor performance published for short to medium length irregular LDPC codes over AWGN channels in the literature. An efficient algorithm for determining the girth and ACE distributions in short to medium length LDPC code Tanner graphs has been proposed. A cyclic PEG (CPEG) algorithm which uses an edge connections sequence that results in LDPC codes with improved girth and ACE distributions is presented. LDPC codes with DE optimized/’good’ degree distributions which have larger minimum distances and stopping distances than previously published for LDPC codes of similar length and rate have been found. It is shown that increasing the minimum distance of LDPC codes lowers their error floor performance over AWGN channels; however, there are threshold minimum distances values above which there is no further lowering of the error floor performance. A minimum local girth (edge skipping) (MLG (ES)) PEG algorithm is presented; the algorithm controls the minimum local girth (global girth) connected in the Tanner graphs of LDPC codes constructed by forfeiting some edge connections. A technique for constructing optimal low correlated edge density (OED) LDPC codes based on modified DE optimized symbol node degree distributions and the MLG (ES) PEG algorithm modification is presented. OED rate-½ (n, k)=(512, 256) LDPC codes have been shown to have lower error floor over the AWGN channel than previously published for LDPC codes of similar length and rate. Similarly, consequent to an improved symbol node degree distribution, rate ½ (n, k)=(1024, 512) LDPC codes have been shown to have lower error floor over the AWGN channel than previously published for LDPC codes of similar length and rate. An improved BP/SPA (IBP/SPA) decoder, obtained by making two simple modifications to the standard BP/SPA decoder, has been shown to result in an unprecedented generalized improvement in the performance of short to medium length irregular LDPC codes under iterative message passing decoding. The superiority of the Slepian Wolf distributed source coding model over other distributed source coding models based on LDPC codes has been shown.

Jan 1, 20180 citations