On a binary erasure channel (BEC) with erasing probability e, the performance of a binary linear code is determined by the incorrigible sets of the code. The incorrigible set distribution (ISD) {Ii}i=0nenumerates the number of incorrigible sets with size i of the code. The probability of unsuccessful decoding under optimal decoding for the code could be formulated by the ISD and ∈. In this paper, we determine the ISDs for the Simplex codes, the Hamming codes, the first order Reed-Muller codes, and the extended Hamming codes, which are some Reed-Muller codes or their shortening or puncturing versions. Then, we show that the probability of unsuccessful decoding under optimal decoding for any binary linear code is monotonously non-decreasing on ∈ in the interval [0,1].
In this paper, we study the list decoding error probability of a linear code over the erasure channel. The notion of L-incorrigible sets of a linear code is introduced to characterize its performance under list decoding. The L-incorrigible set distribution of a linear code can also be used to completely determine its decoding error probability under maximum likelihood decoding over the erasure channel. Furthermore, we show that the L-incorrigible set distribution of a linear code can be determined by its support weight distribution. Finally, the error exponent of the unsuccessful decoding probability under optimal decoding for the ensemble of all [n, nR] linear codes is determined.
In this paper, we study the decoding error probability of linear codes over the erasure channel under the list decoding. The notion of the qℓ-incorrigible sets of linear codes is introduced to characterize its decoding error probability under the list decoding or the maximum likelihood decoding. By calculating the qℓ-incorrigible set distributions, the decoding error probability of a linear code over the erasure channel under the list decoding or the maximum likelihood decoding is expressed by its support weight distributions. For the ensemble of all [n,k] linear codes, the average decoding error probability under the maximum likelihood decoding and the average unsuccessful decoding probability under unambiguous decoding are determined. Furthermore, the error exponent of the average unsuccessful decoding probability under the unambiguous decoding is determined for the ensemble of all [n,nR] linear codes.
Stopping sets and stopping set distribution of an low-density parity-check code are used to determine the performance of this code under iterative decoding over a binary erasure channel (BEC). Let
C be a binary
[n,k] linear code with parity-check matrix
H, where the rows of
H may be dependent. A stopping set
S of
C with parity-check matrix
H is a subset of column indices of
H such that the restriction of
H to
S does not contain a row of weight one. The stopping set distribution
{Ti(H)}i=0n enumerates the number of stopping sets with size
i of
C with parity-check matrix
H. Note that stopping sets and stopping set distribution are related to the parity-check matrix
H of
C. Let
H∗ be the parity-check matrix of
C which is formed by all the non-zero codewords of its dual code
C⊥. A parity-check matrix
H is called BEC-optimal if
Ti(H)=Ti(H∗),i=0,1,...,n and
H has the smallest number of rows. On the BEC, iterative decoder of
C with BEC-optimal parity-check matrix is an optimal decoder with much lower decoding complexity than the exhaustive decoder. In this paper, we study stopping sets, stopping set distributions and BEC-optimal parity-check matrices of binary linear codes. Using finite geometry in combinatorics, we obtain BEC-optimal parity-check matrices and then determine the stopping set distributions for the Simplex codes, the Hamming codes, the first order Reed-Muller codes and the extended Hamming codes.
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
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