Diagonally neighbour transitive codes and frequency permutation arrays

Constant composition codes have been proposed as suitable coding schemes to solve the narrow band and impulse noise problems associated with powerline communication, while at the same time maintaining a constant power output. In particular, a certain class of constant composition codes called frequency permutation arrays have been suggested as ideal, in some sense, for these purposes. In this paper we characterise a family of neighbour transitive codes in Hamming graphs in which frequency permutation arrays play a central rode. We also classify all the permutation codes generated by groups in this family.     

On constant composition codes

A constant composition code over a k-ary alphabet has the property that the numbers of occurrences of the k symbols within a codeword is the same for each codeword. These specialize to constant weight codes in the binary case, and permutation codes in the case that each symbol occurs exactly once. Constant composition codes arise in powerline communication and balanced scheduling, and are used in the construction of permutation codes. In this paper, direct and recursive methods are developed for the construction of constant composition codes.     

常重复合码的构造和界

摘要给出了一种Chebyshev距离下的常重复合码的构造,并在其基础上讨论了它的译码算法和优化处理.考虑了Chebyshev距离下的界及其改进.研究了具有Chebyshev距离和Hamming距离的常重复合码的构造,给出了Hamming距离为4的常重复合码的一个结论.     

Binary permutation sequences as subsets of Levenshtein codes,spectral null codes,run-length limited codes and constant weight codes

We investigate binary sequences which can be obtained by concatenating the columns of (0,1)-matrices derived from permutation sequences. We then prove that these binary sequences are subsets of a surprisingly diverse ensemble of codes, namely the Levenshtein codes, capable of correcting insertion/deletion errors; spectral null codes, with spectral nulls at certain frequencies; as well as being subsets of run-length limited codes, Nyquist null codes and constant weight codes. This paper was presented in part at the IEEE Information Theory Workshop, Chengdu, China, October, 2006.     

Frequency permutation arrays

Motivated by recent interest in permutation arrays, we introduce and investigate the more general concept of frequency permutation arrays (FPAs). An FPA of length n = mλ and distance d is a set T of multipermutations on a multiset of m symbols, each repeated with frequency λ, such that the Hamming distance between any distinct x,y ∈ T is at least d. Such arrays have potential applications in powerline communication. In this article, we establish basic properties of FPAs, and provide direct constructions for FPAs using a range of combinatorial objects, including polynomials over finite fields, combinatorial designs, and codes. We also provide recursive constructions, and give bounds for the maximum size of such arrays. © 2006 Wiley Periodicals, Inc. J Combin Designs 14: 463–478, 2006     

线性等距码的一个判别条件

本通过分析线性等距码的特点，利用投射几何的知识，给出了有限域Fq上的线性等距码的一个判别条件。     

Reed-Muller codes and permutation decoding

We show that the first- and second-order Reed-Muller codes, R(1,m) and R(2,m), can be used for permutation decoding by finding, within the translation group, (m−1)- and (m+1)-PD-sets for R(1,m) for m≥5,6, respectively, and (m−3)-PD-sets for R(2,m) for m≥8. We extend the results of Seneviratne [P. Seneviratne, Partial permutation decoding for the first-order Reed-Muller codes, Discrete Math., 309 (2009), 1967-1970].     

A class of optimal constant composition codes from GDRPs

As a common generalization of constant weight binary codes and permutation codes, constant composition codes (CCCs) have attracted recent interest due to their numerous applications. In this paper, a class of new CCCs are constructed using design-theoretic techniques. The obtained codes are optimal in the sense of their sizes. This result is established, for the most part, by means of a result on generalized doubly resolvable packings which is of combinatorial interest in its own right.      

Error-correcting codes from permutation groups

We replace the usual setting for error-correcting codes (i.e. vector spaces over finite fields) with that of permutation groups. We give an algorithm which uses a combinatorial structure which we call an uncovering-by-bases, related to covering designs, and construct some examples of these. We also analyse the complexity of the algorithm.We then formulate a conjecture about uncoverings-by-bases, for which we give some supporting evidence and prove for some special cases. In particular, we consider the case of the symmetric group in its action on 2-subsets, where we make use of the theory of graph decompositions. Finally, we discuss the implications this conjecture has for the complexity of the decoding algorithm.     

Constructions for retransmission permutation arrays

Li et al. (Retransmission ≠ repeat: simple retransmission permutation can resolve overlapping channel collisions, 2009) introduced a technique for resolving overlapping channel transmissions that used an interesting new type of combinatorial structure. In connection with this problem, they provided an example of a 4 × 4 array having certain desirable properties. We define a class of combinatorial structures, which we term retrans mission permutation arrays, that generalise the example that Li et?al. provided. We show that these arrays exist for all possible orders. We also define some extensions having additional properties, for which we provide some partial results.     

Constructing permutation arrays from groups

Let M(n, d) be the maximum size of a permutation array on n symbols with pairwise Hamming distance at least d. We use various combinatorial, algebraic, and computational methods to improve lower bounds for M(n, d). We compute the Hamming distances of affine semilinear groups and projective semilinear groups, and unions of cosets of AGL(1, q) and PGL(2, q) with Frobenius maps to obtain new, improved lower bounds for M(n, d). We give new randomized algorithms. We give better lower bounds for M(n, d) also using new theorems concerning the contraction operation. For example, we prove a quadratic lower bound for \(M(n,n-2)\) for all \(n\equiv 2 \pmod 3\) such that \(n+1\) is a prime power.     

A new combinatorial approach to the construction of constant composition codes

Constant composition codes(CCCs)are a new generalization of binary constant weight codes and have attracted recent interest due to their numerous applications. In this paper, a new combinatorial approach to the construction of CCCs is proposed, and used to establish new optimal CCCs.     

A new table of permutation codes

Permutation codes (or permutation arrays) have received considerable interest in recent years, partly motivated by a potential application to powerline communication. Powerline communication is the transmission of data over the electricity distribution system. This environment is rather hostile to communication and the requirements are such that permutation codes may be suitable. The problem addressed in this study is the construction of permutation codes with a specified length and minimum Hamming distance, and with as many codewords (permutations) as possible. A number of techniques are used including construction by automorphism group and several variations of clique search based on vertex degrees. Many significant improvements are obtained to the size of the best known codes.     

Covering arrays and intersecting codes

A t-covering array is a set of k binary vectors of length n with the property that, in any t coordinate positions, all 2^t possibilities occur at least once. Such arrays are used for example in circuit testing, and one wishes to minimize k for given values of n and t. The case t = 2 was solved by Rényi, Katona, and Kleitman and Spencer. The present article is concerned with the case t = 3, where important (but unpublished) contributions were made by Busschbach and Roux in the 1980s. One of the principal constructions makes use of intersecting codes (linear codes with the property that any two nonzero codewords meet). This article studies the properties of 3-covering arrays and intersecting codes, and gives a table of the best 3-covering arrays presently known. For large n the minimal k satisfies 3.21256 < k/log n < 7.56444. © 1993 John Wiley & Sons, Inc.     

Decoding permutation arrays with ternary vectors

It is well known that the MacWilliams transform of the weight enumerator of some code having integer coefficients is equivalent to a set of congruences having integer solutions. In this paper, we prove an equivalent condition of Ward’s bound on dimension of divisible codes, which is part of this set of congruences having integer solutions. This new interpretation makes the generalization of Ward’s bound an explicit one.     

A mass formula for self-dual permutation codes

For a module V over a finite semisimple algebra A we give the total number of self-dual codes in V. This enables us to obtain a mass formula for self-dual codes in permutation representations of finite groups over finite fields of coprime characteristic.     

On the permutation groups of cyclic codes

We classify the permutation groups of cyclic codes over a finite field. As a special case, we find the permutation groups of non-primitive BCH codes of prime length. In addition, the Sylow p-subgroup of the permutation group is given for many cyclic codes of length p ^m . Several examples are given to illustrate the results.     

Bounds on permutation codes of distance four

A permutation code of length n and distance d is a set Γ of permutations from some fixed set of n symbols such that the Hamming distance between each distinct x,y∈Γ is at least d. In this note, we determine some new results on the maximum size of a permutation code with distance equal to 4, the smallest interesting value. The upper bound is improved for almost all n via an optimization problem on Young diagrams. A new recursive construction improves known lower bounds for small values of n.