Generalized RM (GRM) code[13] 

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.

Rate

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

Notes

See books [68] for details of GRM codes.

Parents

Children

Cousins

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]
G. Reeves and H. D. Pfister, “Achieving Capacity on Non-Binary Channels with Generalized Reed-Muller Codes”, (2023) arXiv:2305.07779
[6]
E. F. Assmus and J. D. Key, Designs and Their Codes (Cambridge University Press, 1992) DOI
[7]
W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes (Cambridge University Press, 2003) DOI
[8]
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.
[9]
S. G. Vléduts and Yu. I. Manin, “Linear codes and modular curves”, Journal of Soviet Mathematics 30, 2611 (1985) DOI
[10]
T. Høholdt, J.H. Van Lint, and R. Pellikaan, 1998. Algebraic geometry codes. Handbook of coding theory, 1 (Part 1), pp.871-961.
[11]
T. Blackmore and G. H. Norton, “Matrix-Product Codes over ? q”, Applicable Algebra in Engineering, Communication and Computing 12, 477 (2001) DOI
[12]
S. Yekhanin, “Locally Decodable Codes”, Foundations and Trends® in Theoretical Computer Science 6, 139 (2012) DOI
[13]
Gopi, Sivakanth. Locality in coding theory. Diss. Princeton University, 2018.
[14]
S. D. Berman, “On the theory of group codes”, Cybernetics 3, 25 (1969) DOI
[15]
Charpin, Pascale. Codes idéaux de certaines algèbres modulaires. Diss. 1982.
[16]
P. Landrock and O. Manz, “Classical codes as ideals in group algebras”, Designs, Codes and Cryptography 2, 273 (1992) DOI
[17]
W. Willems, "Codes in Group Algebras." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
[18]
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
[19]
S. Arora et al., “Proof verification and the hardness of approximation problems”, Journal of the ACM 45, 501 (1998) DOI
[20]
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
[21]
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
[22]
M. Chapman, T. Vidick, and H. Yuen, “Efficiently stable presentations from error-correcting codes”, (2023) arXiv:2311.04681
[23]
R. E. Blahut, Algebraic Codes for Data Transmission (Cambridge University Press, 2003) DOI
[24]
J. B. Little, “Algebraic geometry codes from higher dimensional varieties”, (2008) arXiv:0802.2349
Page edit log

Your contribution is welcome!

on github.com (edit & pull request)— see instructions

edit on this site

Zoo Code ID: generalized_reed_muller

Cite as:
“Generalized RM (GRM) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/generalized_reed_muller
BibTeX:
@incollection{eczoo_generalized_reed_muller, title={Generalized RM (GRM) code}, booktitle={The Error Correction Zoo}, year={2022}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/generalized_reed_muller} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/generalized_reed_muller

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/generalized_reed_muller.yml.