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

A Fast Polar Code Construction Method Based on Monte Carlo

ZHANG Shiyi, HUANG Zhiliang, ZHOU Shuihong, ZHONG Farong

Published Sep 1, 2019• 0 citations
Publisher

Abstract

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.

DOI
10.19678/j.issn.1000-3428.0052038

Related papers

A Fast Two-Phase Monte Carlo Method for Constructing Polar Codes With Arbitrary Binary Kernel

Shiyi Zhang, Zhiliang Huang, Geng Chen +1 more

We propose a two-phase Monte Carlo (TPMC) method to accelerate the original Monte Carlo (MC) method for constructing polar codes with high-dimensional kernels. In the TPMC method, some of the most reliable and unreliable bits are obtained by Gaussian approximate-density evolution (GA-DE) method in the first phase; in the second phase, these most reliable and unreliable bits are viewed as frozen bits. Then, the MC method are used to evaluate the remaining bits and select some best bits from the remaining bits. Finally, these best bits and the most reliable bits are combined as the information bits of the constructed polar code. By our investigation, most bits can be fixed as frozen bits in the second phase without error performance loss of the constructed polar codes. Because computation of frozen bits can be saved and computation of the GA-DE method can be ignored in contrast to that of the MC method, the TPMC method substantially reduces the complexity of the MC method. Simulation results show that 1) For a$G_{15}^{\otimes 3}$polar code with block length 3375 and code rate 1/2, the TPMC method can fix 3200 bits as frozen bits in the second phase without error performance loss, which reduces the computation cost by approximately 92.6% over the MC method; 2) Polar codes with high-dimensional kernels constructed by the TPMC method outperforms polar codes with the$G_{2}$kernel constructed by the Tal-Vardy method in terms of error performance; 3) With the same computational cost, the TPMC method can construct better polar codes than the MC method.

IEEE Access•Jan 1, 2019•4 citations

Frozen bits selection for polar codes based on simulation and BP decoding

Jingbo Liu, Jin Sha

In the construction of polar code, the selection of frozen bits affects the error-correcting performance significantly. Several calculation-based algorithms have been proposed for general binary-input discrete memoryless channels (B-DMCs) like the additive white Gaussian noise (AWGN) channel. In this paper, a method for frozen bits selection based on Monte Carlo simulation and belief propagation (BP) decoding is proposed. The information bits are selected out one by one incrementally. The numerical results show that the proposed algorithm can effectively improve the bit error rate (BER) and frame error rate (FER) performance compared with the conventional selection method, especially in high signal noise ratio (SNR) region. Moreover, the algorithm can be used to construct polar codes with any rate through a complete iteration.

IEICE Electronics Express•Jan 1, 2017•13 citations

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

Rongchi Xu, Peiyao Chen, Ling Liu +2 more

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.

Entropy•Apr 2, 2025•0 citations

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

Low Complexity Construction of Polar Codes with BP Decoder over Medium to High SNR Region

Hui Wang, Shuolei Gan

In this paper, we focus on the low-complexity construction method of polar codes with belief propagation (BP) decoder over additive white Gaussian noise (AWGN) channels. Firstly, the zero-noise BP decoding analysis method is proposed to determine the reliability of each bit channel via recursively calculating log-likelihood ratios (LLRs) of nodes from right to left in the factor graph. The final LLR can comprehensively reflect the structural characteristics of each bit channel. Then, the zero-noise LLR criterion based construction is introduced to select the frozen bit indices. Specifically, the lower the LLR value, the higher the priority of the corresponding bit selected as the frozen bit. Due to the assumed noise-free environment, the proposed zero-noise LLR criterion based construction is channel-independent. Finally, the simulation results show that, the zero-noise LLR criterion based construction can sort out the critical bit channels to load the frozen bits. When compared with other construction methods for BP decoder, such as the LLR-based bit-swapping construction and the simulation-based bit-swapping construction, the proposed zero-noise LLR criterion based construction not only has the best error correction ability over medium to high signal-to-noise ratio (SNR) region, but also exhibits the lowest construction complexity.

International Conference on Computer and Communication Systems (ICCCS)•Apr 21, 2023•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
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.
We propose a two-phase Monte Carlo (TPMC) method to accelerate the original Monte Carlo (MC) method for constructing polar codes with high-dimensional kernels. In the TPMC method, some of the most reliable and unreliable bits are obtained by Gaussian approximate-density evolution (GA-DE) method in the first phase; in the second phase, these most reliable and unreliable bits are viewed as frozen bits. Then, the MC method are used to evaluate the remaining bits and select some best bits from the remaining bits. Finally, these best bits and the most reliable bits are combined as the information bits of the constructed polar code. By our investigation, most bits can be fixed as frozen bits in the second phase without error performance loss of the constructed polar codes. Because computation of frozen bits can be saved and computation of the GA-DE method can be ignored in contrast to that of the MC method, the TPMC method substantially reduces the complexity of the MC method. Simulation results show that 1) For aG15⊗3G_{15}^{\otimes 3}G15⊗3​polar code with block length 3375 and code rate 1/2, the TPMC method can fix 3200 bits as frozen bits in the second phase without error performance loss, which reduces the computation cost by approximately 92.6% over the MC method; 2) Polar codes with high-dimensional kernels constructed by the TPMC method outperforms polar codes with theG2G_{2}G2​kernel constructed by the Tal-Vardy method in terms of error performance; 3) With the same computational cost, the TPMC method can construct better polar codes than the MC method.
In the construction of polar code, the selection of frozen bits affects the error-correcting performance significantly. Several calculation-based algorithms have been proposed for general binary-input discrete memoryless channels (B-DMCs) like the additive white Gaussian noise (AWGN) channel. In this paper, a method for frozen bits selection based on Monte Carlo simulation and belief propagation (BP) decoding is proposed. The information bits are selected out one by one incrementally. The numerical results show that the proposed algorithm can effectively improve the bit error rate (BER) and frame error rate (FER) performance compared with the conventional selection method, especially in high signal noise ratio (SNR) region. Moreover, the algorithm can be used to construct polar codes with any rate through a complete iteration.
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.
In this paper, we focus on the low-complexity construction method of polar codes with belief propagation (BP) decoder over additive white Gaussian noise (AWGN) channels. Firstly, the zero-noise BP decoding analysis method is proposed to determine the reliability of each bit channel via recursively calculating log-likelihood ratios (LLRs) of nodes from right to left in the factor graph. The final LLR can comprehensively reflect the structural characteristics of each bit channel. Then, the zero-noise LLR criterion based construction is introduced to select the frozen bit indices. Specifically, the lower the LLR value, the higher the priority of the corresponding bit selected as the frozen bit. Due to the assumed noise-free environment, the proposed zero-noise LLR criterion based construction is channel-independent. Finally, the simulation results show that, the zero-noise LLR criterion based construction can sort out the critical bit channels to load the frozen bits. When compared with other construction methods for BP decoder, such as the LLR-based bit-swapping construction and the simulation-based bit-swapping construction, the proposed zero-noise LLR criterion based construction not only has the best error correction ability over medium to high signal-to-noise ratio (SNR) region, but also exhibits the lowest construction complexity.
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.