Pairs of codes with prescribed Hamming distances and coincidences

The main problem of coding theory is to construct codes with large Hamming-distances between the code-words. In this work we describe a fast algorithm for generating pairs of q-ary codes with prescribed pairwise Hamming-distances and coincidences (for a letter s ∈ {0,1,...,q − 1}, the number of s-coincidences between codewords a and b is the number of letters s in the same positions both in a and b). The method is a generalization of a method for constructing set-systems with prescribed intersection sizes (Grolmusz (2002) Constructing set-systems with prescribed intersection sizes. J Algorithms 44:321–337), where only the case q = 2 and s = 1 was examined. As an application, we show that the modular version of the classical Delsarte-inequality does not hold for odd, non-prime power composite moduli.      

Compact storage schemes for formatted files by spanning trees

The use of spanning trees in the compression of data files is studied. A new upper bound for the length of the minimal spanning tree, giving the size of the compressed file, is derived. A special front compression technique is proposed for unordered files. The space demands are compared to an information theoretical lower bound of the file size.