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.     

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.     

Constructions for Permutation Codes in Powerline Communications

A permutation array (or 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. One motivation for coding with permutations is powerline communication. After summarizing known results, it is shown here that certain families of polynomials over finite fields give rise to permutation arrays. Additionally, several new computational constructions are given, often making use of automorphism groups. Finally, a recursive construction for permutation arrays is presented, using and motivating the more general notion of codes with constant weight composition.     

Cyclically permutable representations of cyclic codes

Cyclically permutable codes have been studied for several applications involving synchronization, code-division multiple-access (CDMA) radio systems and optical CDMA. The usual emphasis is on finding constant weight cyclically permutable codes with the maximum number of codewords. In this paper the question of when a particular error-correcting code is equivalent (by permutation of the symbols) to a cyclically permutable code is addressed. The problem is introduced for simplex codes and a motivating example is given. In the final section it is shown that the construction technique may be applied in general to cyclic codes.     

New Algorithms of Distance-Increasing Mappings from Binary Vectors to Permutations by Swaps

Mappings from the set of binary vectors of a fixed length to the set of permutations of the same length that strictly increase Hamming distances are useful for the construction of permutation codes (permutation arrays). In this paper, we propose new simpler algorithms of distance-increasing mappings. These algorithms do not need any table lookup operations, and they are built up with fewer swap perations. In the comparison of our new algorithms with other DIMs, we also give some numerical results to illustrate that the distance expansion distributions of our new mappings are not bad.     

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.     

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.     

Permutation Cellular Automata

Permutation cellular automata are cellular automata defined by using finite maximal prefix codes. The overall dynamics of onesided and twosided permutation cellular automata is studied. For some classes of permutation cellular automata including the class of those defined by using finite maximal bifix codes, the overall dynamics is completely or partially described in terms of the codes used to define them.     

SELF-DUAL PERMUTATION CODES OVER FORMAL POWER SERIES RINGS AND FINITE PRINCIPAL IDEAL RINGS

In this paper, we study self-dual permutation codes over formal power series rings and finite principal ideal rings. We first give some results on the torsion codes associated with the linear codes over formal power series rings. These results allow for obtaining some conditions for non-existence of self-dual permutation codes over formal power series rings. Finally, we describe self-dual permutation codes over finite principal ideal rings by examining permutation codes over their component chain rings.     

Consolidation for compact constraints and Kendall tau LP decodable permutation codes

Invented in the 1960s, permutation codes have reemerged in recent years as a topic of great interest because of properties making them attractive for certain modern technological applications, especially flash memory. In 2011 a polynomial time algorithm called linear programming (LP) decoding was introduced for a class of permutation codes where the feasible set of codewords was a subset of the vertex set of a code polytope. In this paper we investigate a new class of linear constraints for matrix polytopes with no fractional vertices through a new concept called “consolidation.” We then introduce a necessary and sufficient condition for which LP decoding methods, originally designed for the Euclidean metric, may be extended to provide an efficient decoding algorithm for permutation codes with the Kendall tau metric.     

How to find small AI-systems for antiblocking decoding

The antiblocking decoding algorithm established in Kroll and Vincenti (2010) [6] is based on the notion of an antiblocking system. It is comparable with the permutation decoding algorithm. Instead of a permutation decoding set, called a PD-set, consisting of automorphisms of the code, it uses an antiblocking system, called an AI-system, consisting of information sets.As the permutation decoding algorithm is more efficient the smaller the PD-set, so the antiblocking decoding algorithm is more effective the smaller the AI-system. Therefore, it is important for the applications to find small AI-systems.As in the case of PD-sets, there is no method that guarantees in general how to construct optimal or nearly optimal AI-systems.In this paper, we present first some general results on the existence and construction of small antiblocking systems using properties of antiblocking systems derived in Kroll and Vincenti (2008) [4]. The crucial point for the construction of antiblocking systems is a lemma, in which a recursive procedure is provided. In the second part, we apply these findings to construct small AI-systems for some codes arising from a cap of 20 points in PG(4,3).     

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.      

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.     

On the existence of self-dual permutation codes of finite groups

Motivated by a research on self-dual extended group codes, we consider permutation codes obtained from submodules of a permutation module of a finite group of odd order over a finite field, and demonstrate that the condition “the extension degree of the finite field extended by n’th roots of unity is odd” is sufficient but not necessary for the existence of self-dual extended transitive permutation codes of length n + 1. It exhibits that the permutation code is a proper generalization of the group code, and has more delicate structure than the group code.     

On the enumeration of self-dual codes

We give the complete classification of all binary, self-dual, doubly-even (32, 16) codes. There are 85 non-equivalent, self-dual, doubly-even (32, 16) codes. Five of these have minimum weight 8, namely, a quadratic residue code and a Reed-Muller code, and three new codes. A set of generators is given for a code in each equivalence class together with its entire weight distribution and the order of its entire group with other information facilitating the computation of permutation generators. From this list it is possible to identify all self-dual codes of length less than 32 and the numbers of these are included.     

Lehmer code transforms and Mahonian statistics on permutations

In 2000 Babson and Steingrímsson introduced the notion of vincular patterns in permutations. They show that essentially all well-known Mahonian permutation statistics can be written as combinations of such patterns. Also, they proved and conjectured that other combinations of vincular patterns are still Mahonian. These conjectures were proved later: by Foata and Zeilberger in 2001, and by Foata and Randrianarivony in 2006.In this paper we give an alternative proof of some of these results. Our approach is based on permutation codes which, like the Lehmer code, map bijectively permutations onto subexcedant sequences. More precisely, we give several code transforms (i.e., bijections between subexcedant sequences) which when applied to the Lehmer code yield new permutation codes which count occurrences of some vincular patterns. These code transforms can be seen as a pre-compression step of the Lehmer code because they map some redundancies into runs of 0s. Also, our proofs, unlike the previous ones, provide explicit bijections between permutations having a given value for two different Mahonian pattern-based statistics.     

Gray code for permutations with a fixed number of cycles

We give the first Gray code for the set of n-length permutations with a given number of cycles. In this code, each permutation is transformed into its successor by a product with a cycle of length three, which is optimal. If we represent each permutation by its transposition array then the obtained list still remains a Gray code and this allows us to construct a constant amortized time (CAT) algorithm for generating these codes. Also, Gray code and generating algorithm for n-length permutations with fixed number of left-to-right minima are discussed.     

Automorphism groups of cyclic codes

In this article we study the automorphism groups of binary cyclic codes. In particular, we provide explicit constructions for codes whose automorphism groups can be described as (a) direct products of two symmetric groups or (b) iterated wreath products of several symmetric groups. Interestingly, some of the codes we consider also arise in the context of regular lattice graphs and permutation decoding.     

Information sets in abelian codes: defining sets and Groebner basis

In Bernal and Simón (IEEE Trans Inf Theory 57(12):7990–7999, 2011) we introduced a technique to construct information sets for every semisimple abelian code by means of its defining set. This construction is a non trivial generalization of that given by Imai (Inf Control 34:1–21, 1977) in the case of binary two-dimensional cyclic (TDC) codes. On the other hand, Sakata (IEEE Trans Inf Theory IT-27(5):556–565, 1981) showed a method for constructing information sets for binary TDC codes based on the computation of Groebner basis which agrees with the information set obtained by Imai. Later, Chabanne (IEEE Trans Inf Theory 38(6):1826–1829, 1992) presents a generalization of the permutation decoding algorithm for binary abelian codes by using Groebner basis, and as a part of his method he constructs an information set following the same ideas introduced by Sakata. In this paper we show that, in the general case of q-ary multidimensional abelian codes, both methods, that based on Groebner basis and that defined in terms of the defining sets, also yield the same information set.     

Codes from the incidence matrices of graphs on 3-sets

We examine the p-ary linear codes from incidence matrices of the three uniform subset graphs with vertex set the set of subsets of size 3 of a set of size n, with adjacency defined by two vertices as 3-sets being adjacent if they have zero, one or two elements in common, respectively. All the main parameters of the codes and the nature of the minimum words are obtained, and it is shown that the codes can be used for full error-correction by permutation decoding. We examine also the binary codes of the line graphs of these graphs.