Decoding Reed–Muller Codes Using Redundant Code Constraints
Mengke Lian, Christian Häger, Henry D. Pfister
Abstract
The recursive projection-aggregation (RPA) decoding algorithm for Reed-Muller (RM) codes was recently introduced by Ye and Abbe. We show that the RPA algorithm is closely related to (weighted) belief-propagation (BP) decoding by interpreting it as a message-passing algorithm on a factor graph with redundant code constraints. We use this observation to introduce a novel decoder tailored to high-rate RM codes. The new algorithm relies on puncturing rather than projections and is called recursive puncturing-aggregation (RXA). We also investigate collapsed (i.e., non-recursive) versions of RPA and RXA and show some examples where they achieve similar performance with lower decoding complexity.
Topics & Concepts
PuncturingDecoding methodsList decodingComputer scienceBelief propagationFactor graphBerlekamp–Welch algorithmAlgorithmCode (set theory)Sequential decodingMessage passingTheoretical computer scienceConcatenated error correction codeBlock codeParallel computingTelecommunicationsProgramming languageSet (abstract data type)Error Correcting Code TechniquesDNA and Biological ComputingAdvanced Wireless Communication Techniques