A linear time erasure-resilient code with nearly optimal recovery

Abstract

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,l,r)-erasure-resilient code consists of an encoding algorithm and a decoding algorithm with the following properties. The encoding algorithm produces a set of l-bit packets of total length cn from an n-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