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)~.
\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)\) [1][2][3].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 [7][8][9], 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
- 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 ([14], Thm. 15.3.24; [15], Ch. 3.2; [16]).
- Polynomial evaluation code — GRS (RS) codes are in one-to-one correspondence with univariate polynomial evaluation codes with \(\cal X\) being the projective (affine) line ([14], Thm. 15.3.24; [15], Ch. 3.2; [16]).
Children
- Alternant code — Alternant codes are subfield subcodes of GRS codes.
- Bose–Chaudhuri–Hocquenghem (BCH) code — BCH codes are subfield subcodes of GRS codes.
- 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}\) ([17], pg. 523; [16]).
- Extended GRS code — Extended GRS codes can be thought of as GRS codes that include an evaluation point of zero.
- Hermitian code — Hermitian codes are concatenated GRS codes [18].
- Reed-Solomon (RS) code — A GRS code for which all multipliers \(v_i\) are unity reduces to an RS code.
Cousins
- 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 [6].
- Binary BCH code — Binary BCH codes are subfield subcodes of GRS codes.
- Galois-qudit GRS code — Hermitian self-orthogonal GRS codes are used to construct Galois-qudit GRS codes in the Hermitian construction.
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). DOI; 1612.01361
- [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]
- Alain Couvreur et al., “Distinguisher-Based Attacks on Public-Key Cryptosystems Using Reed-Solomon Codes”. 1307.6458
- [13]
- Marco Baldi et al., “Enhanced public key security for the McEliece cryptosystem”. 1108.2462
- [14]
- W. C. Huffman, J.-L. Kim, and P. Solé, 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]
- W. C. Huffman and V. Pless, Fundamentals of Error-correcting Codes (Cambridge University Press, 2003). DOI
- [18]
- T. Yaghoobian and I. F. Blake, “Hermitian codes as generalized Reed-Solomon codes”, Designs, Codes and Cryptography 2, 5 (1992). DOI
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)
Zoo code information
Cite as:
“Generalized RS (GRS) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/generalized_reed_solomon