Linear time erasure codes with nearly optimal recovery (extended abstract)

Noga Alon, Jeff Edmonds, Michael Luby

Research output: Contribution to journalConference article

40 Scopus citations

Abstract

An (n, c, l, r)-erasure 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 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)512-519
Number of pages8
JournalAnnual Symposium on Foundations of Computer Science - Proceedings
StatePublished - Dec 1 1995
Externally publishedYes
EventProceedings of the 1995 IEEE 36th Annual Symposium on Foundations of Computer Science - Milwaukee, WI, USA
Duration: Oct 23 1995Oct 25 1995

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

Fingerprint Dive into the research topics of 'Linear time erasure codes with nearly optimal recovery (extended abstract)'. Together they form a unique fingerprint.

  • Cite this