We study and enumerate cyclic codes which include generalised Reed-Solomon codes as function field codes. This geometrical approach allows to construct longer codes and to get more information on the parameters defining the codes. We provide a closed formula in terms of Stirling numbers for the number of irreducible polynomials and we relate it with other formulas existing in the literature. Further, we study quasi-cyclic codes as orbit codes in the Grassmannian parameterizing constant dimension codes. In addition, we review Horn’s algorithm and apply it to construct classical codes by their defining ideals.
- cyclic code
Function fields are used ubiquitously in algebraic coding theory for their flexibility in constructions and have produced excellent linear codes. Suitable families of function fields, for example good towers of function fields, have been used to construct families of codes with parameters bound better than the asymptotic bound.
Let a power of a prime number . It is well known, that there exists exactly one finite field with elements which is isomorphic to the splitting field of the polynomial over the prime field . Any other field of characteristic contains a copy of . We denote respectively by and the affine space and the projective space over . Let be the algebra of polynomials in variables over .
The encoding of an information word into a k-dimensional subspace is usually known as coding for errors and erasures in random network coding . Namely, let be an dimensional vector space over , a code for an operator channel with ambient space is simply a non-empty collection of subspaces of . The collection of subspaces is a code for error correcting errors that happen to send data through an operator channel. The matrix coding the information is parameterised by random variables which constitute the letters of an alphabet. Here the operator channel is an abstraction of the operator encountered in random linear network coding, when neither transmitter nor receiver has knowledge of the channel transfer characteristics. The input and output alphabet for an operator channel is the projective geometry. A good code is capable of correcting error and erasures at the output of the operator channel. Thus in order to construct good codes one need to choose a metric consistent with channel errors and search of a set of vectors with given metric properties as a correcting code. The codes considered here are codes for channels whose errors are consistent with the weighted Hamming metric (WHM).
Let be a non-singular, projective, irreducible curve defined over , as the vanishing locus of a polynomial . We define the number of rational points on the curve to be
It is a polynomial in with integer coefficients, whenever is a prime power.
The number of points on over the extensions of is encoded in an exponential generating series, called the zeta function of :
Garcia and Stichtenoth analysed the asymptotic behaviour of the number of rational places and the genus in towers of function fields, . From Garcia-Stichtenoth’s second tower one obtains codes over any field where is an even power of a prime .
One of the main problems in coding theory is to obtain non-trivial lower bounds of the number of rational places of towers of function fields such that . Suitable families of function fields, for example good towers of function fields, have been used to construct families of codes that beat the Gilbert-Varshamov bound. This paper aims to explore this link for the study and construction of quasi-cyclic codes. For example good codes are obtained for curves of genus 0, they are in fact extended generalised Reed-Solomon codes.
Notation. Let denote the Galois field of elements and let denote the vector spaces of all ordered n-tuples over . The Hamming weight of a vector , denoted by is then number of non-zero entries in x. A linear code of length and dimension over is a k-dimensional subspace of . Such a code is called code if its minimum Hamming distance is . For a positive integer, is a partition of into parts if the are positive and decreasing.
2. Algebraic geometric codes
Let be a finite field of elements, where is a power of a prime. We consider as an alphabet a set of rational points lying on a smooth projective curve of genus and degree defined over the field . If is a divisor on the curve , is the linear series attached to this divisor with coefficients in the field.
Definition 2.1. Algebraic Geometric Codes (AGC) are constructed by evaluation of the global sections of a line bundle or a vector bundle on the curveoverdistinct rational places. Namely, letbe the function field of the curve,the divisoranda divisor ofof degreesuch that. Then the geometric Goppa code associated with the divisorsandis defined by
Recall that is a cyclic Galois extension and it is finitely generated by unique element . is a primitive element and is a basis of the field extension ↪ , that is, .
In the sequel, an -code is a k-dimensional subspace of
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 genusWe 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.
2.3 Generating functions of conjugacy classes in a group
The automorphism group of the projective line is the projective linear group . Any finite subgroup defines a uniform Cayley (sum) hypergraph whose vertices are the generating tuples of and the edges are element sets represented by random variables . In particular, if is the ordinary generating function that enumerates , that is, number of conjugacy classes in , then is the ordinary generating function enumerating sequences of elements in . If is an abelian group, then . In general, we will consider -arcs in which represent casual connections between the variables. Applications are known in statistics, for example the multinomial experiment consists of identical independent trials, and there are possible outcomes (classes, categories or cells) to each trial and the cell counts are the random variables, the number of observations that fall into each of the categories.
Definition 2.13. Inaarc is a set ofpoints anyof which form a basis for, or in other words,of them but notare collinear.
Consider the normal rational curve over :
is a (q + 1)-arc in the n-dimensional projective space .
We see that if , the NRC is a basis of a q-dimensional projective subspace, that is, a . So we can enumerate how many NRC’s are there in a . The answer is , the number of ways of choosing such a set of points in a particular q-space. If , the NRC is an example of a (q + 1)-arc. It contains q + 1 points, and every set of points are linearly independent.
The problem of considering finite subgroups and conjugacy classes in the automorphism group of the projective line can be generalised to that of finite subgroups in , the collineation group of the normal rational curve.
This research has been partially supported by the COST Action IC1104 and the project ARES (Team for Advanced Research on Information Security and Privacy. Funded by Ministry of Economy and Competitivity).