A Neyman-Pearson approach to universal erasure and list decoding

We study communication over an unknown, possibly unreliable, discrete memoryless channel. For such problems, an erasure option at the decoder is desirable. We use constant-composition random codes and propose a generalization of the Maximum Mutual Information decoder. The proposed decoder is parameterized by a weighting function that can be designed to optimize the fundamental tradeoff between undetected-error and erasure exponents. Explicit solutions are identified. The class of functions can be further enlarged to optimize a similar tradeoff for list decoders. The optimal exponents admit simple expressions in terms of the sphere-packing exponent, at all rates below capacity. For small erasure exponents, these expressions coincide with those derived by Forney (1968) for symmetric channels, using Maximum a Posteriori decoding. Thus for those channels at least, ignorance of the channel law is inconsequential.