In this paper, we study theRandom Access Problemin DNA storage, which addresses the challenge of retrieving a specific information strand from a DNA-based storage system. In this framework, the data is represented bykinformation strands which represent the data and are encoded intonstrands using a linear code. Then, each sequencing read returns one encoded strand which is chosen uniformly at random. The goal under this paradigm is to design codes that minimize the expected number of reads required to recover an arbitrary information strand. We fully solve the case whenk= 2, showing that the best possible code attains a random access expectation of 1 + 2/ √2+1 ≈ 0.914 · 2 forqlarge enough. Moreover, we extend a previous construction, originally developed fork= 3, to arbitrary values ofk. Our construction usesBk−1sequences overZq−1, that always exist over large finite fields. We show that for everyk≥ 4, this generalized construction outperforms all previous constructions in terms of reducing the random access expectation.

In this paper, we investigate codes designed to correct two bursts of deletions, where each burst has a length of exactlyb, whereb> 1. The previous best construction, achieved through the syndrome compression technique, had a redundancy of at most 7 logn+O(logn/ log logn) bits. In contrast, our work introduces a novel approach for constructing q-ary codes that attain a redundancy of at most 5 logn+O(log logn) bits for allb> 1 andq≥ 2. Additionally, for the case whereb= 1, we present a new construction of q-ary two-deletion correcting codes with a redundancy of 5 logn+ O(log logn) bits, for allq> 2.

Abstract In this paper, we focus on constructing unique-decodable and list-decodable codes for the recently studied (t, e)-composite-asymmetric error-correcting codes ((t, e)-CAECCs). Let $$\mathcal {X}$$ X be an $$m \times n$$ m × n binary matrix in which each row has Hamming weight w. If at most t rows of $$\mathcal {X}$$ X contain errors, and in each erroneous row, there are at most e occurrences of $$1 \rightarrow 0$$ 1 → 0 errors, we say that a (t, e)-composite-asymmetric error occurs in $$\mathcal {X}$$ X . For general values of m, n, w, t, and e, we propose new constructions of (t, e)-CAECCs with redundancy at most $$(t-1)\log (m) + O(1)$$ ( t - 1 ) log ( m ) + O ( 1 ) , where O(1) is independent of the code length m. In particular, this yields a class of (2, e)-CAECCs that are optimal in terms of redundancy. When m is a prime power, the redundancy can be further reduced to $$(t-1)\log (m) - O(\log (m))$$ ( t - 1 ) log ( m ) - O ( log ( m ) ) . To further increase the code size, we introduce a combinatorial object called a weak $$B_e$$ B e -set. When $$e = w$$ e = w , we present an efficient encoding and decoding method for our codes. Finally, we explore potential improvements by relaxing the requirement of unique decoding to list-decoding. We show that when the list size is t! or an exponential function of t, there exist list-decodable (t, e)-CAECCs with constant redundancy. When the list size is two, we construct list-decodable (3, 2)-CAECCs with redundancy $$\log (m) + O(1)$$ log ( m ) + O ( 1 ) .

In response to the evolving landscape of data storage, researchers have increasingly explored non-traditional platforms, with DNA-based storage emerging as a cutting-edge solution. Our work is motivated by the potential of in-vivo DNA storage, known for its capacity to store vast amounts of information efficiently and confidentially within an organism's native DNA. While promising, in-vivo DNA storage faces challenges, including susceptibility to errors introduced by mutations. To understand the long-term behavior of such mutation systems, we investigate the frequency of k-tuples after multiple mutation applications. Drawing inspiration from related works, we generalize results from the study of mutation systems, particularly focusing on the frequency of k-tuples. In this work, we provide a broad analysis through the construction of a specialized matrix and the identification of its eigenvectors. In the context of substitution and duplication systems, we leverage previous results on almost sure convergence, equating the expected frequency to the limiting frequency. Moreover, we demonstrate convergence in probability under certain assumptions.

In response to the evolving landscape of data storage, researchers have increasingly explored non-traditional platforms, with DNA-based storage emerging as a cutting-edge solution. Our work is motivated by the potential of in-vivo DNA storage, known for its capacity to store vast amounts of information efficiently and confidentially within an organism’s native DNA. While promising, in-vivo DNA storage faces challenges, including susceptibility to errors introduced by mutations. One way to understand the long-term effect of such mutations on the stored information is to investigate the frequency of k-tuples after multiple mutations. Drawing inspiration from related works, we generalize results from the study of duplication systems, particularly focusing on the frequency (or proportion) of k-tuples. We provide a general method for the analysis of mutation systems through the construction of a specialized matrix, dubbed substitution matrix, and the identification of its eigenvectors. Specifically, we derive an expression for the expected frequency of k-tuples. In the context of duplication errors, we leverage existing results on the almost sure convergence of the frequency of k-tuples. This allows us to equate the expected frequency of k-tuples to the limiting frequency of k-tuples. In addition, we demonstrate the convergence in probability of the frequency of k-tuples under certain assumptions.

Private information retrieval (PIR) codes and batch codes are two important types of codes that are designed for coded distributed storage systems and private information retrieval protocols. These codes have been the focus of much attention in recent years, as they enable efficient and secure storage and retrieval of data in distributed systems. In this paper, we introduce a new class of codes called (s, t)-batch codes. These codes are a type of storage codes that can handle any multi-set oftrequests, comprised ofsdistinct information symbols. Importantly, PIR codes and batch codes are special cases of (s, t)-batch codes. The main goal of this paper is to explore the relationship between the number of redundancy symbols and the (s, t)-batch code property. Specifically, we establish a lower bound on the number of redundancy symbols required and present several constructions of (s, t)-batch codes. Furthermore, we extend this property to the case where each request is a linear combination of information symbols, which we refer to asfunctional(s, t)-batch codes.

Motivated by applications in polymer-based data storage, we study the problem of reconstructing a string from part of its composition multiset. We give a full description of strings that cannot be uniquely reconstructed up to reversal from their multisets of all the prefix-suffix compositions. Leveraging this description, we prove that for alln⩾ 6, there exists a string of lengthnthat cannot be uniquely reconstructed up to reversal. Moreover, for alln⩾ 6, we explicitly construct the set consisting of all lengthnstrings that can be uniquely reconstructed up to reversal. As a byproduct, we obtain that any binary string can be constructed using Dyck strings and Catalan-Bertrand strings. For any given string s, we provide a method to explicitly construct the set of all strings with the same prefix-suffix composition multiset as s, as well as a formula for the size of this set. Furthermore, we construct two classes of composition codes that can respectively correct composition missing errors and mass-reducing substitution errors. In addition, we raise a new problem: reconstructing a string when only given its compositions of substrings of length at mostr. We give suitable codes under some conditions.

In this paper, we present a novel communication channel, called the absorption channel, inspired by information transmission in neurons. Our motivation comes from in-vivo nano-machines, emerging medical applications, and brain-machine interfaces that communicate over the nervous system. For any given finite alphabet, we give codes that can correct absorption errors. For the binary alphabet, we show that the known binary (multiple-)deletion correcting codes already provide a good solution. For a single-absorption error, we show that the Varshamov-Tenengolts codes provide a near-optimal code in our setting. When the alphabet size$q$is at least 3, we construct a single-absorption correcting code whose redundancy is at most$3\log _{q}(n)+O_{q}(1)$. Then, based on this code and ideas introduced by Gabrys et al. (2022), we give a second construction of single-absorption correcting codes with redundancy$\log _{q}(n)+12\log _{q}\log _{q}(n)+O_{q}(1)$, which is optimal up to an$O\left ({\log _{q}\log _{q}(n)}\right)$. Here,$O_{q}(1)$denotes a number dependent on$q$but independent of the code-length$n$. Finally, we apply the syndrome compression technique with pre-coding to obtain a subcode of the single-absorption correcting code. This subcode can combat multiple absorption errors and has low redundancy. For each setup, efficient encoders and decoders are provided.

In this paper, we present a novel communication channel, called the absorption channel, inspired by information transmission in neurons. Our motivation comes from invivo nano-machines, emerging medical applications, and brain-machine interfaces that communicate over the nervous system.For any given finite alphabet, we give codes that can correct absorption errors. For the binary alphabet, the known binary (multiple-)deletion correcting codes already provide a good solution. For single-absorption error, we prove that the Varshamov-Tenengolts codes can provide a near-optimal code in our setting. When the alphabet size q is at least 3, we first construct a single-absorption correcting code whose redundancy is at most 3 logq(n)+O(1). Then, based on this code and ideas introduced in [1], we give a second construction of single-absorption correcting codes with redundancy logq(n) + 12 logqlogq(n) + O(1), which is optimal up to an O(logqlogq(n)).Finally, we apply the syndrome compression technique with pre-coding to obtain a subcode of the single-absorption correcting code. This subcode can combat multiple-absorption errors and has low redundancy.

In recent years, DNA has emerged as a potentially viable storage technology. DNA synthesis, which refers to the task of writing the data into DNA, is perhaps the most costly part of existing storage systems. Consequently, the high cost and low throughput limit the practical use of available DNA synthesis technologies. It has been found that the homopolymer run (i.e., the repetition of the same nucleotide) is a major factor affecting the synthesis and sequencing errors. Recently, Lenz et al. (2020) raised and studied the coding problem for efficient synthesis for DNA-based storage systems. Among other things, they studied the maximal code size under synthesis constraints. In Makarychev et al. (2020), the authors studied the role of batch optimization in reducing the cost of large-scale DNA synthesis, for a given pool$\mathcal {S}$of random quaternary strings of fixed length. This problem is related to the problem posed in Lenz et al. (2020) which can be viewed as the opposite side of the coin. Instead of seeking the largest code in which every codeword can be synthesized in a certain amount of time, they asked what is the average synthesis time of a randomly chosen string. Following the lead of Makarychev et al. (2020), in this paper, we take a step forward towards the theoretical understanding of DNA synthesis, and study the homopolymer run of length$k \geqslant 1$. Specifically, we are given a set of DNA strands$\mathcal {S}$, randomly drawn from a Markovian distribution modeling a general homopolymer run length constraint, that we wish to synthesize. For this problem, we derive asymptotically tight high probability lower and upper bounds on the cost of DNA synthesis, for any$k \geqslant 1$. Our bounds imply that, perhaps surprisingly, the periodic sequence$\overline { \mathsf {ACGT}}$is asymptotically optimal in the sense of achieving the smallest possible cost. Our main technical contribution is the representation of the DNA synthesis process as a certain constrained system, for which string techniques can be applied.

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. Under the name of recoverable systems, a class of storage codes on ${\mathbb{Z}}$ was recently studied relying on methods from constrained systems and ergodic theory. In this work, we address the question of the maximum capacity of recoverable systems on ${\mathbb{Z}}$ and ${{\mathbb{Z}}^2}$ from a combinatorial perspective. We establish a closed form formula 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.

Motivated by the established notion of storage codes, we consider sets of infinite sequences over a finite alphabet such that every$k$-tuple of consecutive entries is uniquely recoverable from its$l$-neighborhood in the sequence. We address the problem of finding the maximum growth rate of the set, which we term capacity, as well as constructions of explicit families that approach the optimal rate. The techniques that we employ rely on the connection of this problem with constrained systems. In the second part of the paper we consider a modification of the problem wherein the entries in the sequence are viewed as random variables over a finite alphabet that follow some joint distribution, and the recovery condition requires that the Shannon entropy of the$k$-tuple conditioned on its$l$-neighborhood be bounded above by some$\epsilon >0$. We study properties of measures on infinite sequences that maximize the metric entropy under the recoverability condition. Drawing on tools from ergodic theory, we prove some properties of entropy-maximizing measures. We also suggest a procedure of constructing an$\epsilon $-recoverable measure from a corresponding deterministic system.

Motivated by the established notion of storage codes, we consider sets of infinite sequences over a finite alphabet such that every$k$-tuple of consecutive entries is uniquely recoverable from its$l$-neighborhood in the sequence. In the first part of the paper we address the problem of finding the maximum growth rate of the set as well as constructions of explicit families (based on constrained coding) that approach the optimal rate. In the second part we consider a modification of the problem wherein the entries in the sequence are viewed as random variables over a finite alphabet, and the recovery condition requires that the Shannon entropy of the$k$-tuple conditioned on its$l$-neighborhood be bounded above by some$\epsilon > 0$. We study properties of measures on infinite sequences that maximize the metric entropy under the recoverability condition. Drawing on tools from ergodic theory, we prove some properties of entropy-maximizing measures. We also suggest a procedure of constructing an$\epsilon$-recoverable measure from a corresponding deterministic system, and prove that for small$\epsilon$the constructed measure is a maximizer of the metric entropy.

In this paper we consider the problem of encoding data into repeat-free sequences in which sequences are imposed to contain any k-tuple at most once (for predefined k). First, the capacity of the repeat-free constraint are calculated. Then, an efficient algorithm, which uses two bits of redundancy, is presented to encode length- n sequences for k=2+2log(n). This algorithm is then improved to support any value of k of the form k=alog(n), for 1 <; a, while its redundancy is o(n). We also calculate the capacity of repeat-free sequences when combined with local constraints which are given by a constrained system, and the capacity of multi-dimensional repeat-free codes.

Cassuto and Blaum recently studied the symbol-pair channel, a model where every two consecutive symbols are read together. This special channel structure is motivated by the limitations of the reading process in high density data storage systems, where it is no longer possible to read individual symbols. In this new paradigm, the errors are not individual symbol errors, but rather symbol-pair errors, where at least one of the symbols is erroneous. In this work, we study bounds and constructions of codes over the symbol-pair channel. We extend the Johnson bound and the linear programming bound for this channel and show that they improve upon existing bounds. We then propose new code constructions that improve upon existing results for pair-distance six, seven, and ten.

We introduce a dynamical model of node repair in distributed storage systems wherein the storage nodes are subjected to failures according to independent Poisson processes. The main parameter that we study is the time-average capacity of the network in the scenario where a fixed subset of the nodes support a higher repair bandwidth than the other nodes. The sequence of node failures generates random permutations of the nodes in the encoded block, and we model the state of the network as a Markov random walk on permutations of n elements. As our main result we show that the capacity of the network can be increased compared to the static (worst-case) model of the storage system, while maintaining the same (average) repair bandwidth, and we derive estimates of the increase. We also quantify the capacity increase in the case that the repair center has information about the sequence of the recently failed storage nodes.

In this paper we consider the problem of encoding data into repeat-free sequences in which sequences are imposed to contain any k-tuple at most once (for predefined k). First, the capacity and redundancy of the repeat-free constraint are calculated. Then, an efficient algorithm, which uses a single bit of redundancy, is presented to encode length-n sequences for k = 2 + 2 log n. This algorithm is then improved to support any value of k of the form k = a log n, for 1 <; a ≤ 2, while its redundancy is o(n). Lastly, we also calculate the capacity of this constraint when combined with local constraints which are given by a constrained system.

We propose a Coded selective-repeat ARQ protocol with cumulative feedback, by building on the uncoded baseline scheme for ARQ, developed by Ausavapattanakun and Nosratinia. Our method leverages discrete-time queuing and coding theory to analyze the performance of the proposed data transmission method. We incorporate forward error-correction (FEC) to reduce in-order delivery delay, and exploit a matrix signal-flow graph approach to analyze the throughput and delay. We demonstrate and contrast the performance of the Coded ARQ protocol with that of the uncoded ARQ scheme, with minimum coding, i.e., with a sliding window of size 2. Coded ARQ can provide gains up to about 40% in terms of throughput. It also provides delay guarantees, and is robust to various challenges such as imperfect and delayed feedback, burst erasures, and round-trip time fluctuations.

We study random string-duplication systems, which we call Pólya string models. These are motivated by a class of mutations that are common in most organisms and lead to an abundance of repeated sequences in their genomes. Unlike previous works that study the combinatorial capacity of string-duplication systems, or in a probabilistic setting, various string statistics, this work provides the exact entropy rate or bounds on it, for several probabilistic models. The entropy rate determines the compressibility of the resulting sequences, as well as quantifying the amount of sequence diversity that these mutations can create. In particular, we study the entropy rate of noisy string-duplication systems, including the tandem-duplication, end-duplication, and interspersed-duplication systems, where in all cases we study duplication of length 1 only. Interesting connections are drawn between some systems and the signature of random permutations, as well as to the beta distribution common in population genetics.

The main goal in group testing is to recover a small subset of defective items from a larger population while efficiently reducing the total number of (possibly noisy) required tests/measurements. Under the assumption that the input-output statistical relationship (i.e., channel law) is known to the recovery algorithm, the fundamental as well as the computational limits of the group testing problem are relatively better understood than when these statistical relationships are unknown. Practical considerations, however, render this assumption inapplicable, and “blind” recovery/estimation procedures, independent of the input-output statistics, are desired. In this paper, we analyze the fundamental limits of a general noisy group testing problem, when this relationship is unknown. Specifically, in the first part of this paper, we propose an efficient scheme, based on the idea of separate-decoding of items (where each item is recovered separately), for which we derive sufficient conditions on the number of tests required for exact recovery. The difficulty in obtaining these conditions stems from the fact that we allow the number of defective items to grow with the population size, which in turn requires delicate concentration analysis of certain probabilities. Furthermore, we show that in several scenarios, our proposed scheme achieves the same performance as that of the corresponding non-blind recovery algorithm (where the input-output statistics are known), implying that the proposed blind scheme is robust/universal. Finally, in the second part of this paper, we propose also an inefficient combinatorial-based scheme (or, “joint-decoding”), for which we derive similar sufficient conditions.

Cassuto and Blaum recently studied the symbol-pair channel, a model where every two consecutive symbols are read together. This special structure of channels is motivated by the limitations of the reading process in high density data storage systems, where it is no longer possible to read individual symbols. In this new paradigm, the errors are no longer individual symbol errors, but rathersymbol-pair errors, where at least one of the symbols is erroneous. In this work, we study bounds and construction of codes over the symbol-pair channels. We extend the Johnson bound and the linear programming bound for this channel and show that they improve upon existing bounds. We then propose new code constructions that improve upon existing results that use linear cyclic codes when the pair distance is between four and ten.

The main goal in group testing is to recover a small subset of defective items from a larger population, while efficiently reducing the total number of (possibly noisy) required tests/measurements. In this paper, we analyze the fundamental limits of a general noisy group testing problem when the channel law is unknown. Specifically, we obtain sufficient conditions on the number of tests required for exact recovery using two decoders; the first is based on joint-decoding (inefficient), and the second is a based on separate-decoding (efficient). We show that in several scenarios, our decoders achieve the same performance as if the channel was known, implying that the proposed decoders are robust/universal.

We find a new formula for the limit of the capacity of certain sequences of multidimensional semiconstrained systems as the dimension tends to infinity. We do so by generalizing the notion of independence entropy, originally studied in the context of constrained systems, to the study of semiconstrained systems. Using the independence entropy, we obtain new lower bounds on the capacity of multidimensional semiconstrained systems in general, and d-dimensional axial-product systems in particular. In the case of the latter, we prove our bound is asymptotically tight, giving the exact limiting capacity in terms of the independence entropy. We show the new bound improves upon the best-known bound in a case study of (0, k, p)-RLL.

We generalize the notion of independence entropy to the study of semiconstrained systems. Using it, we obtain a new lower bound on the capacity of multi-dimensional semiconstrained systems. We show the new bound improves upon the best-known bound in a case study of (0, k, p)-RLL semiconstrained systems.

We study random string-duplication systems, called Pólya string models, motivated by certain random mutation processes in the genome of living organisms. Unlike previous works that study the combinatorial capacity of string-duplication systems, or peripheral properties such as symbol frequency, this work provides exact capacity or bounds on it, for several probabilistic models. In particular, we give the exact capacity of the random tandem-duplication system, and the end-duplication system, and bound the capacity of the complement tandem-duplication system. Interesting connections are drawn between the former and the beta distribution common to population genetics, as well as between the latter system and signatures of random permutations.

Semiconstrained systems were recently suggested as a generalization of constrained systems, commonly used in communication and data-storage applications that require certain offending subsequences be avoided. In an attempt to apply techniques from constrained systems, we study sequences of constrained systems that are contained in, or contain, a given semiconstrained system, while approaching its capacity. In the case of contained systems we describe to such sequences resulting in constant-to-constant bit-rate block encoders and sliding-block encoders. Surprisingly, in the case of containing systems we show that a “generic” semiconstrained system is never contained in a proper fully-constrained system.

When transmitting information over a noisy channel, two approaches, dating back to Shannon's work, are common: assuming the channel errors are independent of the transmitted content and devising an error-correcting code or assuming the errors are data dependent and devising a constrained-coding scheme that eliminates all offending data patterns. In this paper, we analyze a middle road, which we call a semiconstrained system. In such a system, which is an extension of the channel with the cost constraints model, we do not eliminate the error-causing sequences entirely, but rather restrict the frequency in which they appear. We address several key issues in this paper. The first is proving closed-form bounds on the capacity, which allow us to bound the asymptotics of the capacity. In particular, we bound the rate at which the capacity of the semiconstrained (0,k) -RLL tends to 1 as k grows. The second key issue is devising efficient encoding and decoding procedures that asymptotically achieve capacity with vanishing error. Finally, we consider delicate issues involving the continuity of the capacity and a relaxation of the definition of semiconstrained systems.

When transmitting information over a noisy channel, two approaches are common: assuming the channel errors are independent of the transmitted content and devising an error-correcting code, or assuming the errors are data dependent and devising a constrained-coding scheme that eliminates all offending data patterns. In this paper we analyze a middle road, which we call a semiconstrained system. In such a model, which is an extension of the channel with cost constraints, we do not eliminate the error-causing sequences entirely, but rather restrict the frequency in which they appear. We address several key issues in this study. The first is proving closed-form bounds on the capacity which allow us to bound the asymptotics of the capacity. In particular, we bound the rate at which the capacity of the semiconstrained (0, k)-RLL tends to 1 as k grows. The second key issue is devising efficient encoding and decoding procedures that asymptotically achieve capacity with vanishing error. Finally, we consider delicate issues involving the continuity of the capacity and a relaxation of the definition of semiconstrained systems.

The Ising channel, which was introduced in 1990, is a channel with memory that models intersymbol interference. In this paper, we consider the Ising channel with feedback and find the capacity of the channel together with a capacity-achieving coding scheme. To calculate the channel capacity, an equivalent dynamic programming (DP) problem is formulated and solved. Using the DP solution, we establish that the feedback capacity is the expression C = (2Hb(a)/3+a) ≈ 0.575522, where (a) is a particular root of a fourth-degree polynomial and Hb(x) denotes the binary entropy function. Simultaneously, a = arg max0≤x≤1(2Hb(x)/3+x). Finally, an error-free, capacity-achieving coding scheme is provided together with the outlining of a strong connection between the DP results and the coding scheme.

In this paper we consider the Ising channel, which is a channel with memory. We formulate a dynamic program that characterizes the capacity of the Ising channel with feedback and solve it numerically using the value iteration algorithm. We then establish analytically that the feedback capacity is the expression C = (2H(a)/3+a) ≈ 0.575522 where a is a particular root of a fourth-degree polynomial and, simultaneously, is the value that maximizes (2H(z)/3+z) over 0 ≤ z ≤ 1, where H(z) is the binary entropy function.