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

arXiv:2009.06796 · Globecom

Decoding Polar Codes with Reinforcement Learning

Nghia Doan, Seyyed Ali Hashemi, Warren J. Gross

Published Dec 1, 2020• 16 citations
arXivHTMLPDF

Abstract

In this paper we address the problem of selecting factor-graph permutations of polar codes under belief propagation (BP) decoding to significantly improve the error-correction performance of the code. In particular, we formalize the factor-graph permutation selection as the multi-armed bandit problem in reinforcement learning and propose a decoder that acts like an online-learning agent that learns to select the good factor-graph permutations during the course of decoding. We use state-of-the-art algorithms for the multi-armed bandit problem and show that for a 5G polar codes of length 128 with 64 information bits, the proposed decoder has an error-correction performance gain of around 0.125 dB at the target frame error rate of 10-4, when compared to the approach that randomly selects the factor-graph permutations.

DOI
10.1109/globecom42002.2020.9348007

Related papers

On the Decoding of Polar Codes on Permuted Factor Graphs

Nghia Doan, Seyyed Ali Hashemi, Marco Mondelli +1 more

Polar codes are a channel coding scheme for the next generation of wireless communications standard (5G). The belief propagation (BP) decoder allows for parallel decoding of polar codes, making it suitable for high throughput applications. However, the error-correction performance of polar codes under BP decoding is far from the requirements of 5G. It has been shown that the error-correction performance of BP can be improved if the decoding is performed on multiple permuted factor graphs of polar codes. However, a different BP decoding scheduling is required for each factor graph permutation which results in the design of a different decoder for each permutation. Moreover, the selection of the different factor graph permutations is at random, which prevents the decoder to achieve a desirable error correction performance with a small number of permutations. In this paper, we first show that the permutations on the factor graph can be mapped into suitable permutations on the codeword positions. As a result, we can make use of a single decoder for all the permutations. In addition, we introduce a method to construct a set of predetermined permutations which can provide the correct codeword if the decoding fails on the original permutation. We show that for the 5G polar code of length 1024, the error-correction performance of the proposed decoder is more than 0.25 dB better than that of the BP decoder with the same number of random permutations at the frame error rate of 10-4.

arXiv:1806.11195•Globecom•Dec 1, 2018•87 citations

Enhancing Belief Propagation Decoding of Polar Codes: A Reinforcement Learning Approach

Mohsen Moradi, Salman Habib, David G. M. Mitchell

Short block-length polar-like codes showcase exceptional error correction performance (ECP) using sequential decoding or successive cancellation list decoding with a large list size. However, achieving a high level of reliability with these methods involves high-latency decoding. To meet the growing demand for low-latency communication with acceptable complexity, belief propagation (BP) decoding emerges as an attractive option, although its ECP is known to fall short of those high-latency alternatives. In this paper, we propose an enhanced BP decoding approach for polar codes, leveraging reinforcement learning (RL) to optimize the message-passing schedule. Moreover, we investigate the design of the polar code rate profile and corresponding Tanner graph representation to enhance the benefits of RL. Numerical results demonstrate a performance gain of more than 1 dB for polar codes with a length of 128 and a rate of 0.5 compared to conventional BP decoding alone at highEb/N0values, demonstrating the promise of the proposed approach.

IEEE Communications Letters•Apr 9, 2025•3 citations

Improved Belief Propagation List Decoding for Polar Codes

Binghao Li, Baoming Bai, Min Zhu +1 more

In this paper, we present an improved belief propagation list (BPL) decoding algorithm for polar codes. Rather than getting L factor graphs (FGs) at random and cyclic shift permutation, we use the upper bounds on the block error propability of polar codes with different FGs as the metric to choose the best L FGs. By observing the bounds of different FGs, we propose a heuristic method to reduce search complexity. Simulation results show that there is only a gap of 0.2 dB between the frame error rate (FER) performance of the improved BPL decoder using RM16-GA construction and that of length-1024 5G polar code decoded by SCL with the same list size of 32 at FER =10-4. Moreover, with the proposed FG selection method, BPL decoding can reduce clock cycles by 97.74% compared with the SCL decoding.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2020•10 citations

Belief Propagation With Permutated Graphs of Polar Codes

Liping Li, Liangliang Liu

The belief propagation (BP) decoding of polar codes provides better bit error rate (BER) and packet error rate (PER) performance than the successive cancelation (SC) decoding. It has been reported in the literature that the graph of BP decoding of polar codes can be permuted to provide even better decoding performance. In this paper, we theoretically prove that all permutations of the graph are equivalent in terms of the polar encoding. For BP decoding, it is shown that permutations of the layers of the graph also permute the bit channels. A principle which protects the weakest information bit channel is provided in the paper. Two parallel BP decoders, one employing the standard graph and the other selected based on the selection principle, are also proposed to work together. The simulation results show that when the total number of iterations is fixed, the proposed BP decoding can have the same performance as the existing permutation scheme while provides a higher throughput.

IEEE Access•Jan 1, 2020•8 citations

Improved Hybrid RM-Polar Codes and Decoding on Stable Permuted Factor Graphs

Wu Wei, Zhen Zhai, Paul H. Siegel

A new family of modified polar codes and a new permutation selection scheme for belief propagation list (BPL) decoding are presented. We first propose a new code construction methodology to interpolate between Reed-Muller (RM) codes and polar codes. By taking advantage of an existing partial order on bit-channels whose corresponding indices share the same Hamming weight, we analyze the complexity of the new construction method. It is shown that we need to compute the reliability of roughly a fraction 1/log3/2N of all the bit-channels contained in the subset. Then, we explore a special family of factor-graph layer permutations called stable permutations (SPs) that preserve a specified information set when the corresponding bit permutations are applied to message bit indices. Simulation results show that the error-rate performance of the new family of codes is better than that of 5G polar codes under successive cancellation list (SCL) decoding. In addition, the SP selection scheme stands out as a preferred one for BPL decoding in terms of error-rate performance, while the average number of iterations per belief propagation (BP) decoder on the permuted factor graph is close to that of the original BP decoder when an early stopping condition is applied.

International Symposium on Turbo Codes and Iterative Information Processing•Aug 30, 2021•3 citations

Partially Permuted Multi-Trellis Belief Propagation for Polar Codes

Vismika Ranasinghe, Nandana Rajatheva, Matti Latva‐aho

Belief propagation (BP) is an iterative decoding algorithm for polar codes which can be parallelized effectively to achieve higher throughput. However, because of the presence of error floor due to cycles and stopping sets in the factor graph, the performance of the BP decoder is far from the performance of state of the art cyclic redundancy check (CRC) aided successive cancellation list (CA-SCL) decoders. It has been shown that successive BP decoding on multiple permuted factor graphs, which is called the multi-trellis BP decoder, can improve the error performance. However, when permuting the entire factor graph, since the decoder dismisses the information from the previous permutation, the number of iterations required is significantly larger than that of the standard BP decoder. In this work, we propose a new variant of the multi-trellis BP decoder which permutes only a subgraph of the original factor graph. This enables the decoder to retain information of variable nodes in the subgraphs, which are not permuted, reducing the required number of iterations needed in-between the permutations. As a result, the proposed decoder can perform permutations more frequently, hence being more effective in mitigating the effect of cycles which cause oscillation errors. Experimental results show that for a polar code with block length 1024 and rate 0.5 the error performance gain of the proposed decoder at the frame error rate of $10^{-6}$ is 0.25 dB compared to multi-trellis decoder based on full permutations. This performance gain is achieved along with reduced latency in terms of the number of iterations.

arXiv:1911.08868•International Conference on Communications•Jun 1, 2020•3 citations
In this paper we address the problem of selecting factor-graph permutations of polar codes under belief propagation (BP) decoding to significantly improve the error-correction performance of the code. In particular, we formalize the factor-graph permutation selection as the multi-armed bandit problem in reinforcement learning and propose a decoder that acts like an online-learning agent that learns to select the good factor-graph permutations during the course of decoding. We use state-of-the-art algorithms for the multi-armed bandit problem and show that for a 5G polar codes of length 128 with 64 information bits, the proposed decoder has an error-correction performance gain of around 0.125 dB at the target frame error rate of 10-4, when compared to the approach that randomly selects the factor-graph permutations.
Polar codes are a channel coding scheme for the next generation of wireless communications standard (5G). The belief propagation (BP) decoder allows for parallel decoding of polar codes, making it suitable for high throughput applications. However, the error-correction performance of polar codes under BP decoding is far from the requirements of 5G. It has been shown that the error-correction performance of BP can be improved if the decoding is performed on multiple permuted factor graphs of polar codes. However, a different BP decoding scheduling is required for each factor graph permutation which results in the design of a different decoder for each permutation. Moreover, the selection of the different factor graph permutations is at random, which prevents the decoder to achieve a desirable error correction performance with a small number of permutations. In this paper, we first show that the permutations on the factor graph can be mapped into suitable permutations on the codeword positions. As a result, we can make use of a single decoder for all the permutations. In addition, we introduce a method to construct a set of predetermined permutations which can provide the correct codeword if the decoding fails on the original permutation. We show that for the 5G polar code of length 1024, the error-correction performance of the proposed decoder is more than 0.25 dB better than that of the BP decoder with the same number of random permutations at the frame error rate of 10-4.
Short block-length polar-like codes showcase exceptional error correction performance (ECP) using sequential decoding or successive cancellation list decoding with a large list size. However, achieving a high level of reliability with these methods involves high-latency decoding. To meet the growing demand for low-latency communication with acceptable complexity, belief propagation (BP) decoding emerges as an attractive option, although its ECP is known to fall short of those high-latency alternatives. In this paper, we propose an enhanced BP decoding approach for polar codes, leveraging reinforcement learning (RL) to optimize the message-passing schedule. Moreover, we investigate the design of the polar code rate profile and corresponding Tanner graph representation to enhance the benefits of RL. Numerical results demonstrate a performance gain of more than 1 dB for polar codes with a length of 128 and a rate of 0.5 compared to conventional BP decoding alone at highEb/N0values, demonstrating the promise of the proposed approach.
In this paper, we present an improved belief propagation list (BPL) decoding algorithm for polar codes. Rather than getting L factor graphs (FGs) at random and cyclic shift permutation, we use the upper bounds on the block error propability of polar codes with different FGs as the metric to choose the best L FGs. By observing the bounds of different FGs, we propose a heuristic method to reduce search complexity. Simulation results show that there is only a gap of 0.2 dB between the frame error rate (FER) performance of the improved BPL decoder using RM16-GA construction and that of length-1024 5G polar code decoded by SCL with the same list size of 32 at FER =10-4. Moreover, with the proposed FG selection method, BPL decoding can reduce clock cycles by 97.74% compared with the SCL decoding.
The belief propagation (BP) decoding of polar codes provides better bit error rate (BER) and packet error rate (PER) performance than the successive cancelation (SC) decoding. It has been reported in the literature that the graph of BP decoding of polar codes can be permuted to provide even better decoding performance. In this paper, we theoretically prove that all permutations of the graph are equivalent in terms of the polar encoding. For BP decoding, it is shown that permutations of the layers of the graph also permute the bit channels. A principle which protects the weakest information bit channel is provided in the paper. Two parallel BP decoders, one employing the standard graph and the other selected based on the selection principle, are also proposed to work together. The simulation results show that when the total number of iterations is fixed, the proposed BP decoding can have the same performance as the existing permutation scheme while provides a higher throughput.
A new family of modified polar codes and a new permutation selection scheme for belief propagation list (BPL) decoding are presented. We first propose a new code construction methodology to interpolate between Reed-Muller (RM) codes and polar codes. By taking advantage of an existing partial order on bit-channels whose corresponding indices share the same Hamming weight, we analyze the complexity of the new construction method. It is shown that we need to compute the reliability of roughly a fraction 1/log3/2N of all the bit-channels contained in the subset. Then, we explore a special family of factor-graph layer permutations called stable permutations (SPs) that preserve a specified information set when the corresponding bit permutations are applied to message bit indices. Simulation results show that the error-rate performance of the new family of codes is better than that of 5G polar codes under successive cancellation list (SCL) decoding. In addition, the SP selection scheme stands out as a preferred one for BPL decoding in terms of error-rate performance, while the average number of iterations per belief propagation (BP) decoder on the permuted factor graph is close to that of the original BP decoder when an early stopping condition is applied.
Belief propagation (BP) is an iterative decoding algorithm for polar codes which can be parallelized effectively to achieve higher throughput. However, because of the presence of error floor due to cycles and stopping sets in the factor graph, the performance of the BP decoder is far from the performance of state of the art cyclic redundancy check (CRC) aided successive cancellation list (CA-SCL) decoders. It has been shown that successive BP decoding on multiple permuted factor graphs, which is called the multi-trellis BP decoder, can improve the error performance. However, when permuting the entire factor graph, since the decoder dismisses the information from the previous permutation, the number of iterations required is significantly larger than that of the standard BP decoder. In this work, we propose a new variant of the multi-trellis BP decoder which permutes only a subgraph of the original factor graph. This enables the decoder to retain information of variable nodes in the subgraphs, which are not permuted, reducing the required number of iterations needed in-between the permutations. As a result, the proposed decoder can perform permutations more frequently, hence being more effective in mitigating the effect of cycles which cause oscillation errors. Experimental results show that for a polar code with block length 1024 and rate 0.5 the error performance gain of the proposed decoder at the frame error rate of 10−610^{-6}10−6 is 0.25 dB compared to multi-trellis decoder based on full permutations. This performance gain is achieved along with reduced latency in terms of the number of iterations.