Construction of Polar Codes for Arbitrary Discrete Memoryless Channels

DOI10.1109/TIT.2017.2765663zbMATH Open1390.94875arXiv1603.05736OpenAlexW2765658857MaRDI QIDQ4566635FDOQ4566635

Authors: T. C. Gülcü, Min Ye, Alexander Barg 

Publication date: 27 June 2018

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

Abstract: It is known that polar codes can be efficiently constructed for binary-input channels. At the same time, existing algorithms for general input alphabets are less practical because of high complexity. We address the construction problem for the general case, and analyze an algorithm that is based on successive reduction of the output alphabet size of the subchannels in each recursion step. For this procedure we estimate the approximation error as $O(m{u}^{-1/(q-1)}),$ where $mu$ is the "quantization parameter," i.e., the maximum size of the subchannel output alphabet allowed by the algorithm. The complexity of the code construction scales as $O(Nm{u}^4),$ where $N$ is the length of the code. We also show that if the polarizing operation relies on modulo-$q$ addition, it is possible to merge subsets of output symbols without any loss in subchannel capacity. Performing this procedure before each approximation step results in a further speed-up of the code construction, and the resulting codes have smaller gap to capacity. We show that a similar acceleration can be attained for polar codes over finite field alphabets. Experimentation shows that the suggested construction algorithms can be used to construct long polar codes for alphabets of size $q=16$ and more with acceptable loss of the code rate for a variety of polarizing transforms.

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

Mathematics Subject Classification ID

Source coding (94A29) Linear codes (general theory) (94B05) Channel models (including quantum) in information and communication theory (94A40)

Cited In (3)

• A Simple Proof of Polarization and Polarization for Non-Stationary Memoryless Channels
• Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels
• Polar Coding Without Alphabet Extension for Asymmetric Models

This page was built for publication: Construction of Polar Codes for Arbitrary Discrete Memoryless Channels

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