Finite-Length Scaling for Polar Codes

DOI10.1109/TIT.2014.2341919MaRDI QIDQ2983385zbMATH OpenFDO

Authors Seyed Hamed Hassani, Kasra Alishahi, Ruediger Urbanke

Publication date 16 May 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1304.4778

Mathematics Subject Classification ID

Error probability in coding theory (94B70)

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_{me}$ we know that we can construct a coding scheme that allows transmission at rate $R$ with an error probability not exceeding $P_{me}$. 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_{me}$. 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_{me}>0$, then the required block-length $N$ scales in terms of the rate $R<I(W)$ as $Ngeqfracalpha(I(W)-R{)}^{underlinemu}$, where $alpha$ is a positive constant that depends on $P_{me}$ and $I(W)$, and $underlinemu=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 $$, where $$ is a constant that depends on $P_{me}$ and $I(W)$, and $overlinemu=6$.

Recommendations

• Improved Bounds on the Finite Length Scaling of Polar Codes
• On the Finite Length Scaling of <inline-formula> <tex-math notation="LaTeX">$q$ </tex-math> </inline-formula>-Ary Polar Codes
• Near-Optimal Finite-Length Scaling for Polar Codes Over Large Alphabets
• Polar codes with exponentially small error at finite block length
• Scaling Exponent of List Decoders With Applications to Polar Codes
• Binary Linear Codes With Optimal Scaling: Polar Codes With Large Kernels
• Finite-Length Scaling for Iteratively Decoded LDPC Ensembles
• Polar Codes: Characterization of Exponent, Bounds, and Constructions
• Polar Codes: Speed of Polarization and Polynomial Gap to Capacity
• Unified Scaling of Polar Codes: Error Exponent, Scaling Exponent, Moderate Deviations, and Error Floors

Cited in

(4)

• Scaling Exponent of List Decoders With Applications to Polar Codes
• On the Finite Length Scaling of <inline-formula> <tex-math notation="LaTeX">$q$ </tex-math> </inline-formula>-Ary Polar Codes
• Algorithmic polarization for hidden Markov models
• Reed-Muller Codes

This page was built for publication: Finite-Length Scaling for Polar Codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2983385)