Search

A $(1,k)$ -overlap-free code, motivated by applications in DNA-based data storage systems and synchronization between communication devices, is a set of words in which no prefix of length $t$ of any word is the suffix of any word for every integer $t$ such that $1\leq t\leq k$ . A $(1,n-1)$ -overlap-free code of length $n$ is said to be non-overlapping. We provide a construction for $q$ -ary $(1,k)$ -overlap-free codes of length $2k$ , which can be viewed as a generalization of the Zero Block Construction presented by Blackburn, Esfahani, Kreher and Stinson recently over a binary alphabet, and analyze the asymptotic behavior of their sizes. When $n\geq 2k$ , an explicit general lower bound and an asymptotic lower bound for the size of an optimal $q$ -ary $(1,k)$ -overlap-free code of length $n$ are presented. The exact value of the maximum size of $q$ -ary (1, 2)-overlap-free codes of length $n$ is determined for any $n\geq 4$ , and a construction for $q$ -ary $(1,k)$ -overlap-free codes of length $k+2$ is given.

A multichannel conflict-avoiding code (MC-CAC) is a collection of two-dimensional codewords represented by zero-one matrices, and any pair of distinct codewords have at most one overlapping 1 regardless of the relative time offsets. Such codes are of practical interest as they are able to provide a hard guarantee that each active user has a successful transmission within every consecutive $n$ time slots in a wireless network with multiple asynchronous collision channels. In a more practical setting, it is assumed that in each time slot each source node can only pick one channel and send one packet in the chosen channel, and hence the at most one-packet per time slot (AM-OPPTS) restriction is appended to an MC-CAC. Only upper bounds for the number of codewords of an AM-OPPTS MC-CAC with weights three and four were known in the literature, and constructions for AM-OPPTS MC-CACs have not been explored and analyzed systematically. This paper is devoted to establishing combinatorial constructions for AM-OPPTS MC-CACs by introducing holey group divisible packings with prescribed automorphism groups. As applications of our constructions, the exact values of the sizes of both an optimal AM-OPPTS MC-CAC $(m,n,3)$ and an optimal AM-OPPTS MC-CAC $\left({m,p^{r},\frac {p+1}{2}}\right)$ are determined for certain $m,n,p$ and $r$ .

Abstract: In this paper, it is shown that the necessary conditions for the existence of a (gv, {g, 3α}, 3, λ)-DF in Z gv for α ∈ {0, 1, 2} are also sufficient with two exceptions of (v, g, λ, α) = (9, 1, 1, 1), (9, 1, 2, 2). Finally, the existence spectrum of a cyclic (3, λ)-GDD of type g v is determined.