2006/07/07 by Jos H. Weber, Khaled Abdel-Ghaffar, Weber, Jos H. +2
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Coding theory and cryptography #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.cs/0607024
8 pages, submitted to IEEE Transactions on Information Theory
arxiv created 2006/07/07 · openalex publication_date 2006/07/07 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The performance of iterative decoding techniques for linear block codes correcting erasures depends very much on the sizes of the stopping sets associated with the underlying Tanner graph, or, equivalently, the parity-check matrix representing the code. In this paper, we introduce the notion of dead-end sets to explicitly demonstrate this dependency. The choice of the parity-check matrix entails a trade-off between performance and complexity. We give bounds on the complexity of iterative decoders achieving optimal performance in terms of the sizes of the underlying parity-check matrices. Further, we fully characterize codes for which the optimal stopping set enumerator equals the weight enumerator.