2010/03/01 by Yong Jiang, Shu-Tao Xia, Jiang, Yong +5
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Cooperative Communication and Network Coding #DNA and Biological Computing #Error Correcting Code Techniques #FOS: Computer and information sciences #Information Theory (cs.IT) #cs.IT #math.IT
paper · pdf · doi:10.48550/arxiv.1003.0367
33 pages, submitted to IEEE Trans. Inform. Theory, Feb. 2010
arxiv created 2010/03/01 · openalex publication_date 2010/03/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.