Moderate Deviations And Exact Asymptotics In Channel Coding

Abstract

Investigation of the data rate, blocklength and error probability interplay for the optimum block code(s) on a discrete memoryless channel is a fundamental problem of information theory. Because of the intricacy of the problem, it is ubiquitous to allow blocklength to grow unboundedly, which, in turn, gives informative optimality results. Although there are classical asymptotic regimes to investigate this interplay, they have certain limitations. This thesis is about two new asymptotics in channel coding, proposed to address these limitations. In moderate deviations, we consider the optimal error performance of the sequence of codes with rates increasing to the capacity with a speed between the classical asymptotic regimes of error exponents and normal approximation and prove that error probability vanishes sub-exponentially fast with a rate related to the dispersion of the channel. This conclusion is in contrast with the classical asymptotic regimes, in which either error probability vanishes or rate increases to the capacity, but not simultaneously. We believe that this contrast makes moderate deviations more relevant to practical code design, since the goal of the channel coding is to attain a rate that is close to capacity and an error probability that is close to zero. In exact asymptotics, we concentrate on the sub-exponential factors of the wellknown exponentially decaying bounds on the error probability to improve their orders. The reason of this quest is the fact that the exponent of these bounds vanishes as rate approaches the capacity, which, in turn, makes the sub-exponential terms to play a sig- nificant role in the approximation of the error probability for this range of rates. The sharpened orders of the sub-exponential factors of these refinements are close to each other in general, and are equal for symmetric channels. Moreover, we reveal a phase transition of the optimal order of the pre-factor for this class of channels.