Machine Learning-Aided Efficient Decoding of Reed-Muller Subcodes

Mohammad Vahid Jamali, Xiyang Liu, Ashok Vardhan Makkuva, Hessam Mahdavifar, Sewoong Oh, Pramod Viswanath

Abstract

Reed-Muller (RM) codes are capacity-achieving error-correcting codes, yet their practical application is hindered by rigid code rates and high decoding complexity. This paper investigates RM subcodes to achieve rate flexibility and introduces a machine learning-aided recursive decoding framework. We propose the soft-subRPA algorithm, a differentiable extension of the Recursive Projection-Aggregation (RPA) decoder. By training a model to prune the projection space, we achieve near-optimal performance while reducing computational complexity by a factor of 4 to 9.

Introduction

Reed-Muller (RM) codes are fundamental in coding theory due to their ability to reach the capacity of various communication channels. However, they face two significant hurdles:

  1. Rigid Rates: Standard RM codes only support a limited set of dimensions for a given blocklength.
  2. Decoding Complexity: State-of-the-art decoders like RPA require numerous "projections" (alternative data perspectives), leading to high computational costs.

RM subcodes address the rate limitation but lose the symmetry of full RM codes, making efficient decoding even more challenging. This work presents a solution that leverages machine learning to intelligently prune the decoding process, maintaining high performance with minimal overhead.

Methodology: subRPA and ML-Aided Pruning

The core of our approach is the extension of the RPA algorithm to subcodes. The proposed subRPA and its differentiable counterpart, soft-subRPA, utilize a recursive structure to decompose complex decoding tasks into simpler sub-problems.

Schematic of the recursive subRPA and soft-subRPA decoding algorithms across multiple layers of 1-D projections.

By replacing hard binary decisions with probabilistic Log-Likelihood Ratios (LLRs), the decoding process becomes differentiable. This allows us to use gradient-based machine learning to assign weights to different projections. We employ a "SOFT top-k" operator during training, enabling the model to learn which projections are most informative and prune the rest. This strategy transforms a discrete combinatorial selection problem into a continuous optimization task.

Experimental Results

We evaluated our approach using synthetic data generated for Additive White Gaussian Noise (AWGN) channels. The results indicate significant efficiency gains and performance improvements over traditional methods.

Performance and Efficiency

The ML-aided decoder matches the performance of the "full-projection" baseline while utilizing significantly fewer resources. Specifically, the pruned decoder achieves near-MAP (Maximum A Posteriori) performance with 4 to 9 times fewer projections.

Block error rate (BLER) performance comparison of ML-trained projection pruning against full-projection, minRank, and maxRank heuristics.

As shown in the figure above, selecting the "wrong" projections (maxRank) can lead to a performance loss of over 1 dB. In contrast, the ML-trained selection perfectly tracks the full-projection performance. While a simple "minRank" heuristic performs well, the ML approach proves more robust, particularly when the number of allowed projections is highly constrained.

Comparison with Time-Sharing

A common alternative for achieving flexible rates is "time-sharing" between standard RM codes. Our findings show that RM subcodes decoded with the proposed methods significantly outperform time-sharing, providing gains of up to 1 dB in Signal-to-Noise Ratio (SNR).

Conclusion and Future Work

This work demonstrates that combining classical coding theory with modern machine learning can overcome the traditional trade-offs between flexibility, performance, and complexity in RM codes. While the training process is computationally intensive, the resulting decoder is highly efficient for real-time applications. Future research will explore scaling these methods to longer codes using higher-dimensional projections and improving the generalization of ML models across varying SNR conditions.

Summary updated

Abstract

Reed-Muller (RM) codes achieve the capacity of general binary-input memoryless symmetric channels and are conjectured to have a comparable performance to that of random codes in terms of scaling laws. However, such results are established assuming maximum-likelihood decoders for general code parameters. Also, RM codes only admit limited sets of rates. Efficient decoders such as successive cancellation list (SCL) decoder and recently-introduced recursive projection-aggregation (RPA) decoders are available for RM codes at finite lengths. In this paper, we focus on subcodes of RM codes with flexible rates. We first extend the RPA decoding algorithm to RM subcodes. To lower the complexity of our decoding algorithm, referred to as subRPA, we investigate different approaches to prune the projections. Next, we derive the soft-decision based version of our algorithm, called soft-subRPA, that not only improves upon the performance of subRPA but also enables a differentiable decoding algorithm. Building upon the soft-subRPA algorithm, we then provide a framework for training a machine learning (ML) model to search for good sets of projections that minimize the decoding error rate. Training our ML model enables achieving very close to the performance of full-projection decoding with a significantly smaller number of projections. We also show that the choice of the projections in decoding RM subcodes matters significantly, and our ML-aided projection pruning scheme is able to find a good selection, i.e., with negligible performance degradation compared to the full-projection case, given a reasonable number of projections.
BibTeX
@article{jamali2023machine,
  author = {Mohammad Vahid Jamali and Xiyang Liu and Ashok Vardhan Makkuva and Hessam Mahdavifar and Sewoong Oh and Pramod Viswanath},
  title = {{Machine Learning-Aided Efficient Decoding of Reed-Muller Subcodes}},
  journal = {IEEE J. Sel. Areas Inf. Theory},
  year = {2023},
  doi = {10.1109/jsait.2023.3298362},
}
Figure