Finite-Length Scaling of Polar Codes

Abstract

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_{\mathrm{e}}$ we know that we can construct a coding scheme that allows transmission at rate $R$ with an error probability not exceeding $P_{\mathrm{e}}$. 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_{\mathrm{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. Our approach is based on analyzing the dynamics of the un-polarized channels. The main results of this paper can be summarized as follows. Consider the sum of Bhattacharyya parameters of sub-channels chosen (by the polar coding scheme) to transmit information. If we require this sum to be smaller than a given value $P_{\mathrm{e}}>0$, then the required block-length $N$ scales in terms of the rate $R<I(W)$ as $N\ge \frac{\alpha }{(I(W)-R{)}^{\underline{\mu }}}$, where $\alpha$ is a positive constant that depends on $P_{\mathrm{e}}$ and $I(W)$, and $\underline{\mu }=3.579$. Also, we show that with the same requirement on the sum of Bhattacharyya parameters, the block-length scales in terms of the rate like $N\le \frac{\beta }{(I(W)-R{)}^{\overline{\mu }}}$, where $\beta$ is a constant that depends on $P_{\mathrm{e}}$ and $I(W)$, and $\overline{\mu }=6$.

In IEEE Transactions on Information Theory, 2014

References in corpus (1)

• Improved Successive Cancellation Decoding of Polar Codes

Cited by in corpus (11)

• A Low-Latency List Successive-Cancellation Decoding Implementation for Polar Codes
• Polar Codes' Simplicity, Random Codes' Durability
• Log-logarithmic Time Pruned Polar Coding
• Adjacent-Bits-Swapped Polar codes: A new code construction to speed up polarization
• Scaling Exponent and Moderate Deviations Asymptotics of Polar Codes for the AWGN Channel
• Channel Polarization through the Lens of Blackwell Measures
• Entropies of weighted sums in cyclic groups and an application to polar codes
• On the Scaling Exponent of Polar Codes for Binary-Input Energy-Harvesting Channels
• Fast Search Method for Large Polarization Kernels
• ABS+ Polar Codes: Exploiting More Linear Transforms on Adjacent Bits
• The Fractality of Polar and Reed-Muller Codes