List Decoding—Random Coding Exponents and Expurgated Exponents

Abstract

Some new results are derived concerning random coding error exponents and expurgated exponents for list decoding with a deterministic list-size L. Two asymptotic regimes are considered, the fixed list-size regime, where L is fixed independently of the block length n, and exponential list size, where L grows exponentially with n. We first derive a general upper bound on the list-decoding average error probability, which is suitable for both regimes. This bound leads to more specific bounds in the two regimes. In the fixed list-size regime, the bound is related to known bounds and we establish its exponential tightness. In the exponential list-size regime, we establish the achievability of the well-known sphere packing lower bound. An immediate byproduct of our analysis in both regimes is the universality of the maximum mutual information list decoder in the error exponent sense. Finally, we consider expurgated bounds at low rates, both using Gallager's approach and Csiszár-Körner-Marton approach, which is equivalent for the optimal input assignment. The latter expurgated bound, which involves the notion of multi-information, is also modified to apply to continuous alphabet channels, and in particular, to the Gaussian memoryless channel, where the expression of the expurgated bound becomes quite explicit.