IET Communications

Coset graphs for low-density parity check codes: performance on the binary erasure channel

Josef Lauri, Cen Jung Tjhai

Published Mar 25, 2011• 0 citations

Abstract

The authors show that a popular way of constructing quasi-cyclic low-density parity check (LDPC) codes is a special case of a construction which is common in graph theory and group theory. It is shown that a generalisation of this construction as coset graphs produces (dv, dc)-regular LDPC codes that have an advantage in terms of the minimum stopping set size compared to quasi-cyclic LDPC codes. A (dv, dc)-regular quasi-cyclic LDPC code cannot have minimum stopping set size larger than (dv+1)!. However, by using coset graphs, a (3, 5)-regular LDPC code with minimum stopping set size of 28 and a (3, 4)-regular LDPC code with minimum stopping set size larger than 32 have been obtained. In addition, the idea of coset graphs also provides a compact algebraic way of describing bipartite graph and the associated parity-check matrix of an LDPC code. Simulation results of iterative decoding of the coset graphs LDPC codes over the binary erasure channel show that some of the codes converge well and based on the truncated stopping set distributions of the codes, which are exhaustively and efficiently enumerated, the error-floor of the codes at low probability of erasure is estimated.

DOI: 10.1049/iet-com.2010.0220

Related papers

Small Stopping Sets Counting Methods for Quasi-cyclic Low Density Parity Check Codes Based on the Cycle Theory

Yang Xiao

It is well known that performance of low-density parity check (LDPC) codes under iterative decoding is determined by the size of the smallest stopping sets in the Tanner graph.To solve this problem,we propose necessary and sufficient conditions of quasi-cyclic LDPC codes without small stopping sets.According to the proposed theorems and corollaries,we can design good QC-LDPC codes without small stopping sets which outperforms random LDPC codes by SNR =0.3 dB at BER of le-5,and count the number of the small stopping sets.The method can be used effectively to evaluate performance of LDPC codes according to their stopping sets distributions.It can find the number of cycles of LDPC codes which is less complex than existing algorithms.

Jan 1, 20080 citations

An Efficient Algorithm to Find All Small-Size Stopping Sets of Low-Density Parity-Check Matrices

Eirik Rosnes, Øyvind Ytrehus

In this work, we introduce an efficient algorithm to find all stopping sets, of size less than some threshold, of a fixed low-density parity-check (LDPC) matrix. The solution is inspired by the algorithm proposed by Rosnes and Ytrehus in 2005 to find an exhaustive list of all small-size turbo stopping sets in a turbo code. The efficiency of the proposed algorithm is demonstrated by several numerical examples. For instance, we have applied the algorithm to the well-known (3, 5)-regular (155, 64) Tanner code and found all stopping sets of size at most 18 in about 1 min on a standard desktop computer. Also, we have verified that the minimum stopping set size of the (4896, 2474) Ramanujan-Margulis code is indeed 24, and that the corresponding multiplicity is exactly 204. Furthermore, we have applied the algorithm to the IEEE 802.16e LDPC codes and determined the minimum stopping set size and the corresponding multiplicity exactly for these codes. Finally, as an application, we present a greedy algorithm to find a small number of redundant parity checks to add to the original parity-check matrix in order to remove all stopping sets in the corresponding Tanner graph of size less than the minimum distance. An extensive case study of the (155, 64) Tanner code illustrates the usefulness of the algorithm, and we present a 110 times 155 redundant parity-check matrix for this code with no stopping sets of size less than the minimum distance. Simulation results of iterative decoding on the binary erasure channel show performance improvements for low-to-medium erasure probabilities when this redundant parity-check matrix is used for decoding.

IEEE Transactions on Information TheoryAug 24, 200963 citations

Quasi-Cyclic Generalized LDPC Codes With Low Error Floors

Gianluigi Liva, W.E. Ryan, Marco Chiani

In this paper, a novel methodology for designing structured generalized low-density parity-check (G-LDPC) codes is presented. The proposed design results in quasi-cyclic G-LDPC codes for which efficient encoding is feasible through shift-register-based circuits. The structure imposed on the bipartite graphs, together with the choice of simple component codes, leads to a class of codes suitable for fast iterative decoding. A pragmatic approach to the construction of G-LDPC codes is proposed. The approach is based on the substitution of check nodes in the protograph of a low-density parity-check code with stronger nodes based, for instance, on Hamming codes. Such a design approach, which we call low-density parity-check (LDPC) code doping, leads to low-rate quasi-cyclic G-LDPC codes with excellent performance in both the error floor and waterfall regions on the additive white Gaussian noise channel.

IEEE Transactions on CommunicationsDec 1, 20079 citations

Finding Small Stopping Sets in the Tanner Graphs of LDPC Codes

Gerd Richter

The performance of low-density parity-check (LDPC) codes over the binary erasure channel for a low erasure probability is limited by small stopping sets. The frame error rate over the additive white Gaussian noise (AWGN) channel for a high signal-to-noise ratio is limited by small trapping sets and by the minimum distance of the LDPC code, which is equal to the codeword with the minimal Hamming weight. In this paper, we present a simple and fast algorithm based on the error impulse method to find small stopping sets in the Tanner graphs of LDPC codes. Since a codeword with small Hamming weight can be represented by a special stopping set, the algorithm can also be used to find the minimum distance of LDPC codes. Furthermore, we use the size of the small stopping sets and the minimum distance of the code to calculate asymptotic performance bounds for LDPC codes transmitted over the binary erasure and the AWGN channel, respectively and compare the bounds with simulations. 1

Apr 3, 200627 citations

On the probabilistic computation of the stopping redundancy of LDPC codes

Masanori Hirotomo, Yoshiho Konishi, Masakatu Morii

On the binary erasure channel (BEC), the performance of low-density parity-check (LDPC) codes decoded by iterative algorithms is estimated by the small stopping sets in the codes. The size of smallest stopping set is called the stopping distance. Since it depends on the structure of parity-check matrix for the code, we can construct the parity-check matrix by adding dependent rows so that the stopping distance is equal to the minimum distance. The stopping redundancy is defined as the smallest number of rows in such a parity-check matrix. In this paper, we propose a probabilistic algorithm for computing the stopping redundancy of LDPC codes. Additionally, we show numerical results of computing the stopping redundancy of (155,64), (504,252) and (1008,504) LDPC codes.

IEEE International Symposium on Information Theory (ISIT)Jun 1, 20091 citation

Improved Stopping Set Elimination by Parity-Check Matrix Extension of LDPC Codes

Saejoon Kim, Jun Heo, Hyuncheol Park

Stopping sets associated with a parity-check matrix of low-density parity-check codes limit the performance of iterative decoding over the binary erasure channel. In this letter, we propose a parity-check matrix extension scheme that eliminates stopping sets of small sizes. The results show that our proposed scheme provides significant performance improvement compared to previously known parity-check matrix extension schemes.

IEEE Communications LettersApr 6, 20115 citations