Generalized RM (GRM) code

Generalized RM (GRM) code[1][2][3]

Description

Reed-Muller code GRM\(_q(r,m)\) of length \(n=q^m\) over \(GF(q)\) with \(0\leq r\leq m(q-1)\). Its codewords are evaluations of the set of all degree-\(\leq r\) polynomials in \(m\) variables at a set of distinct points \(\{\alpha_1,\cdots,\alpha_n\}\) in \(GF(q)\).

Since \(\beta^q=\beta\) for any \(\beta\in GF(q)\), the above definition is not injective. Replacing each factor in each polynomial as \(x^q\to x\), the above set reduces to the set of all degree-\(\leq r\) polynomials in \(m\) variables such that no term has an exponent \(q\) or higher on any variable.

Protection

Code parameters for specific \(m,r\) are given in Ref. [4], pg. 46.

Notes

See books [5][6][7] for details of GRM codes.

Parents

Linear \(q\)-ary code
Polynomial evaluation code — GRM (PRM) codes are multivariate polynomial evaluation codes with \(\cal X\) being the entire \(m\)-dimensional affine (projective) space over \(GF(q)\) ([4], pgs. 44-46; [8][9]).
Matrix-product code — Applying a special case of the matrix-product procedure yields GRM codes [10].

Child

Projective RM (PRM) code

Cousins

Reed-Muller (RM) code
Cyclic linear \(q\)-ary code — GRM codes with nonzero evaluation points are cyclic ([4], pg. 52).
Extended GRS code — GRM codes for univariate polynomials (\(m=1\)) reduce to extended RS codes [11].
\(q\)-ary Hamming code — Hamming codes are dual to first-order GRM codes ([4], pg. 45).

References

[1]: T. Kasami, Shu Lin, and W. Peterson, “New generalizations of the Reed-Muller codes--I: Primitive codes”, IEEE Transactions on Information Theory 14, 189 (1968). DOI
[2]: E. Weldon, “New generalizations of the Reed-Muller codes--II: Nonprimitive codes”, IEEE Transactions on Information Theory 14, 199 (1968). DOI
[3]: P. Delsarte, J. M. Goethals, and F. J. Mac Williams, “On generalized ReedMuller codes and their relatives”, Information and Control 16, 403 (1970). DOI
[4]: M. A. Tsfasman and S. G. Vlăduţ, Algebraic-geometric Codes (Springer Netherlands, 1991). DOI
[5]: E. F. Assmus and J. D. Key, Designs and Their Codes (Cambridge University Press, 1992). DOI
[6]: W. C. Huffman and V. Pless, Fundamentals of Error-correcting Codes (Cambridge University Press, 2003). DOI
[7]: E. F. Assmus, Jr. and J. D. Key, “Polynomial codes and finite geometries,” in Handbook of Coding Theory, eds. V. S. Pless and W. C. Huffman. Amsterdam: Elsevier, 1998, pp. 1269–1343.
[8]: S. G. Vléduts and Y. I. Manin, “Linear codes and modular curves”, Journal of Soviet Mathematics 30, 2611 (1985). DOI
[9]: T. Høholdt, J.H. Van Lint, and R. Pellikaan, 1998. Algebraic geometry codes. Handbook of coding theory, 1 (Part 1), pp.871-961.
[10]: T. Blackmore and G. H. Norton, “Matrix-Product Codes over ? q”, Applicable Algebra in Engineering, Communication and Computing 12, 477 (2001). DOI
[11]: John B. Little, “Algebraic geometry codes from higher dimensional varieties”. 0802.2349

Cite as:

“Generalized RM (GRM) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/generalized_reed_muller

Github: https://github.com/errorcorrectionzoo/eczoo_data/tree/main/codes/classical/q-ary_digits/eval/generalized_reed_muller.yml.