Generalized RS (GRS) code 


An \([n,k,n-k+1]_q\) linear code that is a modification of the RS code where codeword polynomials are multiplied by additional prefactors. Each message \(\mu\) is encoded into a string of values of the corresponding polynomial \(f_\mu\) at the points \(\alpha_i\), multiplied by a corresponding nonzero factor \(v_i \in GF(q)\), \begin{align} \mu\to\left( v_{1}f_{\mu}\left(\alpha_{1}\right),v_{2}f_{\mu}\left(\alpha_{2}\right),\cdots,v_{n}f_{\mu}\left(\alpha_{n}\right)\right)~. \tag*{(1)}\end{align}


The code can detect \(n-k\) errors, and can correct errors \( \left\lfloor (n-k)/2\right\rfloor \) errors.


The decoding process of GRS codes reduces to the solution of a polynomial congruence equation, usually referred to as the key equation. Decoding schemes are based on applications of the Euclid algorithm to solve the key equation.Berlekamp-Massey decoder with runtime of order \(O(n^2)\) [13].Guruswami-Sudan list decoder [4,5] and modification by Koetter-Vardy for soft-decision decoding [6].Hard-decision decoder for errors within the Singleton bound [7].


Commonly used in mass storage systems such as CDs, DVDs, QR codes etc.Various cloud storage systems [8].Public-key cryptosystems generalizing those that used Goppa codes [911], some of which were proven to be insecure [12]. More recent works focus on methods to mask the algebraic structure using subcodes of GRS codes [13]. For example, a key-recovery attack was developed in Ref. [14] for a variant of masking method proposed in Ref. [15].





E. Berlekamp, “Nonbinary BCH decoding (Abstr.)”, IEEE Transactions on Information Theory 14, 242 (1968) DOI
J. Massey, “Shift-register synthesis and BCH decoding”, IEEE Transactions on Information Theory 15, 122 (1969) DOI
E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, 1968
V. Guruswami and M. Sudan, “Improved decoding of Reed-Solomon and algebraic-geometry codes”, IEEE Transactions on Information Theory 45, 1757 (1999) DOI
V. Guruswami and M. Sudan, “Improved decoding of Reed-Solomon and algebraic-geometric codes”, Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280) DOI
R. Koetter and A. Vardy, “Algebraic soft-decision decoding of reed-solomon codes”, IEEE Transactions on Information Theory 49, 2809 (2003) DOI
Berman, A., Dor, A., Shany, Y., Shapir, I., and Doubchak, A. (2023). U.S. Patent No. 11,855,658. Washington, DC: U.S. Patent and Trademark Office.
H. Dau et al., “Repairing Reed-Solomon Codes With Multiple Erasures”, IEEE Transactions on Information Theory 64, 6567 (2018) arXiv:1612.01361 DOI
R. J. McEliece, A public-key cryptosystem based on algebraic coding theory, Technical report, Jet Propulsion Lab. DSN Progress Report (1978).
H. Janwa and O. Moreno, “McEliece public key cryptosystems using algebraic-geometric codes”, Designs, Codes and Cryptography 8, (1996) DOI
H. Niederreiter (1986). Knapsack-type cryptosystems and algebraic coding theory. Problems of Control and Information Theory. Problemy Upravlenija I Teorii Informacii. 15: 159–166.
V. M. SIDELNIKOV and S. O. SHESTAKOV, “On insecurity of cryptosystems based on generalized Reed-Solomon codes”, Discrete Mathematics and Applications 2, (1992) DOI
T. P. Berger and P. Loidreau, “How to Mask the Structure of Codes for a Cryptographic Use”, Designs, Codes and Cryptography 35, 63 (2005) DOI
A. Couvreur et al., “Distinguisher-Based Attacks on Public-Key Cryptosystems Using Reed-Solomon Codes”, (2014) arXiv:1307.6458
M. Baldi et al., “Enhanced public key security for the McEliece cryptosystem”, (2014) arXiv:1108.2462
A. Couvreur, H. Randriambololona, "Algebraic Geometry Codes and Some Applications." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
M. A. Tsfasman and S. G. Vlăduţ, Algebraic-Geometric Codes (Springer Netherlands, 1991) DOI
T. Høholdt, J.H. Van Lint, and R. Pellikaan, 1998. Algebraic geometry codes. Handbook of coding theory, 1 (Part 1), pp.871-961.
T. Yaghoobian and I. F. Blake, “Hermitian codes as generalized Reed-Solomon codes”, Designs, Codes and Cryptography 2, 5 (1992) DOI
W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes (Cambridge University Press, 2003) DOI
M. Grassl and M. Rotteler, “Quantum MDS codes over small fields”, 2015 IEEE International Symposium on Information Theory (ISIT) (2015) arXiv:1502.05267 DOI
S. Ball, “Grassl–Rötteler cyclic and consta-cyclic MDS codes are generalised Reed–Solomon codes”, Designs, Codes and Cryptography 91, 1685 (2022) DOI
H. Liu and S. Liu, “A class of constacyclic codes are generalized Reed–Solomon codes”, Designs, Codes and Cryptography 91, 4143 (2023) DOI
T. Bergamaschi, L. Golowich, and S. Gunn, “Approaching the Quantum Singleton Bound with Approximate Error Correction”, (2022) arXiv:2212.09935
Page edit log

Your contribution is welcome!

on (edit & pull request)— see instructions

edit on this site

Zoo Code ID: generalized_reed_solomon

Cite as:
“Generalized RS (GRS) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022.
@incollection{eczoo_generalized_reed_solomon, title={Generalized RS (GRS) code}, booktitle={The Error Correction Zoo}, year={2022}, editor={Albert, Victor V. and Faist, Philippe}, url={} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:

Cite as:

“Generalized RS (GRS) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022.