A linear time erasure-resilient code with nearly optimal recovery

We develop an efficient scheme that produces an encoding of a given message such that the message can be decoded from any portion of the encoding that is approximately equal to the length of the message. More precisely, an (n, c, I, r)-erasureresilient code consists of an encoding algorithm and a decoding algorithm with the following properties. The encoding algorithm produces a set of /-bit packets of total length en from an ra-bit message. The decoding algorithm is able to recover the message from any set of packets whose total length is r, i.e., from any set of r /l packets. We describe erasure-resilient codes where both the encoding and decoding algorithms run in linear time and where r is only slightly larger than n.