Linear-Time Binary Codes Correcting Localized Erasures

We consider a communication model over a binary channel in which the transmitter knows which bits of the n-bit transmission are prone to loss in the channel. A possible practical situation in which this can occur is real-time transmission over an Internet link using two-different priorities and sending a part of the message over a low-priority connection. We call this model channel with localized erasures in analogy with localized errors studied earlier in the literature. We present two constructions of binary codes with t (1 + epsilon) check bits, where t = alpha n is the maximal possible number of erasures. One construction is on-line and has complexity O(n . log sup 2 (1/alpha)/epsilon sup 4 alpha sup 2) binary operations for encoding and O(n . log(1/alpha)/epsilon sup 2 alpha ) binary operations for decoding. The other construction is recursive. The encoding/decoding algorithms assume a delay of n bits, i.e., rely on the entire codeword. The encoding/decoding complexity is O(n . log sup 2 (1/ alpha)/epsilon sup 2 alpha sup 2) and O(n . log (1/alpha)/epsilon alpha) binary operations, respectively.