Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Entropy

Bit-Level Construction for Multiplicative-Repetition-Based Non-Binary Polar Codes

Rongchi Xu, Peiyao Chen, Ling Liu, Min Zhu, Baoming Bai

Published Apr 2, 2025• 0 citations
Publisher

Abstract

In this paper, we discuss non-binary polar codes using a 2×2 matrix over a Galois field GF(2q) as the kernel. Conventional construction of non-binary polar codes divides the synthesized channels into frozen channels and information channels. Each information channel carries one symbol, i.e., q bits. However, there are many middle channels with insufficient polarization, which cannot carry one symbol of q bits but only i bits, 1≤i<q,i∈Z, at finite block length. In this paper, we consider bit-level construction for multiplicative repetition (MR)-based non-binary polar codes and propose a bit-level construction based on the two following methods. We first calculate the error probability and channel capacity lower bound of each synthesized channel based on the channel degradation method, and then determine both the number and index of the carried bits for each synthesized channel according to the symbol error probability and capacity. To reduce complexity, we also introduce a Monte-Carlo method. We compute the error probability of each synthesized channel carrying i information bits and select the optimal construction that can minimize the union bound of the error probability. Finally, an improved construction-based probabilistic shaping method for MR-based non-binary polar codes is considered. Simulation results show that the proposed construction significantly improved the decoding performance compared with the conventional construction scheme.

DOI
10.3390/e27040377

Related papers

Improved Construction for Multiplicative Repetition Based Non-Binary Polar Codes

Rongchi Xu, Peiyao Chen, Ling Liu +2 more

Conventional construction of non-binary polar codes divides the synthesized channels into the frozen channels and information channels. Each information channel carries one symbol i.e.$q$bits. However, there are many middle channels with insufficient polarization, which can not carry one symbol of$q$bits but only$i$bits,$1 \leq i<q, i \in \mathbb{Z}$, at finite block lengths. In this paper, we consider the bit-level construction for multiplicative repetition (MR) based non-binary polar codes and propose bitlevel improved construction for channel degradation method and Monte-Carlo method. Simulation results show that the proposed construction can significantly improve the decoding performance compared with the conventional construction scheme.

IEEE Information Theory Workshop (ITW)•Nov 24, 2024•1 citation

Sphere Decoding for Binary Polar Codes with the Modified Multiplicative Repetition Construction

Haiqiang Chen, Yuanbo Liu, Shuping Dang +3 more

Compared to the successive cancellation (SC)-based decoding algorithms, the sphere decoding (SD) algorithm can achieve better performance with reduced computational complexity, especially for short polar codes. In this paper, we propose a new method to construct the binary polar codes with the modified multiplicative repetition (MR)-based matrix. Different from the original construction, we first design a$2\times 2\ q\text{-ary}$kernel to guarantee the single-level polarization effect. Then, by replacing the new-designed binary companion matrix, a novel strategy is further developed to enhance the polarization in the bit level, resulting in a better distance property. Finally, the SD-based Monte-Carlo (SDMC) method is used to construct MR-based binary polar codes, while the resulting codes without the butterfly pattern are decoded by the SD algorithm. Simulation results show that the proposed method with the SD algorithm can achieve a maximum performance gain of 0.27 dB compared to the original method with slightly lower complexity.

Tsinghua Science & Technology•Dec 30, 2024•1 citation

Performance and Construction of Polar Codes: The Perspective of Bit Error Probability

Bolin Wu, Kai Niu, Jincheng Dai

Most existing works of polar codes focus on the analysis of block error probability. However, in many scenarios, bit error probability is also important for evaluating the performance of channel codes. In this paper, we establish a new framework to analyze the bit error probability of polar codes. Specifically, by revisiting the error event of bit-channel, we first introduce the conditional bit error probability as a metric to evaluate the reliability of bit-channel for both systematic and non-systematic polar codes. Guided by the concept of polar subcode, we then derive an upper bound on the conditional bit error probability of each bit-channel, and accordingly, an upper bound on the bit error probability of polar codes. Based on these, two types of construction metrics aiming at minimizing the bit error probability of polar codes are proposed, which are of linear computational complexity and explicit forms. Simulation results show that the polar codes constructed by the proposed methods can outperform those constructed by the conventional methods.

arXiv:2204.07435•Apr 15, 2022•0 citations

A Fast Polar Code Construction Method Based on Monte Carlo

ZHANG Shiyi, HUANG Zhiliang, ZHOU Shuihong, ZHONG Farong

In order to construct high-dimensional core matrix polar codes quickly,a two-stage polar code construction method TPMC based on Monte Carlo(MC) is proposed.In the first stage,the most reliable and unreliable bits are obtained by using the Gauss approximation method with linear complexity.In the second stage,the above bits are fixed as frozen bits and MC method is implemented to measure the error rate of the remaining bit channels.The bits with a lower error rate are selected from the remaining bits,and are combined with most reliable information bits in the first stage to form an information bits set.Simulation results show that compared with MC method,TPMC method can reduce the computational complexity and improve the decoding efficiency.

•Sep 1, 2019•0 citations

A Lower Bound on the Probability of Error of Polar Codes over BMS Channels

Boaz Shuval, Ido Tal

Polar codes are a family of capacity-achieving codes that have explicit and low-complexity construction, encoding, and decoding algorithms. Decoding of polar codes is based on the successive-cancellation decoder, which decodes in a bit-wise manner. A decoding error occurs when at least one bit is erroneously decoded. The various codeword bits are correlated, yet performance analysis of polar codes ignores this dependence: the upper bound is based on the union bound, and the lower bound is based on the worst-performing bit. Improvement of the lower bound is afforded by considering error probabilities of two bits simultaneously. These are difficult to compute explicitly due to the large alphabet size inherent to polar codes. In this paper, we propose a method to lower-bound the error probabilities of bit pairs. We develop several transformations on pairs of synthetic channels that make the resultant synthetic channels amenable to alphabet reduction. Our method yields lower bounds that significantly improve upon currently known lower bounds for polar codes under successive-cancellation decoding.

IEEE Transactions on Information Theory•Oct 12, 2018•7 citations

A Lower Bound on the Probability of Error of Polar Codes over BMS Channels

Boaz Shuval, Ido Tal

Polar codes are a family of capacity-achieving codes that have explicit and low-complexity construction, encoding, and decoding algorithms. Decoding of polar codes is based on the successive-cancellation decoder, which decodes in a bit- wise manner. A decoding error occurs when at least one bit is erroneously decoded. The various codeword bits are correlated, yet performance analysis of polar codes ignores this dependence: the upper bound is based on the union bound, and the lower bound is based on the worst-performing bit. Improvement of the lower bound is afforded by considering error probabilities of two bits simultaneously. These are difficult to compute explicitly due to the large alphabet size inherent to polar codes. In this research we propose a method to lower-bound the error probabilities of bit pairs. We develop several transformations on pairs of synthetic channels that make the resultant synthetic channels amenable to alphabet reduction. Our method yields lower bounds that significantly improve upon currently known lower bounds for polar codes under successive-cancellation decoding.

arXiv:1701.01628•Jan 6, 2017•0 citations
In this paper, we discuss non-binary polar codes using a 2×2 matrix over a Galois field GF(2q) as the kernel. Conventional construction of non-binary polar codes divides the synthesized channels into frozen channels and information channels. Each information channel carries one symbol, i.e., q bits. However, there are many middle channels with insufficient polarization, which cannot carry one symbol of q bits but only i bits, 1≤i<q,i∈Z, at finite block length. In this paper, we consider bit-level construction for multiplicative repetition (MR)-based non-binary polar codes and propose a bit-level construction based on the two following methods. We first calculate the error probability and channel capacity lower bound of each synthesized channel based on the channel degradation method, and then determine both the number and index of the carried bits for each synthesized channel according to the symbol error probability and capacity. To reduce complexity, we also introduce a Monte-Carlo method. We compute the error probability of each synthesized channel carrying i information bits and select the optimal construction that can minimize the union bound of the error probability. Finally, an improved construction-based probabilistic shaping method for MR-based non-binary polar codes is considered. Simulation results show that the proposed construction significantly improved the decoding performance compared with the conventional construction scheme.
Conventional construction of non-binary polar codes divides the synthesized channels into the frozen channels and information channels. Each information channel carries one symbol i.e.qqqbits. However, there are many middle channels with insufficient polarization, which can not carry one symbol ofqqqbits but onlyiiibits,1≤i<q,i∈Z1 \leq i<q, i \in \mathbb{Z}1≤i<q,i∈Z, at finite block lengths. In this paper, we consider the bit-level construction for multiplicative repetition (MR) based non-binary polar codes and propose bitlevel improved construction for channel degradation method and Monte-Carlo method. Simulation results show that the proposed construction can significantly improve the decoding performance compared with the conventional construction scheme.
Compared to the successive cancellation (SC)-based decoding algorithms, the sphere decoding (SD) algorithm can achieve better performance with reduced computational complexity, especially for short polar codes. In this paper, we propose a new method to construct the binary polar codes with the modified multiplicative repetition (MR)-based matrix. Different from the original construction, we first design a2×2 q-ary2\times 2\ q\text{-ary}2×2 q-arykernel to guarantee the single-level polarization effect. Then, by replacing the new-designed binary companion matrix, a novel strategy is further developed to enhance the polarization in the bit level, resulting in a better distance property. Finally, the SD-based Monte-Carlo (SDMC) method is used to construct MR-based binary polar codes, while the resulting codes without the butterfly pattern are decoded by the SD algorithm. Simulation results show that the proposed method with the SD algorithm can achieve a maximum performance gain of 0.27 dB compared to the original method with slightly lower complexity.
Most existing works of polar codes focus on the analysis of block error probability. However, in many scenarios, bit error probability is also important for evaluating the performance of channel codes. In this paper, we establish a new framework to analyze the bit error probability of polar codes. Specifically, by revisiting the error event of bit-channel, we first introduce the conditional bit error probability as a metric to evaluate the reliability of bit-channel for both systematic and non-systematic polar codes. Guided by the concept of polar subcode, we then derive an upper bound on the conditional bit error probability of each bit-channel, and accordingly, an upper bound on the bit error probability of polar codes. Based on these, two types of construction metrics aiming at minimizing the bit error probability of polar codes are proposed, which are of linear computational complexity and explicit forms. Simulation results show that the polar codes constructed by the proposed methods can outperform those constructed by the conventional methods.
In order to construct high-dimensional core matrix polar codes quickly,a two-stage polar code construction method TPMC based on Monte Carlo(MC) is proposed.In the first stage,the most reliable and unreliable bits are obtained by using the Gauss approximation method with linear complexity.In the second stage,the above bits are fixed as frozen bits and MC method is implemented to measure the error rate of the remaining bit channels.The bits with a lower error rate are selected from the remaining bits,and are combined with most reliable information bits in the first stage to form an information bits set.Simulation results show that compared with MC method,TPMC method can reduce the computational complexity and improve the decoding efficiency.
Polar codes are a family of capacity-achieving codes that have explicit and low-complexity construction, encoding, and decoding algorithms. Decoding of polar codes is based on the successive-cancellation decoder, which decodes in a bit-wise manner. A decoding error occurs when at least one bit is erroneously decoded. The various codeword bits are correlated, yet performance analysis of polar codes ignores this dependence: the upper bound is based on the union bound, and the lower bound is based on the worst-performing bit. Improvement of the lower bound is afforded by considering error probabilities of two bits simultaneously. These are difficult to compute explicitly due to the large alphabet size inherent to polar codes. In this paper, we propose a method to lower-bound the error probabilities of bit pairs. We develop several transformations on pairs of synthetic channels that make the resultant synthetic channels amenable to alphabet reduction. Our method yields lower bounds that significantly improve upon currently known lower bounds for polar codes under successive-cancellation decoding.
Polar codes are a family of capacity-achieving codes that have explicit and low-complexity construction, encoding, and decoding algorithms. Decoding of polar codes is based on the successive-cancellation decoder, which decodes in a bit- wise manner. A decoding error occurs when at least one bit is erroneously decoded. The various codeword bits are correlated, yet performance analysis of polar codes ignores this dependence: the upper bound is based on the union bound, and the lower bound is based on the worst-performing bit. Improvement of the lower bound is afforded by considering error probabilities of two bits simultaneously. These are difficult to compute explicitly due to the large alphabet size inherent to polar codes. In this research we propose a method to lower-bound the error probabilities of bit pairs. We develop several transformations on pairs of synthetic channels that make the resultant synthetic channels amenable to alphabet reduction. Our method yields lower bounds that significantly improve upon currently known lower bounds for polar codes under successive-cancellation decoding.