A generic (r,m)-erasure correcting set is a collection of vectors in F2rwhich can be used to generate, for each binary linear code of codimension r, a collection of parity check equations that enables iterative decoding of all correctable erasure patterns of size at most m. That is to say, the only stopping sets of size at most m for the generated parity check equations are the erasure patterns for which there is more than one manner to fill in the erasures to obtain a codeword. We give an explicit construction of generic (r,m)-erasure correcting sets of cardinality Sigmai=0m-1(ir-1). Using a random-coding-like argument, we show that for fixed m, the minimum size of a generic (r,m)-erasure correcting set is linear in r
Recently there has been interest in the construction of small parity-check sets for iterative decoding of the Hamming code with the property that each uncorrectable (or stopping) set of size three is the support of a codeword and hence uncorrectable anyway. Here we reformulate and generalize the problem and improve on this construction. We show that a parity-check collection that corrects all correctable erasure patterns of size m for the Hamming code with codimension r provides, in fact, for all codes of codimension r a corresponding "generic" parity-check collection with this property. This leads in a natural way to a necessary and sufficient condition for such generic parity-check collections. We use this condition to construct a generic parity-check collection for codes of codimension r correcting all correctable erasure patterns of size at most m, for all r and mlesr, thus generalizing the known construction for m=3. Then we discuss optimality of our construction and show that it can be improved for mges3 and r large enough. Finally, we discuss some directions for further research
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.
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.
Most decoding algorithms of linear codes, in general, are designed to correct or detect errors. However, many channels cause erasures in addition to errors. In principle, decoding over such channels can be accomplished by deleting the erased symbols and decoding the resulting vector with respect to a punctured code. For any given linear code and any given maximum number of correctable erasures, we introduce parity-check matrices yielding 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. This allows for the separation of erasures from errors to facilitate decoding. The parity-check matrices typically have redundant rows. We give several constructions of such matrices and prove general bounds on their minimum sizes.
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.
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.