3. CODING THEORY

The references between [ ] are listed in publications.html for typology.

My research in this area, above the results presented in the previous sections related to Galois geometries, has been in various directions.


3.1  TOPOLOGY OF NETWORKS

In [21] the problem of packet switched networks has been attacked. We translated it into design theoretic language. The solution of this problem involves weighted (n,k)-arcs in projective planes and 3-dimensional codes. The main problem concerned maximal coverings. A construction method for maximal coverings has been presented which then turned out to be uniquely determined. This resolves a problem which according to a statement of one of the leading experts in this area (C.J. Colbourn , 1999) seemed inaccessible as it seemed to contain the solution of the packing problem of plane arcs of arbitrary species. The solution of the problem was considered to be particularly relevant and has been the object of international research efforts for almost two decades. In those attempts various methods were used in order to translate the problem into different areas: graph theory [J.C.Bermond et al. 1983], computer aided numerical analysis and design theory [B.Yener et al., 1997], theory of projective planes [C. J. Colbourn, 2002]. Only in [21] the level of generality is reached which allows to establish a complete solution in a generic case. It also leads to links with coding theory which had not been known before and to a new type of a design-theoretic problem.
More novel aspects in the approach of [21] are the use of the graph-theoretical concept, the fractional matching number and the use of linear programming which allows to demonstrate optimality in the relevant generic situation. Finally in [21] the design-theoretic formulation leads to a new type of extremal structures which generalizes the notion of an almost projective plane: significative examples are found in the paper.


3.2  NMDS CODES

This class of codes (both the code and its dual of Singleton defect 1) are the most valuable after the MDS codes.
In fact the problem of finding good linear codes can be described as maximizing the minimum distance when length and dimension are given. It is known that the minimum distance cannot exceed the Singleton bound and MDS codes are precisely those which achieve equality. Essentially those cannot exist for length larger than n+2. It follows that the next problem along this line consists in the construction of codes of Singleton defect 1.
In [AC5] and [28] we find a family of highly symmetric linear codes whose automorphism group contains the direct product of a Galois group and a group of permutations acting regularly. The family contains many classical codes (the extended Hamming code, the hexacode, the Golaycodes, the Pless codes) and also some new codes defined over GF(4) and GF(8) with extremely good parameters. The family can be extended in a natural way to codes defined over a ring. In fact the Z_4-linear octacode which yields the famous Nordstrom-Robinson code belongs to the family as well.
The paper contains also the algebraic-geometric description of one of the two maximal NMDS codes over GF(8) (which are classified in [15]). This is the code which possesses an unusually large group of symmetries (direct product of an A_4 and an elementary abelian group of order 16). The description makes use of the combinatorial notion of an ordered design. The results closely connected to (n,k)-arcs have been illustrated in the previous section.


3.3  CODICI LDPC

In [54] new classes of LDPC codes are constructed, in some cases with new parameters. This has been achieved via a geometric approach based on the concept of a configuration. In view of the efficiency of the decoding algorithm the Tanner graph associated to the code is not allowed to contain short cycles. This poses the mathematical problem to construct bipartite graphs with large girth. In combinatorial terms this comes down to the construction of symmetric configurations.
Group-theoretic and combinatorial methods have been used in  [AC10] and [AC15] for the construction of new classes of configurations.
In particular in [AC15] we used the Golomb rulers and the modular Golomb rulers as key instruments.
This led to many new parameters, in particular in the cyclic case; new upper bounds have been derived on the minimum integer E(k) (Ec(k)) such that for every v > E(k) (Ec(k)) there exists a simmetric v_k-configuration (cyclic simmetric).
In the area of symmetric graphs we studied in [57] the unitary graphs. Their classification constitutes the main result of the paper. Those graphs are a family of symmetric graphs whose vertices are the flags of the Hermitian unital where the adjacency relation is determined by the underlying field. They admit the unitary group as a group of automorphisms. Those graphs play a significant role in the classification of the symmetric graphs with complete quotients such that the corresponding incidence relation is 2-transitive on the points.


3.4  ADDITIVE CODES

The notion of an additive code is a vast range generalization of the classical concept of a linear code. In the most general sense they are linear over a finite abelian group written additively. In my research this concept is used in a slightly restricted variant where the alphabet is considered to be a vector space and linearity holds only with respect to the underlying field.
In the geometric interpretation the theory of linear codes is equivalent to the theory of point sets in projective Galois spaces and their distribution on hyperplanes. The geometric interpretation of additive q_2-ary q-linear codes (this is a parametric subfamily) is the theory of lines in space and their distribution on hyperplanes. This restricted concept is in itself a far-reaching generalization of the concept of a linear code. In fact it contains the theory of quantum stabilizer codes as a special case. In [AC9] we use the geometric description to prove the non-existence of an additive [12,7,5]_4-code. The complete determination of the parameters of quaternary additive codes of length 12 is in [45], again using geometric language. This paper also contains the construction of a new optimal code of length 13. In [48] we present another non-existence result which in geometric terms is equivalent to the statement that for every system of 12 lines in PG(8, 2) there is a hyperplane containing more than 5 of those lines.


3.5  QUANTUM CODES

In those last years I started studying the theory of quantum codes. The research on quantum computations, although still in an embryonal state, is extremely active, supported also by national governments and military agencies.
The quantum error-correcting codes are very significant in protecting from information errors in a future quantum computer. The construction of a quantum computer currently is the aim of various research groups. Potentially a quantum computer may be able to solve problems much faster than any classical computer. One popular example is the factorization of composite numbers, a problem which is at the heart of the most common cryptographical algorithms.
The fundamental work of CRSS (1998) translates the problem of error correction in quantum computations into the language of coding theory over finite fields (quantum stabilizer codes, a special case of additive codes). In [43] we take another step forward by translating the problem of quantum error-correction into a geometric language: binary quantum codes and more in general quaternary additive codes are described in terms of systems of points and lines in binary Galois spaces. This approach has shed new light on some classical quantum code families, has allowed new constructions and has led to relations with objects like quadrics and APN functions (a basic concept in the cryptographical theory of S-boxes). This geometric point of view has allowed us in [43] to solve certain problems concerning the existence of optimal quantum codes, in particular the construction of quantum codes with new parameters. An analogous geometric approach was used in [51] to demonstrate the non-existence of a [[13, 5, 6]] quantum stabilizer code, thus solving a problem which has been open for years. The proof relies not only on systems of points and lines in the ambient space PG(7,2) but also in certain subspaces and factor spaces. As a consequence several open problems have been removed from the database M. Grassl, http://www.codetables.de.
In [AC18], [L2], [53], we study linear quantum codes with parameters [[n, n -10, 4]] via their geometric counterparts, caps in
PG(4, 4) satisfying the property that the intersection cardinality with any hyperplane always has the same parity as the cardinality n. In particular we determine the spectrum of those caps and we obtain a complete classification of the extremal examples. Those examples have been used to obtain inductive definitions of infinite families of quantum caps in higher dimension.
General constructions for quantum codes over arbitrary finite fields are described in [58]. One such construction generalizes a theorem from the fundamental paper by CRSS. The central part of our paper consists of the study of quantum caps in quaternary projective spaces. Various recursive constructions are obtained.