Generating parity check equations for bounded-distance iterative erasure decoding
Henk D. L. Hollmann, Ludo Tolhuizen · 2006
A generic (r,m)-erasure correcting set is a collection of vectors in F2rwhich 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 the erasures to obtain a codeword. We give an explicit construction of generic (r,m)-erasure correcting sets of cardinality Sigmai=0m-1(ir-1). 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