Finite-Length Scaling for Polar Codes

Dr. Hamed Hassani

ETH Zurich

Abstract:

The channel coding theorem states that for any rate below the capacity, we can construct a coding scheme that allows reliable transmission at that rate as long as we pick a sufficiently large block length. But what is "sufficiently large"? To address this question, we let the rate approach capacity and ask how we must "scale" the block length in terms of the rate in order to achieve a fixed error probability. We refer to this as the "finite-length scaling" behavior. The question of the optimal scaling was addressed by Strassen, as well as by Polyanskiy, Poor and Verdu. The result is that, for any code, the block length must grow at least as the square of the reciprocal of the gap to capacity.

Polar codes are optimal in the sense that they achieve capacity for the class of binary-input memoryless output-symmetric channels. In this talk, we ask to what degree they are also optimal in terms of their finite-length behavior. Since the exact scaling behavior depends on the channel, our objective is to provide scaling laws that hold universally for all binary-input memoryless output-symmetric channels.

Biography:

Hamed Hassani earned his two B. Sc. degrees in electrical engineering and mathematics from Sharif University of Technology, Iran, in 2007 and his Ph.D. degree from EPFL, Lausanne, Switzerland, in 2013. After continuing briefly as a post-doc at EPFL, he now conducts post-doctoral research at ETH, Zurich, Switzerland. Hamed's fields of interest include coding and information theory, theory and application of graphical models, as well as machine learning. He is the recipient of the 2014 IEEE Information Theory Society Thomas M. Cover Dissertation Award.