Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Finite-Length Scaling for Polar Codes
 
research article

Finite-Length Scaling for Polar Codes

Hassani, Seyed Hamed  
•
Alishahi, Kasra
•
Urbanke, Ruediger L.
2014
Ieee Transactions On Information Theory

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)<((mu))under bar>, 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 <= beta/(I (W)- R)((mu)) over bar, where beta is a constant that depends on P-e and I (W), and (mu) over bar = 6.

  • Details
  • Metrics
Type
research article
DOI
10.1109/Tit.2014.2341919
Web of Science ID

WOS:000342416900005

Author(s)
Hassani, Seyed Hamed  
Alishahi, Kasra
Urbanke, Ruediger L.
Date Issued

2014

Publisher

Ieee-Inst Electrical Electronics Engineers Inc

Published in
Ieee Transactions On Information Theory
Volume

60

Issue

10

Start page

5875

End page

5898

Subjects

Coding for noisy channels

•

finite block length regime

•

polar codes

•

scaling laws

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
LTHC  
Available on Infoscience
October 23, 2014
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/107602
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés