The trapping redundancy of a linear code is the number of rows of a smallest parity-check matrix such that no submatrix forms an (a, b)-trapping set. This concept was first introduced in the context of low-density parity-check (LDPC) codes in an attempt to estimate the number of redundant rows in a parity-check matrix suitable for iterative decoding. Essentially the same concepts appear in other contexts as well such as robust syndrome extraction for quantum error correction. Among the known upper bounds on the trapping redundancy, the strongest one was proposed by employing a powerful tool in probabilistic combinatorics, called the Lovász Local Lemma. Unfortunately, the proposed proof invoked this tool in a situation where an assumption made in the lemma does not necessarily hold. Hence, although we do not doubt that nonetheless the proposed bound actually holds, for it to be a mathematical theorem, a more rigorous proof is desired. Another disadvantage of the proposed bound is that it is only applicable to (a, b)-trapping sets with rather small a. Here, we give a more general and sharper upper bound on trapping redundancy by making mathematically more rigorous use of probabilistic combinatorics without relying on the lemma. Our bound is applicable to all potentially avoidable (a, b)-trapping sets with a smaller than the minimum distance of a given linear code, while being generally much sharper than the bound through the Lovász Local Lemma. In fact, our upper bound is sharp enough to exactly determine the trapping redundancy for many cases, thereby providing precise knowledge in the form of a more general bound with mathematical rigor.
We generalize the notion of the stopping redundancy in order to study the smallest size of a trapping set in Tanner graphs of linear block codes. In this context, we introduce the notion of the trapping redundancy of a code, which quantifies the relationship between the number of redundant rows in any parity-check matrix of a given code and the size of its smallest trapping set. Trapping sets with certain parameter sizes are known to cause error-floors in the performance curves of iterative belief propagation (BP) decoders, and it is therefore important to identify decoding matrices that avoid such sets. Bounds on the trapping redundancy are obtained using probabilistic and constructive methods, and the analysis covers both general and elementary trapping sets. Numerical values for these bounds are computed for the [2640, 1320] Margulis code and the class of projective geometry codes, and compared with some new code-specific trapping set size estimates.
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.
The l-th stopping redundancy ρι(C) of the binary [n, k, d] code C, 1 ≤ l ≤ d, is defined as the minimum number of rows in the parity-check matrix of C, such that the smallest stopping set is of size at least l. The stopping redundancy ρ(C) is defined as ρd(C). In this work, we improve on the probabilistic analysis of stopping redundancy, proposed by Han, Siegel and Vardy, which yields the best bounds known today. In our approach, we judiciously select the first few rows in the parity-check matrix, and then continue with the probabilistic method. By using similar techniques, we improve also on the best known bounds on ρι(C), for 1 ≤ l ≤ d. Our approach is compared to the existing methods by numerical computations.
It is now well known that the performance of a linear code
C under iterative decoding on a binary erasure channel (and other channels) is determined by the size of the smallest stopping set in the Tanner graph for
C. Several recent papers refer to this parameter as the \emph{stopping distance}
s of
C. This is somewhat of a misnomer since the size of the smallest stopping set in the Tanner graph for
C depends on the corresponding choice of a parity-check matrix. It is easy to see that
s≤d, where
d is the minimum Hamming distance of
C, and we show that it is always possible to choose a parity-check matrix for
C (with sufficiently many dependent rows) such that
s=d. We thus introduce a new parameter, termed the \emph{stopping redundancy} of
C, defined as the minimum number of rows in a parity-check matrix
H for
C such that the corresponding stopping distance
s(H) attains its largest possible value, namely
s(H)=d. We then derive general bounds on the stopping redundancy of linear codes. We also examine several simple ways of constructing codes from other codes, and study the effect of these constructions on the stopping redundancy. Specifically, for the family of binary Reed-Muller codes (of all orders), we prove that their stopping redundancy is at most a constant times their conventional redundancy. We show that the stopping redundancies of the binary and ternary extended Golay codes are at most 35 and 22, respectively. Finally, we provide upper and lower bounds on the stopping redundancy of MDS codes.
It is now well known that the performance of a linear code Copf under iterative decoding on a binary erasure channel (and other channels) is determined by the size of the smallest stopping set in the Tanner graph for Copf. Several recent papers refer to this parameter as the stopping distance s of Copf. This is somewhat of a misnomer since the size of the smallest stopping set in the Tanner graph for Copf depends on the corresponding choice of a parity-check matrix. It is easy to see that s les d, where d is the minimum Hamming distance of Copf, and we show that it is always possible to choose a parity-check matrix for Copf (with sufficiently many dependent rows) such that s=d. We thus introduce a new parameter, the stopping redundancy of Copf, defined as the minimum number of rows in a parity- check matrix H for Copf such that the corresponding stopping distance s(H) attains its largest possible value, namely, s(H)=d. We then derive general bounds on the stopping redundancy of linear codes. We also examine several simple ways of constructing codes from other codes, and study the effect of these constructions on the stopping redundancy. Specifically, for the family of binary Reed-Muller codes (of all orders), we prove that their stopping redundancy is at most a constant times their conventional redundancy. We show that the stopping redundancies of the binary and ternary extended Golay codes are at most 34 and 22, respectively. Finally, we provide upper and lower bounds on the stopping redundancy of MDS codes
Linear block codes over noisy channels causing both erasures and errors can be decoded by deleting the erased symbols and decoding the resulting vector with respect to a punctured code and then retrieving the erased symbols. This can be accomplished using separating parity-check matrices. For a given maximum number of correctable erasures, such matrices yield parity-check equations that do not check any of the erased symbols and which are sufficient to characterize all punctured codes corresponding to this maximum number of erasures. Separating parity-check matrices typically have redundant rows. An upper bound on the minimum number of rows in separating parity-check matrices, which is called the separating redundancy, is derived which proves that the separating redundancy tends to behave linearly as a function of the code length.