A linear time erasure-resilient code with nearly optimal recovery

Noga Alon, Michael Luby

Research output: Contribution to journalArticlepeer-review

98 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)1732-1736
Number of pages5
JournalIEEE Transactions on Information Theory
Issue number6 PART 1
StatePublished - 1996
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences


  • Erasure-resilient codes
  • Linear time
  • Lossy pocket networks
  • MDS codes
  • Real-time transmission
  • Redundancy encoding
  • Reed-solomon codes


Dive into the research topics of 'A linear time erasure-resilient code with nearly optimal recovery'. Together they form a unique fingerprint.

Cite this