2006/06/06 by Henk D. L. Hollmann, Hollmann, Henk D. L., Ludo Tolhuizen +2
Biochemistry, Genetics and Molecular Biology · Computer Science · Engineering · Mathematics · #Advanced Wireless Communication Techniques #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/0606026
Accepted for publication in Proc Int Symposium on Information Theory 2006, ISIT 06
arxiv created 2006/06/06 · openalex publication_date 2006/06/06 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A generic (r,m)-erasure correcting set is a collection of vectors in \bF2r which can be used to generate, for each binary linear code of codimension r, a collection of parity check equations that enables iterative decoding of all correctable erasure patterns of size at most m. That is to say, the only stopping sets of size at most m for the generated parity check equations are the erasure patterns for which there is more than one manner to fill in theerasures to obtain a codeword. We give an explicit construction of generic (r,m)-erasure correcting sets of cardinality ∑i=0m-1 r-1\choose i. Using a random-coding-like argument, we show that for fixed m, the minimum size of a generic (r,m)-erasure correcting set is linear in r. Keywords: iterative decoding, binary erasure channel, stopping set