RPA decoding needs fewer projections for structured errors
RPA Decoding with Few Subspace Projections for Correcting Structured Error Patterns in RM Codes
Information Theory
Summary
Reed-Muller codes help fix mistakes in digital data, but decoding them can be slow because it looks at many parts. The authors found that when the errors follow a pattern, like a burst of mistakes in a row, the decoder can check fewer parts yet still fix all errors. This makes decoding potentially faster and more efficient for these special cases. Their work shows how picking which parts to check carefully can reduce the effort needed to correct data.
What this means in practice
- •For communication system designers: Design more efficient decoders that correct burst errors with fewer projections to reduce computational cost.
- •For data storage engineers: Improve error correction for storage media that experience structured error patterns, enabling faster and less resource-intensive recovery.
Authors
Shiv Pratap Singh Rathore, Navin Kashyap
Abstract
The Recursive Projection Aggregation (RPA) decoder for Reed-Muller codes uses, in its default implementation, all one-dimensional subspaces at each level of recursion. We restrict our attention to the case where the number of errors is $t<d_{\mathrm{min}}/2$. It is known that if the number of errors is $t<d_{\mathrm{min}}/2$, then $2t+1$ subspaces at each level of recursion are sufficient to correct these errors. We show that, for structured error patterns, the number of subspaces required for correction can be reduced further by appropriately selecting the subspaces used for projection. In particular, when errors occur as a single burst of length $t < d_{\mathrm{min}}/2$, three subspaces at each level of recursion suffice for correction. We obtain similar results for multiple bursts and other structured error patterns as well.