Finite-Length Scaling for Polar Codes

Consider a binary-input memoryless output-symmetric channel W. Such a channel has a capacity, call it I (W), and for any R < I (W) and strictly positive constant P-e we know that we can construct a coding scheme that allows transmission at rate R with an error probability not exceeding Pe. Assume now that we let the rate R tend to I (W) and we ask how we have to scale the blocklength N in order to keep the error probability fixed to P-e. We refer to this as the finite-length scaling behavior. This question was addressed by Strassen as well as Polyanskiy, Poor, and Verdu, and the result is that N must grow at least as the square of the reciprocal of I (W) - R. Polar codes are optimal in the sense that they achieve capacity. In this paper, we are asking to what degree they are also optimal in terms of their finite-length behavior. Since the exact scaling behavior depends on the choice of the channel, our objective is to provide scaling laws that hold universally for all binary-input memoryless output-symmetric channels. Our approach is based on analyzing the dynamics of the un-polarized channels. More precisely, we provide bounds on (the exponent of) the number of subchannels whose Bhattacharyya constant falls in a fixed interval [a, b]. Mathematically, this can be stated as bounding the sequence {1/n log Pr(Z(n) is an element of [a, b])}(n is an element of N), where Z(n) is the Bhattacharyya process. We then use these bounds to derive tradeoffs between the rate and the block-length. The main results of this paper can be summarized as follows. Consider the sum of Bhattacharyya parameters of subchannels chosen (by the polar coding scheme) to transmit information. If we require this sum to be smaller than a given value P-e > 0, then the required block-length N scales in terms of the rate R < I (W) as N >= alpha/(I (W) - R), where a is a positive constant that depends on P-e and I (W). We show that (mu) under bar = 3.579 is a valid choice, and we conjecture that indeed the value of (mu) under bar can be improved to (mu) under bar = 3.627, the parameter for the binary erasure channel. Also, we show that with the same requirement on the sum of Bhattacharyya parameters, the blocklength scales in terms of the rate like N