We propose a coding method to transform binary sequences into DNA base sequences (codewords), namely sequences of the symbols A, T, C, and G, that satisfy the following two properties: 1) run-length constraint: the maximum run-length of each symbol in each codeword is at most three and 2) GC-content constraint: the GC-content of each codeword is close to 0.5, say between 0.4 and 0.6. The proposed coding scheme is motivated by the problem of designing codes for DNA-based data storage systems, where the binary digital data is stored in synthetic DNA base sequences. Existing literature either achieve code rates not greater than 1.78 bits per nucleotide or lead to severe error propagation. Our method achieves a rate of 1.9 bits per DNA base with low encoding/ decoding complexity and limited error propagation.

We consider construction of deletion and substitution correcting codes with low redundancy and efficient encoding/ decoding. First, by simplifying the method of Sima et al . (ISIT 2020), we construct a family of binary single-deletion $s$ -substitution correcting codes with redundancy $(s+1) (2s+1)\log _{2} n+o(\log _{2} n)$ and encoding complexity $O(n^{2})$ , where $n$ is the blocklength of the code and $s\geq 1$ . The construction can be viewed as a generalization of Smagloy et al .’s construction (ISIT 2020), and for the special case of $s=1$ , our construction is a slight improvement in redundancy of the existing works. Further, we modify the syndrome compression technique by combining a precoding process and construct a family of systematic $t$ -deletion $s$ -substitution correcting codes with polynomial time encoding/decoding algorithms for both binary and nonbinary alphabets, where $t\geq 1$ and $s\geq 1$ . Specifically, our binary $t$ -deletion $s$ -substitution correcting codes of length $n$ have redundancy $(4t+3s)\log _{2}n+o(\log _{2}n)$ , whereas, for $q$ being a prime power, the redundancy of $q$ -ary $t$ -deletion $s$ -substitution codes is asymptotically $\left({4t+4s-1-\lfloor \frac {2s-1}{q}\rfloor }\right)\vphantom {{\lfloor \frac {2s-1}{q}\rfloor }_{j}}\log _{q} n + o(\log _{q}n)$ as $n\to \infty $ . We also construct a family of binary systematic $t$ -deletion correcting codes (i.e., $s=0$ ) with redundancy $(4t-1)\log _{2} n+o(\log _{2} n)$ . The proposed constructions improve upon the redundancy of the state-of-the-art constructions.

In this paper, we construct q -ary two-deletion correcting codes and burst-deletion correcting codes, where q ≥ 2 is an even integer. For two-deletion codes, our construction has redundancy 5 log n + O (log q log log n ) and has encoding complexity near-linear in n , where n is the length of the message sequences. For burst-deletion codes, we first present a construction of binary codes with redundancy log n +9 log log n + γ _t + o (log log n ) bits (γ _t is a constant that depends only on t ) and capable of correcting a burst of at most t deletions, which improves the Lenz-Polyanskii Construction (ISIT 2020). Then we give a construction of q -ary codes with redundancy log n +(8 log q + 9) log log n + γ _t + o (log log n ) bits and capable of correcting a burst of at most t deletions.

The process of DNA-based data storage (DNA storage for short) can be mathematically modelled as a communication channel, termed DNA storage channel, whose inputs and outputs are sets of unordered sequences. To design error correcting codes for DNA storage channel, a new metric, termed the sequence-subset distance, is introduced, which generalizes the Hamming distance to a distance function defined between any two sets of unordered vectors and helps to establish a uniform framework to design error correcting codes for DNA storage channel. We further introduce a family of error correcting codes, referred to as sequence-subset codes, for DNA storage and show that the error-correcting ability of such codes is completely determined by their minimum distance. We derive some upper bounds on the size of the sequence-subset codes including a tight bound for a special case, a Singleton-like bound and a Plotkinlike bound. We also propose some constructions, including an optimal construction for that special case, which imply lower bounds on the size of such codes.

We consider the locally repairable codes (LRCs), aiming at sequentially recovering multiple erasures; in particular, we propose and study the so-called (n, k, r, t)-sequential LRCs (SLRC) as an [n, k] linear code, where any t' (≤ t) erasures can be sequentially recovered, each by r (2 ≤ r <; k) other code symbols. Here, sequential recovering means that the erased symbols are recovered one by one, and an already recovered symbol can be used to recover the remaining erased symbols. This important recovering method, in contrast with the extensively studied parallel recovering, is currently far from being thoroughly understood; more specifically, there are to date no codes constructed for arbitrary t ≥ 3 erasures and bounds to evaluate the performance of such codes. We first derive a tight upper bound on the code rate of the (n, k, r, t)-SLRC for t = 3 and r ≥ 2. We then propose two constructions of binary (n, k, r, t)-SLRCs for general r, t ≥ 2 (existing constructions only deal with t ≤7 erasures). The first construction generalizes the method of direct product construction. The second construction is based on the resolvable configurations and yields SLRCs for any r ≥ 2 odd t ≥ 3. For both constructions, the rates are optimal for t ∈ {2, 3} and are higher than most of the existing LRC families for arbitrary t ≥ 4.

In this article, under a general cost function C, we present a dynamic programming (DP) method to obtain an optimal sequential deterministic quantizer (SDQ) for q-ary input discrete memoryless channel (DMC). The DP method has complexity O(q (N-M) ² M), where N and M are the alphabet sizes of the DMC output and quantizer output, respectively. Then, starting from the quadrangle inequality, two techniques are applied to reduce the DP method's complexity. One technique makes use of the Shor-Moran-Aggarwal-Wilber-Klawe (SMAWK) algorithm and achieves complexity O(q (N-M) M). The other technique is much easier to be implemented and achieves complexity O(q (N ² - M ² )). We further derive a sufficient condition under which the optimal SDQ is optimal among all quantizers and the two techniques are applicable. This generalizes the results in the literature for binary-input DMC. Next, we show that the cost function of α-mutual information ( α-MI)-maximizing quantizer belongs to the category of C. We further prove that under a weaker condition than the sufficient condition we derived, the aforementioned two techniques are applicable to the design of α-MI-maximizing quantizer. Finally, we illustrate the particular application of our design method to practical pulse-amplitude modulation systems.