Comparison shows CHIRRUP better exploits repeated data in decoding codes
The Value of Duplicate Measurements When Decoding Second-Order Reed-Muller Codes
Information Theory
Summary
The paper studies two ways to decode second-order Reed-Muller codes, which are important for error correction in communication. One method (RPA) uses a certain mathematical object called a skew-symmetric matrix, while the other (CHIRRUP) uses a symmetric matrix with values mod 4. The authors explain how these mathematical objects relate and how differences in their ranks affect the decoding reliability. They find that CHIRRUP is better at using repeated measurements, especially on certain code families, helping it to outperform the standard RPA method.
What this means in practice
- •For communications engineers: Improve decoding algorithms for error-correcting codes in digital communication systems when multiple noisy measurements are available.
- •For network hardware designers: Design decoders that efficiently combine repeated data to improve reliability in wireless or optical links using Reed-Muller codes.
Authors
Ziang Gao, Robert Calderbank
Abstract
We compare the performance of the RPA and CHIRRUP decoding algorithms for second-order Reed--Muller codes. The RPA algorithm recovers a binary quadratic form associated with a skew-symmetric matrix $M$, whereas CHIRRUP recovers a $\mathbb{Z}_4$-valued quadratic form associated with a symmetric matrix $P$. We describe how the Gray map connects the evaluation vectors of these forms, inducing a rank-preserving correspondence between $M$ and $P$. We analyze how Euclidean distance between evaluation vectors is governed by matrix rank differences using Delsarte--Goethals sets $DG(m,r)$. We demonstrate that CHIRRUP uses repeated measurements more effectively than RPA on these ensembles. While a kernel-aware variant of RPA improves performance on singular quadratic forms by aggregating projection directions across cosets of $\ker M$, CHIRRUP's tree search combines multiple row estimates more efficiently on $DG(m,r)$ when $r < \frac{m-1}{2}$, outperforming vanilla RPA.