EURASIP Journal on Wireless Communications and Networking

New Technique for Improving Performance of LDPC Codes in the Presence of Trapping Sets

Esa Alghonaim, Aiman Helmi El-Maleh, Mohamed Adnan Landolsi

Published May 5, 2008• 9 citations

Abstract

Trapping sets are considered the primary factor for degrading the performance of low-density parity-check (LDPC) codes in the error-floor region. The effect of trapping sets on the performance of an LDPC code becomes worse as the code size decreases. One approach to tackle this problem is to minimize trapping sets during LDPC code design. However, while trapping sets can be reduced, their complete elimination is infeasible due to the presence of cycles in the underlying LDPC code bipartite graph. In this work, we introduce a new technique based on trapping sets neutralization to minimize the negative effect of trapping sets under belief propagation (BP) decoding. Simulation results for random, progressive edge growth (PEG) and MacKay LDPC codes demonstrate the effectiveness of the proposed technique. The hardware cost of the proposed technique is also shown to be minimal.

DOI: 10.1155/2008/362897

Related papers

A Performance Improvement and Error Floor Avoidance Technique for Belief Propagation Decoding of LDPC Codes

E. Cavus, Babak Daneshrad

In this work, we introduce a unique technique that improves the performance of the BP decoding in waterfall and error-floor regions by reversing the decoder failures. Based on the short cycles existing in the bipartite graph, an importance sampling simulation technique is used to identify the bit and check node combinations that are the dominant sources of error events, called trapping sets. Then, the identified trapping sets are used in the decoding process to avoid the pre-known failures and to converge to the transmitted codeword. With a minimal additional decoding complexity, the proposed technique is able to provide performance improvements for short-length LDPC codes and push or avoid error-floor behaviors of longer codes

IEEE International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC)Aug 2, 200657 citations

Performance improvement of short-length regular low-density parity-check codes with low-complexity post-processing

Raghunadh K. Bhattar, K.R. Ramakrishnan, K. S. Dasgupta

It is well known that extremely long low-density parity-check (LDPC) codes perform exceptionally well for error correction applications, short-length codes are preferable in practical applications. However, short-length LDPC codes suffer from performance degradation owing to graph-based impairments such as short cycles, trapping sets and stopping sets and so on in the bipartite graph of the LDPC matrix. In particular, performance degradation at moderate to high Eb/N0 is caused by the oscillations in bit node a posteriori probabilities induced by short cycles and trapping sets in bipartite graphs. In this study, a computationally efficient algorithm is proposed to improve the performance of short-length LDPC codes at moderate to high Eb/N0. This algorithm makes use of the information generated by the belief propagation (BP) algorithm in previous iterations before a decoding failure occurs. Using this information, a reliability-based estimation is performed on each bit node to supplement the BP algorithm. The proposed algorithm gives an appreciable coding gain as compared with BP decoding for LDPC codes of a code rate equal to or less than 1/2 rate coding. The coding gains are modest to significant in the case of optimised (for bipartite graph conditioning) regular LDPC codes, whereas the coding gains are huge in the case of unoptimised codes. Hence, this algorithm is useful for relaxing some stringent constraints on the graphical structure of the LDPC code and for developing hardware-friendly designs.

IET CommunicationsOct 16, 20121 citation

An application of generalized belief propagation: splitting trapping sets in LDPC codes

Jean-Christophe Sibel, Sylvain Reynal, David Declercq

Generalized belief propagation (GBP) is known to be a well-suited technique for approximate inference problems in loopy factor graphs. It can absorb problematic subgraphs inside regions to reduce their influence on the inference. However, the choice of regions to be used in GBP remains a delicate issue. This paper proposes an approach to create specific regions when dealing with Low-Density Parity-Check (LDPC) codes. We split trapping sets, known to degrade the decoding performance, to make GBP locally optimal. Experiments show that GBP can then perform better than BP, especially in the error-floor region.

IEEE International Symposium on Information Theory (ISIT)Jun 1, 20147 citations

Breaking the Trapping Sets in LDPC Codes: Check Node Removal and Collaborative Decoding

Soonyoung Kang, Jaekyun J. Moon, Jeongseok Ha +1 more

Trapping sets strongly degrade performance of low-density parity check (LDPC) codes in the low-error-rate region. This creates significant difficulties for the deployment of LDPC codes to low-error-rate applications such as storage and wireless systems with no or limited retransmission options. We propose a novel technique for breaking trapping sets based on collaborative decoding that utilizes two different decoding modes. While the main decoding mode executes message passing based on the original parity check matrix of the corresponding LDPC code, the sub-decoding mode operates on a modified parity check matrix formed by removing a portion of check nodes in the factor graph representation of the given code. The modified parity check matrix is designed to promote a passing of correct information into erroneous variable nodes in the trapping set. Theoretical properties of the proposed trapping-set-breaking technique have been established based on the notion of the improved separation for the trapped variable nodes. Simulation results show that the proposed collaborative LDPC decoding scheme switching between the two decoding modes back and forth effectively breaks dominant trapping sets of various known types of regular and irregular LDPC codes.

IEEE Transactions on CommunicationsNov 5, 201517 citations

Techniques for improving ldpc codes performance

Esa Alghonaim

Low Density Parity Check (LDPC) codes are considered to be one of the best classes of error-correcting codes. This thesis deals with two major issues in LDPC codes: decoder design to enhance error correction performance and efficient decoder implementation. Five techniques have been introduced in this thesis. First, an efficient platform for LDPC code design and performance evaluation is developed. This platform implements parallel simulation algorithms to efficiently evaluate the performance of the proposed algorithms for LDPC decoders and code design. Second, an innovative technique is introduced to improve the performance of LDPC decoding in the error-floor region. Special structures in the code graph, called trapping sets, are considered to be the major source of decoding errors in the error-floor region. The proposed technique is based on eliminating the negative effect of trapping sets during LDPC decoding. As a third contribution, a novel approach to improve the decoder performance and/or throughput is introduced. This approach is based on utilizing LDPC decoder idle times by introducing two queues: one at the decoder input and the other at the decoder output. This architecture enables the decoder to run extra iterations beyond the conventional maximum allowable iterations. The fourth proposed technique reduces the bit error rate of LDPC decoders. This technique is based on tracking the number of failed parity check equations in the intermediate decoding iterations, rather than only relying on the final decoder output (after reaching the maximum number of iterations). The last proposed technique deals with the construction of interconnect efficient fully-parallel LDPC codes with high error correction performance. Fully-parallel implementation is very hard due to the complexity of processing elements interconnections. The proposed technique is based on constructing LDPC codes with less complex interconnections and with low impact on the error correction performance. This goal is achieved by putting a constraint on the maximum connection length between any two processing elements.

Jan 1, 20080 citations

Generalized Belief Propagation to break trapping sets in LDPC codes

Jean-Christophe Sibel, Sylvain Reynal, David Declercq

Abstract—In this paper, we focus on the Generalized Belief Propagation (GBP) algorithm to solve trapping sets in Low-Density Parity-Check (LDPC) codes. Trapping sets are topo-logical structures in Tanner graphs of LDPC codes that are not correctly decoded by Belief Propagation (BP), leading to exhibit an error-floor in the Bit-Error Rate (BER). Stemming from statistical physics of spin glasses, GBP consists in passing messages between clusters of Tanner graph nodes in another graph called the region-graph. Here, we introduce a specific clustering of nodes, based on a novel local loopfree principle, that breaks trapping sets such that the resulting region-graph is locally loopfree. We then construct a hybrid decoder made of BP and GBP that proves to be a powerful decoder as it clearly improves the BER and defeats the error-floor. Index Terms—LDPC codes, Generalized Belief Propagation, trapping sets, error-floor, local clustering

Feb 3, 20140 citations