Analytic combinatorics in several variables refers to a suite of tools that provide sharp asymptotic estimates for certain combinatorial quantities. In this paper, we apply these tools to determine the Gilbert-Varshamov lower bound on the rate of optimal codes in$L_{1}$metric. Several different code spaces are analyzed, including the simplex and the hypercube in${\mathbb {Z}}^{n}$, all of which are inspired by concrete data storage and transmission models such as the permutation channel, the repetition channel, the adjacent transposition (bit-shift) channel, the multilevel flash memory channel, etc.

Motivated by applications in spatial genomics, we revisit group testing (Dorfman 1943) and propose the class of$\lambda$-ADD-codes, studying such codes with certain distance$d$and codelength$n$. When$d$is constant, we provide explicit code constructions with rates close to 1/2. When$d$is proportional to$n$, we provide a GV-type lower bound whose rates are efficiently computable. Upper bounds for such codes are also studied.

We study and propose schemes that map messages onto constant-weight codewords using variable-length prefixes. We provide polynomial-time computable formulas that estimate the average number of redundant bits incurred by our schemes. In addition to the exact formulas, we also perform an asymptotic analysis and demonstrate that our scheme uses 1/2 log2n+O(1) redundant bits to encode messages into length-n words with weight (n/2) + μ for constant μ. We also propose schemes that map messages into balanced codebooks with error-correcting capabilities. For such schemes, we provide methods to enumerate the average number of redundant bits.

Analytic combinatorics in several variables refers to a suite of tools that provide sharp asymptotic estimates for certain combinatorial quantities. In this paper, we apply these tools to determine the Gilbert–Varshamov (GV) bound for the sticky insertion and the constrained-synthesis channel.

In this work, we investigate a challenging problem, which has been considered to be an important criterion in designing codewords for DNA computing purposes, namely secondary structure avoidance in single-stranded DNA molecules. In short, secondary structure refers to the tendency of a single-stranded DNA sequence to fold back upon itself, thus becoming inactive in the computation process. The main contribution of this work is to provide an explicit construction of DNA codes that completely avoid the formation of secondary structures of arbitrary stem length.Formally, given codeword length n and arbitrary integer m ⩾ 2, we provide efficient methods to construct DNA codes of length n that avoid secondary structure of any stem length more than or equal to m. Particularly, when m = 3, our constructions yield a family of DNA codes of rate 1.3031 bits/nt, while the highest rate found in the prior art was 1.1609 bits/nt. In addition, for m ⩾ 3log n+4, we provide an efficient encoder that incurs only one redundant symbol.

The de Bruijn based timing and synchronization (dBTS) system has been proposed and studied recently for some channels require reliable synchronization, such as quantum communication. To avoid a long period of no-pulse in the dBTS system, we propose to study the run length limited de Bruijn sequences which not only are run length limited sequences but also can be used to locate the location of any sub-string. Such subjects are expected to have various applications and they also present some interesting theoretical questions in combinatorics, algorithms and coding theory.In this paper, we are the first to provide an explicit formula of the maximal length of the run length limited de Bruijn sequences. Besides that, using Lyndon words, we present an efficient construction of a run length limited de Bruijn sequence with the maximal length. Furthermore, we also provide a sub-linear decoding algorithm which can locate the position of an arbitrary sub-string.

A multiset combinatorial batch code (MCBC) over vector space consists of a set of subspaces of$\mathbb{F}_{q}^{n}$, each corresponding to a server, such that requests consisting of$t$dimensional subspaces, can be retrieved from the servers. The code is said to be regular if all the subspaces in the code have the same dimension. The aim is to find the minimum number of total storage, and also the minimum number of servers in the regular case, fixing other parameters. In this paper, we provide bounds and constructions for this new class of batch codes.

An (n,d)-robust positioning sequence (RPS) is a binary sequence where every pair of length-n subwords is distance d apart. In this paper, we study the quantity P(n,d), which denotes maximum length of an (n,d)-RPS, and provide tight estimates in the range n/2 < d ≤ n. First, we show that the usual Plotkin bound cannot be attained when certain divisibility conditions hold. Next, using the concept of differences, we construct an infinite family of RPSs that attain a modified Plotkin bound. Finally, except for 16 cases, we determine the exact values of P(n,d) for δ(n) ≤ d ≤ n ≤ 50, where δ(n) = ⌈n/2⌉ if n ≢ 0(mod 4) and δ(n) = (n +2)/2 if n ≡ 0(mod 4).

A robust positioning pattern is a large array that allows a mobile device to locate its position by reading a possibly corrupted small window around it. In this paper, we provide constructions of binary positioning patterns, equipped with efficient locating algorithms, that are robust to a constant number of errors and have redundancy within a constant factor of optimality. Furthermore, we modify our constructions to correct rank errors and obtain binary positioning patterns robust to any errors of rank less than a constant number. Additionally, we construct $q$-ary robust positioning sequences robust to a large number of errors, some of which have length attaining the upper bound. Our construction of binary positioning sequences that are robust to a constant number of errors has the least known redundancy among those explicit constructions with efficient locating algorithms. On the other hand, for binary robust positioning arrays, our construction is the first explicit construction whose redundancy is within a constant factor of optimality. The locating algorithms accompanying both constructions run in time cubic in sequence length or array dimension.

A robust positioning pattern is a large array that allows a mobile device to locate its position by reading a possibly corrupted small window around it. This paper provides constructions of binary positioning patterns, equipped with efficient locating algorithms, that are robust to a constant number of errors and have redundancy within a constant factor of optimality. Our construction of binary robust positioning sequences has the least known redundancy amongst those explicit constructions with efficient locating algorithms. On the other hand, for binary robust positioning arrays, our construction is the first explicit construction whose redundancy is within a constant factor of optimality. The locating algorithms accompanying our constructions run in time cubic in sequence length or array dimensions.