Description
Let \( G(x) \) be a polynomial describing a projective-plane curve with coefficients from \( GF(q^m) \) for some fixed integer \(m\). Let \( L \) be a finite subset of the extension field \( GF(q^m) \) where \(q\) is prime, meaning \( L = \{\alpha_1, \cdots, \alpha_n\} \) is a subset of nonzero elements of \( GF(q^m) \). A Goppa code \( \Gamma(L,G) \) is an \([n,k,d]_q\) linear code consisting of all vectors \(a = a_1, \cdots, a_n\) such that \( R_a(x) =0 \) modulo \(G(x)\), where \( R_a(x) = \sum_{i=1}^n \frac{a_i}{z - \alpha_i} \).
Goppa codes are residue AG codes [4; Thm. 15.3.28]. Their duals are evaluation codes that are sometimes called geometric Reed Solomon codes [5; Thm. 2.71].
Protection
Decoding
Realizations
Notes
Parents
- Generalized RS (GRS) 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}\) ([15], pg. 523; [5]).
- Cartier code — Goppa codes are Cartier codes from a curve of genus zero [16].
Cousins
- \(q\)-ary linear LTC — Goppa codes are locally testable [17].
- Bose–Chaudhuri–Hocquenghem (BCH) code — Narrow-sense BCH codes are Goppa codes with \(L=\{1,\alpha^{-1},\cdots,\alpha^{1-n}\}\) and \(G(x)=x^{\delta-1}\) ([15], pg. 522).
- Binary quantum Goppa code — Classical Goppa codes are used to construct their quantum versions.
References
- [1]
- V. D. Goppa, "A new class of linear error-correcting codes", Probl. Peredach. Inform., vol. 6, no. 3, pp. 24-30, Sept. 1970.
- [2]
- V. D. Goppa, "Rational representation of codes and (Lg) codes", Probl. Peredach. Inform., vol. 7, no. 3, pp. 41-49, Sept. 1971.
- [3]
- E. Berlekamp, “Goppa codes”, IEEE Transactions on Information Theory 19, 590 (1973) DOI
- [4]
- A. Couvreur, H. Randriambololona, "Algebraic Geometry Codes and Some Applications." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [5]
- T. Høholdt, J.H. Van Lint, and R. Pellikaan, 1998. Algebraic geometry codes. Handbook of coding theory, 1 (Part 1), pp.871-961.
- [6]
- N. Patterson, “The algebraic decoding of Goppa codes”, IEEE Transactions on Information Theory 21, 203 (1975) DOI
- [7]
- Y. Sugiyama et al., “A method for solving key equation for decoding goppa codes”, Information and Control 27, 87 (1975) DOI
- [8]
- R. McEliece, The Theory of Information and Coding (Cambridge University Press, 2002) DOI
- [9]
- 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
- [10]
- Daniel J. Bernstein, "Understanding binary-Goppa decoding." Cryptology ePrint Archive (2022).
- [11]
- R. J. McEliece, A public-key cryptosystem based on algebraic coding theory, Technical report, Jet Propulsion Lab. DSN Progress Report (1978).
- [12]
- H. Janwa and O. Moreno, “McEliece public key cryptosystems using algebraic-geometric codes”, Designs, Codes and Cryptography 8, (1996) DOI
- [13]
- H. Niederreiter (1986). Knapsack-type cryptosystems and algebraic coding theory. Problems of Control and Information Theory. Problemy Upravlenija I Teorii Informacii. 15: 159–166.
- [14]
- V. M. SIDELNIKOV and S. O. SHESTAKOV, “On insecurity of cryptosystems based on generalized Reed-Solomon codes”, Discrete Mathematics and Applications 2, (1992) DOI
- [15]
- W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes (Cambridge University Press, 2003) DOI
- [16]
- A. Couvreur, “Codes and the Cartier Operator”, (2012) arXiv:1206.4728
- [17]
- T. Kaufman and S. Litsyn, “Almost Orthogonal Linear Codes are Locally Testable”, 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS’05) DOI
Page edit log
- Victor V. Albert (2022-08-21) — most recent
- Victor V. Albert (2021-12-15)
- Manasi Shingane (2021-12-14)
Cite as:
“Classical Goppa code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/goppa