Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1003.0367

Stopping Set Distributions of Some Linear Codes

Yong Jiang, Shu‐Tao Xia, Fang‐Wei Fu

Published Mar 1, 2010• 0 citations
arXivHTMLPDF

Abstract

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 $\{T_i(H)\}_{i=0}^n$ 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^{\perp}$. A parity-check matrix $H$ is called BEC-optimal if $T_i(H)=T_i(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.

DOI
10.48550/arxiv.1003.0367

Related papers

On the Stopping Distance and the Stopping Redundancy of Codes

Schwartz, Moshe, Alexander Vardy

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 \le 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.

arXiv:cs/0503058•Mar 23, 2005•0 citations

On the stopping distance and the stopping redundancy of codes

M. Schwartz, Alexander Vardy

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

IEEE Transactions on Information Theory•Mar 1, 2006•178 citations

Complete Enumeration of Stopping Sets of Full-Rank Parity-Check Matrices of Hamming Codes

Khaled Abdel-Ghaffar, Jos H. Weber

Stopping sets, and in particular their numbers and sizes, play an important role in determining the performance of iterative decoders of linear codes over binary erasure channels. In the 2004 Shannon Lecture, McEliece presented an expression for the number of stopping sets of size three for a full-rank parity-check matrix of the Hamming code. In this correspondence, we derive an expression for the number of stopping sets of any given size for the same parity-check matrix.

arXiv:cs/0603007•IEEE Transactions on Information Theory•Aug 29, 2007•20 citations

On the stopping distance and the stopping redundancy of codes

M. Schwartz, Alexander Vardy

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

IEEE International Symposium on Information Theory (ISIT)•Jan 1, 2005•27 citations

On the probabilistic computation of the stopping redundancy of LDPC codes

Masanori Hirotomo, Yoshiho Konishi, Masakatu Morii

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.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2009•1 citation

The Stopping Set Property and the Iterative Decoding Perfor- mance of Binary Block Codes on BSC and AWGN Channel

Zhijie Ren

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.

•Sep 26, 2011•1 citation
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 CCC be a binary [n,k][n,k][n,k] linear code with parity-check matrix HHH, where the rows of HHH may be dependent. A stopping set SSS of CCC with parity-check matrix HHH is a subset of column indices of HHH such that the restriction of HHH to SSS does not contain a row of weight one. The stopping set distribution {Ti(H)}i=0n\{T_i(H)\}_{i=0}^n{Ti​(H)}i=0n​ enumerates the number of stopping sets with size iii of CCC with parity-check matrix HHH. Note that stopping sets and stopping set distribution are related to the parity-check matrix HHH of CCC. Let H∗H^{*}H∗ be the parity-check matrix of CCC which is formed by all the non-zero codewords of its dual code C⊥C^{\perp}C⊥. A parity-check matrix HHH is called BEC-optimal if Ti(H)=Ti(H∗),i=0,1,...,nT_i(H)=T_i(H^*), i=0,1,..., nTi​(H)=Ti​(H∗),i=0,1,...,n and HHH has the smallest number of rows. On the BEC, iterative decoder of CCC 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 CCC 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 CCC. Several recent papers refer to this parameter as the \emph{stopping distance} sss of CCC. This is somewhat of a misnomer since the size of the smallest stopping set in the Tanner graph for CCC depends on the corresponding choice of a parity-check matrix. It is easy to see that s≤ds \le ds≤d, where ddd is the minimum Hamming distance of CCC, and we show that it is always possible to choose a parity-check matrix for CCC (with sufficiently many dependent rows) such that s=ds = ds=d. We thus introduce a new parameter, termed the \emph{stopping redundancy} of CCC, defined as the minimum number of rows in a parity-check matrix HHH for CCC such that the corresponding stopping distance s(H)s(H)s(H) attains its largest possible value, namely s(H)=ds(H) = ds(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
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.
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.