In this paper, we introduce stopping sets for iterative row-column decoding of product codes using optimal constituent decoders. When transmitting over the binary erasure channel (BEC), iterative row-column decoding of product codes using optimal constituent decoders will either be successful, or stop in the unique maximum-size stopping set that is contained in the (initial) set of erased positions. Let Cpdenote the product code of two binary linear codes Ccand Crof minimum distances dc and drand second generalized Hamming weights d2(Cc) and d2(Cr), respectively. We show that the size sminof the smallest noncode- word stopping set is at least mm(drd2(Cc),dcd2(Cr)) > drdc, where the inequality follows from the Griesmer bound. If there are no codewords in Cpwith support set S, where S is a stopping set, then S is said to be a noncodeword stopping set. An immediate consequence is that the erasure probability after iterative row-column decoding using optimal constituent decoders of (finite-length) product codes on the BEC, approaches the erasure probability after maximum-likelihood decoding as the channel erasure probability decreases. We also give an explicit formula for the number of noncodeword stopping sets of size smin, which depends only on the first nonzero coefficient of the constituent (row and column) first and second support weight enumerators, for the case when d2(Cr)rand d2(Cc)c. Finally, as an example, we apply the derived results to the product of two (extended) Hamming codes and two Golay codes.
In this paper, we introduce stopping sets for iterative row-column decoding of product codes using optimal constituent decoders. When transmitting over the binary erasure channel (BEC), iterative row-column decoding of product codes using optimal constituent decoders will either be successful, or stop in the unique maximum-size stopping set that is contained in the (initial) set of erased positions. Let Cpdenote the product code of two binary linear codes Ccand Crof minimum distances dc and drand second generalized Hamming weights d2(Cc) and d2(Cr), respectively. We show that the size sminof the smallest noncode- word stopping set is at least mm(drd2(Cc),dcd2(Cr)) > drdc, where the inequality follows from the Griesmer bound. If there are no codewords in Cpwith support set S, where S is a stopping set, then S is said to be a noncodeword stopping set. An immediate consequence is that the erasure probability after iterative row-column decoding using optimal constituent decoders of (finite-length) product codes on the BEC, approaches the erasure probability after maximum-likelihood decoding as the channel erasure probability decreases. We also give an explicit formula for the number of noncodeword stopping sets of size smin, which depends only on the first nonzero coefficient of the constituent (row and column) first and second support weight enumerators, for the case when d2(Cr)rand d2(Cc)c. Finally, as an example, we apply the derived results to the product of two (extended) Hamming codes and two Golay 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.
This paper is devoted to the finite-length analysis of turbo decoding over the binary erasure channel (BEC). The performance of iterative belief-propagation decoding of low-density parity-check (LDPC) codes over the BEC can be characterized in terms ofstopping sets. We describe turbo decoding on the BEC which is simpler than turbo decoding on other channels. We then adapt the concept of stopping sets to turbo decoding and state an exact condition for decoding failure. Apply turbo decoding until the transmitted codeword has been recovered, or the decoder fails to progress further. Then the set of erased positions that will remain when the decoder stops is equal to the unique maximum-sizeturbo stopping setwhich is also a subset of the set of erased positions. Furthermore, we present some improvements of the basic turbo decoding algorithm on the BEC. The proposed improved turbo decoding algorithm has substantially better error performance as illustrated by the given simulation results. Finally, we give an expression for the turbo stopping set size enumerating function under the uniform interleaver assumption, and an efficient enumeration algorithm of small-size turbo stopping sets for a particular interleaver. The solution is based on the algorithm proposed by Garelloet al.in 2001 to compute an exhaustive list of all low-weight codewords in a turbo code.
In the field of Error Correcting Coding (ECC), the concept of ''stopping set'' recently became a hot topic. A stopping set for a parity-check matrix is the set of bits which would cause the iterative decoding progress in Binary Erasure Channel (BEC) to ''stop'' when it is erased. It has already been proved in several papers that the decoding performance under iterative decoding algorithm of any linear block code in BEC is determined by their stopping set performance, in particular, their size and number. And it is commonly assumed by the coding researchers that those codes which have better stopping set performance would also perform better in other channels. In this thesis, the decoding performance of linear block codes, in particular, Hamming Codes, the original LDPC code proposed by Gallager and FG-LDPC codes is studied in Binary Symmetric Channel (BSC) and Additive White Gaussian Noise (AWGN) channel. Three iterative decoding algorithms, respectively Bit-Flipping algorithm, Weighted Bit-Flipping algorithm and Sum Product Algorithm are used. To emphasize the influence of stopping set property, the parity-check matrix for each code is modified by adding linearly dependent rows to the original parity-check matrix, or removing rows from it. These modifications are made in order to change the stopping set property of the codes. The performance of the modified parity-check matrices is thus analyzed, by comparing them to the original ones, using both theoretical analysis and simulation. The results show that the stopping set performance of linear block codes is not a crucial factor to their performances on other channels as it is in BEC. Sometimes the linear block codes of a better stopping set property do perform better in other channels, but sometimes the performance barely changes or even degrades. More precisely, the decoding performance of a certain parity-check matrix is determined by the type of codes, the type of channel and the decoding algorithm, rather than its stopping set property.
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 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.
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.