Search

Non-overlapping codes are a set of codewords such that the prefix of each codeword is not a suffix of any codeword in the set, including itself. If the lengths of the codewords are variable, it is additionally required that every codeword is not contained in any other codeword as a subword. Let $C(n,q)$ be the maximum size of $q$-ary fixed-length non-overlapping codes of length $n$. The upper bound on $C(n,q)$ has been well studied. However, the nontrivial upper bound on the maximum size of variable-length non-overlapping codes of length at most $n$ remains open. In this paper, by establishing a link between variable-length non-overlapping codes and fixed-length ones, we are able to show that the size of a $q$-ary variable-length non-overlapping code is upper bounded by $C(n,q)$. Furthermore, we prove that the average length of the codewords in a $q$-ary variable-length non-overlapping codes is lower bounded by $\lceil \log_q \tilde{C} \rceil$, and is asymptotically no shorter than $n-2$ as $q$ approaches $\infty$, where $\tilde{C}$ denotes the cardinality of $q$-ary variable-length non-overlapping codes of length up to $n$.

A storage code is an assignment of symbols to the vertices of a connected graph $G(V,E)$ with the property that the value of each vertex is a function of the values of its neighbors, or more generally, of a certain neighborhood of the vertex in $G$. In this work we introduce a new construction method of storage codes, enabling one to construct new codes from known ones via an interleaving procedure driven by resolvable designs. We also study storage codes on $\mathbb Z$ and ${\mathbb Z}^2$ (lines and grids), finding closed-form expressions for the capacity of several one and two-dimensional systems depending on their recovery set, using connections between storage codes, graphs, anticodes, and difference-avoiding sets.

The fixed length Levenshtein (FLL) distance between two words $\mathbf{x,y} \in \mathbb{Z}_m^n$ is the smallest integer $t$ such that $\mathbf{x}$ can be transformed to $\mathbf{y}$ by $t$ insertions and $t$ deletions. The size of a ball in FLL metric is a fundamental but challenging problem. Very recently, Bar-Lev, Etzion, and Yaakobi explicitly determined the minimum, maximum and average sizes of the FLL balls with radius one. In this paper, based on these results, we further prove that the size of the FLL balls with radius one is highly concentrated around its mean by Azuma's inequality.

Non-overlapping codes are a set of codewords in $\bigcup_{n \ge 2} \mathbb{Z}_q^n$, where $\mathbb{Z}_q = \{0,1,\dots,q-1\}$, such that, the prefix of each codeword is not a suffix of any codeword in the set, including itself; and for variable-length codes, a codeword does not contain any other codeword as a subword. In this paper, we investigate a generic method to generalize binary codes to $q$-ary for $q > 2$, and analyze this generalization on the two constructions given by Levenshtein (also by Gilbert; Chee, Kiah, Purkayastha, and Wang) and Bilotta, respectively. The generalization on the former construction gives large non-expandable fixed-length non-overlapping codes whose size can be explicitly determined; the generalization on the later construction is the first attempt to generate $q$-ary variable-length non-overlapping codes. More importantly, this generic method allows us to utilize the generating function approach to analyze the cardinality of the underlying $q$-ary non-overlapping codes. The generating function approach not only enables us to derive new results, e.g., recurrence relations on their cardinalities, new combinatorial interpretations for the constructions, and the limit superior of their cardinalities for some special cases, but also greatly simplifies the arguments for these results. Furthermore, we give an exact formula for the number of fixed-length words that do not contain the codewords in a variable-length non-overlapping code as subwords. This thereby solves an open problem by Bilotta and induces a recursive upper bound on the maximum size of variable-length non-overlapping codes.

Binary sequences with low odd-periodic correlation magnitudes have found important applications in communication systems. It is well known that the nega-cyclic shift and negation preserve the odd-periodic autocorrelation function (OACF) values in general. In this paper, we define a new operation based on Parker's transformation, which also preserves the OACF values of binary sequences. This enables us to classify Parker's 16 cases into 8 ones, and may possibly further allow to classify all constructions based on Parker's transformation., Comment: 9 pages