An XOR-based erasure-resilient coding scheme
Johannes Blömer, Malik Kalfane, Richard M. Karp, Marek Karpiński, Michael G. Luby, David Zuckerman · 1995
An (m; n; b; r)-erasure-resilient coding scheme consists of an encoding algorithm and a decoding algorithm with the following properties. The encoding algorithm produces a set of n packets each containing b bits from a message of m packets containing b bits. The decoding algorithm is able to recover the message from any set of r packets. Erasure-resilient codes have been used to protect real-time traffic sent through packet based networks against packet losses. In this paper we describe a erasure-resilient coding scheme that is based on a version of Reed-Solomon codes and which has the property that r = m: Both the encoding and decoding algorithms run in quadratic time and have been customized to give the first real-time implementations of Priority Encoding Transmission (PET) [2],[1] for medium quality video transmission on Sun SPARCstation 20 workstations. 1 Introduction Most existing and proposed networks are packet based, where a packet is a fixed length indivisible unit of inform...