Construction of Polar Codes with Reinforcement Learning

Yun Liao, Seyyed Ali Hashemi, John M. Cioffi, Andrea Goldsmith

Abstract

Polar codes are a cornerstone of 5G error correction, yet their standard construction methods are optimized for simplified Successive-Cancellation (SC) decoders rather than the high-performance Successive-Cancellation List (SCL) decoders used in practice. This paper presents a novel approach by researchers at Stanford University that reframes polar code construction as a reinforcement learning (RL) problem. By modeling bit selection as a sequential decision-making process in a maze-traversing game, the authors demonstrate that an RL agent can discover code structures that significantly outperform current industry standards for SCL decoders.

Introduction

In modern wireless communications, polar codes ensure data integrity by selecting the most reliable bit-channels to carry information while "freezing" others. Traditionally, this selection is based on the assumption of an SC decoder. However, real-world systems employ SCL decoders, which maintain a list of candidate codewords to improve performance. Because SCL decoding is non-linear and sequential, finding an optimal code construction for it is mathematically complex. This work bridges the gap by using reinforcement learning to optimize codes directly for the target decoder's characteristics.

Methodology: Construction as a Maze-Traversing Game

The core innovation lies in formulating the selection of $K$ information bits out of $N$ total bits as a Markov Decision Process (MDP). The authors visualize this as a maze-traversing game on a grid.

The polar code construction process modeled as a path-finding problem in a grid, where moves correspond to bit assignments.

The RL Framework

  • The Environment: A grid where moving "down" represents freezing a bit and moving "right" represents assigning it as an information bit. A complete codeword construction requires exactly $N$ moves to reach the terminal state.
  • The Agent: The system utilizes the SARSA($\lambda$) algorithm. This choice allows the agent to use "eligibility traces," which help it understand how early decisions in the codeword construction affect the final decoding outcome.
  • The Reward Function: To minimize the Frame Error Rate (FER), the agent is penalized whenever a decoder fails. The authors use an SCL-Genie decoder during training. If the correct codeword is dropped from the decoder's list at any point, the game ends, and the agent receives a negative reward. This forces the agent to prioritize bit combinations that maximize the probability of the correct path remaining in the SCL list.

Experimental Setup

The performance was evaluated using simulated transmissions over Additive White Gaussian Noise (AWGN) channels with BPSK modulation. The study focused on:

  • Short blocks: $\mathcal{P}(16, 8)$
  • Medium blocks: $\mathcal{P}(128, 64)$ and Cyclic Redundancy Check (CRC)-aided $\mathcal{P}(128, 56+8)$. Results were compared against the standard construction method by Tal & Vardy (2013), which is a benchmark for 5G implementations.

Key Results and Discussion

The RL-based approach, referred to as the "Game" construction, demonstrated clear advantages over traditional methods. When tested with a basic SC decoder, the agent successfully rediscovered the known optimal construction, validating the framework's integrity.

Comparison of Frame Error Rate (FER) between standard 5G constructions and the RL-based 'Game' construction across different list sizes.

As shown in the performance metrics, the RL-constructed codes consistently achieved lower FER than standard constructions when paired with SCL decoders (list sizes 2, 4, and 8). The gains were particularly pronounced when integrated with CRC, suggesting that the RL agent learns to exploit the synergy between the code structure and the CRC-aided list decoding process. Furthermore, the RL approach proved highly efficient; for a 128-bit code, the agent converged in fewer than 80,000 samples, making it significantly faster than exhaustive Monte Carlo search methods.

Conclusion and Future Directions

This research proves that reinforcement learning can effectively navigate the complex design space of error-correction codes. By optimizing for the actual decoder used in deployment, RL discovers superior bit-channel combinations that traditional theory-driven methods overlook.

Future work aims to scale this approach to longer codewords ($N \geq 1024$) by transitioning from tabular RL to Deep Reinforcement Learning. Additionally, exploring the robustness of these learned constructions across varying Signal-to-Noise Ratios (SNR) and different channel models remains a key area for further investigation.

Summary updated

BibTeX
@article{liao2020construction,
  author = {Yun Liao and Seyyed Ali Hashemi and John M. Cioffi and Andrea Goldsmith},
  title = {{Construction of Polar Codes with Reinforcement Learning}},
  journal = {IEEE Trans. Communications},
  year = {2020},
  doi = {10.1109/tcomm.2021.3120274},
}
Figure