Isometry classes of linear codes



next up previous
Next: Indecomposability Up: Isometry Classes of Indecomposable Previous: Notation

Isometry classes of linear codes

A linear -code over the Galois field is a -dimensional subspace of the vector space . As usual codewords will be written as rows . A -matrix over is called a generator matrix of the linear -code , if and only if the rows of form a basis of , so that . Two linear -codes are called equivalent, if and only if there is an isometry (with respect to the Hamming metric) which maps onto . Using the notion of finite group actions one can easily express equivalence of codes in terms of the wreath product action introduced above: and are equivalent, if and only if there exist (where denotes the multiplicative group of the Galois field) such that .

The complete monomial group of degree over acts on as it was described above (see equation (2)) in the more general case of on :

 

In order to apply the results of the theory of finite group actions, this equivalence relation for linear -codes is translated into an equivalence relation for generator matrices of linear codes, and these generator matrices are considered to be functions where is the -th column of the generator matrix . (We exclude -columns for obvious reasons.)

. Theorem   The matrices corresponding to the two functions and from to are generator matrices of two equivalent codes, if and only if and lie in the same orbit of the following action of as permutation group on :

or, more explicitly,

Following SLEPIAN, we use the following notation:

the number of orbits of functions under the group action of 2.1, i.e. .
the number of orbits of functions under the group action of 2.1, such that for all , and all the value of is different from . (In the case , this is the number of injective functions .)
the number of equivalence classes of linear -codes over with no columns of zeros. (A linear -code has columns of zeros, if and only if there is some such that for all codewords , and so we should exclude such columns.)
the number of classes of injective linear -codes over with no columns of zeros. (A linear -code is called injective, if and only if for all , and there is some codeword such that .)
the number of classes of indecomposable linear -codes over with no columns of zeros. (The definition of an indecomposable code will be given later.)
the number of classes of indecomposable, injective linear -codes over with no columns of zeros.
be the number of classes of linear -codes over with columns of zeros allowed.

The following formulae hold:

 

As initial values we have for , and for . It is important to realize that

In the next section we will show that the or can be computed from the or respectively, so the main problem is the computation of the or .

In the case the wreath product becomes the group , and so there is the group acting on and the symmetric group acting on . Applying the formulae (3) and (4) we get

 

and

 

In the case the wreath product acts both on range and domain of the functions . Applying LEHMANN's Lemma 1.1 there is the bijection

where

and acts on by . Using this bijection we have to investigate the following action of :

where acts on by . The set of the -orbits is the -dimensional projective space:

and the representation of as a permutation group is the projective linear group .

This proves in fact the following to be true:

. Theorem The isometry classes of linear -codes over are the orbits of on the set of mappings . This set of orbits is equal to the set of orbits of on the set , which can be represented by a complete set of mappings of different content, if the content of is defined to be the sequence of orders of inverse images .

Thus the set of isometry classes of linear -codes over is equal to the set of orbits of on the set of mappings of different content that form -matrices of rank .

The particular classes of elements with orders of inverse images are the classes consisting of Hamming codes.

Knowing the cycle index of acting on the equations (3) and (4) can be applied again.

In [13] SLEPIAN explained how the cycle index of can be computed using results of ELSPAS [3]. The first author [4] generalized this concept for computing the cycle indices of and acting on or respectively. The steps of the method used were the following ones:

  1. Determination of the conjugacy classes of by applying the theory of normal forms of matrices (or vector space endomorphisms). This theory can be found in many textbooks of algebra.
  2. Determination of the order of the conjugacy classes, which can be found in DICKSON, GREEN or KUNG [8][5][2].
  3. Determination of the cycle type of a linear map or of a projectivity respectively. Since normal forms of regular matrices are strongly connected with companion and hypercompanion matrices (see [6]) of monic, irreducible polynomials over it is important to know the exponent or subexponent of such polynomials (see [6][11]). The exponent of such a polynomial is defined to be

    and the subexponent is

    This element is uniquely defined, and it is called the integral element of . The exponent of can be used to compute the cycle type of the companion or hypercompanion matrices of a monic, irreducible polynomial , and by a direct product formula for cycle indices the cycle types of the normal forms in can be derived. Using the subexponent of and defining a formula similar to the direct product formula of cycle indices, which depends on the integral element of as well, the cycle type of a projectivity can be computed.

  4. Determination of the cycle index by applying formula ().
These cycle indices are now available in the computer algebra package SYMMETRICA. Tables obtained this way are shown lower down.



next up previous
Next: Indecomposability Up: Isometry Classes of Indecomposable Previous: Notation



Herr Fripertinger
Sun Feb 05 17:20:29 MET 1995