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))\). Any nontrivial \(q\)-ary linear code invariant under this group is equivalent to a GRM code [4].
Protection
Code parameters for specific \(m,r\) are given in Ref. [5][6; pg. 46].
Rate
GRM codes achieve capacity on sufficiently symmetric non-binary channels [7].
Notes
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)\) [11,12][6; pgs. 44-46].
- Multiplicity code — Multivariate multiplicity codes of degree \(s=1\) reduce to GRM codes.
- Matrix-product code — Applying a special case of the matrix-product procedure yields GRM codes [13].
- \(q\)-ary linear LCC — GRM codes are LDCs and LCCs [14,15].
Children
- Reed-Muller (RM) code — Binary GRM codes are RM codes.
- Projective RM (PRM) code
Cousins
- Group-algebra code — GRM codes over prime-power fields are group-algebra codes [16–18][19; Ex. 16.4.11].
- Cyclic linear \(q\)-ary code — GRM codes with nonzero evaluation points are cyclic [6; pg. 52].
- \(q\)-ary linear LTC — GRM codes for \(r<q\) can be LTCs in the low- [20,21] and high-error [22,23] regimes. They admit weakly stable presentations of their corresponding groups [24].
- Finite-geometry LDPC (FG-LDPC) code — Some EG-LDPC codes are duals of subfield subcodes of GRM codes [25; pg. 448].
- Extended GRS code — GRM codes for univariate polynomials (\(m=1\)) reduce to extended RS codes [26].
- \(q\)-ary Hamming code — \(q\)-ary Hamming codes are dual to first-order GRM codes [6; pg. 45].
- Galois-qudit quantum RM code
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]
- P. Delsarte, “On cyclic codes that are invariant under the general linear group”, IEEE Transactions on Information Theory 16, 760 (1970) DOI
- [5]
- M. Tsfasman, S. Vlǎduţ, and D. Nogin. Algebraic geometric codes: basic notions. Vol. 139. American Mathematical Society, 2022.
- [6]
- M. A. Tsfasman and S. G. Vlăduţ, Algebraic-Geometric Codes (Springer Netherlands, 1991) DOI
- [7]
- G. Reeves and H. D. Pfister, “Achieving Capacity on Non-Binary Channels with Generalized Reed-Muller Codes”, (2023) arXiv:2305.07779
- [8]
- E. F. Assmus and J. D. Key, Designs and Their Codes (Cambridge University Press, 1992) DOI
- [9]
- W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes (Cambridge University Press, 2003) DOI
- [10]
- 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.
- [11]
- S. G. Vléduts and Yu. I. Manin, “Linear codes and modular curves”, Journal of Soviet Mathematics 30, 2611 (1985) DOI
- [12]
- T. Høholdt, J.H. Van Lint, and R. Pellikaan, 1998. Algebraic geometry codes. Handbook of coding theory, 1 (Part 1), pp.871-961.
- [13]
- T. Blackmore and G. H. Norton, “Matrix-Product Codes over ? q”, Applicable Algebra in Engineering, Communication and Computing 12, 477 (2001) DOI
- [14]
- S. Yekhanin, “Locally Decodable Codes”, Foundations and Trends® in Theoretical Computer Science 6, 139 (2012) DOI
- [15]
- Gopi, Sivakanth. Locality in coding theory. Diss. Princeton University, 2018.
- [16]
- S. D. Berman, “On the theory of group codes”, Cybernetics 3, 25 (1969) DOI
- [17]
- Charpin, Pascale. Codes idéaux de certaines algèbres modulaires. Diss. 1982.
- [18]
- P. Landrock and O. Manz, “Classical codes as ideals in group algebras”, Designs, Codes and Cryptography 2, 273 (1992) DOI
- [19]
- W. Willems, "Codes in Group Algebras." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [20]
- L. Babai et al., “Checking computations in polylogarithmic time”, Proceedings of the twenty-third annual ACM symposium on Theory of computing - STOC ’91 (1991) DOI
- [21]
- S. Arora et al., “Proof verification and the hardness of approximation problems”, Journal of the ACM 45, 501 (1998) DOI
- [22]
- 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 (1997) DOI
- [23]
- 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 (1997) DOI
- [24]
- M. Chapman, T. Vidick, and H. Yuen, “Efficiently stable presentations from error-correcting codes”, (2023) arXiv:2311.04681
- [25]
- R. E. Blahut, Algebraic Codes for Data Transmission (Cambridge University Press, 2003) DOI
- [26]
- J. B. Little, “Algebraic geometry codes from higher dimensional varieties”, (2008) arXiv:0802.2349
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