Description
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}
Protection
The code can detect \(n-k\) errors, and can correct errors \( \left\lfloor (n-k)/2\right\rfloor \) errors.
Rate
Decoding
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)\) [2–4].Guruswami-Sudan list decoder [5,6] and modification by Koetter-Vardy for soft-decision decoding [7].Hard-decision decoder for errors within the Singleton bound [8].
Realizations
Commonly used in mass storage systems such as CDs, DVDs, QR codes etc.Various cloud storage systems [9].A variation of the McEliece public-key cryptosystem [10,11] by Niederreiter [12] replaced the generator matrix by the parity check matrix of a GRS code. This was proven to be insecure since the public key exposes the algebraic structure of code [13]. More recent works focus on methods to mask the algebraic structure using subcodes of GRS codes [14]. For example, a key-recovery attack was developed in Ref. [15] for a variant of masking method proposed in Ref. [16].
Parents
- Evaluation AG code — GRS (RS) codes are in one-to-one correspondence with evaluation AG codes of univariate polynomials \(f\) with \(\cal X\) being the projective (affine) line [19,20][17; Thm. 15.3.24][18; Ch. 3.2].
- Maximum distance separable (MDS) code — GRS codes have distance \(n-k+1\), saturating the Singleton bound.
- Distributed-storage code — GRS codes are used in various cloud storage systems [9].
Children
- Extended GRS code — Extended GRS codes can be thought of as GRS codes that include an evaluation point of zero.
- Reed-Solomon (RS) code — A GRS code for which all multipliers \(v_i\) are unity reduces to an RS code.
Cousins
- Concatenated code — Concatenations of GRS codes with random linear codes almost surely attain the GV bound [1].
- Random code — Concatenations of GRS codes with random linear codes almost surely attain the GV bound [1].
- Linear \(q\)-ary code — Concatenations of GRS codes with random linear codes almost surely attain the GV bound [1].
- Hermitian code — Hermitian codes are concatenated GRS codes [21].
- Classical Goppa code — Goppa codes are \(GF(q)\)-subfield subcode of the dual of the GRS code over \(GF(q^m)\) with evaluation points \(\alpha_i\) and factors \(v_i=G(\alpha_i)^{-1}\) ([22], pg. 523; [20]).
- Alternant code — Alternant codes are subfield subcodes of GRS codes.
- Quantum maximum-distance-separable (MDS) code — Some MDS codes are constructed from cyclic and constacyclic codes [23] which are GRS codes [24,25].
- Folded quantum Reed-Solomon (FQRS) code — A folded quantum generalized RS (GRS) code can be constructed in similar fashion from GRS codes as FQRS codes are constructed from FRS codes [26; Sec. 3].
- Galois-qudit GRS code
References
- [1]
- C. Thommesen, “The existence of binary linear concatenated codes with Reed - Solomon outer codes which asymptotically meet the Gilbert- Varshamov bound”, IEEE Transactions on Information Theory 29, 850 (1983) DOI
- [2]
- E. Berlekamp, “Nonbinary BCH decoding (Abstr.)”, IEEE Transactions on Information Theory 14, 242 (1968) DOI
- [3]
- J. Massey, “Shift-register synthesis and BCH decoding”, IEEE Transactions on Information Theory 15, 122 (1969) DOI
- [4]
- E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, 1968
- [5]
- V. Guruswami and M. Sudan, “Improved decoding of Reed-Solomon and algebraic-geometry codes”, IEEE Transactions on Information Theory 45, 1757 (1999) DOI
- [6]
- 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
- [7]
- R. Koetter and A. Vardy, “Algebraic soft-decision decoding of reed-solomon codes”, IEEE Transactions on Information Theory 49, 2809 (2003) DOI
- [8]
- 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.
- [9]
- H. Dau et al., “Repairing Reed-Solomon Codes With Multiple Erasures”, IEEE Transactions on Information Theory 64, 6567 (2018) arXiv:1612.01361 DOI
- [10]
- R. J. McEliece, A public-key cryptosystem based on algebraic coding theory, Technical report, Jet Propulsion Lab. DSN Progress Report (1978).
- [11]
- H. Janwa and O. Moreno, “McEliece public key cryptosystems using algebraic-geometric codes”, Designs, Codes and Cryptography 8, (1996) DOI
- [12]
- H. Niederreiter (1986). Knapsack-type cryptosystems and algebraic coding theory. Problems of Control and Information Theory. Problemy Upravlenija I Teorii Informacii. 15: 159–166.
- [13]
- V. M. SIDELNIKOV and S. O. SHESTAKOV, “On insecurity of cryptosystems based on generalized Reed-Solomon codes”, Discrete Mathematics and Applications 2, (1992) DOI
- [14]
- 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
- [15]
- A. Couvreur et al., “Distinguisher-Based Attacks on Public-Key Cryptosystems Using Reed-Solomon Codes”, (2014) arXiv:1307.6458
- [16]
- M. Baldi et al., “Enhanced public key security for the McEliece cryptosystem”, (2014) arXiv:1108.2462
- [17]
- A. Couvreur, H. Randriambololona, "Algebraic Geometry Codes and Some Applications." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [18]
- M. A. Tsfasman and S. G. Vlăduţ, Algebraic-Geometric Codes (Springer Netherlands, 1991) DOI
- [19]
- M. Tsfasman, S. Vlǎduţ, and D. Nogin. Algebraic geometric codes: basic notions. Vol. 139. American Mathematical Society, 2022.
- [20]
- T. Høholdt, J.H. Van Lint, and R. Pellikaan, 1998. Algebraic geometry codes. Handbook of coding theory, 1 (Part 1), pp.871-961.
- [21]
- T. Yaghoobian and I. F. Blake, “Hermitian codes as generalized Reed-Solomon codes”, Designs, Codes and Cryptography 2, 5 (1992) DOI
- [22]
- W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes (Cambridge University Press, 2003) DOI
- [23]
- M. Grassl and M. Rotteler, “Quantum MDS codes over small fields”, 2015 IEEE International Symposium on Information Theory (ISIT) (2015) arXiv:1502.05267 DOI
- [24]
- S. Ball, “Grassl–Rötteler cyclic and consta-cyclic MDS codes are generalised Reed–Solomon codes”, Designs, Codes and Cryptography 91, 1685 (2022) DOI
- [25]
- H. Liu and S. Liu, “A class of constacyclic codes are generalized Reed–Solomon codes”, Designs, Codes and Cryptography 91, 4143 (2023) DOI
- [26]
- T. Bergamaschi, L. Golowich, and S. Gunn, “Approaching the Quantum Singleton Bound with Approximate Error Correction”, (2022) arXiv:2212.09935
Page edit log
- Victor V. Albert (2022-09-16) — most recent
- Victor V. Albert (2022-05-17)
- Muhammad Junaid Aftab (2022-04-21)
- Qingfeng (Kee) Wang (2021-12-20)
Cite as:
“Generalized RS (GRS) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/generalized_reed_solomon