Coding over an erasure channel with a large alphabet size

Abstract

An erasure channel with a fixed alphabet size q, where q Gt 1, is studied. It is proved that over any erasure channel (with or without memory), <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">maximum</i> <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">distance</i> <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">separable</i> (MDS) codes achieve the minimum probability of error (assuming maximum likelihood decoding). Assuming a memoryless erasure channel, the error exponent of MDS codes are compared with that of random codes. It is shown that the envelopes of these two exponents are identical for rates above the critical rate. Noting the optimality of MDS codes, it is concluded that random coding is exponentially optimal as long as the block size N satisfies N < q + 1.