Necessary and sufficient conditions for tight equi-difference conflict-avoiding codes of weight three

A conflict-avoiding code (CAC) C of length n and weight k is a collection of k-subsets of such that holds for any , , where . A CAC with maximum code size for given n and k is called optimal. Furthermore, an optimal CAC C is said to be tight equi-difference if holds and any codeword has the form . The concept of a CAC is motivated from applications in multiple-access communication systems. In this paper, we give a necessary and sufficient condition to construct tight equi-difference CACs of weight k = 3 and characterize the code length n’s admitting the condition through a number theoretical approach.      

Optimal conflict-avoiding codes of odd length and weight three

A conflict-avoiding code (CAC) \({\mathcal{C}}\) of length n and weight k is a collection of k-subsets of \({\mathbb{Z}_{n}}\) such that \({\Delta (x) \cap \Delta (y) = \emptyset}\) for any \({x, y \in \mathcal{C}}\) , \({x\neq y}\) , where \({\Delta (x) = \{a - b:\,a, b \in x, a \neq b\}}\) . Let CAC(n, k) denote the class of all CACs of length n and weight k. A CAC with maximum size is called optimal. In this paper, we study the constructions of optimal CACs for the case when n is odd and k = 3.     

New optimal constructions of conflict-avoiding codes of odd length and weight 3

Conflict-avoiding codes (CACs) have played an important role in multiple-access collision channel without feedback. The size of a CAC is the number of codewords which equals the number of potential users that can be supported in the system. A CAC with maximal code size is said to be optimal. The use of an optimal CAC enables the largest possible number of asynchronous users to transmit information efficiently and reliably. In this paper, the maximal sizes of both equidifference and non equidifference CACs of odd prime length and weight 3 are obtained. Meanwhile, the optimal constructions of both equidifference and non equidifference CACs are presented. The numbers of equidifference and non equidifference codewords in an optimal code are also obtained. Furthermore, a new modified recursive construction of CACs for any odd length is shown. Non equidifference codes can be constructed in this method.     

Optimal doubly constant weight codes

A doubly constant weight code is a binary code of length n₁ + n₂, with constant weight w₁ + w₂, such that the weight of a codeword in the first n₁ coordinates is w₁. Such codes have applications in obtaining bounds on the sizes of constant weight codes with given minimum distance. Lower and upper bounds on the sizes of such codes are derived. In particular, we show tight connections between optimal codes and some known designs such as Howell designs, Kirkman squares, orthogonal arrays, Steiner systems, and large sets of Steiner systems. These optimal codes are natural generalization of Steiner systems and they are also called doubly Steiner systems. © 2007 Wiley Periodicals, Inc. J Combin Designs 16: 137–151, 2008     

Optimal constant weight covering codes and nonuniform group divisible 3-designs with block size four

Let K _q (n, w, t, d) be the minimum size of a code over Z _q of length n, constant weight w, such that every word with weight t is within Hamming distance d of at least one codeword. In this article, we determine K _q (n, 4, 3, 1) for all n ≥ 4, q = 3, 4 or q = 2 ^m  + 1 with m ≥ 2, leaving the only case (q, n) = (3, 5) in doubt. Our construction method is mainly based on the auxiliary designs, H-frames, which play a crucial role in the recursive constructions of group divisible 3-designs similar to that of candelabra systems in the constructions of 3-wise balanced designs. As an application of this approach, several new infinite classes of nonuniform group divisible 3-designs with block size four are also constructed.     

A tight asymptotic bound on the size of constant-weight conflict-avoiding codes

In the study of multiple-access in the collision channel, conflict-avoiding code is used to guarantee that each transmitting user can send at least one packet successfully in the worst case within a fixed period of time, provided that at most k users out of M potential users are active simultaneously. The number of codewords in a conflict-avoiding code determines the number of potential users that can be supported in a system. Previously, upper bound on the size of conflict-avoiding code is known only for Hamming weights three, four and five. The asymptotic upper in this paper extends the known results to all Hamming weights, and is proved to be tight by exhibiting infinite sequences of conflict-avoiding codes which meet this bound asymptotically for all Hamming weights.     

Optimal cyclic quaternary constant‐weight codes of weight three

A cyclic code is a cyclic q‐ary code of length n, constant weight w and minimum distance d. Let denote the largest possible size of a cyclic code. The pure and mixed difference method plays an important role in the determination of upper bound on . By analyzing the distribution of odd mixed and pure differences, an improved upper bound on is obtained for . A new construction based on special sequences is provided and the exact value of is almost completely determined for all d and n except when and . Our constructions reveal intimate connections between cyclic constant weight codes and special sequences, particularly Skolem‐type sequences.     

Constructions for optimal cyclic ternary constant-weight codes of weight four and distance six

A cyclic ${(n,d,w)}_q$ code is a $q$-ary cyclic code of length $n$, minimum Hamming distance $d$ and weight $w$. In this paper, we investigate cyclic ${(n,6,4)}_3$ codes. A new upper bound on $C{A}_3(n,6,4)$, the largest possible number of codewords in a cyclic ${(n,6,4)}_3$ code, is given. Two new constructions for optimal cyclic ${(n,6,4)}_3$ codes based on cyclic $(n,4,1)$ difference packings are presented. As a consequence, the exact value of $C{A}_3(n,6,4)$ is determined for any positive integer $n\equiv 0,6,18(mod24)$. We also obtain some other infinite classes of optimal cyclic ${(n,6,4)}_3$ codes.     

Optimal ternary linear codes

Let n _q (k, d) denote the smallest value of n for which there exists a linear [n, k, d]-code over GF(q). An [n, k, d]-code whose length is equal to n _q (k, d) is called optimal. The problem of finding n _q (k, d)has received much attention for the case q = 2. We generalize several results to the case of an arbitrary prime power q as well as introducing new results and a detailed methodology to enable the problem to be tackled over any finite field.In particular, we study the problem with q = 3 and determine n ₃(k, d) for all d when k 4, and n ₃(5, d) for all but 30 values of d.     

Optimal ternary quasi-cyclic codes

Quasi-cyclic codes have provided a rich source of good linear codes. Previous constructions of quasi-cyclic codes have been confined mainly to codes whose length is a multiple of the dimension. In this paper it is shown how searches may be extended to codes whose length is a multiple of some integer which is greater than the dimension. The particular case of 5-dimensional codes over GF(3) is considered and a number of optimal codes (i.e., [n, k, d]-codes having largest possible minimum distance d for given length n and dimension k) are constructed. These include ternary codes with parameters [45, 5, 28], [36, 5, 22], [42, 5, 26], [48, 5, 30] and [72, 5, 46], all of which improve on the previously best known bounds.This research has been supported by the British SERC.     

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.     

The weight distributions of some cyclic codes with three or four nonzeros over \mathbb F _3

Because of efficient encoding and decoding algorithms comparing with linear block codes, cyclic codes form an important family and have applications in communications and storage systems. However, their weight distributions are known only for a few cases mainly on the codes with no more than three nonzeros. In this paper, the weight distributions of two classes of cyclic codes with three or four nonzeros are determined.