Hermitian code[1,2][3; Sec. 4.4.3] 

Description

Evaluation AG code of rational functions evaluated on points lying on a Hermitian curve in either affine or projective space. Hermitian codes improve over RS codes in length: that RS codes have length at most \(q+1\) while Hermitian codes have length \(q^3 + 1\).

Hermitian codes of polynomials of total degree at most \(D\) can come in affine and epicyclic flavours, depending on whether the evaluations are over the affine plane or the bicyclic plane. The affine codes have length \(q^3\), epicyclic codes have length \((q-2)(q+1)^2\), and projective coeds have length \(q^3+1\).

The affine-space equation defining a Hermitian curve over \(\mathbb{F}_q = GF(q)\) is \(H(x,y) = x^{q+1} + y^{q+1} - 1\), while the projective-space equation, or Fermat version, is \(H(x:y:z) = x^{q+1} + y^{q+1} - z^{q+1}\). Substituting \(u = x+z\), \(v = x+y\), and \(w = x+y+z \) yields \(H(x,y,z) = x^{q+1} - y^{q}z - yz^{q} \), the Stichtenoth version of the curve.

To define the codes, fix \(r, D\) and let \begin{align} M_D = \left\{f(x,y,z) = \sum_{i+j \leq D = D}a_{i,j}x^{i}y^{j}z^{D - (i+j)}\right\} \tag*{(1)}\end{align} be the message space of degree-\(D\) polynomials, and \begin{align} S = \{(x:y:z) \in PG(2,q) \mid H(x:y:z) = 0 \}~. \tag*{(2)}\end{align} The Hermitian code \( C \) over is \begin{align} C = \{(f(\alpha_i))_{\alpha_i \in S}, \: f \in M_D \}~. \tag*{(3)}\end{align}

In affine coordinates, the Stichtenoth form of the curve is \begin{align} f(x,y) = x^{q+1} - y^{q} - y = N(x) - \text{tr}(y)~, \tag*{(4)}\end{align} where \(N(x) := x^{(q^{n}-1)/(q-1)}\) and \(\text{tr} := 1 + x^{q} + \ldots + x^{q^n}\) are the field norm and field trace in \(\mathbb{F}_{q^n}\), respectively. The Fermat version can be written as \(H(u,v,w) = u\overline{u} + v\overline{v} - w\overline{w}\), where the conjugation map \(\overline{u} = u^{q}\) is an isomorphism of \(\mathbb{F}_q \). In fact, when the field of evaluations \(\mathbb{F}_{q^2}\) is viewed as a quadratic extension of \(\mathbb{F}_q\) then the conjugation map is an \(\mathbb{F}_q\)-isomorphism that permutes the roots of the quadratic irreducible polynomial used to generate \(\mathbb{F}_{q^2}\) from \( \mathbb{F}_q[x]\).

There exists a family of Hermitian codes invariant under \(PGL(2,GF(q))\) [4].

Protection

Distance determined by properties of the Hermitian curve, the underlying field, and the functions used [5]; see [6; Sec. 5.3] for the general result. For evaluations of polynomials up to degree \(D\), the Hermitian code protects against at least \(n - (q+1)D\) errors whenever \(D < q + 1 \). If \(D \geq q+1 \), the Hermitian code protects against at least \(n-k - \frac{q(q-1)}{2} + 1\) errors.

Rate

For polynomial evaluations up to degree \(D\): if \(D < q + 1 \), \(k = \frac{(D+1)(D+2)}{2}\), and if \(D \geq q + 1 \), \(k = (q+1)D - \frac{q(q-1)}{2} + 1 \).

Decoding

Unique decoding using syndromes and error locator ideals for polynomial evaluations. Note that Hermitian codes are linear codes so we can compute the syndrome of a received vector. Moreover, akin to the error-locator ideals found in decoding Reed-Solomon codes, for the multivariate case we must define an error locator ideal \(\Lambda \) such that the variety of this ideal over \(\mathbb{F}^{2}_q\) is exactly the set of errors. The Sakata algorithm uses these two ingredients to get a unique decoding procedure [7].

Parent

  • Evaluation AG code — Hermitian codes are evaluation AG codes with \(\cal X\) being a Hermitian curve [2][6; Ex. 2.74]. This curve is maximal, meaning that Hermitian codes are evaluation AG codes with maximum possible length given a fixed genus.

Cousins

References

[1]
H. Tiersma, “Remarks on codes from Hermitian curves (Corresp.)”, IEEE Transactions on Information Theory 33, 605 (1987) DOI
[2]
R. E. Blahut, Algebraic Codes on Lines, Planes, and Curves (Cambridge University Press, 2001) DOI
[3]
M. Tsfasman, S. Vlǎduţ, and D. Nogin. Algebraic geometric codes: basic notions. Vol. 139. American Mathematical Society, 2022.
[4]
G. Korchmáros and P. Speziali, “Hermitian codes with automorphism group isomorphic to PGL(2,q) with q odd”, Finite Fields and Their Applications 44, 1 (2017) DOI
[5]
K. Yang and P. V. Kumar, “On the true minimum distance of Hermitian codes”, Lecture Notes in Mathematics 99 (1992) DOI
[6]
T. Høholdt, J.H. Van Lint, and R. Pellikaan, 1998. Algebraic geometry codes. Handbook of coding theory, 1 (Part 1), pp.871-961.
[7]
S. Sakata, “Finding a minimal set of linear recurring relations capable of generating a given finite two-dimensional array”, Journal of Symbolic Computation 5, 321 (1988) DOI
[8]
T. Yaghoobian and I. F. Blake, “Hermitian codes as generalized Reed-Solomon codes”, Designs, Codes and Cryptography 2, 5 (1992) DOI
[9]
Hansen, Johan P. Group codes on algebraic curves. Universität zu Göttingen. SFB Geometrie und Analysis, 1987.
[10]
W. Willems, "Codes in Group Algebras." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
Page edit log

Your contribution is welcome!

on github.com (edit & pull request)— see instructions

edit on this site

Zoo Code ID: hermitian

Cite as:
“Hermitian code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/hermitian
BibTeX:
@incollection{eczoo_hermitian, title={Hermitian code}, booktitle={The Error Correction Zoo}, year={2022}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/hermitian} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/hermitian

Cite as:

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

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