Linear time erasure codes with nearly optimal recovery
- 19 November 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 512-519
- https://doi.org/10.1109/sfcs.1995.492581
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.Keywords
This publication has 10 references indexed in Scilit:
- Priority encoding transmissionPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Expander codesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Matching nuts and bolts fasterInformation Processing Letters, 1996
- Performance evaluation of Forward Error Correction in ATM networksACM SIGCOMM Computer Communication Review, 1992
- Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphsIEEE Transactions on Information Theory, 1992
- Efficient dispersal of information for security, load balancing, and fault toleranceJournal of the ACM, 1989
- Explicit construction of linear sized tolerant networksDiscrete Mathematics, 1988
- Ramanujan graphsCombinatorica, 1988
- Deterministic simulation in LOGSPACEPublished by Association for Computing Machinery (ACM) ,1987
- Explicit expanders and the Ramanujan conjecturesPublished by Association for Computing Machinery (ACM) ,1986