The Use of Prime Residues as a Block Erasure Code With Linear Decoding Time

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.