Enumeration of block codesTopIntroduction


The methods and results presented in this paper are interesting in the framework of classification of discrete structures [13],[10]. Very often discrete structures can be described as equivalence classes of certain objects. If these equivalence classes can be expressed as orbits under a group G acting on a set X -- i.e. there is a mapping G´X -> X, (g,x) -> gx such that g1(g2x)=(g1g2)x and 1x=x -- then there exist some combinatorial and algebraic methods for the classification of these structures. For instance each element in the discrete structure of unlabelled graphs can be considered as the set of all possible labellings of a given graph which is the orbit of a labelled graph under the action of the symmetric group; or the isometry classes of block-codes are orbits of special wreath-products. In a first step one can enumerate these structures by applying the Cauchy-Frobenius-Lemma, which says that the number of G-orbits is the average number of fixed points
| G|

g G 
| Xg|,    Xg: = { x X | gx = x} .
In a second step certain properties of these structures can be described by weight functions or by their stabilizer (the stabilizer of xÎX is the subgroup Gx:={gÎG | gx=x} of G) and the numbers of structures with these additional properties can be computed by the Pólya-de Bruijn-Redfield-Theory or by Burnsides Lemma. The more details of a structure are specified and prescribed by parameters the closer comes the enumeration procedure to the construction of all structures with given properties. The most ambitious task is the computation of complete lists of representatives of a discrete structure, which can be done by arranging both algebraic and combinatorial algorithms in a very tricky way. Having computed these lists we can investigate each representative for its properties. When the numbers of representatives get too large in order to compute complete lists, it is useful, helpful and makes sense to compute representatives uniformly at random. This way we can produce unprejudiced lists of representatives which can be used to check hypotheses on them and afterwards we can try to prove the valid ones.

Let A be a finite alphabet, then an [n,m] block code C over A is an m-subset of An. In order to describe the isometry classes of block codes we need the notion of wreath products. The wreath product SA wr Sn is a group formed by a set {(y,p) | yÎSAn, pÎSn } with multiplication (y,p)(y', p')=(yy'p, pp'), where yy'p(i):=y(i)y'p(i) and y'p(i):=y'(p-1i). (For more details on group actions and wreath products cf. [12].)

Two [n,m] codes C1 and C2 will be called equivalent, if and only if there is some (y,p) in the full monomial group SA wr Sn such that

C1 = (y,p)(C2): = { (y,p)f | f C2} ,
where (y,p)f(i)=y(i)f(p-1i). (I.e. SA wr Sn acts in form of the exponentiation on An which induces an action on the set of all subsets of An.) The equivalence classes under this group action are exactly the isometry classes of [n,m] codes.

In previous papers [6][4][3][5] we were dealing with the enumeration of isometry classes of linear (n,k) codes over a finite field GF(q). In this situation we had to determine the number of isometry classes of k-dimensional subspaces of GF(q)n, which can be described as orbits under the action of GF(q)* wr Sn. Of course, each linear (n,k)-code over GF(q) is an [n,qk] block code.

last changed: January 23, 2001

Enumeration of block codesTopIntroduction