Ensemble-Tight Second-Order Asymptotics for Guessing-Based Decoding with Abandonment

This paper considers guessing-based decoders with abandonment for discrete memoryless channels in which all codewords have the same composition. This class of decoders rank-orders all input sequences in the type class from “closest” to “farthest” from the channel output and then queries them sequentially in that order for codeword membership. Decoding stops when a codeword is encountered or when a predetermined number of guesses is reached and decoding is abandoned. Ensemble-tight first- and second-order asymptotics are derived for the code rate and abandonment rate. The optimal secondorder region is characterized in terms of the minimum of the second-order code and abandonment rates.