Generic erasure correcting sets: Bounds and constructions

A generic (r,m)-erasure correcting set generates for each binary linear code of codimension r a collection of parity check equations that enables iterative decoding of all potentially correctable erasure patterns of size at most m. As we have shown earlier, such a set essentially is just a parity check collection with this property for the Hamming code of codimension r.We prove non-constructively that for fixed m the minimum size F(r,m) of a generic (r,m)-erasure correcting set is linear in r. Moreover, we show constructively that F(r,3)⩽3(r−1)log23+1, which is a major improvement on a previous construction showing that .In the course of this work we encountered the following problem that may be of independent interest: what is the smallest size of a collection such that, given any set of s independent vectors in , there is a vector c∈C that has inner product 1 with all of these vectors? We show non-constructively that, for fixed s, this number is linear in n.