An Analysis of RPA Decoding of Reed-Muller Codes Over the BSC

2024/12/11 by Rameshwar, V. Arvind, Lalitha, V.
#FOS: Computer and information sciences #Information Theory (cs.IT)

paper · doi:10.48550/arxiv.2412.08129

Abstract

In this paper, we revisit the Recursive Projection-Aggregation (RPA) decoder, of Ye and Abbe (2020), for Reed-Muller (RM) codes. Our main contribution is an explicit upper bound on the probability of incorrect decoding, using the RPA decoder, over a binary symmetric channel (BSC). Importantly, we focus on the events where a single iteration of the RPA decoder, in each recursive call, is sufficient for convergence. Key components of our analysis are explicit estimates of the probability of incorrect decoding of first-order RM codes using a maximum likelihood (ML) decoder, and estimates of the error probabilities during the aggregation phase of the RPA decoder. Our results allow us to show that for RM codes with blocklength N = 2^m, the RPA decoder can achieve vanishing error probabilities, in the large blocklength limit, for RM orders that grow roughly logarithmically in m.

Related

• Recursive projection-aggregation decoding of Reed-Muller codes
• Reed-Muller Subcodes: Machine Learning-Aided Design of Efficient Soft Recursive Decoding
• Machine Learning-Aided Efficient Decoding of Reed-Muller Subcodes
• Multi-Factor Pruning for Recursive Projection-Aggregation Decoding of RM Codes
• Sparse Multi-Decoder Recursive Projection Aggregation for Reed-Muller\n Codes