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.
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.
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.
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.
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.
In this paper, we study the minimum/stopping distance of array low-density parity-check (LDPC) codes. An array LDPC code is a quasi-cyclic LDPC code specified by two integers q and m, where q is an odd prime and m q. In the literature, the minimum/stopping distance of these codes (denoted by d(q, m) and h(q, m), respectively) has been thoroughly studied for m 5. Both exact results, for small values of q and m, and general (i.e., independent of q) bounds have been established. For m = 6, the best known minimum distance upper bound, derived by Mittelholzer, is d(q, 6) 32. In this paper, we derive an improved upper bound of d(q, 6) 20 and a new upper bound d(q, 7) 24 by using the concept of a template support matrix of a codeword/stopping set. The bounds are tight with high probability in the sense that we have not been able to find codewords of strictly lower weight for several values of q using a minimum distance probabilistic algorithm. Finally, we provide new specific minimum/stopping distance results for m 7 and low-to-moderate values of q ≤79.
In this work, we study the minimum/stopping distance of array low-density parity-check (LDPC) codes. An array LDPC code is a quasi-cyclic LDPC code specified by two integers q and m, where q is an odd prime and m <= q. In the literature, the minimum/stopping distance of these codes (denoted by d(q,m) and h(q,m), respectively) has been thoroughly studied for m <= 5. Both exact results, for small values of q and m, and general (i.e., independent of q) bounds have been established. For m=6, the best known minimum distance upper bound, derived by Mittelholzer (IEEE Int. Symp. Inf. Theory, Jun./Jul. 2002), is d(q,6) <= 32. In this work, we derive an improved upper bound of d(q,6) <= 20 and a new upper bound d(q,7) <= 24 by using the concept of a template support matrix of a codeword/stopping set. The bounds are tight with high probability in the sense that we have not been able to find codewords of strictly lower weight for several values of q using a minimum distance probabilistic algorithm. Finally, we provide new specific minimum/stopping distance results for m <= 7 and low-to-moderate values of q <= 79.