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.

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)\) [13].Guruswami-Sudan list decoder [4] and modification by Koetter-Vardy for soft-decision decoding [5].

Realizations

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

Parents

Children

Cousins

References

[1]
E. Berlekamp, “Nonbinary BCH decoding (Abstr.)”, IEEE Transactions on Information Theory 14, 242 (1968) DOI
[2]
J. Massey, “Shift-register synthesis and BCH decoding”, IEEE Transactions on Information Theory 15, 122 (1969) DOI
[3]
E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, 1968
[4]
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
[5]
R. Koetter and A. Vardy, “Algebraic soft-decision decoding of reed-solomon codes”, IEEE Transactions on Information Theory 49, 2809 (2003) DOI
[6]
H. Dau et al., “Repairing Reed-Solomon Codes With Multiple Erasures”, IEEE Transactions on Information Theory 64, 6567 (2018) arXiv:1612.01361 DOI
[7]
R. J. McEliece, A public-key cryptosystem based on algebraic coding theory, Technical report, Jet Propulsion Lab. DSN Progress Report (1978).
[8]
H. Janwa and O. Moreno, “McEliece public key cryptosystems using algebraic-geometric codes”, Designs, Codes and Cryptography 8, (1996) DOI
[9]
H. Niederreiter (1986). Knapsack-type cryptosystems and algebraic coding theory. Problems of Control and Information Theory. Problemy Upravlenija I Teorii Informacii. 15: 159–166.
[10]
V. M. SIDELNIKOV and S. O. SHESTAKOV, “On insecurity of cryptosystems based on generalized Reed-Solomon codes”, Discrete Mathematics and Applications 2, (1992) DOI
[11]
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
[12]
A. Couvreur et al., “Distinguisher-Based Attacks on Public-Key Cryptosystems Using Reed-Solomon Codes”, (2014) arXiv:1307.6458
[13]
M. Baldi et al., “Enhanced public key security for the McEliece cryptosystem”, (2014) arXiv:1108.2462
[14]
A. Couvreur, H. Randriambololona, "Algebraic Geometry Codes and Some Applications." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
[15]
M. A. Tsfasman and S. G. Vlăduţ, Algebraic-Geometric Codes (Springer Netherlands, 1991) DOI
[16]
T. Høholdt, J.H. Van Lint, and R. Pellikaan, 1998. Algebraic geometry codes. Handbook of coding theory, 1 (Part 1), pp.871-961.
[17]
T. Yaghoobian and I. F. Blake, “Hermitian codes as generalized Reed-Solomon codes”, Designs, Codes and Cryptography 2, 5 (1992) DOI
[18]
W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes (Cambridge University Press, 2003) DOI
Page edit log

Your contribution is welcome!

on github.com (edit & pull request)

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/tree/main/codes/classical/q-ary_digits/ag/rs/generalized_reed_solomon.yml.