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. Near-Optimal Finite-Length Scaling for Polar Codes Over Large Alphabets
 
research article

Near-Optimal Finite-Length Scaling for Polar Codes Over Large Alphabets

Pfister, Henry D.
•
Urbanke, Ruediger L.  
September 1, 2019
Ieee Transactions On Information Theory

For any prime power q, Mori and Tanaka introduced a family of q-ary polar codes based on the q x q Reed-Solomon polarization kernels. For transmission over a q-ary erasure channel, they also derived a closed-form recursion for the erasure probability of each effective channel. In this paper, we use that expression to analyze the finite-length scaling of these codes on the q-ary erasure channel with erasure probability epsilon is an element of (0, 1). Our primary result is that for any gamma > 0 and delta > 0, there is a q0, such that for all q >= q(0), the fraction of effective channels with erasure rate at most N-gamma is at least 1 - epsilon - O(N-1/2+delta), where N = q(n) is the blocklength. Since this fraction cannot be larger than 1 - epsilon - O(N-1/2+delta), this establishes near-optimal finite-length scaling for this family of codes. Our approach can be seen as an extension of a similar analysis for binary polar codes by Hassani, Alishahi, and Urbanke. A similar analysis is also considered for q-ary polar codes with m x m polarizing matrices. This separates the effect of the alphabet size from the effect of the matrix size. If the polarizing matrix at each stage is drawn independently and uniformly from the set of invertible m x m matrices, then the linear operator associated with the Lyapunov function analysis can be written in the closed form. To prove near-optimal scaling for polar codes with fixed q as m increases, however, two technical obstacles remain. Thus, we conclude by stating two concrete mathematical conjectures that, if proven, would imply near-optimal scaling for fixed q.

  • Details
  • Metrics
Type
research article
DOI
10.1109/TIT.2019.2915595
Web of Science ID

WOS:000481981000025

Author(s)
Pfister, Henry D.
•
Urbanke, Ruediger L.  
Date Issued

2019-09-01

Published in
Ieee Transactions On Information Theory
Volume

65

Issue

9

Start page

5643

End page

5655

Subjects

Computer Science, Information Systems

•

Engineering, Electrical & Electronic

•

Computer Science

•

Engineering

•

channel capacity

•

finite-length scaling

•

galois fields

•

lyapunov function

•

polar codes

•

channel polarization

•

exponent

•

bounds

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
LTHC  
Available on Infoscience
September 6, 2019
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/160913
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