Channel Coding: Non-asymptotic Fundamental Limits

March 8, 2011
Time: 11:00am-12:00pm
Interschool Lab, Room 750 CEPSR
Speaker: Yury Polyanskiy, Princeton University

Abstract

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 my 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.

Speaker Biography

Yury Polyanskiy received the B.S. and M.S. degrees (both with honors) in applied mathematics and physics from the Moscow Institute of Physics and Technology in 2003 and 2005, respectively. In 2010 he obtained Ph.D. in electrical engineering from Princeton University, where he is currently a postdoctoral research associate. In 2000-2005, he was with the Department of Surface Oilfield Equipment, Borets Company LLC, where he rose to the position of Chief Software Designer. His research interests include information theory, coding theory and the theory of random processes. Dr. Polyanskiy won a silver medal at the 30th International Physics Olympiad (IPhO), held in Padova, Italy. He was a recipient of the Best Student Paper Awards at the 2008 and 2010 IEEE International Symposiums on Information Theory (ISIT).


500 W. 120th St., Mudd 1310, New York, NY 10027    212-854-3105               
©2014 Columbia University