Weight patterns revealed for specific generalized Reed Muller codes
Weight spectra of some families of GRM codes
Information Theory
Summary
Generalized Reed–Muller codes are mathematical tools used to detect and correct errors in data transmissions. The authors figured out exactly which weights (or error-correcting capabilities) appear in certain families of these codes when the parameters follow specific patterns. Their method uses mathematical induction combined with computer calculations to confirm the patterns. This helps expand what we know about these codes and how they might perform.
What this means in practice
- •For error correction engineers: Determine exact error detection capabilities for certain Reed–Muller based codes to inform design of reliable communication systems.
- •For cryptography developers: Use detailed code weight information to assess security margins and error resilience in cryptographic protocols using Reed–Muller codes.
Tested on simulated data.
Authors
Minjia Shi, Zhaokang Xing, Patrick Sole
Abstract
Let $\mathrm{RM}_q(r,m)$ denote the generalized Reed--Muller code of order $r$ and length $q^m$ over the finite field $\mathbb{F}_q$. We completely determine the weight spectra of $\mathrm{RM}_3(2m-i,m)$ for $i=3,4$, $\mathrm{RM}_4(3m-i,m)$ for $i=2,3$, $\mathrm{RM}_5(4m-4,m)$, and $\mathrm{RM}_7(6m-4,m)$, in the ranges of $m$ specified in the corresponding results. The proofs proceed by induction on $m$, using a sumset inclusion for GRM weight spectra together with results on low-weight codewords. The required base cases are established by computations in Magma and, for certain ternary cases, exact constraint solving with Z3.