IEEE International Symposium on Information Theory (ISIT)

Stopping sets in codes from designs

Navin Kashyap, Alexander Vardy

Published Jan 1, 2003• 50 citations

Abstract

The size of the smallest stopping set in LDPC codes helps in analyzing their performance under iterative decoding, just a minimum distance helps in analyzing the performance under maximum likelihood decoding. We study stopping sets in LDPC codes arising from 2-designs, in particular LDPC codes derived from projective and Euclidean geometries. We derive upper and lower bounds on the size of the smallest stopping set in such codes, and provide examples of codes that achieve these bounds.

DOI: 10.1109/isit.2003.1228136

Related papers

On the stopping distance of finite geometry ldpc codes

Shu‐Tao Xia, Fang‐Wei Fu

In this letter, the stopping sets and stopping distance of finite geometry LDPC (FG-LDPC) codes are studied. It is known that FG-LDPC codes are majority-logic decodable and a lower bound on the minimum distance can be thus obtained. It is shown in this letter that this lower bound on the minimum distance of FG-LDPC codes is also a lower bound on the stopping distance of FG-LDPC codes, which implies that FG-LDPC codes have considerably large stopping distance. This may explain in one respect why some FG-LDPC codes perform well with iterative decoding in spite of having many cycles of length 4 in their Tanner graphs.

IEEE Communications LettersMay 1, 200629 citations

Small stopping sets in projective low-density parity-check codes

Yuichiro Fujiwara, Yu Tsunoda

It is known that redundant parity-check equations can improve the performance of an LDPC code by reducing the number of harmful substructures in the parity-check matrix. However, it is a difficult problem to design a parity-check matrix in such a way that it avoids substructures that are known to be harmful to iterative decoding while keeping the number of redundant parity-check equations moderate and ensuring other desirable properties. We explicitly give redundant parity-check matrices for cyclic regular LDPC codes of length n and minimum distance d ~ √n in which there are only n parity-check equations but no stopping sets of size d+1 or smaller except for those that correspond to the nonzero codewords of the smallest weight. We do this by showing that the well-known projective LDPC codes from the incidence matrices of projective planes PG(2, q) with q even have this property. This result may give insight into how the small number of redundant parity-check equations in the geometric LDPC codes may be contributing to the good performance reported in the literature. We also give a slightly improved upper bound on the size of a smallest generic erasure correcting set.

IEEE Information Theory Workshop (ITW)Aug 1, 20190 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

On the Stopping Distance and Stopping Redundancy of Finite Geometry LDPC Codes

Haiyang LIU, Xinggang Lin, Lianrong Ma +1 more

The stopping distance and stopping redundancy of a linear code are important concepts in the analysis of the performance and complexity of the code under iterative decoding on a binary erasure channel. In this paper, we studied the stopping distance and stopping redundancy of Finite Geometry LDPC (FG-LDPC) codes, and derived an upper bound of the stopping redundancy of FG-LDPC codes. It is shown from the bound that the stopping redundancy of the codes is less than the code length. Therefore, FG-LDPC codes give a good trade-off between the performance and complexity and hence are a very good choice for practical applications.

IEICE Transactions on Fundamentals of Electronics Communications and Computer SciencesAug 1, 20084 citations

Minimum distance and pseudodistance lower bounds for generalised LDPC codes

Christine A. Kelley

Two different ways of obtaining generalised low-density parity-check (LDPC) codes are considered. Lower bounds on the minimum distance, stopping distance and pseudodistance are derived for these codes using graph-based analysis. These bounds are generalisations of Tanner's bit- and parity-oriented bound for simple (LDPC) codes. The new bounds are useful in predicting the performance of generalised LDPC codes under maximum-likelihood decoding, graph-based iterative decoding and linear programming decoding, and rely on the connectivity of the Tanner graph.

International Journal of Information and Coding TheoryJan 1, 20101 citation

Performance of low-density parity-check codes with linear minimum distance

Hossein Pishro-Nik, Faramarz Fekri

This paper studies the performance of the iterative decoding of LDPC code ensembles that have linear typical minimum distance and stopping set size. We first obtain a lower bound on the achievable rates of these ensembles over MBIOS channels. Then, we give upper bounds on the rate of LDPC codes with linear minimum distance, given their right degree distribution over the BEC.

IEEE International Symposium on Information Theory (ISIT)Dec 23, 20040 citations