2.1 Generalised Reed-Solomon codes as cyclic codes
Another important family of Goppa codes is obtained considering the normal rational curve (NRC) defined over :
Assuming that are coprime, the set forms a basis of over , where is the characteristic of the field. Thus points in the NRC are in correspondence with linear combinations of the base vectors up to collineation. The Goppa codes of dimension defined over are constructed by evaluating non-zero polynomials of degree less than over a sequence of distinct elements in , if , then the map
is injective, since the existence of a non-zero polynomial of degree less than vanishing on all implies by the fundamental theorem of algebra (a non-zero polynomial of degree with coefficients in a field can have at most roots). These are just Reed-Solomon codes of parameters over a finite field , with parity check polynomial , where is a primitive root of such that . Any codeword can be expanded into a -ary vector with respect to the basis . Construction of generalised Reed-Solomon codes over only employ elements of , hence their lengths are at most . In order to get longer codes, one can make use of elements of an extension of , for instance considering subfield subcodes of Reed-Solomon codes. In this way, one gets cyclic codes. Recall that a linear cyclic code is an ideal in the ring generated by a polynomial with roots in the splitting field of , where , (). We shall identify the code with the set of its codewords. A natural question then to ask is how many irreducible polynomials of degree at least 2 are there over the algebraic closure of . Next theorem expresses this number in terms of Stirling numbers.
Theorem 2.2. Assume that, then the number of polynomials of degreedecomposable into distinct linear factors over a finite fieldof arbitrary characteristic a prime number, is equal to, whereis the falling factorial polynomial, whereis the Stirling number of the first kind (the number of ways to partition a set ofobjects intonon-empty subsets), divided by the order of the affine transformation group of the affine line, that is.
Proof. We need to count all the polynomials in one variable of degree fixed. We assume that our polynomial decomposes into linear factors, otherwise we work over , where denotes the algebraic closure of the finite field . Since the number of ordered sequences on symbols is and each root is counted with its multiplicity, it follows that the number of monic polynomials with different roots is . Now we observe that polynomials are invariant by the action of automorphisms of the affine line, so we must divide this number by the order of this group which is .
Theorem 2.3. Given a set of integersmodule, there is a setofintegers which is a set of roots, that is, there is a polynomial, whereis a generator offor some prime numberandis the least integer such that. The idealgenerates inis a cyclic linear code of parameters.
Proof. Let be the least integer such that divides , then . We define an equivalence relation on the set of integers , by declaring two integers and in the range to be conjugate module if . This equivalence relation partition the set into cyclotomic cosets. The cyclotomic coset containing , which we will denote by , can be described explicitly as the set , where is the least positive integer such that and is not necessarily the smallest integer in such coset. Denote by the set consisting of the smallest integers in each cyclotomic coset, then is a set root, that is, it is a set of integers in arithmetic progression modulo whose increment is relatively prime to . Let , then the polynomial defines a cyclic code of parameters .
As an application of Theorem 2.2, given an integer , we can count the number of cyclic codes of parameters for each and set of roots in the splitting field of , the corresponding polynomial generates a linear cyclic code in the ring . Thus for each there are exactly cyclic codes.
In the theory of error-correcting codes to a given code , one assigns another important parameter, the minimum distance which measures how good the decoding is.
Definition 2.4. The distance between vectorsandin the Weighted Hamming metric (WHM) is defined by a function:
where , if and if . The weight of a vector in the WHM is . The value and vector are called a weight of position and a vector of weights of positions respectively.
Geometrically a binary vector of length gives the coordinates of a vertex of a unit cube in dimensions.
Example 1. Consider the Goppa code defined by the rational functionwhich admits as decomposition into partial fractions the expression. The presence of a double factorcorresponds to the existence of an eigenspacein the vector spaceof multiplicity 2 and thus ansplitting subspace where the operatoris just the linear operator, withthe eigenvalue associated toandis the generator matrix of the code. We recall that andimensionalsubspace issplitting ifis invariant under the action of any elementin the Galois group of the extension.
2.2 Algebraic function field codes
A much greater variety of linear codes is obtained if one uses places of arbitrary degree rather than just places of degree 1. These codes are more naturally described through function field codes. A general viewpoint is that function field codes are certain finite dimensional linear subspaces of an algebraic function field over a finite field as in Goppa’s construction.
In the paper , the authors introduce another construction where places of arbitrary degree are allowed. The method consists of choosing two divisors and of an algebraic curve over with . Then is a subspace of the vector space over . If we choose a basis of , then the coordinate vectors of the elements of form a linear code over of length and dimension . These are known as function field codes and they provide a general perspective on the construction of algebraic-geometry codes .
Example 2. We consider as in  the Suzuki curvedefined overby the following equationwithand. This curve has exactlyrational places with a single place at infinityand it is of genus We construct a code out of the divisor andwhereis the sum of therational points and the parametersatisfies the boundandis the genus of the curve.
Observe that the geometric Goppa code is an -subspace of and its dimension as an vector space is the dimension of the code. Geometrically, it corresponds to a point in the Grassmannian . The set of codewords recognised by the code admits the following description in terms of monomial ideals in the variables :
where and are elements in the function field over . Moreover, it is a generating set for the linear series associated to the divisor .
Theorem 2.5. Cyclic codes are function field codes constructed over the curvewith affine equationdefined over a finite fieldofelements, whereis a power of a primeandare integer numbers greater or equal than 2.
Proof. Let us assume is an integer even number, thus , with an integer odd number. We recall that a linear cyclic code is an ideal in the ring generated by a polynomial with roots in the splitting field of , where . If we consider the factorisation of the polynomial over , we get . We see that the point with is an rational place of the affine curve . The other rational places are with ,..., , , and the place at . The cyclic code is realised as the algebraic geometric code associated to the divisors , and the parameter satisfies the bound , where is the genus of the curve . Note that is the least integer such that . In particular is a generator of .
If is an integer odd number, by Theorem 2.3, we know there is a set of roots , such that is a generator of . Now we consider the points with and the point at , and the cyclic code is realised as the function field code associated to the divisors and .
Remark 2.6. The proof given in theorem gives a realisation of cyclic codes as AG codes constructed over the curve with affine model. In particular when, we cover the codes defined over the Hermitian curve.
Another important family of cyclic codes is obtained considering the roots of the polynomial over its splitting field. These codes are of great importance in ADN-computing and as they are linear codes, they can be described as function fields. Let be a primitive element of the underlying vector space over . Since the base field is of characteristic , has different zeroes. Let be the extension field containing the roots of unity where . Moreover the set constitutes a basis over the prime field , and the field extensions are isomorphic.
Example 3. The polynomialoveris irreducible, thus the fieldsare isomorphic, and the rootscorrespond to one place of degree 2 in the extension field.
Example 4. We define the polynomials, with, and. Then, ifis a separable polynomial, then the Galois group ofoveris a regular extension with Galois group.
Observe that is the function field of an dimensional projective space over . Suppose that are the roots of in a splitting field of over . Each coefficient of in is symmetric in , thus by the theorem on symmetric functions, we can write as a symmetric polynomial in with rational coefficients. On the other side, for a permutation , set in and , where runs through all permutations in .
Theorem 2.7. (Hilbert) Letbe acting on. The fieldofinvariants is, whereis thesymmetric polynomial inandhas Galois groupover. It is the splitting field of the polynomial
Let be a finite field such that . A non-zero polynomial in defines a curve on the plane . The elliptic curves are curves of the form , where is a polynomial of degree 3 with coefficients in .
Proposition 2.8. Letbe a factorisation of an integer positive numberinto irreducible coprime factors and assume, then there is a sequence of field extensions.
Proof. Consider the map
where is the jth elementary symmetric function in the variables . Thus , are the coefficients of the equation:
If we apply Theorem 2.7 to the elementary symmetric polynomial in the symbols , we get that the field of invariants of the polynomial contains an extension of . Moreover, for any divisor of , one can consider the field of invariants, and apply Theorem 2.7 to the symbols , where . Then we get an extension of and all its -subspaces are stable under .
Example 5. Assumeand we study again the roots of the polynomialin its splitting field. Letbe a non-trivial n-root of unity, for any divisorof, one can consider the symbols. The field ofinvariants of the polynomialis the set of solutions to the equation:
In , for any divisor of , there are exactly solutions to Eq. (2) if is odd and solutions if is even.
Instead of considering divisors of , we can consider a partition of into two parts. For example for an integer , we consider the partition of . Fix two elements of rank and rank . These points correspond to linear transformations , . It is well known that the corresponding points and in the Grassmannians of dimensional subspaces and the Grassmannian of dimensional subspaces respectively are dual subspaces in the underlying vector space for the Euclidean inner product. Note that the Hamming weight is preserved under invertible linear transformation. This case is of great interest for applications in coding theory, since the corresponding codes with generator matrices and respectively are dual codes. Namely, given a linear -code, a parity check matrix for is an matrix of rank such that . Then the dual code is the linear code generated by the parity check matrix of . There is a right action of the general linear group on :
One can study the orbits of by the action of any subgroup in the general linear group . For example we can study the orbit of any triangle group: the Klein group , the dihedral group, the alternated groups and or the symmetric group . Take as the standard shift operator on , a linear code is said to be quasi-cyclic of index or quasi-cyclic if and only if is invariant under . If , it is just a cyclic code. The quantity is called the co-index of . Namely, if we view a codeword of as a polynomial , then .
Example 6. We study the action of a rotation element on the Grassmannianof lines in a 3-dimensional projective space. We apply to any linea rotationof angle, represented by the array of vectors. It is easy to see that the orbit code by the composed actionwithdivisor ofis a quasi-cyclic code of index.
In general, we study generalised Grassmannians or more commonly known as flag varieties. Fix a partition of and let be the variety of partial flags of vector spaces
such that . The group acts on in the natural way. Fix an element and denote by the stabilizer of in and by the subgroup of elements which induces the identity on for all . Put , then we have .
Proposition 2.9. Let us consider the factorisation ofinto irreducible pairwise coprime factorswith, andbe the partition of exponents. Then there is a flag varietyof partial flags ofvector spaces:
such that .
Proof Observe that the result follows trivially for the case in which is a prime number . If factorizes into two irreducible prime factors, the result follow as we have seen above, there is a flag and then by induction in the result follows.
Given a cyclic code over of length , its defining set is given by the exponents occurring in , where is the generator polynomial of the ideal of the code in .
Let be an primitive root of unity. The cyclotomic polynomial is the minimal polynomial of over . It is monic of degree of the Euler’s totient function . It has integer coefficients and it is irreducible over . In , we have the factorization into irreducible polynomials:
By Möebius inversion:
In the case of binary codes where , Bezzateev and Shekhunova  have obtained that the number of irreducible normalized polynomials of degree over satisfy the following equation:
where is the Möebius function:
Let equals the least common multiple , then is a defining set for . We will describe the defining set by the exponents occurring in with , where . A parity check matrix for the code is given by:
The code is obtained as the subfield subcode of :
Given a triple of subsets of of the same cardinality , we associate to them partitions and as follows. Let , then the corresponding partition is defined as , and respectively for . We call the triple admissible for the Horn problem, if the corresponding triple of partitions occurs as eigenvalues of a triple of Hermitian by matrices, with the third one the sum of the first two.
We describe Horn’s inductive procedure to produce set of triples .
Example 7. Let us consider the triple of subsets
and the corresponding triple of partitions arises from the triple of diagonal 3 by 3 matrices with diagonal entries and .
Lemma 2.10. For any tripleadmissible for the Horn problem, the polynomials defined byandgenerate a cyclic code of lengthand, whereandis the characteristic of the field.
Proof. The cyclic code generated by coincides with the cyclic code generated by and respectively for and the polynomials and It is the cyclic code generated by the minimal polynomial of .
Remark 2.11. We see that Horn’s algorithm is relevant since some classical code constructions can be seen as ideals in a finite dimensional commutative semi simple algebra over a finite fieldwithelements anda prime number as in example (3).
Lemma 2.12. The family of cyclic codes obtained by considering the roots of the polynomialover its splitting fields are indeed AG codes arising from genus 0 curves, and by Riemann-Roch theorem, their parameters satisfy the bound, whereis the minimum distance.
Proof Let be the extension field containing the roots of unity where . Moreover the set constitutes a basis over the prime field , and the field extensions are isomorphic.