The Use of Prime Residues as a Block Erasure Code With Linear
Decoding Time Source: Adobe Systems It is well known that prime
residues can be used as a forward error correction code. The
Chinese remainder theorem can be used to reconstruct the
original data in "Almost" linear time. The authors show that
when formulated as a block erasure code, prime residues can be
decoded in exactly linear time. The only requirement is that
some kind of packet sequence numbers accompanies the data. When
formulated this way, prime residue encoding forms a non-
systematic block erasure code that is asymptotically MDS
(maximum distance separable) as the word size is increased. The
uses for this code include digital fountain implementation,
efficient payload distribution for digital watermarking, and
more.