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. ve 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 ) log 2 3 + 1 , which is a major improvement on a previous construction showing that F ( r , 3 ) ⩽ 1 + 1 2 r ( r − 1 ) . course of this work we encountered the following problem that may be of independent interest: what is the smallest size of a collection C ⊆ F 2 n such that, given any set of s independent vectors in F 2 n , 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.