Stopping sets play a crucial role in failure events of iterative decoders over a binary erasure channel (BEC). The ℓth stopping redundancy is the minimum number of rows in the parity-check matrix of a code, which contains no stopping sets of size up to ℓ. In this paper, a notion of coverable stopping sets is defined. In order to achieve maximum-likelihood performance under iterative decoding over the BEC, the parity-check matrix should contain no coverable stopping sets of size ℓ, for 1 ≤ ℓ ≤ n-k, where n is the code length, k is the code dimension. By estimating the number of coverable stopping sets, we obtain upper bounds on the ℓth stopping redundancy, 1 ≤ ℓ ≤ n-k. The bounds are derived for both specific codes and code ensembles. In the range 1 ≤ ℓ ≤ d-1, for specific codes, the new bounds improve on the results in the literature. Numerical calculations are also presented.
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.
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.
We extend the framework for studying the stopping redundancy of a linear block code by introducing and analyzing the stopping redundancy hierarchy.The stopping redundancy hierarchy of a code represents a measure of the trade-off between performance and complexity of iteratively decoding a code used over the binary erasure channel.It is defined as an ordered list of positive integers in which the ith entry, termed the i-th stopping redundancy, corresponds to the minimum number of rows in any parity-check matrix of the code that has stopping distance at least i.In particular, we derive lower and upper bounds for the i-th stopping redundancy of a code by using probabilistic methods and Bonferroni-type inequalities.Furthermore, we specialize the findings for cyclic codes, and show that parity-check matrices in cyclic form have some desirable redundancy properties.We also propose to investigate the influence of the generator codeword of the cyclic parity-check matrix on its stopping distance properties.
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
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, termed 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
We investigate the stopping redundancy hierarchy of linear block codes and its connection to permutation decoding techniques. An element in the ordered list of stopping redundancy values represents the smallest number of possibly linearly dependent rows in any parity-check matrix of a code that avoids stopping sets of up to a given size. Redundant parity-check equations can be shown to have a similar effect on decoding performance as permuting the coordinates of the received codeword according to a selected set of automorphisms of the code. Based on this finding we develop new decoding strategies for data transmission over the binary erasure channel that combine iterative message passing and permutation decoding in order to avoid errors confined to stopping sets. We also introduce the notion of s-SAD sets, containing the smallest number of automorphisms of a code with the property that they move any set of not more than s erasures into positions that do not correspond to stopping sets within a judiciously chosen parity-check matrix.