Generalized RS (GRS) code 

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

Concatenations of GRS codes with random linear codes almost surely attains the GV bound [1].

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)\) [24].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

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

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) 28 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]
P. Delsarte, “On subfield subcodes of modified Reed-Solomon codes (Corresp.)”, IEEE Transactions on Information Theory 21, 575 (1975) DOI
[24]
M. Grassl and M. Rotteler, “Quantum MDS codes over small fields”, 2015 IEEE International Symposium on Information Theory (ISIT) (2015) arXiv:1502.05267 DOI
[25]
S. Ball, “Grassl–Rötteler cyclic and consta-cyclic MDS codes are generalised Reed–Solomon codes”, Designs, Codes and Cryptography 91, 1685 (2022) DOI
[26]
H. Liu and S. Liu, “A class of constacyclic codes are generalized Reed–Solomon codes”, Designs, Codes and Cryptography 91, 4143 (2023) DOI
[27]
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 github.com (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. https://errorcorrectionzoo.org/c/generalized_reed_solomon
BibTeX:
@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={https://errorcorrectionzoo.org/c/generalized_reed_solomon} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/generalized_reed_solomon

Cite as:

“Generalized RS (GRS) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/generalized_reed_solomon

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/q-ary_digits/ag/reed_solomon/generalized_reed_solomon.yml.