Repository logo
 

Large Deviations Behavior of the Logarithmic Error Probability of Random Codes

Accepted version
Peer-reviewed

Type

Article

Change log

Abstract

This work studies the deviations of the error exponent of the constant composition code ensemble around its expectation, known as the error exponent of the typical random code (TRC). In particular, it is shown that the probability of randomly drawing a codebook whose error exponent is smaller than the TRC exponent is exponentially small; upper and lower bounds for this exponent are given, which coincide in some cases. In addition, the probability of randomly drawing a codebook whose error exponent is larger than the TRC exponent is shown to be double–exponentially small; upper and lower bounds to the double–exponential exponent are given. The results suggest that codebooks whose error exponent is larger than the error exponent of the TRC are extremely rare. The key ingredient in the proofs is a new large deviations result of type class enumerators with dependent variables.

Description

Keywords

Decoding, Encoding, Monte Carlo methods, Random variables, Error probability, Mutual information, Viterbi algorithm, Error exponent, expurgated exponent, large deviations, typical random code

Journal Title

IEEE Transactions on Information Theory

Conference Name

Journal ISSN

0018-9448
1557-9654

Volume Title

66

Publisher

Institute of Electrical and Electronics Engineers (IEEE)

Rights

All rights reserved
Sponsorship
European Research Council (725411)