Generalized RM (GRM) code

Generalized RM (GRM) code[1–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 the points of \(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.

Its automorphism group is the general affine group \(GA(m,GF(q))\) [4]. Any nontrivial \(q\)-ary linear code invariant under this group is equivalent to a GRM code [5].

Protection

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

Rate

GRM codes achieve capacity on sufficiently symmetric non-binary channels [8].

Notes

See books [9–11] for details of GRM codes.

Cousins

Group-algebra code— GRM codes over prime-power fields are group-algebra codes [12–14][15; Exam. 16.4.11].
Cyclic linear \(q\)-ary code— GRM codes with nonzero evaluation points are cyclic [7; pg. 52].
\(q\)-ary linear LTC— GRM codes for \(r<q\) can be LTCs in the low- [16,17] and high-error [18,19] regimes. They admit weakly stable presentations of their corresponding groups [20].
Difference-set cyclic (DSC) code— DSC codes can be subfield subcodes of GRM codes, and visa versa [21; Thm. 6.14].
Finite-geometry LDPC (FG-LDPC) code— Some EG-LDPC codes are duals of subfield subcodes of GRM codes [22; pg. 448].
Batch code— GRM codes can be used to construct batch codes [23].
\(q\)-ary Hamming code— \(q\)-ary Hamming codes are dual to first-order GRM codes [7; pg. 45].
Galois-qudit quantum RM code— Generalized RM codes can be used to construct Galois-qudit RM codes.
Galois-qudit expander code— Expander codes with RS inner codes contain GRM codewords because tensor products of univariate polynomials (corresponding to RS codewords) yield multivariate polynomials (corresponding to GRM codewords) [24].

Member of code lists

Primary Hierarchy

Classical Domain

Galois-field Kingdom

\(q\)-ary codeECC

Additive \(q\)-ary codeECC

Linear \(q\)-ary codeECC

Evaluation code

Polynomial evaluation code

Parents

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)\) [25,26][7; pgs. 44-46].

Multiplicity codeLinear \(q\)-ary ECC

Multivariate multiplicity codes of degree \(s=1\) reduce to GRM codes.

Matrix-product codeECC

Applying a special case of the matrix-product procedure yields GRM codes [27].

\(q\)-ary linear LCCLinear \(q\)-ary LCC LRC Distributed-storage LDC ECC

GRM codes are LDCs and LCCs [28,29].

Generalized RM (GRM) code

Children

Reed-Muller (RM) code

Binary GRM codes are RM codes.

Extended GRS code

GRM codes for univariate polynomials (\(m=1\)) reduce to extended RS codes [30].

Projective RM (PRM) code

Quantum convolutional code

GRM codes can be used to construct quantum convolutional codes [31–33].

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]: T. Berger and P. Charpin, “The automorphism group of Generalized Reed-Muller codes”, Discrete Mathematics 117, 1 (1993) DOI
[5]: P. Delsarte, “On cyclic codes that are invariant under the general linear group”, IEEE Transactions on Information Theory 16, 760 (1970) DOI
[6]: M. Tsfasman, S. Vlǎduţ, and D. Nogin. Algebraic geometric codes: basic notions. Vol. 139. American Mathematical Society, 2022.
[7]: M. A. Tsfasman and S. G. Vlăduţ, Algebraic-Geometric Codes (Springer Netherlands, 1991) DOI
[8]: G. Reeves and H. D. Pfister, “Achieving Capacity on Non-Binary Channels with Generalized Reed-Muller Codes”, (2023) arXiv:2305.07779
[9]: E. F. Assmus and J. D. Key, Designs and Their Codes (Cambridge University Press, 1992) DOI
[10]: W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes (Cambridge University Press, 2003) DOI
[11]: 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.
[12]: S. D. Berman, “On the theory of group codes”, Cybernetics 3, 25 (1969) DOI
[13]: Charpin, Pascale. Codes idéaux de certaines algèbres modulaires. Diss. 1982.
[14]: P. Landrock and O. Manz, “Classical codes as ideals in group algebras”, Designs, Codes and Cryptography 2, 273 (1992) DOI
[15]: W. Willems, "Codes in Group Algebras." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
[16]: L. Babai, L. Fortnow, L. A. Levin, and M. Szegedy, “Checking computations in polylogarithmic time”, Proceedings of the twenty-third annual ACM symposium on Theory of computing - STOC ’91 21 (1991) DOI
[17]: S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy, “Proof verification and the hardness of approximation problems”, Journal of the ACM 45, 501 (1998) DOI
[18]: R. Raz and S. Safra, “A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP”, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing - STOC ’97 475 (1997) DOI
[19]: S. Arora and M. Sudan, “Improved low-degree testing and its applications”, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing - STOC ’97 485 (1997) DOI
[20]: M. Chapman, T. Vidick, and H. Yuen, “Efficiently stable presentations from error-correcting codes”, (2023) arXiv:2311.04681
[21]: C. Ding, Codes from Difference Sets (WORLD SCIENTIFIC, 2014) DOI
[22]: R. E. Blahut, Algebraic Codes for Data Transmission (Cambridge University Press, 2003) DOI
[23]: T. Baumbaugh, Y. Diaz, S. Friesenhahn, F. Manganiello, and A. Vetter, “Batch Codes from Hamming and Reed-Müller Codes”, (2017) arXiv:1710.07386
[24]: L. Golowich and T.-C. Lin, “Quantum LDPC Codes with Transversal Non-Clifford Gates via Products of Algebraic Codes”, (2024) arXiv:2410.14662
[25]: S. G. Vléduts and Yu. I. Manin, “Linear codes and modular curves”, Journal of Soviet Mathematics 30, 2611 (1985) DOI
[26]: T. Høholdt, J.H. Van Lint, and R. Pellikaan, 1998. Algebraic geometry codes. Handbook of coding theory, 1 (Part 1), pp.871-961.
[27]: T. Blackmore and G. H. Norton, “Matrix-Product Codes over ? q”, Applicable Algebra in Engineering, Communication and Computing 12, 477 (2001) DOI
[28]: S. Yekhanin, “Locally Decodable Codes”, Foundations and Trends® in Theoretical Computer Science 6, 139 (2012) DOI
[29]: Gopi, Sivakanth. Locality in coding theory. Diss. Princeton University, 2018.
[30]: J. B. Little, “Algebraic geometry codes from higher dimensional varieties”, (2008) arXiv:0802.2349
[31]: S. A. Aly, A. Klappenecker, and P. K. Sarvepalli, “On Quantum and Classical BCH Codes”, (2006) arXiv:quant-ph/0604102
[32]: S. A. Aly, “On Quantum and Classical Error Control Codes: Constructions and Applications”, (2008) arXiv:0812.5104
[33]: “Nonbinary Stabilizer Codes”, Mathematics of Quantum Computation and Quantum Technology 305 (2007) DOI

Page edit log

Victor V. Albert (2022-07-20) — most recent

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/edit/main/codes/classical/q-ary_digits/ag/rm/generalized_reed_muller.yml.