Cyclically Equivariant Neural Decoders for Cyclic Codes

Xiangyu Chen, Min Ye

Introduction

In digital communications, error-correcting codes are essential for ensuring that data arrives intact despite noisy transmission channels. While classic decoding algorithms like Belief Propagation (BP) are highly efficient, they are not always optimal. Recently, "neural decoders" have emerged as a powerful generalization of BP. By treating the decoding Trellis graph as a neural network, these models can learn optimal weights from data to improve decoding accuracy.

However, most existing neural decoders operate as "black boxes." They ignore the rich algebraic structure inherent in specific families of codes, such as cyclic codes (e.g., BCH and Reed-Muller codes). For a cyclic code, the ideal decoder should be "equivariant": if you cyclically shift (rotate) the input bits, the output bits should undergo the exact same rotation. Standard neural networks do not guarantee this property, forcing them to spend massive amounts of computational time and training data "re-learning" the same decoding rules for every possible bit rotation.

This paper introduces a novel neural decoder specifically designed for cyclic codes by baking algebraic symmetry—specifically cyclical equivariance—directly into the network architecture.

Methodology: Baking Symmetry into the Architecture

To exploit the symmetry of cyclic codes, the researchers propose two major innovations:

1. Cyclically Equivariant Neural Decoder

Instead of using a standard $(n-k) \times n$ parity check matrix, the authors utilize an $n \times n$ cyclic matrix where every row is a shifted version of the first.

Cyclic matrix structure illustrating how weights are shared across shifted versions of the code.

Crucially, they impose a shift-invariant weight structure on the neural network. In the network's Trellis graph, edges that represent "the same" relationship in a rotated version of the code share the exact same learnable weights. This architectural constraint makes the decoder provably equivariant to cyclic shifts.

The Trellis graph showing how weights are shared across different layers and nodes to maintain cyclical equivariance.

2. List Decoding Procedure

The authors further exploit the fact that extended BCH and Reed-Muller (RM) codes are invariant under a large group of permutations (automorphisms). By adding a dummy parity bit and applying different permutations to the noisy input, they generate a "list" of candidate decodings. The decoder then selects the most likely codeword from this list, which significantly boosts overall performance.

Key Insights and Results

The authors evaluated their model on widely used families of cyclic codes, including various configurations of BCH codes and Punctured Reed-Muller (PRM) codes. Because of the built-in symmetry properties, the model can be trained entirely using the "all-zero" codeword, vastly simplifying the data generation process.

  • Massive Efficiency Gains: The most striking result is the training speed. By forcing the network to be equivariant, the authors drastically reduced the number of parameters the model needed to learn. For a BCH(63,45) code, their model trained in just 10 minutes, whereas the previous state-of-the-art (Hyper-Graph-Network) took over 2 days on the same hardware—a roughly 300x reduction in training time.
  • Improved Accuracy: The new decoder consistently outperformed previous neural BP decoders by approximately 0.7dB across various signal-to-noise ratios (SNR).
  • List Decoding Power: The proposed list decoding method provided up to a 3dB gain, bringing performance remarkably close to the theoretical Maximum Likelihood (ML) limit.
  • High-Rate Near-Optimality: For high-rate codes (rate $\ge 0.7$), the gap between this equivariant list decoder and the optimal ML decoder was less than 0.1dB.

Limitations and Future Work

While the results are highly promising, the authors note a few limitations. First, there is a "Rate Gap": while the decoder is nearly optimal for high-rate codes, a performance gap of >1dB to the ML lower bound remains for medium-to-low-rate codes. The theoretical reason for this distinction is still unclear.

Additionally, while highly accurate, the list decoding procedure increases computational overhead during inference (though it remains highly parallelizable). Finally, the current architecture is specifically tailored to cyclic codes. Extending these equivariant principles to other code families with different symmetry groups, such as Low-Density Parity-Check (LDPC) codes, remains an exciting open challenge for future research.

Summary updated

Abstract

Neural decoders were introduced as a generalization of the classic Belief Propagation (BP) decoding algorithms, where the Trellis graph in the BP algorithm is viewed as a neural network, and the weights in the Trellis graph are optimized by training the neural network. In this work, we propose a novel neural decoder for cyclic codes by exploiting their cyclically invariant property. More precisely, we impose a shift invariant structure on the weights of our neural decoder so that any cyclic shift of inputs results in the same cyclic shift of outputs. Extensive simulations with BCH codes and punctured Reed-Muller (RM) codes show that our new decoder consistently outperforms previous neural decoders when decoding cyclic codes. Finally, we propose a list decoding procedure that can significantly reduce the decoding error probability for BCH codes and punctured RM codes. For certain high-rate codes, the gap between our list decoder and the Maximum Likelihood decoder is less than $0.1$dB. Code available at github.com/cyclicallyneuraldecoder
BibTeX
@inproceedings{chen2021cyclically,
  author = {Xiangyu Chen and Min Ye},
  title = {{Cyclically Equivariant Neural Decoders for Cyclic Codes}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=Zlknm0Rx79},
}
Figure