Stopping set properties determine the iterative decoding performance of any linear block code on the Binary Erasure Channel (BEC). Furthermore, there is a common conception that they are crucial factors on other channels, like the Binary Symmetric Channel (BSC), as well. In order to investigate whether this is true indeed, we study stopping set properties and iterative decoding performance on the BSC of Finite-Geometry Low-Density Parity-Check (FG-LDPC) codes, which have been chosen due to their eectiveness and the good structure of their parity-check matrices (PCMs). Also modied versions of these PCMs are considered. As a rather surprising result, we show that a PCM with better stopping set properties than another PCM of the same code does not necessarily lead a better decoding performance on the BSC. Also, PCMs of the same code with the same stopping set properties, do not always have the same decoding performance on the BSC.
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.
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.
A generalized low-density parity check code (GLDPC) is a low-density parity check code in which the constraint nodes of the code graph are block codes, rather than single parity checks. In this paper, we study GLDPC codes which have BCH or Reed-Solomon codes as subcodes under bounded distance decoding (BDD). The performance of the proposed scheme is investigated in the limit case of an infinite length (cycle free) code used over a binary erasure channel (BEC) and the corresponding thresholds for iterative decoding are derived. The performance of the proposed scheme for finite code lengths over a BEC is investigated as well. Structures responsible for decoding failures are defined and a theoretical analysis over the ensemble of GLDPC codes which yields exact bit and block error rates of the ensemble average is derived. Unfortunately this study shows that GLDPC codes do not compare favorably with their LDPC counterpart over the BEC. Fortunately, it is also shown that under certain conditions, objects identified in the analysis of GLDPC codes over a BEC and the corresponding theoretical results remain useful to derive tight lower bounds on the performance of GLDPC codes over a binary symmetric channel (BSC). Simulation results show that the proposed method yields competitive performance with a good decoding complexity trade-off for the BSC.
This paper investigates decoding of low-density parity-check (LDPC) codes over the binary erasure channel (BEC). We study the iterative and maximum-likelihood (ML) decoding of LDPC codes on this channel. We derive bounds on the ML decoding of LDPC codes on the BEC. We then present an improved decoding algorithm. The proposed algorithm has almost the same complexity as the standard iterative decoding. However, it has better performance. Simulations show that we can decrease the error rate by several orders of magnitude using the proposed algorithm. We also provide some graph-theoretic properties of different decoding algorithms of LDPC codes over the BEC which we think are useful to better understand the LDPC decoding methods, in particular, for finite-length 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 (BP) decoding of low-density parity-check (LDPC) codes over the BEC can be characterized in terms of stopping sets. In the first part 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 until 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 size turbo stopping set which is also a subset of the set of erased positions. In the second part 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
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.