Result: Permutation codes with specified packing radius

Most papers on permutation codes have concentrated on the minimum Hamming distance of the code. An (n, d) permutation code (or permutation array) is simply a set of permutations on n elements in which the Hamming distance between any pair of distinct permutations (or codewords) is at least d. An (n, 2e + 1) or (n, 2e + 2) permutation code is able to correct up to e errors. These codes have a potential application to powerline communications. It is known that in an (n, 2e) permutation code the balls of radius e surrounding the codewords may all be pairwise disjoint, but usually some overlap. Thus an (n, 2e) permutation code is generally unable to correct e errors using nearest neighbour decoding. On the other hand, if the packing radius of the code is defined as the largest value of e for which the balls of radius e are all pairwise disjoint, a permutation code with packing radius e can be denoted by [n, e]. Such a permutation code can always correct e errors. In this paper it is shown that, in almost all cases considered, the number of codewords in the best [n, e] code found is substantially greater than the largest number of codewords in the best known (n, 2e + 1) code. Thus the packing radius more accurately specifies the requirement for an e-error-correcting permutation code than does the minimum Hamming distance. The techniques used include construction by automorphism group and several variations of clique search They are enhanced by two theoretical results which make the computations feasible.