During the last year most of the work in the project "Combinatorial constructions under group actions" P12642-MAT was devoted to the classification, enumeration, construction and random generation of linear codes. This work was based on results partially derived in the previous project "Construction of finite structures" P10189-PHY. All the old and new results of the last years were now collected into a text book "Codierungstheorie" [2] published at Springer. In international cooperation with the "Lehrstuhl II für Mathematik der Universität Bayreuth" it was possible to write this book. It serves both as an introduction to coding theory, and as a demonstration of the results achieved in joint work on the classification of linear codes.
Professor Adalbert Kerber wrote in the preface of this book:
When speaking about classification of linear codes, we are mainly interested in describing the isometry classes of linear (n,k)-codes over a finite field GF(q). These classes can be represented as orbits of k-dimensional linear subspaces of GF(q)n under the action of the full monomial groups GF(q)* wr Sn (cf. [8]). Applying various methods from algebraic combinatorics (cf. [10]) it is possible to describe them as orbits of functions from {1,...,n} to the projective geometry PGk-1(q) under the action of the direct product PGLk(q)´Sn of projective linear groups and symmetric groups.
When classifying objects under a group action you are generally interested in complete lists of orbit representatives. (Group actions are often diminishing the numbers of objects dramatically when collecting equivalent objects to one orbit, here in the case of codes, all isometric codes to one isomorphism class of codes.) In situations where there are still too many representatives probabilistic methods can be applied for generating orbit representatives uniformly at random. I. e., for any orbit the probability that a generated representative belongs to this orbit does not depend on the special choice of the orbit. For all orbits this probability is the fraction 1 divided by the number of different orbits. The Dixon-Wilf-algorithm ([3]) describes such a probabilistic method. During the last year it was adopted to the random generation of linear codes and implemented in the computer algebra system SYMMETRICA [11]. Details about random generation of linear codes can be found in [7]. This paper was submitted to Aequationes mathematicae, where in the meantime it is already accepted for publication. Moreover Harald Fripertinger was presenting these ideas in a lecture at the 41-st Séminaire Lotharingien de Combinatoire in Domaine Saint-Jacques, Saint-Nabor, in March 1998. During the year we were generating millions of codes to various parameters uniformly at random and we were checking them for certain properties. For instance we were analyzing the distribution of the minimum distances of (n,k)-codes for given parameters n and k.
Furthermore a program was developed in SYMMETRICA which computes generator matrices of binary linear (n,k)-codes of given minimum distance. And a database program for handling the optimal minimum distance of linear codes of length n and dimension k was implemented. It manipulates lower and upper bounds for the minimum distance of (n,k)-codes as it is described in the first chapter of [2].
The methods of enumeration, construction and random generation of linear codes were generalized to the classification of block codes. The corresponding paper [5] was published in the journal "Design, Codes and Cryptography".
Two further articles were accepted for publication. Their final versions were partially rewritten according to the latest results and to the referees suggestions.