Channel coding: non-asymptotic fundamental limits

Noise is an inalienable property of all communication systems appearing in nature. Such noise acts against the very purpose of communication, that is delivery of a data to the destination with minimal possible distortion. This creates a problem that has been addressed by various disciplines over the past century. In particular, information theory studies the question of the maximum possible rate achievable by an ideal system under certain assumptions regarding the noise generation and structural design constraints. The study of such questions, initiated by Claude Shannon in 1948, has typically been carried out in the asymptotic limit of an infinite number of signaling degrees of freedom (blocklength). Such a regime corresponds to the regime of laws of large numbers, or more generally ergodic limits, in probability theory. However, with the ever increasing demand for ubiquitous access to real time data, such as audio and video streaming for mobile devices, as well as the advent of modern sparse graph codes, one is interested in describing fundamental limits non-asymptotically, i.e. for blocklengths of the order of 1000. Study of these practically motivated questions requires new tools and techniques, which are systematically developed in this work. Knowledge of the behavior of the fundamental limits in the non-asymptotic regime enables the analysis of many related questions, such as the energy efficiency, effects of dynamically varying channel state, assessment of the suboptimality of modern codes, benefits of feedback, etc. As a result it is discovered that in several instances classical (asymptotics-based) conclusions do not hold under this more refined approach.