We introduce the sum channel, a new channel model motivated by applications in distributed storage and DNA data storage. In the error-free case, it takes as input an $\ell$-row binary matrix and outputs an $(\ell+1)$-row matrix whose first $\ell$ rows equal the input and whose last row is their parity (sum) row. We construct a two-deletion-correcting code with redundancy $2\lceil\log_2\log_2 n\rceil + O(\ell^2)$ for $\ell$-row inputs. When $\ell=2$, we establish an upper bound of $\lceil\log_2\log_2 n\rceil + O(1)$, implying that our redundancy is optimal up to a factor of 2. We also present a code correcting a single substitution with $\lceil \log_2(\ell+1)\rceil$ redundant bits and prove that it is within one bit of optimality.

The Coupon Collector Problem (CCP) is a well-known combinatorial problem that seeks to estimate the number of random draws required to complete a collection of $n$ distinct coupon types. Various generalizations of this problem have been applied in numerous engineering domains. However, practical applications are often hindered by the computational challenges associated with deriving numerical results for moments and distributions. In this work, we present three algorithms for solving the most general form of the CCP, where coupons are collected under any arbitrary drawing probability, with the objective of obtaining $t$ copies of a subset of $k$ coupons from a total of $n$. The First algorithm provides the base model to compute the expectation, variance, and the second moment of the collection process. The second algorithm utilizes the construction of the base model and computes the same values in polynomial time with respect to $n$ under the uniform drawing distribution, and the third algorithm extends to any general drawing distribution. All algorithms leverage Markov models specifically designed to address computational challenges, ensuring exact computation of the expectation and variance of the collection process. Their implementation uses a dynamic programming approach that follows from the Markov models framework, and their time complexity is analyzed accordingly.

A $t$-all-symbol PIR code and a $t$-all-symbol batch code of dimension $k$ consist of $n$ servers storing linear combinations of $k$ information symbols with the following recovery property: any symbol stored by a server can be recovered from $t$ pairwise disjoint subsets of servers. In the batch setting, we further require that any multiset of size $t$ of stored symbols can be recovered from~$t$ disjoint subsets of servers. This framework unifies and extends several well-known code families, including one-step majority-logic decodable codes, (functional) PIR codes, and (functional) batch codes. In this paper, we determine the minimum code length for some small values of $k$ and $t$, characterize structural properties of codes attaining this optimum, and derive bounds that show the trade-offs between length, dimension, minimum distance, and $t$. In addition, we study MDS codes and the simplex code, demonstrating how these classical families fit within our framework, and establish new cases of an open conjecture from \cite{YAAKOBI2020} concerning the minimal $t$ for which the simplex code is a $t$-functional batch code.

We initiate the study of DNA-based distributed storage systems, where information is encoded across multiple DNA data storage containers to achieve robustness against container failures. In this setting, data are distributed over $M$ containers, and the objective is to guarantee that the contents of any failed container can be reliably reconstructed from the surviving ones. Unlike classical distributed storage systems, DNA data storage containers are fundamentally constrained by sequencing technology, since each read operation yields the content of a uniformly random sampled strand from the container. Within this framework, we consider several erasure-correcting codes and analyze the expected recovery time of the data stored in a failed container. Our results are obtained by analyzing generalized versions of the classical Coupon Collector's Problem, which may be of independent interest.

In large-scale array-based DNA synthesis, optical and chemical coupling between nearby sites can limit simultaneous activations. Motivated by this constraint, we study strands synthesized according to a fixed global synthesis sequence, with at most one strand per row advancing in each cycle. We focus on the fundamental case of two strands in a single row and analyze the expected completion time of row-constrained synthesis. We introduce the laggard-first (LF) policy, a simple rule that always advances the strand with fewer synthesized symbols when a conflict arises, and establish that it is asymptotically optimal among online policies without look-ahead. In the binary case, one-symbol look-ahead strictly improves on the no-look-ahead bound. We further show that even complete advance knowledge does not eliminate the scheduling loss, as even a globally optimal schedule incurs an unavoidable expected overhead that grows linearly with the strand length. Finally, we complement these scheduling results with a dynamic programming algorithm for computing an optimal offline synthesis order and a constant-redundancy binary coding scheme that yields a deterministic worst-case synthesis time guarantee.

The sequence reconstruction problem, introduced by Levenshtein in 2001, considers a communication setting in which a sender transmits a codeword and the receiver observes K independent noisy versions of this codeword. In this work, we study the problem of efficient reconstruction when each of the $K$ outputs is corrupted by a $q$-ary discrete memoryless symmetric (DMS) substitution channel with substitution probability $p$. Focusing on Reed-Solomon (RS) codes, we adapt the Koetter-Vardy soft-decision decoding algorithm to obtain an efficient reconstruction algorithm. For sufficiently large blocklength and alphabet size, we derive an explicit rate threshold, depending only on $(p, K)$, such that the transmitted codeword can be reconstructed with arbitrarily small probability of error whenever the code rate $R$ lies below this threshold.

Motivated by their applications in DNA-based storage systems, codes capable of correcting consecutive deletions have attracted significant attention. An important class of such codes consists of those that can correct multiple consecutive deletion errors, commonly referred to as multiple $b$-burst deletion-correcting codes. In this paper, we investigate the fundamental limits of multiple $b$-burst deletion-correcting codes. Specifically, we first characterize several structural properties of the associated deletion balls. Then, leveraging these properties, we derive several upper bounds and a combinatorial lower bound on the maximum size of such codes. As a consequence, our bounds improve upon the previously known results for general parameter regimes and are shown to be asymptotically optimal for certain cases.

As DNA data storage advances toward practical deployment, minimizing sequencing coverage depth is critical for reducing operational costs and retrieval latency. We study the random access problem of recovering a specific information strand from a DNA-based storage system. In this setting, $k$ information strands are encoded into $n$ strands using a generator matrix $G$, and each sequencing read returns one encoded strand sampled uniformly at random with replacement. We derive an exact formula for the expected number of samples required to recover a specific information strand, yielding an $O(n)$-time algorithm for fixed field size $q$ and dimension $k$. We further obtain explicit formulas for the average and maximum expected number of samples, enabling an efficient search for optimal generator matrices for small parameters. We present new constructions that improve the best-known upper bounds from $0.8815k$ to $0.8811k$ for $k=3$, and from $0.8637k$ to $0.8629k$ for $k=4$, for sufficiently large $q$. We also establish a tighter lower bound on the expected number of samples, which in particular proves the optimality of the simple parity code when $n=k+1$ over any field size $q$. Finally, for the non-random access setting, we derive new lower bounds and constructions that characterize the asymptotic behavior of the expected number of samples required to recover all information strands.

The performance of Reed–Solomon codes (RS codes, for short) in the presence of insertion and deletion errors has attracted growing attention in recent literature. In this work, we further study this intriguing mathematical problem, focusing on two regimes. First, we study the question of how wellfull-lengthRS codes perform against insertions and deletions. For 2-dimensional RS codes, we provide a complete characterization of codes that cannot correct even a single insertion or deletion. Furthermore, we prove that for sufficiently large field sizeq, nearly all full-length 2-dimensional RS codes can correct up to (1 - δ)qinsertion and deletion errors for any 0k≥ 2, there exists a full-lengthk-dimensional RS code capable of correctingq/(10k) insertion and deletion errors, providedqis large enough. Second, we focus on rate-1/2 RS codes that can correct a single insertion or deletion error. We present a polynomial-time algorithm that constructs such codes over fields of sizeq= Θ(k4). This result matches the existential bound given in [1].

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 work, we study linear error-correcting codes against adversarial insertion-deletion (indel) errors. While most constructions for the indel model are nonlinear, linear codes offer compact representations, efficient encoding, and decoding algorithms, making them highly desirable. A key challenge in this area is achieving rates close to the half-Singleton bound for efficient linear codes over finite fields. We improve upon previous results by constructing explicit codes over Fq2, linear over Fq, with rate 1/2 − δ − ε that can efficiently correct a δ-fraction of indel errors, whereq=O(ε−4). Additionally, we construct fully linear codes over Fqwith rate 1/2 − 2 √ δ − ε that can also efficiently correct δ-fraction of indels. These results significantly advance the study of linear codes for the indel model, bringing them closer to the theoretical half-Singleton bound. We also generalize the half-Singleton bound, for every codeC⊆ Fnlinear over E ⊂ F a subfield of F, such thatChas the ability to correct δ-fraction of indels, the rate is bounded by (1 − δ)/2.

DNA labelingis a tool in molecular biology and biotechnology to visualize, detect, and study DNA at the molecular level. In this process, a DNA molecule islabeledby a set of specific patterns, referred to aslabels, and is then imaged. The resulting image is modeled as an (ℓ + 1)-ary sequence, where ℓ is the number of labels, in which any non-zero symbol indicates the appearance of the corresponding label in the DNA molecule. Thelabeling capacityrefers to the maximum information rate that can be achieved by the labeling process for any given set of labels. The main goal of this paper is to study the minimum number of labels of the same length required to achieve the maximum labeling capacity of 2 for DNA sequences or log2qfor an arbitrary alphabet of sizeq. The solution to this problem requires the study of path unique subgraphs of the de Bruijn graph with the largest number of edges. We provide upper and lower bounds on this value. We draw new connections to existing literature that let us prove an asymptotic result as the label length tends to infinity.

Constrained coding is a subfield of coding theory that tackles efficient communication under constraints. While fixed constraints (e.g., a fixed set of substrings may not appear in transmitted messages) have a general optimal solution, there is increasing demand for supportingparametricconstraints that are dependent on the message length and portray some property (e.g., no log(n)consecutive zeros). Several works have tackled such parametric constraints throughiterativealgorithms, yet they require complex constructions specific to each constraint to guarantee convergence throughmonotonic progression. In this paper, we propose a universal framework for tacklinganyparametric constraint problem through a new simple iterative algorithm. By reducing an execution of this iterative algorithm to an acyclic graph traversal, we prove a surprising result that guarantees convergence with low average time complexityeven without requiring any monotonic progression. We demonstrate the effectiveness of this universal framework, with much of our focus on the special case of single-symbol redundancy, while also considering a variety of bothlocalandglobalconstraints. We begin by exploring the local constraints involving illegal substrings of variable length, where the construction essentially iteratively replaces forbidden windows. This local algorithm is applied to various fundamental constraints, achieving state-of-the-art results through simple adaptations of the universal algorithm. We then continue by exploring global constraints, and demonstrate the effectiveness of the proposed construction on repeat-free encoding, reverse-complement encoding and DNA data storage. Overall, the proposed framework generates state-of-the-art constructions with significant ease while also enabling the simultaneous integration of multiple constraints for the first time.

In thesequence reconstruction problem, a codewordxis transmitted through several identical channels where each channel produces a noisy read ofx, and the problem is to analyze how to uniquely reconstructxbased on these noisy reads. Levenshtein has studied the minimum number of reads which guarantees unique reconstruction ofx, which is one sufficient condition for unique reconstruction. In this paper, we move on to a different perspective and propose a new framework for unique reconstruction. Our new sufficient condition for unique reconstruction takes both the number of reads and the distances among the reads into consideration. We offer both theoretical analysis and corresponding efficient reconstruction algorithms for our reconstruction framework.

In this work, we consider the problem of efficient decoding of codes from insertions and deletions. Most of the known efficient codes are codes with synchronization strings which allow one to reduce the problem of decoding insertions and deletions to that of decoding substitution and erasures. Our new approach, presented in this paper, reduces the problem of decoding insertions and deletions to that of list recovery. Specifically, any ($\rho, 2 \rho n+1, L$) -list-recoverable code is a ($\rho, L$) -list decodable insdel code. As an example, we apply this technique to Reed-Solomon (RS) codes, which are known to have efficient listrecovery algorithms up to the Johnson bound. In the adversarial insdel model, this provides efficient (list) decoding from$t$insdel errors, assuming that$t \cdot k=O(n)$. This is the first efficient insdel decoder for$[n, k]$RS codes for$k>2$. Additionally, we explore random insdel models, such as the Davey-MacKay channel, and show that for certain choices of$\rho$, a$\left(\rho, n^{1 / 2+0.001}, L\right)$-listrecoverable code of length$n$can, with high probability, efficiently list decode the channel output, ensuring that the transmitted codeword is in the output list. In the context of RS codes, this leads to a better rate-error tradeoff for these channels compared to the adversarial case. We also adapt the KoetterVardy algorithm, a famous soft-decision list decoding technique for RS codes, to correct insertions and deletions induced by the Davey-MacKay channel.

Despite their significant advantages over competing technologies, nanopore sequencers are plagued by high error rates, due to physical characteristics of the nanopore and inherent noise in the biological processes. It is thus paramount not only to formulate efficient error-correcting constructions for these channels, but also to establish bounds on the minimum redundancy required by such coding schemes. In this context, we adopt a simplified model of nanopore sequencing inspired by the work of Mao et al., accounting for the effects of intersymbol interference and measurement noise. For an input sequence of length$n$, The vector that is produced, designated as the read vector, may additionally suffer at most$t$substitution errors. We employ the well-known graph-theoretic clique-cover technique to establish that at least$t \log n-O(1)$bits of redundancy are required to correct multiple ($t \geqslant 2$) substitutions. While this is surprising in comparison to the case of a single substitution, that necessitates at most$\log \log n-O(1)$bits of redundancy, a suitable error-correcting code that is optimal up to a constant follows immediately from the properties of read vectors.

This paper studies the sequence reconstruction problem for a channel inspired by protein identification. We introduce a coloring channel, where a sequence is transmitted through a channel that deletes all symbols not belonging to a fixed subset (the coloring) of the alphabet. By extending this to a coloring profile, a tuple of distinct colorings, we analyze the channel's information rate and capacity. We prove that optimal (i.e., achieving maximum information rate) coloring profiles correspond to 2 -covering designs and identify the minimal covering number required for maximum information rate, as well as the minimum number for which any coloring profile is optimal.

The coverage depth problem in DNA data storage is about minimizing the expected number of reads until all data is recovered. When they exist, MDS codes offer the best performance in this context. This paper focuses on the scenario where the base field is not large enough to allow the existence of MDS codes. We investigate the performance for the coverage depth problem of codes defined over a small finite field, providing closed formulas for the expected number of reads for various code families. We also compare the results with the theoretical bounds in asymptotic regimes. The techniques we apply range from probability, to duality theory and combinatorics.

Phased Burst Errors (PBEs) are bursts of errors occurring at one or more known locations. The correction of PBEs is a classical topic in coding theory, with prominent applications such as the design of array codes for memory systems or distributed storage. We propose a general yet finegrained approach to this problem, accounting not only for the number of bursts but also the error structure in each burst. By modeling PBEs as an error set in an adversarial channel, we investigate bounds on the maximal size of codes that can correct them. The PBE-correction capability of generalized concatenated codes is analyzed, and asymptotically good PBE-correcting codes are constructed, recovering a classical construction in a specific problem instance.

Burst errors, which involve the corruption of consecutive symbols, are a more realistic and common type of error in many communication and storage systems. While classical codes for burst correction are well-established, quantum errorcorrecting codes that handle burst errors and error localization have been less explored. In this paper, we present constructions of quantum codes designed to locate and correct burst errors. We introduce a nearly optimal quantum error-locating burst code, which can identify an interval of$2 b$qubits containing a burst of quantum errors of length at most$b$, improving upon previous constructions in terms of redundancy. This code leverages a stabilizer framework that is not based on the CSS (Calderbank-Shor-Steane) construction, offering a more efficient error-locating capability. Additionally, our construction can correct a large structured set of burst errors, specifically those of length$b$that do not end with a$Y$Pauli operator. We prove that the redundancy of this code is optimal with respect to this error set.

In this work, we study linear error-correcting codes against adversarial insertion-deletion (indel) errors. While most constructions for the indel model are nonlinear, linear codes offer compact representations, efficient encoding, and decoding algorithms, making them highly desirable. A key challenge in this area is achieving rates close to the half-Singleton bound for efficient linear codes over finite fields. We improve upon previous results by constructing explicit codes over$\mathbb{F}_{q^{2}}$, linear over$\mathbb{F}_{q}$, with rate$1 / 2-\delta-\varepsilon$that can efficiently correct a$\delta$-fraction of indel errors, where$q=O\left(\varepsilon^{-4}\right)$. Additionally, we construct fully linear codes over$\mathbb{F}_{q}$with rate$1 / 2-2 \sqrt{\delta}-\varepsilon$that can also efficiently correct$\delta$-fraction of indels. These results significantly advance the study of linear codes for the indel model, bringing them closer to the theoretical half-Singleton bound.

Labeling of DNA molecules is a fundamental technique for DNA visualization and analysis. This process was mathematically modeled in [1], where the received sequence indicates the positions of the used labels. In this work, we develop error correcting codes for labeled DNA sequences, establishing bounds and constructing explicit systematic encoders for single substitution, insertion, and deletion errors. We focus on two cases: (1) using the complete set of length-two labels and (2) using the minimal set of length-two labels that ensures the recovery of DNA sequences from their labeling for 'almost' all DNA sequences.

We address the challenge of optimizing the capacity-achieving input distribution for a multinomial channel under the constraint of limited input support size, which is a crucial aspect in the design of DNA storage systems. We propose an algorithm that further elaborates the Multidimensional Dynamic Assignment Blahut-Arimoto (M-DAB) algorithm [1]. Our proposed algorithm integrates variational autoencoder for determining the optimal locations of input distribution, into the alternating optimization of the input distribution locations and weights.

DNA-based storage systems face a primary bottleneck in their parallel strand synthesis processes, affecting both economic viability and operational efficiency. Current methodologies predominantly employ either enzymatic DNA synthesis, permitting the addition of any nucleotide to individual strands per cycle, or photolithographic synthesis, facilitating the selective addition of a single nucleotide across multiple strands simultaneously. This research studies a theoretical hybrid framework combining both approaches, enabling the selection of a fixed number of nucleotides within each synthesis cycle. We introduce the term complex synthesis sequence to describe the nucleotide addition pattern and extend the concepts of subsequence and supersequence to enable standard sequences to be subsequences of complex synthesis sequences. We extend Lenz et al.'s definition of information rate and use an analog of the deletion ball to derive expressions for the maximal information rate obtainable in this model. We develop an algorithm to determine the optimal synthesis sequence in this model for known strands, show that the solution is analogous to finding an SCS, and derive the required dynamic programming algorithm to solve it.

BACKGROUND: DNA data storage is an emerging technology that caught the attention of many researchers and engineers. This technology uses DNA molecules as a storage medium and thus presents an extremely dense and durable storage device. However, the unique nature of the errors in DNA, which include insertion, deletion, and substitution errors, requires the development of new algorithmic and coding solutions for these storage systems. RESULTS: The DNA-Storalator is a cross-platform software tool that simulates in a simplified digital point of view biological and computational processes involved in the process of storing data in DNA molecules. The simulator receives an input file with the designed DNA strands that store digital data and emulates the different biological and algorithmical components of DNA-based storage system. The biological component includes simulation of the synthesis, PCR, and sequencing stages which are expensive and complicated and therefore are not widely accessible to the community. These processes amplify the data and generate noisy copies of each DNA strand, where the errors are insertions, deletions, long-deletions, and substitutions. The DNA-Storalator injects errors to the data based on the error rates, as they vary between different synthesis and sequencing technologies. The rates are based on comprehensive analysis of data from previous experiments but can also be customized. Additionally, the tool can analyze new datasets and characterize their error rates to build new error models for future usage in the simulator. The DNA-Storalator also enables control of the amplification process and the distribution of the number of copies per designed strand. The coding and algorithmic components are: 1. Clustering algorithms which partition all output noisy strands into groups according to the designed strand they originated from; 2. State-of-the-art reconstruction algorithms that are invoked on each cluster to output a close/exact estimation of the designed strand; 3. Integration with external error-correcting codes and other encoding and decoding techniques. CONCLUSIONS: The suggested computational DNA storage simulator grants researchers from all fields an accessible complete simulator to examine new biological technologies, coding techniques, and algorithms for current and future DNA storage systems.

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 ) .

We investigate the problems of privately repairing erasures and evaluating their linear combinations for Reed-Solomon codes with low communication bandwidths. We propose two approaches: one based on hiding subspaces used to form parity-check equations, and another based on multiplying parity-check equations with random polynomials. We also derive a lower bound on the repair bandwidth for the single erasure case under reasonable assumptions about the schemes being used and demonstrate the optimality of the proposed schemes for codes of specific lengths.

Although the expenses associated with DNA sequencing have been rapidly decreasing, the current cost of sequencing information stands at roughly${\$}120$/GB, which is dramatically more expensive than reading from existing archival storage solutions today. In this work, we aim to reduce not only the cost but also the latency of DNA storage by initiating the study of the DNA coverage depth problem, which aims to reduce the required number of reads to retrieve information from the storage system. Under this framework, our main goal is to understand the effect of error-correcting codes and retrieval algorithms on the required sequencing coverage depth. We establish that the expected number of reads that are required for information retrieval is minimized when the channel follows a uniform distribution. We also derive upper and lower bounds on the probability distribution of this number of required reads and provide a comprehensive upper and lower bound on its expected value. We further prove that for a noiseless channel and uniform distribution, MDS codes are optimal in terms of minimizing the expected number of reads. Additionally, we study the DNA coverage depth problem under the random-access setup, in which the user aims to retrieve just a specific information unit from the entire DNA storage system. We prove that the expected retrieval time is at least k for$[n,k]$MDS codes as well as for other families of codes. Furthermore, we present explicit code constructions that achieve expected retrieval times below k and evaluate their performance through analytical methods and simulations. Lastly, we provide lower bounds on the maximum expected retrieval time. Our findings offer valuable insights for reducing the cost and latency of DNA storage.

This paper introduces a new solution to DNA storage that integrates all three steps of retrieval, namely clustering, reconstruction, and error correction.DNA-correcting codesare presented as a unique solution to the problem of ensuring that the output of the storage system is unique for any valid set of input strands. To this end, we introduce a novel distance metric to capture the unique behavior of the DNA storage system and provide necessary and sufficient conditions for DNA-correcting codes. We also establish bounds and constructions for these codes, including an exploration of the ℓ∞distance applied to permutations. Here, instead of interpreting permutation elements as numerical values and assessing absolute differences, we treat them as vectors and consider the Hamming distance to better model the DNA Storage System.

Temperature control is of utmost importance in transmission systems. In this paper, a binary channel model is considered in which the transmission of a one causes a temperature increase while communicating a zero causes a temperature drop. By putting constraints on the input sequences, it is guaranteed that the channel temperature will not exceed a certain pre-determined maximum. In the asymptotic regime, the capacity of such a channel is studied. For the non-asymptotic regime, fixed-length codes are presented, with the property that codewords can be freely cascaded without violating the temperature constraint. Optimization of the code size is investigated and codewords are enumerated using generating functions.

Robust Gray codes were introduced by (Lolck and Pagh, SODA 2024). Informally, a robust Gray code is a (binary) Gray code$\mathcal {G}$so that, given a noisy version of the encoding$\mathcal {G}(j)$of an integer j, one can recover$\hat {j}$that is close to j (with high probability over the noise). Such codes have found applications in differential privacy. In this work, we present near-optimal constructions of robust Gray codes. In more detail, we construct a Gray code$\mathcal {G}$of rate$1 - H_{2}(p) - \varepsilon $that is efficiently encodable, and that is robust in the following sense. Supposed that$\mathcal {G}(j)$is passed through the binary symmetric channel${\text {BSC}}_{p}$with cross-over probability p, to obtain x. We present an efficient decoding algorithm that, given x, returns an estimate$\hat {j}$so that$| j - \hat {j}|$is small with high probability.

In this work we consider a generalization of the well-studied problem of coding for “stuck-at” errors, which we refer to as “strong stuck-at” codes. In the traditional framework of stuck-at codes, the task involves encoding a message into a one-dimensional binary vector. However, a certain number of the bits in this vector are ‘frozen’, meaning they are fixed at a predetermined value and cannot be altered by the encoder. The decoder, aware of the proportion of frozen bits but not their specific positions, is responsible for deciphering the intended message. We consider a more challenging version of this problem where the decoder does not know also the fraction of frozen bits. We construct explicit and efficient encoding and decoding algorithms that get arbitrarily close to capacity in this scenario. Furthermore, to the best of our knowledge, our construction is the first, fully explicit construction of stuck-at codes that approach capacity.

We investigate the fundamental limits of the recently proposedrandom access coverage depth problemfor DNA data storage. Under this paradigm, it is assumed that the user information consists ofkinformation strands, which are encoded intonstrands via a generator matrixG. During the sequencing process, the strands are read uniformly at random, as each strand is available in a large number of copies. In this context, the random access coverage depth problem refers to the expected number of reads (i.e., sequenced strands) required to decode a specific information strand requested by the user. This problem heavily depends on the generator matrixG, and besides computing the expectation for different choices ofG, the goal is to construct matrices that minimize the maximum expectation over all possible requested information strands, denoted byTmax(G). In this paper, we introduce new techniques to investigate the random access coverage depth problem, capturing its combinatorial nature and identifying the structural properties of generator matrices that are advantageous. We establish two general formulas to determineTmax(G) for arbitrary generator matrices. The first formula depends on the linear dependencies between columns ofG, whereas the second formula takes into account recovery sets and their intersection structure. We also introduce the concept ofrecovery balanced codesand provide three sufficient conditions for a code to be recovery balanced. These conditions can be used to computeTmax(G) for various families of codes, such as MDS, simplex, Hamming, and binary Reed-Muller codes. Additionally, we study the performance of modified systematic MDS and simplex matrices, showing that the best results forTmax(G) are achieved with a specific combination of encoded strands and replication of the information strands.

DNA labelingis a powerful tool in molecular biology and biotechnology that allows for the visualization, detection, and study of DNA at the molecular level. Under this paradigm, a DNA molecule is beinglabeledby specifickpatterns and is then imaged. Then, the resulting image is modeled as a$(k+1)$-ary sequence in which any non-zero symbol indicates on the appearance of the corresponding label in the DNA molecule. The primary goal of this work is to study thelabeling capacity, which is defined as the maximal information rate that can be obtained using this labeling process. The labeling capacity is computed for almost any pattern of a single label and several results for multiple labels are provided as well. Moreover, we provide the optimal minimal number of labels of length one or two, over any alphabet of sizeq, that are needed in order to achieve the maximum labeling capacity of$\log _{2}(q)$. Lastly, we discuss the maximal labeling capacity that can be achieved using a certain number of labels of length two.

We consider gradient coding in the presence of an adversary controlling so-called malicious workers trying to corrupt the computations. Previous works propose the use of MDS codes to treat the responses from malicious workers as errors and correct them using the error-correction properties of the code. This comes at the expense of increasing the replication, i.e., the number of workerseach partial gradientis computed by. In this work, we propose a way to reduce the replication to$ {s} +1$instead of$2 {s} +1$in the presence ofsmalicious workers. Our method detects erroneous inputs from the malicious workers, transforming them into erasures. This comes at the expense ofsadditional local computations at the main node and additional rounds of light communication between the main node and the workers. We define a general framework and give fundamental limits for fractional repetition data allocations. Our scheme is optimal in terms of replication and local computation and incurs a communication cost that is asymptotically, in the size of the dataset, a multiplicative factor away from the derived bound. We furthermore show how additional redundancy can be exploited to reduce the number of local computations and communication cost, or, alternatively, tolerate straggling workers.

The channel output entropy of a transmitted sequence is the entropy of the possible channel outputs, and similarly, the channel input entropy of a received sequence is the entropy of all possible transmitted sequences. The goal of this work is to study these entropy values for thek-deletion andk-insertion channels, where exactlyksymbols are deleted or inserted in the transmitted sequence, respectively. If all possible sequences are transmitted with the same probability, then studying the input and output entropies becomes equivalent. For both the 1-deletion and 1-insertion channels, it is shown that among all sequences with a fixed number of runs, the input entropy is minimized for sequences with a skewed distribution of run lengths, and it is maximized for sequences with a balanced distribution of run lengths. Among our results, we establish a conjecture by Atashpendar et al., which claims that for the 1-deletion channel, the input entropy is maximized by the alternating sequences among all binary sequences. This conjecture is also verified for the 2-deletion channel, where it is proved that sequences with a single run minimize the input entropy.

In conventional DNA synthesis machines, usually many strands are synthesized in parallel by iterating through a supersequence$\boldsymbol {s}$and adding in each cycle the next nucleotide to a programmable subset of the strands. The length of$\boldsymbol {s}$determines the number of the cycles, hence the time and the cost of the synthesis process. Recently, in order to reduce the number of synthesis cycles, researchers have suggested to append in each cycle a shortmer, i.e., a sequence of nucleotides, instead of a single one. The present work studies this synthesis technique from a theoretical point of view. In particular, it discusses which shortmers are the best to use (in order to reduce the number of cycles), and how to calculate the number of cycles required to synthesize in parallel a set of strands using a given set of shormers. Lastly, and following a previously described connection between the DNA synthesis problem and costly constrained graphs, this paper investigates calculating the capacity of non-deterministic costly constrained graphs.

DNA emerges as a promising medium for the exponential growth of digital data due to its density and durability. This study extends recent research by addressing the coverage depth problem in practical scenarios, exploring optimal error-correcting code pairings with DNA storage systems to minimize coverage depth. Conducted within random access settings, the study provides theoretical analyses and experimental simulations to examine the expectation and probability distribution of samples needed for files recovery. Structured into sections covering definitions, analyses, lower bounds, and comparative evaluations of coding schemes, the paper unveils insights into effective coding schemes for optimizing DNA storage systems.

Owing to its several merits over other DNA sequencing technologies, nanopore sequencers hold an immense potential to revolutionize the efficiency of DNA storage systems. However, their higher error rates necessitate further research to devise practical and efficient coding schemes that would allow accurate retrieval of the data stored. Our work takes a step in this direction by adopting a simplified model of the nanopore sequencer inspired by Mao et al., which incorporates some of its physical aspects. This channel model can be viewed as a sliding window of length ℓ that passes over the incoming input sequence and produces the Hamming weight of the enclosed ℓ bits, while shifting by one position at each time step. The resulting (ℓ + 1)-ary vector, referred to as the ℓ-read vector, is susceptible to deletion errors due to imperfections inherent in the sequencing process. We establish that at least log$n$- ℓ bits of redundancy are needed to correct a single deletion. An error-correcting code that is optimal up to an additive constant, is also proposed. Furthermore, we find that for ℓ ≥ 2, reconstruction from two distinct noisy ℓ-read vectors can be accomplished without any redundancy, and provide a suitable reconstruction algorithm to this effect.

Enzymatic DNA labeling is a powerful tool with applications in biochemistry, molecular biology, biotechnology, medical science, and genomic research. This paper contributes to the evolving field of DNA-based data storage by presenting a formal framework for modeling DNA labeling in strings, specifically tailored for data storage purposes. Our approach involves a known DNA molecule as a template for labeling, employing patterns induced by a set of designed labels to represent information. One hypothetical implementation can use CRISPR-Cas9 and gRNA reagents for labeling. Various aspects of the general labeling channel, including fixed-length labels, are explored, and upper bounds on the maximal size of the corresponding codes are given. The study includes the development of an efficient encoder-decoder pair that is proven optimal in terms of maximum code size under specific conditions.

Motivated by distributed algorithms for fuzzy joins, the concept of pair-covering${}^{\prime\prime}$codes is defined. This definition is a generalization of the well-known concept of covering codes. Basic properties and bounds for the pair-covering codes with comparison to the associated properties and bounds for covering codes, are provided. In particular, the sphere covering bound and normal codes are generalized.

The thermal-aware channel has been studied recently to control the temperature of some electronic devices for better performance and longer lifetime. In this work, we consider a thermal-aware channel model where multiple wires are available to the user. The user can use one wire or several wires to write an information word. Particularly, we study the two extreme cases. In the first case, only one wire is permitted for writing the information. The other extreme case is that we are allowed to write information on all the wires in parallel. In the first case, when we send a message through a wire that reaches the highest allowed temperature, we switch to another available wire. We determine the minimum number of wires required to send any arbitrary message. Given the number of wires, our second task is to determine the constrained codewords that can be sent through these wires. We compute the maximum information rate achieved and provide some constructions of codes satisfying these constraints. In the second case when all the wires are available for writing many, interesting questions arise and we briefly describe one of them and its solutions.

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.

This paper studies two problems that are motivated by the novel recent approach of composite DNA that takes advantage of the DNA synthesis property which generates a huge number of copies for every synthesized strand. Under this paradigm, every composite symbols does not store a single nucleotide but a mixture of the four DNA nucleotides. In the first problem, our goal is study how to carefully choose a fixed number of mixtures of the DNA nucleotides such that the decoding probability by the maximum likelihood decoder is maximized. The second problem studies the expected number of strand reads in order to decode a composite strand or a group of composite strands.

In this work we consider a generalization of the well-studied problem of coding for “stuck-at” errors, which we refer to as “strong stuck-at” codes. In the traditional framework of stuck-at codes, the task involves encoding a message into a one-dimensional binary vector. However, a certain number of the bits in this vector are ‘frozen’, meaning they are fixed at a predetermined value and cannot be altered by the encoder. The decoder, aware of the proportion of frozen bits but not their specific positions, is responsible for deciphering the intended message. We consider a more challenging version of this problem where the decoder does not even know the fraction of frozen bits. We construct explicit and efficient encoding and decoding algorithms that get arbitrarily close to capacity in this scenario. Furthermore, to the best of our knowledge, our construction is the first fully explicit construction of stuck-at codes that approaches capacity. The full version of this paper is given in [1].

We investigate the fundamental limits of the recently proposed random access coverage depth problem for DNA data storage. Under this paradigm, it is assumed that the user information consists of$k$information strands, which are encoded into$n$strands via some generator matrix$G$. In the sequencing process, the strands are read uniformly at random, since each strand is available in a large number of copies. In this context, the random access coverage depth problem refers to the expected number of reads (i.e., sequenced strands) until it is possible to decode a specific information strand, which is requested by the user. The goal is to minimize the maximum expectation over all possible requested information strands, and this value is denoted by$T_{\max}(G)$. This paper introduces new techniques to investigate the random access coverage depth problem, which capture its combinatorial nature. We establish two general formulas to find$T_{\max}(G)$for arbitrary matrices. We introduce the concept of recovery balanced codes and combine all these results and notions to compute$T_{\max}(G)$for MDS, simplex, and Hamming codes. We also study the performance of modified systematic MDS matrices and our results show that the best results for$T_{\max}(G)$are achieved with a specific mix of encoded strands and replication of the information strands.

DNA labeling is a tool in molecular biology and biotechnology to visualize, detect, and study DNA at the molec-ular level. In this process, a DNA molecule is labeled by a set of specific patterns, referred to as labels, and is then imaged. The resulting image is modeled as an$(\ell+1)$-ary sequence, where$\ell$is the number of labels, in which any nonzero symbol indicates the appearance of the corresponding label in the DNA molecule. The labeling capacity refers to the maximum information rate that can be achieved by the labeling process for any given set of labels. The main goal of this paper is to study the minimum number of labels of the same length required to achieve the maximum labeling capacity of 2 for DNA sequences or$\log_{2}q$for an arbitrary alphabet of size$q$. The solution to this problem requires the study of path unique subgraphs of the de Bruijn graph with the largest number of edges. We provide upper and lower bounds on this value.

We tackle the problem of Byzantine errors in dis-tributed gradient descent within the Byzantine-resilient gradient coding framework. Our proposed solution can recover the exact full gradient in the presence of$s$malicious workers with a data replication factor of only$s$+ 1. It generalizes previous solutions to any data assignment scheme that has a regular replication over all data samples. The scheme detects malicious workers through additional interactive communication and a small number of local computations at the main node, leveraging group-wise comparisons between workers with a provably optimal grouping strategy. The scheme requires at most$s$interactive rounds that incur a total communication cost logarithmic in the number of data samples.

Constrained coding is a fundamental field in coding theory that tackles efficient communication through constrained channels. While fixed constraints (e.g., a fixed set of substrings may not appear in transmitted messages) have a general optimal solution, there is increasing demand for supporting parametric constraints that are dependent on the message length and portray some property that the substrings must satisfy (e.g., no log (n) consecutive zeros). Several works have tackled such parametric constraints through iterative algorithms following the sequence-replacement approach, yet this approach requires complex constraint-specific properties to guarantee convergence through monotonic progression. In this paper, we propose a universal framework for tackling any parametric constraint problem with far fewer requirements, through a simple iterative algorithm. By reducing an execution of this iterative algorithm to an acyclic graph traversal, we prove a surprising result that guarantees convergence with efficient average time complexity even without requiring any monotonic progression. We demonstrate how to apply this algorithm to the run-length-limited, minimal Hamming weight, local almost-balanced Hamming weight constraints, as well as repeat-free and secondary-structure constraints. Overall, this framework enables state-of-the-art results with minimal effort.

We investigate the problem of privately recovering a single erasure for Reed-Solomon codes with low communication bandwidths. For an$[n,k]_{\mathbb{F}_{q^{\ell}}}$code with$n-k\geq q^{m}+t-1$, we construct a repair scheme that allows a client to recover an arbitrary codeword symbol without leaking its index to any set of$t$colluding helper nodes at a repair bandwidth of$(n-1)(\ell-m)$sub-symbols in$\mathbb{F}_{q}$. When$t=1$, this reduces to the bandwidth of existing repair schemes based on subspace polynomials. We prove the optimality of the proposed scheme when$n=q^{\ell}$under a reasonable assumption about the schemes being used. Our private repair scheme can also be transformed into a private retrieval scheme for data encoded by Reed-Solomon codes.

Data storage in DNA is developing as a possible solution for archival digital data. Recently, to further increase the potential capacity of DNA-based data storage systems, the combinatorial composite DNA synthesis method was suggested. This approach extends the DNA alphabet by harnessing short DNA fragment reagents, known as shortmers. The shortmers are building blocks of the alphabet symbols, each consisting of a fixed number of shortmers. Thus, when information is read, it is possible that one of the shortmers that forms part of the composition of a symbol is missing and therefore the symbol cannot be determined. In this paper, we model this type of error as a type of asymmetric error and propose code constructions that can correct such errors in this setup. We also provide a lower bound on the redundancy of such error-correcting codes and give an explicit encoder and decoder for our construction. Our suggested error model is also supported by an analysis of data from actual experiments that produced DNA according to the combinatorial scheme. Lastly, we also provide a statistical evaluation of the probability of observing such error events, as a function of read depth.

The sequence reconstruction problem, introduced by Levenshtein in 2001, considers a scenario where the sender transmits a codeword from some codebook, and the receiver obtains$N$noisy outputs of the codeword. We study the problem of efficient reconstruction using$N$outputs that are corrupted by substitutions. Specifically, for the ubiquitous Reed-Solomon codes, we adapt the Koetter-Vardy soft-decoding algorithm, presenting a reconstruction algorithm capable of correcting beyond Johnson radius. Furthermore, the algorithm uses$\mathrm{O}(nN)$field operations, where$n$is the codeword length.

Composite DNA is a recent method to increase the base alphabet size in DNA-based data storage. This paper models synthesizing and sequencing of composite DNA and introduces coding techniques to correct substitutions, losses of entire strands, and symbol deletion errors. Non-asymptotic upper bounds on the size of codes with$t$occurrences of these error types are derived. Explicit constructions are presented which can achieve the bounds.

One of the primary sequencing methods gaining prominence in DNA storage is nanopore sequencing, attributed to various factors. In this work, we consider a simplified model of the sequencer, characterized as a channel. This channel takes a sequence and processes it using a sliding window of length$\ell$, shifting the window by$\delta$characters each time. The output of this channel, which we refer to as the read vector, is a vector containing the sums of the entries in each of the windows. The capacity of the channel is defined as the maximal information rate of the channel. Previous works have already revealed capacity values for certain parameters$\ell$and$\delta$. In this work, we show that when$\delta < \ell < 2\delta$, the capacity value is given by$\frac{1}{\delta}\log_{2}\frac{1}{2}(\ell+1+ \sqrt{(\ell+1)^{2}-4(\ell-\delta)(\ell-\delta+1)})$. Additionally, we construct an upper bound when$2\delta < \ell$. Finally, we extend the model to the two-dimensional case and present several results on its capacity.

Motivated by DNA based data storage system, we investigate errors that occur when synthesizing DNA strands in parallel, where each strand is appended one nucleotide at a time by the machine according to a template supersequence. If there is a cycle such that the machine fails, then the strands meant to be appended at this cycle will not be appended, and we refer to this as a synthesis defect. In this paper, we present two families of codes correcting these synthesis defects, which are t-known-synthesis-defect correcting codes and t-synthesis-defect correcting codes. For the first one, it is assumed that the defective cycles are known, and each of the codeword is a quaternary sequence. We provide constructions for this family of codes for$t=1,2$, with redundancy log 4 and$2\log n+O(1)$, respectively. For the second one, the codeword is a set of$M$ordered sequences, and we give a construction for$t=1$to show a strategy for constructing this family of codes. Finally, we derive a lower bound on the redundancy for single-known-synthesis-defect correcting codes, which assures that our construction is almost optimal.

We study a model in which a codeword$x$is transmitted through several identical channels, where each channel produces a noisy read of$x$. The sequence reconstruction problem, proposed by Levenshtein, asks for how to uniquely re-construct$x$based on these noisy reads. Most of previous works focused on the minimum number of reads which guarantees unique reconstruction of$x$in the worst case. In this paper, we move on to a new perspective on the sequence reconstruction problem, and propose a different sufficient condition for unique reconstruction which takes both the number of reads and the distances among the reads into consideration. We offer both theoretical analysis and corresponding efficient reconstruction algorithms.

Storing data in DNA is being explored as an efficient solution for archiving and in-object storage. Synthesis time and cost remain challenging, significantly limiting some applications at this stage. In this paper we investigate efficient synthesis, as it relates to cyclic synchronized synthesis technologies, such as photolithography. We define performance metrics related to the number of cycles needed for the synthesis of any fixed number of bits. We first expand on some results from the literature related to the channel capacity, addressing densities beyond those covered by prior work. This leads us to develop effective encoding achieving rate and capacity that are higher than previously reported. Finally, we analyze cost based on a parametric definition and determine some bounds and asymptotics. We investigate alphabet sizes that can be larger than 4, both for theoretical completeness and since practical approaches to such schemes were recently suggested and tested in the literature.

MOTIVATION: As data storage challenges grow and existing technologies approach their limits, synthetic DNA emerges as a promising storage solution due to its remarkable density and durability advantages. While cost remains a concern, emerging sequencing and synthetic technologies aim to mitigate it, yet introduce challenges such as errors in the storage and retrieval process. One crucial task in a DNA storage system is clustering numerous DNA reads into groups that represent the original input strands. RESULTS: In this paper, we review different methods for evaluating clustering algorithms and introduce a novel clustering algorithm for DNA storage systems, named Gradual Hash-based clustering (GradHC). The primary strength of GradHC lies in its capability to cluster with excellent accuracy various types of designs, including varying strand lengths, cluster sizes (including extremely small clusters), and different error ranges. Benchmark analysis demonstrates that GradHC is significantly more stable and robust than other clustering algorithms previously proposed for DNA storage, while also producing highly reliable clustering results. AVAILABILITY AND IMPLEMENTATION: https://github.com/bensdvir/GradHC.

Using synthetic DNA for data storage and for physical information encoding in labeling, tracing, and authentication applications is becoming more feasible as synthesis and reading technologies are improving. DNA in data storage applications has several advantages such as very high physical density and robustness. Some of the new synthesis technologies lead to repetition noise, consisting of sticky insertions and deletions in the resulting messages. In this paper, we address reconstruction algorithms for multiple trace communication channels with repetition (sticky insertion and deletion) noise. We prove correctness and analyze failure rates, both analytically and on simulated data. We identify a failure mechanism related to alternating stretches in the design sequence that leads to a potential bias in the data derived from reads (traces) and used for reconstruction. To minimize this effect we introduce alternating length limited codes (ALL codes) and analyze some of their properties.

Nanopore sequencing, superior to other sequencing technologies for DNA storage in multiple aspects, has recently attracted considerable attention. Its high error rates, however, demand thorough research on practical and efficient coding schemes to enable accurate recovery of stored data. To this end, we consider a simplified model of a nanopore sequencer inspired by Maoet al., incorporating intersymbol interference and measurement noise. Essentially, our channel model passes a sliding window of lengthlover aq-ary input sequence that outputs thecompositionof the enclosedlbits, and shifts by δ positions with each time step. In this context, the composition of aq-ary vectorxspecifies the number of occurrences inxof each symbol in {0,1,...,q- 1}. The resulting compositions vector, termed theread vector, may also be corrupted bytsubstitution errors. By employing graph-theoretic techniques, we deduce that for δ = 1, at least log lognsymbols of redundancy are required to correct a single (t= 1) substitution. Finally, forl≥ 3, we exploit some inherent characteristics of read vectors to arrive at an error-correcting code that is of optimal redundancy up to a (small) additive constant for this setting. This construction is also found to be optimal for the case of reconstruction from two noisy read vectors.

The increasing demand for data storage has prompted the exploration of new techniques, with molecular data storage being a promising alternative. In this work, we develop coding schemes for a new storage paradigm that can be represented as a collection of two-dimensional arrays. Motivated by error patterns observed in recent prototype architectures, our study focuses on correcting erasures in the last few symbols of each row, and also correcting arbitrary deletions across rows. We present code constructions and explicit encoders and decoders that are shown to be nearly optimal in many scenarios. We show that the new coding schemes are capable of effectively mitigating these errors, making these emerging storage platforms potentially promising solutions.

In the reconstruction model, first proposed by Levenshtein in 2001, a word is transmitted over multiple identical noisy channels that output distinct erroneous words. Given the channels’ outputs, unique decoding of the transmitted word is guaranteed to succeed only if the number of the channels is greater than a specific value. Otherwise, there may be several transmitted words that lead to the same channels’ outputs. In this case, these words are recovered using a list decoder. Calculating the largest list size is a fundamental task when studying the list decoding problem. The present work takes the first steps towards studying list decoding of insertions and deletions under the reconstruction model. More specifically, it assumes that an arbitrary binary word is transmitted over$m~t$-insertion (or$t$-deletion) identical channels, and provides the largest list size for specific values of$m$. These results are mainly achieved by investigating the largest intersection of$m~t$-insertion (or$t$-deletion) balls surrounding arbitrary binary words in the space.

Nanopore sequencers, being superior to other sequencing technologies for DNA storage in multiple aspects, have attracted considerable attention in recent times. Their high error rates however demand thorough research on practical and efficient coding schemes to enable accurate recovery of stored data. To this end, we consider a simplified model of a nanopore sequencer inspired by Mao et al., that incorporates intersymbol interference and measurement noise. Essentially, our channel model passes a sliding window of length ℓ over an input sequence, that outputs the L1-weight of the enclosed ℓ bits and shifts by δ positions with each time step. The resulting (ℓ + 1)-ary vector, termed the read vector, may also be corrupted by t substitution errors. By employing graph-theoretic techniques, we deduce that for δ = 1, at least log log n bits of redundancy are required to correct a single (t = 1) substitution. Finally for ℓ ≥ 3, we exploit some inherent characteristics of read vectors to arrive at an error-correcting code that is optimal up to an additive constant for this setting.

The Invertible Bloom Lookup Table (IBLT) is a probabilistic data structure for set representation, with applications in network and traffic monitoring. It is known for its ability to list its elements, an operation that succeeds with high probability for sufficiently large table. However, listing can fail even for relatively small sets. This paper extends recent work on the worst-case analysis of IBLT, which guarantees successful listing for all sets of a certain size, by introducing more general IBLT schemes. These schemes allow for greater freedom in the implementation of the insert, delete, and listing operations and demonstrate that the IBLT memory can be reduced while still maintaining successful listing guarantees. The paper also explores the time-memory trade-off of these schemes, some of which are based on linear codes and Bh-sequences over finite fields.

Although the expenses associated with DNA sequencing have been rapidly decreasing, the current cost stands at roughly $1.3K/TB, which is dramatically more expensive than reading from existing archival storage solutions today. In this work, we aim to reduce not only the cost but also the latency of DNA storage by studying the DNA coverage depth problem, which aims to reduce the required number of reads to retrieve information from the storage system. Under this framework, our main goal is to understand how to optimally pair an error-correcting code with a given retrieval algorithm to minimize the sequencing coverage depth, while guaranteeing retrieval of the information with high probability. Additionally, we study the DNA coverage depth problem under the random-access setup.

This paper introduces a new solution to DNA storage that integrates all three steps of retrieval, namely clustering, reconstruction, and error correction. DNA-correcting codes are presented as a unique solution to the problem of ensuring that the output of the storage system is unique for any valid set of input strands. To this end, we introduce a novel distance metric to capture the unique behavior of the DNA storage system and provide necessary and sufficient conditions for DNA-correcting codes. The paper also includes several upper bounds and constructions of DNA-correcting codes.

High temperatures in electronic devices have a negative effect on their performance. Various techniques have been proposed and studied to address and combat this thermal challenge. To guarantee that the peak temperature of the devices will be bounded by some maximum temperature, the transmitted signal has to satisfy some constraints.With this motivation, we study the constrained channel that only accepts sequences that satisfy prescribed thermal constraints. The main goal in this paper is to compute the capacity of this channel. We provide the exact capacity of the channel with some certain parameters and we also present some bounds on the capacity in various cases.Finally, we consider the model that multiple wires are available to use and find out the smallest number of wires required to satisfy the thermal constraints.

DNA labeling is a powerful tool in molecular biology and biotechnology that allows for the visualization, detection, and study of DNA at the molecular level. Under this paradigm, a DNA molecule is being labeled by specific k patterns and is then imaged. Then, the resulted image is modeled as a (k +1)-ary sequence in which any non-zero symbol indicates on the appearance of the corresponding label in the DNA molecule. The primary goal of this work is to study the labeling capacity, which is defined as the maximal information rate that can be obtained using this labeling process. The labeling capacity is computed for any single label and several results are provided for multiple labels as well. Moreover, we provide the optimal minimal number of labels of length one or two that are needed in order to gain labeling capacity of 2.

We consider gradient coding in the presence of an adversary controlling so-called malicious workers trying to corrupt the computations. Previous works propose the use of MDS codes to treat the inputs of the malicious workers as errors and correct them using the error-correction properties of the code. This comes at the expense of increasing the replication, i.e., the number of workers each partial gradient is computed by. In this work, we reduce replication by proposing a method that detects the erroneous inputs from the malicious workers, hence transforming them into erasures. For s malicious workers, our solution can reduce the replication to s+1 instead of 2s+1 for each partial gradient at the expense of only s additional computations at the main node and additional rounds of light communication between the main node and the workers. We give fundamental limits of the general framework for fractional repetition data allocation. Our scheme is optimal in terms of replication and local computation but incurs a communication cost that is asymptotically, in the size of the dataset, a multiplicative factor away from the derived bound.

We study a data-driven approach to the bee identification problem for DNA strands. The bee-identification problem, introduced by Tandon et al. (2019), requires one to identify M bees, each tagged by a unique barcode, via a set of M noisy measurements. Later, Chrisnata et al. (2022) extended the model to case where one observes N noisy measurements of each bee, and applied the model to address the unordered nature of DNA storage systems.In such systems, a unique address is typically prepended to each DNA data block to form a DNA strand, but the address may possibly be corrupted. While clustering is usually used to identify the address of a DNA strand, this requires ℳ2data comparisons (when ℳ is the number of reads). In contrast, the approach of Chrisnata et al. (2022) avoids data comparisons completely. In this work, we study an intermediate, data-driven approach to this identification task.For the binary erasure channel, we first show that we can almost surely correctly identify all DNA strands under certain mild assumptions. Then we propose a data-driven pruning procedure and demonstrate that on average the procedure uses only a fraction of ℳ2data comparisons. Specifically, for ℳ = 2nand erasure probability p, the expected number of data comparisons performed by the procedure is κℳ2, where ${\left( {\frac{{1 + 2p - {p^2}}}{2}} \right)^n} \leq \kappa \leq {\left( {\frac{{1 + p}}{2}} \right)^n}$.

In conventional DNA synthesis machines many strands are usually synthesized in parallel by iterating through a supersequence s and adding in each cycle a single nucleotide to a subset of the strands. Then, the length of s determines the number of the cycles, hence the time and the cost of the synthesis process too. Recently, in order to optimize the synthesis process, researchers have suggested to append in each cycle a shortmer instead of a single nucleotide. The present work studies this optimization from a theoretical point of view. In particular, it discusses which shortmers are the best to use, and how to calculate the number of cycles required to synthesize in parallel a set of strands using a set of shormers. Lastly, and following a previously described connection between the DNA synthesis problem and costly constrained graphs, the paper investigates calculating the capacities of such non-deterministic graphs.

MOTIVATION: Optical genome mapping (OGM) is a technique that extracts partial genomic information from optically imaged and linearized DNA fragments containing fluorescently labeled short sequence patterns. This information can be used for various genomic analyses and applications, such as the detection of structural variations and copy-number variations, epigenomic profiling, and microbial species identification. Currently, the choice of labeled patterns is based on the available biochemical methods and is not necessarily optimized for the application. RESULTS: In this work, we develop a model of OGM based on information theory, which enables the design of optimal labeling patterns for specific applications and target organism genomes. We validated the model through experimental OGM on human DNA and simulations on bacterial DNA. Our model predicts up to 10-fold improved accuracy by optimal choice of labeling patterns, which may guide future development of OGM biochemical labeling methods and significantly improve its accuracy and yield for applications such as epigenomic profiling and cultivation-free pathogen identification in clinical samples. AVAILABILITY AND IMPLEMENTATION: https://github.com/yevgenin/PatternCode.

Synthetic polymer-based data storage seems to be a particularly promising candidate that could help to cope with the ever-increasing demand for archival storage requirements. It involves designing molecules of distinct masses to represent the respective bits {0,1}, followed by the synthesis of a polymer of molecular units that reflects the order of bits in the information string. Reading out the stored data requires the use of a tandem mass spectrometer, that fragments the polymer into shorter substrings and provides their corresponding masses, from which thecomposition, i.e. the number of 1s and 0s in the concerned substring can be inferred. Prior works have dealt with the problem of unique string reconstruction from the set of all possible compositions, calledcomposition multiset. This was accomplished either by determining which string lengths always allow unique reconstruction, or by formulating coding constraints to facilitate the same for all string lengths. Additionally, error-correcting schemes to deal with substitution errors caused by imprecise fragmentation during the readout process, have also been suggested. This work builds on this research by extending previously considered error models, mainly confined to substitution of compositions. To this end, we define new error models that consider insertions of spurious compositions and deletions of existing ones, thereby corrupting the composition multiset. We analyze if the reconstruction codebook proposed by Pattabiraman et al. is indeed robust to such errors, and if not, propose new coding constraints to remedy this.

The rapid development of DNA storage has brought the deletion and insertion channel to the front line of research. When the number of deletions is equal to the number of insertions, theFixed Length Levenshtein(FLL) metric is the right measure for the distance between two words of the same length. Similar to any other metric, the size of a ball is one of the most fundamental parameters. In this work, we consider the minimum, maximum, and average size of a ball with radius one, in the FLL metric. The related minimum and the maximum size of a maximal anticode with diameter one are also considered.

We study the adversarial torn-paper channel. This problem is motivated by applications in DNA data storage where the DNA strands that carry information may break into smaller pieces which are received out of order. Our model extends the previously researched probabilistic setting to the worst-case. We develop code constructions for any parameters of the channel for which non-vanishing asymptotic rate is possible and show our constructions achieve asymptotically optimal rate while allowing for efficient encoding and decoding. Finally, we extend our results to related settings included multi-strand storage, presence of substitution errors, or incomplete coverage.

In this paper we study function-correcting codes, a new class of codes designed to protect the function evaluation of a message against errors. We show that FCCs are equivalent to irregular-distance codes, i.e., codes that obey some given distance requirement between each pair of codewords. Using these connections, we study irregular-distance codes and derive general upper and lower bounds on their optimal redundancy. Since these bounds heavily depend on the specific function, we provide simplified, suboptimal bounds that are easier to evaluate. We further employ our general results to specific functions of interest and compare our results to standard error-correcting codes, which protect the whole message.

Motivated by recent advances in DNA-based data storage, we study a communication system, where information is conveyed over many sequences in parallel. In this system, the receiver cannot control the access to these sequences and can only draw from these sequences, unaware which sequence has been drawn. Further, the drawn sequences are susceptible to errors. In this paper, a suitable channel model that models this input-output relationship is analyzed and its information capacity is computed for a wide range of parameters and a general class of drawing distributions. This generalizes previous results for the noiseless case and specific drawing distributions. The analysis can guide future DNA-based data storage experiments by establishing theoretical limits on achievable information rates and by proposing decoding techniques that can be useful for practical implementations of decoders.

Balanced sequences and balanced codes have attracted a lot of research in the last seventy years due to their diverse applications in information theory as well as other areas of computer science and engineering. There have been some methods to classify balanced sequences. This work suggests two new different hierarchies to classify these sequences. The first one is based on the largest$\ell $for which each$\ell $-tuple is contained the same amount of times in the sequence. This property is a generalization for the property required for de Bruijn sequences. The second hierarchy is based on the number of balanced derivatives of the sequence. Enumeration for each such family of sequences and efficient encoding and decoding algorithms are provided in this paper.

This paper studies two families of constraints for two-dimensional and multidimensional arrays. The first family requires that a multidimensional array will not contain a cube of zeros of some fixed size and the second constraint imposes that there will not be two identical cubes of a given size in the array. These constraints are natural extensions of their one-dimensional counterpart that have been rigorously studied recently. For both of these constraints we present conditions on the size of the cube for which the asymptotic rate of the set of valid arrays approaches 1 as well as conditions for the redundancy to be at most a single symbol. For the first family we present an efficient encoding algorithm that uses a single redundant symbol to encode arbitrary information into a valid array and for the second family we present a similar encoder for the two-dimensional case. The results in the paper are also extended to similar constraints where the sub-array is not necessarily a cube, but a box of arbitrary dimensions and only its volume is bounded.

Correcting insertions/deletions as well as substitution errors simultaneously plays an important role in DNA-based storage systems as well as in classical communications. This paper deals with the fundamental task of constructing codes that can correct a single insertion or deletion along with a single substitution. A non-asymptotic upper bound on the size of non-binary single-deletion$s$-substitution correcting codes is derived, showing that the non-asymptotic redundancy of such a code of length$n$has to be at least$(s+1) \log _{q} n$. An explicit construction of binary single-deletion single-substitution correcting codes with at most$6 \log n + 8$redundancy bits is presented.

This paper introduces a new family of reconstruction codes which is motivated by applications in DNA data storage and sequencing. In such applications, DNA strands are sequenced by reading some subset of their substrings. While previous works considered two extreme cases in which all substrings of pre-defined lengths are read or substrings are read with no overlap for the single string case, this work studies two extensions of this paradigm. The first extension considers the setup in which consecutive substrings are read with some given minimum overlap. First, an upper bound is provided on the attainable rates of codes that guarantee unique reconstruction. Then, efficient constructions of codes that asymptotically meet that upper bound are presented. In the second extension, we study the setup where multiple strings are reconstructed together. Given the number of strings and their length, we first derive a lower bound on the read substrings’ length$\ell $that is necessary for the existence of multi-strand reconstruction codes with non-vanishing rates. We then present two constructions of such codes and show that their rates approach 1 for values of$\ell $that asymptotically behave like the lower bound.

Synthetic polymer-based storage promises to accommodate the ever-increasing demand for archival storage. It involves designing molecules of distinct masses to represent the respective bits {0, 1}, followed by the synthesis of a polymer of molecular units that reflects the order of bits in the information string. The stored data can be read by means of a tandem mass spectrometer, that fragments the polymer into shorter substrings and provides their corresponding masses, from which the composition, i.e., the number of 1s and 0s in the concerned substring can be inferred. Prior works tackled the problem of unique string reconstruction from the set of all possible compositions, called the composition multiset. This was accomplished either by determining which string lengths always allow unique reconstruction, or by formulating coding constraints to facilitate the same for all string lengths. Additionally, error-correcting schemes to deal with substitution errors caused by imprecise fragmentation during the readout process, have also been suggested. This work extends previously considered error models that were mainly confined to substitutions of compositions. Our new error models consider insertions and deletions of compositions. The robustness of the reconstruction codebook proposed by Pattabiraman et al. to such errors is examined, and whenever necessary, new coding constraints are proposed to ensure unique reconstruction.

This paper studies the adversarial torn-paper channel. This problem is motivated by applications in DNA data storage where the DNA strands that carry the information may break into smaller pieces that are received out of order. Our model extends the previously researched probabilistic setting to the worst-case. We develop code constructions for any parameters of the channel for which non-vanishing asymptotic rate is possible and show that our constructions achieve optimal asymptotic rate while allowing for efficient encoding and decoding. Finally, we extend our results to related settings included multi-strand storage, presence of substitution errors, or incomplete coverage.

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 DNA-based applications, we generalize the bee identification problem proposed by Tandon et al. (2019). In this setup, we transmit all M codewords from a codebook over some channel and each codeword results in N noisy outputs. Then our task is to identify each codeword from the MN noisy outputs.First, via a reduction to a minimum-cost flow problem on a related flow network ${\mathcal{G}_N}$, we show that the problem can be solved in O(M3) time in the worst case. Next, we consider the deletion channel and study the expected number of edges in the network ${\mathcal{G}_N}$. Specifically, we obtain closed expressions for this quantity for certain codebooks and when the codebook comprises all binary words, we show that this quantity is sub-quadratic when the deletion probability is less than 1/2. This then implies that the expected running time for this codebook is o(M3). For other codebooks, we develop methods to compute the expected number of edges efficiently. Finally, we adapt classical peeling-decoding techniques to reduce the number of nodes and edges in ${\mathcal{G}_N}$.

de Bruijn sequences of order ℓ, i.e., sequences that contain each ℓ-tuple as a window exactly once, have found many diverse applications in information theory and most recently in DNA storage. This family of binary sequences has asymptotic rate of 1/2. To overcome this low rate, we study ℓ-tuples covering sequences, which impose that each ℓ-tuple appears at least once as a window in the sequence. The cardinality of this family of sequences is analyzed while assuming that ℓ is a function of the sequence length n. Lower and upper bounds on the asymptotic rate of this family are given. Moreover, we study an upper bound for ℓ such that the redundancy of the set of ℓ-tuples covering sequences is at most a single symbol. We present an efficient encoding and decoding schemes for ℓ-tuples covering sequences that meet this bound.

In a Private Inference scenario, a server holds a model (e.g., a neural network), a user holds data, and the user wishes to apply the model on her data. The privacy of both parties must be protected; the user’s data might contain confidential information, and the server’s model is his intellectual property.Private inference has been studied extensively in recent years, mostly from a cryptographic perspective by incorporating homo-morphic encryption and multiparty computation protocols, which incur high computational overhead and degrade the accuracy of the model. In this work we take a perpendicular approach which draws inspiration from the expansive Private Information Retrieval literature. We view private inference as the task of retrieving an inner product of a parameter vector with the data, a fundamental step in most machine learning models.By combining binary arithmetic with real-valued one, we present a scheme which enables the retrieval of the inner product for models whose weights are either binarized, or given in fixed-point representation; such models gained increased attention recently, due to their ease of implementation and increased robustness. We also present a fundamental trade-off between the privacy of the user and that of the server, and show that our scheme is optimal in this sense. Our scheme is simple, universal to a large family of models, provides clear information-theoretic guarantees to both parties with zero accuracy loss, and in addition, is compatible with continuous data distributions and allows infinite precision.

We consider the problem of correcting insertion and deletion errors in the d-dimensional space. This problem is well understood for vectors (one-dimensional space) and was recently studied for arrays (two-dimensional space). For vectors and arrays, the problem is motivated by several practical applications such as DNA-based storage and racetrack memories. From a theoretical perspective, it is interesting to know whether the same properties of insertion/deletion correcting codes generalize to the d-dimensional space. In this work, we show that the equivalence between insertion and deletion correcting codes generalizes to the d-dimensional space. As a particular result, we show the following missing equivalence for arrays: a code that can correct trand tcrow/column deletions can correct any combination of $t_{\text{r}}^{{\text{ins}}} + t_{\text{r}}^{{\text{del}}} = {t_{\text{r}}}{\text{ and }}t_{\text{c}}^{{\text{ins}}} + t_{\text{c}}^{{\text{del}}} = {t_{\text{c}}}$ row/column insertions and deletions. The fundamental limit on the redundancy and a construction of insertion/deletion correcting codes in the d-dimensional space remain open for future work.

This paper studies two families of constraints for two-dimensional and multidimensional arrays. The first family requires that a multidimensional array will not contain a cube of zeros of some fixed size and the second constraint imposes that there will not be two identical cubes of a given size in the array. These constraints are natural extensions of their one-dimensional counterpart that have been rigorously studied recently. For both of these constraints we present conditions of the size of the cube for which the asymptotic rate of the set of valid arrays approaches 1 as well as conditions for the redundancy to be at most a single symbol. For the first family, we present an efficient encoding algorithm that uses a single symbol to encode arbitrary information into a valid array and for the second family we present a similar encoder for the two-dimensional case. The results in the paper are also extended to similar constraints where the subarray is not necessarily a cube, but a box of arbitrary dimensions and only its volume is bounded.

The channel output entropy of a transmitted word is the entropy of the possible channel outputs and similarly the input entropy of a received word is the entropy of all possible transmitted words. The goal of this work is to study these entropy values for the k-deletion, k-insertion channel, where exactly k symbols are deleted, inserted in the transmitted word, respectively. If all possible words are transmitted with the same probability then studying the input and output entropies is equivalent. For both the 1-insertion and 1-deletion channels, it is proved that among all words with a fixed number of runs, the input entropy is minimized for words with a skewed distribution of their run lengths and it is maximized for words with a balanced distribution of their run lengths. Among our results, we establish a conjecture by Atashpendar et al. which claims that for the binary 1-deletion, the input entropy is maximized for the alternating words. For the 2-deletion channel, it is proved that constant words with a single run minimize the input entropy.

The sequence reconstruction problem, introduced by Levenshtein in 2001, considers a communication scenario where the sender transmits a codeword from some codebook and the receiver obtains multiple noisy reads of the codeword. The common setup assumes the codebook to be the entire space and the problem is to determine the minimum number of distinct reads that is required to reconstruct the transmitted codeword. Motivated by modern storage devices, we study a variant of the problem where the number of noisy reads$N$is fixed. Specifically, we designreconstruction codesthat reconstruct a codeword from$N$distinct noisy reads. We focus on channels that introduce a single edit error (i.e. a single substitution, insertion, or deletion) and their variants, and design reconstruction codes for all values of$N$. In particular, for the case of a single edit, we show that as the number of noisy reads increases, the number of redundant symbols required can be gracefully reduced from$\log _{q} n+O(1)$to$\log _{q} \log _{q} n+O(1)$, and then to$O(1)$, where$n$denotes the length of a codeword. We also show that these reconstruction codes are asymptotically optimal. Finally, via computer simulations, we demonstrate that in certain cases, reconstruction codes can achieve similar performance as classical error-correcting codes with less redundant symbols.

Resistive memories, such as phase change memories and resistive random access memories have attracted significant attention in recent years due to their better scalability, speed, rewritability, and yet non-volatility. However, their limited endurance is still a major drawback that has to be improved before they can be widely adapted in large-scale systems. In this work, in order to reduce the wear out of the cells, we propose a new coding scheme, called endurance-limited memories (ELM) codes, that increases the endurance of these memories by limiting the number of cell programming operations. Namely, an$\ell $-change$t$-write ELM code is a coding scheme that allows to write$t$messages into some$n$binary cells while guaranteeing that each cell is programmed at most$\ell $times. In case$\ell =1$, these codes coincide with the well-studied write-once memory (WOM) codes. We study some models of these codes which depend upon whether the encoder knows on each write the number of times each cell was programmed, knows only the memory state, or even does not know anything. For the decoder, we consider these similar three cases. We fully characterize the capacity regions and the maximum sum-rates of three models where the encoder knows on each write the number of times each cell was programmed. In particular, it is shown that in these models the maximum sum-rate is$\log \sum _{i=0}^{\ell } {\binom{t }{ i}}$. We also study and expose the capacity regions of the models where the decoder is informed with the number of times each cell was programmed. Finally we present the most practical model where the encoder read the memory before encoding new data and the decoder has no information about the previous states of the memory.

The sequence reconstruction problem, introduced by Levenshtein in 2001, considers a communication scenario where the sender transmits a codeword from some codebook and the receiver obtains multiple noisy reads of the codeword. Motivated by modern storage devices, we introduced a variant of the problem where the number of noisy reads$N$is fixed. Of significance, for the single-deletion channel, using$\log _{2}\log _{2} n +O(1)$redundant bits, we designed a reconstruction code of length$n$that reconstructs codewords from two distinct noisy reads (Caiet al., 2021). In this work, we show that$\log _{2}\log _{2} n -O(1)$redundant bits are necessary for such reconstruction codes, thereby, demonstrating the optimality of the construction. Furthermore, we show that these reconstruction codes can be used in$t$-deletion channels (with$t \geqslant 2$) to uniquely reconstruct codewords from${n^{t-1}}/{(t-1)!}+O\left ({n^{t-2}}\right)$distinct noisy reads. For the two-deletion channel, using higher order VT syndromes and certain runlength constraints, we designed the class ofhigher order constrained shifted VTcode with$2\log _{2} n +o(\log _{2}(n))$redundancy bits that can reconstruct any codeword from any$N \geqslant 5$of its length-$(n-2)$subsequences.

Private information retrieval (PIR) protocols ensure that a user can download a file from a database without revealing any information on the identity of the requested file to the servers storing the database. While existing protocols strictly impose that no information is leaked on the file’s identity, this work initiates the study of the tradeoffs that can be achieved by relaxing the perfect privacy requirement. We refer to such protocols as weakly-private information retrieval (WPIR) protocols. In particular, for the case of multiple noncolluding replicated servers, we study how the download rate, the upload cost, and the access complexity can be improved when relaxing the perfect privacy constraint. To quantify the information leakage on the requested file’s identity we consider mutual information (MI), worst-case information leakage, and maximal leakage (MaxL). We present two WPIR schemes, denoted by Scheme A and Scheme B, based on two recent PIR protocols and show that the download rate of the former can be optimized by solving a convex optimization problem. We also show that Scheme A achieves an improved download rate compared to the recently proposed scheme by Samyet al.under the so-called$\epsilon $-privacy metric. Additionally, a family of schemes based on partitioning is presented. Moreover, we provide an information-theoretic converse bound for the maximum possible download rate for the MI and MaxL privacy metrics under a practical restriction on the alphabet size of queries and answers. For two servers and two files, the bound is tight under the MaxL metric, which settles the WPIR capacity in this particular case. Finally, we compare the performance of the proposed schemes and their gap to the converse bound.

This paper investigates the problem of correcting multiple criss-cross insertions and deletions in arrays. More precisely, we study the unique recovery of$n \times n$arrays affected by${t}$-criss-cross deletionsdefined as any combination of${t_{\mathrm {r}}}$row and${t_{\mathrm {c}}}$column deletions such that${t_{\mathrm {r}}}+ {t_{\mathrm {c}}}= {t}$for a given$t$. We show an equivalence between correcting${t}$-criss-cross deletions and${t}$-criss-cross insertions and show that a code correcting${t}$-criss-cross insertions/deletions has redundancy at least${t} n + {t}\log n - \log ({t}!)$. Then, we present an existential construction of a${t}$-criss-cross insertion/deletion correcting code with redundancy bounded from above by${t} n + \mathcal {O}({t}^{2} \log ^{2} n)$. The main ingredients of the presented code construction are systematic binary${t}$-deletion correcting codes and Gabidulin codes. The first ingredient helps locating the indices of the inserted/deleted rows and columns, thus transforming the insertion/deletion-correction problem into a row/column erasure-correction problem which is then solved using the second ingredient.

Afunctional$k$-batchcode of dimension$s$consists of$n$servers storing linear combinations of$s$linearly independent information bits. Any multiset request of size$k$of linear combinations (or requests) of the information bits can be recovered by$k$disjoint subsets of the servers. The goal under this paradigm is to find the minimum number of servers for given values of$s$and$k$. A recent conjecture states that for any$k=2^{s-1}$requests the optimal solution requires$2^{s}-1$servers. This conjecture is verified for$s \leqslant 5$but previous work could only show that codes with$n=2^{s}-1$servers can support a solution for$k=2^{s-2} + 2^{s-4} + \left \lfloor{ \frac { 2^{s/2}}{\sqrt {24}} }\right \rfloor $requests. This paper reduces this gap and shows the existence of codes for$k=\lfloor \frac {5}{6}2^{s-1} \rfloor - s$requests with the same number of servers. Another construction in the paper provides a code with$n=2^{s+1}-2$servers and$k=2^{s}$requests, which is an optimal result. These constructions are mainly based on extended Simplex codes and equivalently provide constructions forparallel Random I/O (RIO)codes.

The rapid development of DNA storage has brought the deletion and insertion channel, once again, to the front line of research. When the number of deletions is equal to the number of insertions, the Fixed Length Levenshtein$(FLL)$metric is the right measure for the distance between two words of the same length. The size of a ball is one of the most fundamental parameters in any metric. The size of the ball with radius one in the FLL metric depends on the number of runs and the length of the alternating segments of the given word. In this work, we find the minimum, maximum, and average size of a ball with radius one, in the FLL metric. The related minimum and maximum sizes of a maximal anticode with diameter one are also calculated.

This paper studies optimal decoding for a special case of the deletion channel, referred by the t-deletion channel, which deletes exactly$t$symbols of the transmitted word uniformly at random. The goal of the paper is to understand how such an optimal decoder operates in order to minimize the expected normalized distance. A full characterization of a decoder for this setup is given for a channel that deletes one or two symbols. For$t$= 1 it is shown that when the code is the entire space, the decoder is the lazy decoder which simply returns the channel output. Similarly, for$t$= 2 it is shown that the decoder acts as the lazy decoder in almost all cases and when the longest run is significantly long, it prolongs the longest run by one symbol.

Transverse-read is a novel technique to detect the number of ‘1's stored in domain wall memory, also known as racetrack memory, without shifting any domains. Motivated by this technique, we propose a novel scheme to combine transverse-read and shift-operations such that the number of shift-operations can be reduced while still achieving high capacity. We also show that this scheme is helpful to correct errors in domain wall memory. A set of valid words in this transverse-read channel is called a transverse-read code. We first present several properties of transverse-read codes and show that they are equivalent to constrained codes. Then, we compute the maximal asymptotic rate of transverse-read codes for several parameters. Next, we construct achieving capacity codes with efficient encoding/decoding algorithms. Finally, we discuss transverse-read codes which correct shift-errors in domain wall memory.

Locality enables storage systems to recover failed nodes from small subsets of surviving nodes. The setting where nodes are partitioned into subsets, each allowing for local recovery, is well understood. In this work we consider a generalization introduced by Gopalan et al., where, viewing the codewords as arrays, constraints are imposed on the columns and rows in addition to some global constraints. Specifically, we present a generic method of adding such global parity-checks and derive new results on the set of correctable erasure patterns. Finally, we relate the set of correctable erasure patterns in the considered topology to those correctable in tensor-product codes.

Motivated by applications in machine learning and archival data storage, we introduce function-correcting codes, a new class of codes designed to protect a function evaluation on the data against errors. We show that function-correcting codes are equivalent to irregular-distance codes, i.e., codes that obey some given distance requirement between each pair of codewords. Using these connections, we study irregular-distance codes and derive general upper and lower bounds on their optimal redundancy. Since these bounds heavily depend on the specific function, we provide simplified, suboptimal bounds that are easier to evaluate. We further employ our general results to specific functions of interest and we show that function-correcting codes can achieve significantly less redundancy than standard error-correcting codes which protect the whole data.

The de Bruijn graph and its sequences have found many diverse applications in information theory as well as other areas of computer science and engineering such as interconnection networks, VLSI decomposition, and most recently in DNA storage. Binary balanced sequences have also been a subject to a large research during the last forty years with various applications and a lot of interest in information theory. There have been some works on classification of balanced sequences mainly based on their spectral-null order. This work generalizes the concept of de Bruijn sequences, based on the de Bruijn graph of order$\ell$, where each edge is multiplied to a fixed number of multiple edges. This implies that in the sequences derived from the generalized graph each l-tuple has the same multiplicity. Using this generalization we form an interesting hierarchy between balanced sequences. Furthermore, another hierarchy is given by the derivatives of balanced sequences. Enumeration for each such family of sequences and efficient encoding and decoding algorithms are also provided.

The reconstruction model, first proposed by Levenshtein in 2001, assumes that a word is transmitted over multiple identical noisy channels that output distinct words. Given the channels' outputs, the transmitted word is guaranteed to be decoded uniquely only if the number of the channels is greater than some value. Otherwise, there could be several transmitted words leading to the same channels' outputs. Hence, these words should be found following the list decoding approach. Motivated by DNA storage systems, the present work takes the first steps towards studying list decoding for insertions and deletions under the reconstruction model. More specifically, it will be assumed that an arbitrary binary word is transmitted over$m$t-insertions (or$t$deletions) identical channels. For specific values of$m$, bounds on the largest list decoder size are provided. These bounds are mainly derived by investigating the largest intersection of$m$t- insertion (or t-deletion) balls surrounding arbitrary binary words in the space. Furthermore, all pairs of binary words achieving the largest intersection of their t-insertion balls are characterized.

This paper investigates the problem of correcting multiple criss-cross deletions in arrays. More precisely, we study the unique recovery of$n\times n$arrays affected by any combination of$t_{\mathrm{r}}$row and$t_{\mathrm{c}}$column deletions such that$t_{\mathrm{r}}+t_{\mathrm{c}}=t$for a given$t$. We refer to these type of deletions as t-criss-cross deletions. We show that the asymptotic redundancy of a code correcting t-criss-cross deletions is at least$tn+t\log n-\log(t!)$. Then, we present an existential construction of a code capable of correcting t-criss-cross deletions where its redundancy is bounded from above by$tn+\mathcal{O}(t^{2}\log^{2}n)$. The main ingredients of the presented code are systematic binary t-deletion-correcting codes and Gabidulin codes. The first ingredient helps locating the indices of the deleted rows and columns, thus transforming the deletion-correction problem into an erasure-correction problem which is then solved using the second ingredient.

A functional k-batch code of dimension$s$consists of$n$servers storing linear combinations of$s$linearly independent information bits. Any multiset request of size$k$of linear combinations (or requests) of the information bits can be recovered by$k$disjoint subsets of the servers. The goal under this paradigm is to find the minimum number of servers for given values of$s$and$k$. A recent conjecture states that for any$k=2^{s-1}$requests the optimal solution requires$2^{s}-1$servers. This conjecture is verified for$s\leqslant 5$but previous work could only show that codes with$n=2^{s}-1$servers can support a solution for$k=2^{s-2}+2^{s-4}+ \left\lfloor\frac{2^{s/2}}{\sqrt{24}} \right\rfloor$requests. This paper reduces this gap and shows the existence of codes for$k= \lfloor\frac{2}{3}2^{s-1}\rfloor$requests with the same number of servers. Another construction in the paper provides a code with$n=2^{s+1}-2$servers and$k=2^{s}$requests, which is an optimal result. These constructions are mainly based on Hadamard codes and equivalently provide constructions for parallel Random I/O (RIO) codes.

This paper studies the intersections of insertion and deletion balls. The t-insertion, t-deletion ball of a sequence x is the set of all sequences received by t insertions, deletions to x, respectively. While the intersection of either deletion balls or insertion balls has been rigorously studied before, the intersection of an insertion ball and a deletion ball has not been addressed so far. We find the maximum intersection size of any two insertion and deletion balls in the binary case. For the special case of one-insertion and one-deletion balls we find the intersection size for all pair of sequences. Then, we derive the largest and average values of this intersection size. Lastly, we present an algorithm that efficiently computes the intersection of any t1-insertion ball and t2-deletion ball.

Synthetic DNA is an attractive alternative for data storage media due to its high information density, low energy usage, and exceptional robustness. Enzymatic DNA synthesis was recently introduced to allow cost effective synthesis of longer DNA molecules for data storage. This method is characterized by stutter errors which are sticky insertions so that every base in the designed sequence may be synthesized more than once. In this work, we study the problem of reconstructing the original sequence from a set of noisy reads originating from the stuttering enzymatic synthesis. We present different reconstruction algorithms and analyze their expected success probability and error rate for three different scenarios that depend on the information which is known about the stutter errors. We evaluate algorithmic performance analytically as well as by using simulations. We are especially interested in characterizing the performance as a function of the read depth. Our findings can be used to evaluate the trade-offs between synthesis quality indicators and the sequencing depth required for reconstruction with high probability. In principle, the probability of reconstruction failure exponentially decays with the sequencing depth, as demonstrated in the study. We also analyze the use of error-correcting codes to improve the error performance.

The problem of string reconstruction based on its substrings spectrum has received significant attention recently due to its applicability to DNA data storage and sequencing. In contrast to previous works, we consider in this paper a setup of this problem where multiple strings are reconstructed together. Given a multiset S of strings, all their substrings of some fixed length $\ell$, defined as the $\ell$-profile of S, are received and the goal is to reconstruct all strings in S. A multi-strand $\ell$-reconstruction code is a set of multisets such that every element S can be reconstructed from its $\ell$-profile. Given the number of strings k and their length n, we first find a lower bound on the value of $\ell$ necessary for existence of multi-strand $\ell$-reconstruction codes with non-vanishing asymptotic rate. We then present two constructions of such codes and show that their rates approach 1 for values of $\ell$ that asymptotically behave like the lower bound.

Advances in biochemical technologies, such as synthesizing and sequencing devices, have fueled manifold recent experiments on archival digital data storage using DNA. In this paper we review and analyze recent results on information-theoretic aspects of such storage systems. The discussion focuses on a channel model that incorporates the main properties of DNA-based data storage. Namely, the user data is synthesized many times onto a large number of short-length DNA strands. The receiver then draws strands from the stored sequences in an uncontrollable manner. Since the synthesis and sequencing are prone to errors, a received sequence can differ from its original strand, and their relationship is described by a probabilistic channel. Recently, the capacity of this channel was derived for the case of substitution errors inside the sequences. We review the main techniques used to prove a coding theorem and its converse, showing the achievability of the capacity and the fact that it cannot be exceeded. We further provide an intuitive interpretation of the capacity formula for relevant channel parameters, compare with sub-optimal decoding methods, and conclude with a discussion on cost-efficiency.

MOTIVATION: Recent years have seen a growing number and an expanding scope of studies using synthetic oligo libraries for a range of applications in synthetic biology. As experiments are growing by numbers and complexity, analysis tools can facilitate quality control and support better assessment and inference. RESULTS: We present a novel analysis tool, called SOLQC, which enables fast and comprehensive analysis of synthetic oligo libraries, based on NGS analysis performed by the user. SOLQC provides statistical information such as the distribution of variant representation, different error rates and their dependence on sequence or library properties. SOLQC produces graphical reports from the analysis, in a flexible format. We demonstrate SOLQC by analyzing literature libraries. We also discuss the potential benefits and relevance of the different components of the analysis. AVAILABILITY AND IMPLEMENTATION: SOLQC is a free software for non-commercial use, available at https://app.gitbook.com/@yoav-orlev/s/solqc/. For commercial use please contact the authors. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

This paper studies the problem of constructing codes correcting deletions in arrays. Under this model, it is assumed that an$n \times n$array can experience deletions of rows and columns. These deletion errors are referred to as$({t_{\mathrm {r}}}, {t_{\mathrm {c}}})$-criss-cross deletionsif${t_{\mathrm {r}}}$rows and${t_{\mathrm {c}}}$columns are deleted, while a code correcting these deletion patterns is called a$({t_{\mathrm {r}}}, {t_{\mathrm {c}}})$-criss-cross deletion correction code. The definitions forcriss-cross insertionsare similar. It is first shown that when$t_{r}=t_{c}$the problems of correcting criss-cross deletions and criss-cross insertions are equivalent. The focus of this paper lies on the case of (1, 1)-criss-cross deletions. A non-asymptotic upper bound on the cardinality of (1, 1)-criss-cross deletion correction codes is shown which assures that the redundancy is at least$2n-3+2\log n$bits. A code construction with an existential encoding and an explicit decoding algorithm is presented. The redundancy of the construction is at most$2n+4 \log n + 7 +2 \log e$. A construction with explicit encoder and decoder is presented. The explicit encoder adds an extra$5\log n + 5$bits of redundancy to the construction.

Thede Bruijn graph, its sequences, and their various generalizations, have found many applications in information theory, including many new ones in the last decade. In this paper, motivated by a coding problem for emerging memory technologies, a set of sequences which generalize the window property of de Bruijn sequences, on its shorter subsequences, are defined. These sequences can be also defined and viewed as constrained sequences. Hence, they will be calledlocally-constrained de Bruijn sequencesand a set of such sequences will be called alocally-constrained de Bruijn code. Several properties and alternative definitions for such codes are examined and they are analyzed as generalized sequences in the de Bruijn graph (and its generalization) and as constrained sequences. Various enumeration techniques are used to compute the total number of sequences for any given set of parameters. A construction method of such codes from the theory of shift-register sequences is proposed. Finally, we show how these locally-constrained de Bruijn sequences and codes can be applied in constructions of codes for correcting synchronization errors in the$\ell $-symbol read channel and in the racetrack memory channel. For this purpose, these codes are superior in their size to previously known codes.

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.

Lifted Reed-Solomon and multiplicity codes are classes of codes, constructed from specific sets of$m$-variate polynomials. These codes allow for the design of high-rate codes that can recover every codeword or information symbol from many disjoint sets. Recently, the underlying approaches have been combined for the bi-variate case to construct lifted multiplicity codes, a generalization of lifted codes that can offer further rate improvements. We continue the study of these codes by first establishing new lower bounds on the rate of lifted Reed-Solomon codes for any number of variables$m$, which improve upon the known bounds for any$m\ge 4$. Next, we use these results to provide lower bounds on the rate and distance of lifted multiplicity codes obtained from polynomials in an arbitrary number of variables, which improve upon the known results for any$m\ge 3$. Specifically, we investigate a subcode of a lifted multiplicity code formed by the linear span of$m$-variate monomials whose restriction to an arbitrary line in${\mathbb {F}}_{q}^{m}$is equivalent to a low-degree univariate polynomial. We find the tight asymptotic behavior of the fraction of such monomials when the number of variables$m$is fixed and the alphabet size$q=2^\ell $is large. Using these results, we give a new explicit construction of batch codes utilizing lifted Reed-Solomon codes. For some parameter regimes, these codes have a better trade-off between parameters than previously known batch codes. Further, we show that lifted multiplicity codes have a better trade-off between redundancy and the number of disjoint recovering sets for every codeword or information symbol than previously known constructions, thereby providing the best known PIR codes for some parameter regimes. Additionally, we present a new local self-correction algorithm for lifted multiplicity codes.

Partial MDS (PMDS) and sector-disk (SD) codes are classes of erasure correcting codes that combine locality with strong erasure correction capabilities. We construct PMDS and SD codes with local regeneration where each local code is a bandwidth-optimal regenerating MDS code. In the event of a node failure, these codes reduce both, the number of servers that have to be contacted as well as the amount of network traffic required for the repair process. The constructions require significantly smaller field size than the only other construction known in literature. Further, we present a construction of PMDS codes with global regeneration which allow to efficiently repair patterns of node failures that exceed the local erasure correction capability of the code and thereby invoke repair across different local groups.

A covering code is a set of codewords with the property that the union of balls, suitably defined, around these codewords covers an entire space. Generally, the goal is to find the covering code with the minimum size codebook. While most prior work on covering codes has focused on the Hamming metric, we consider the problem of designing covering codes defined in terms of either insertions or deletions. First, we provide new sphere-covering lower bounds on the minimum possible size of such codes. Then, we provide new existential upper bounds on the size of optimal covering codes for a single insertion or a single deletion that are tight up to a constant factor. Finally, we derive improved upper bounds for covering codes using R ≥ 2 insertions or deletions. We prove that codes exist with density that is only a factor O(R logR) larger than the lower bounds for all fixed R. In particular, our upper bounds have an optimal dependence on the word length, and we achieve asymptotic density matching the best known bounds for Hamming distance covering codes.

Thesequence reconstruction problemcorresponds to the model in which a sequence from some code is transmitted over several noisy channels that produce distinct outputs. Then, the channels’ outputs, received by the decoder, are used to recover the transmitted sequence, and the main problem under this paradigm is to calculate the minimum number of channels that enables unique reconstruction of the transmitted word. This problem is equivalent to finding the size of the largest intersection of channels’ outputs sets received after transmitting distinct codewords. Motivated by the error behavior observed in DNA storage systems, the present work extends the study of the reconstruction model to the case in which a binary word is transmitted over channels prone to substitutions, insertions, and deletions. Furthermore, we also study the size of the error balls generated by either one deletion and at most a fixed number of substitutions or one insertion and at most one substitution in a binary word. For the case of only substitutions, we present a decoder of optimal complexity, which improves upon a recent construction of such a decoder. Lastly, a simplification of that decoder is studied in case there are more channels than the minimum required number.

In graph theory, a tree is one of the more popular families of graphs with a wide range of applications in computer science as well as many other related fields. While there are several distance measures over the set of all trees, we consider here the one which defines the so-called tree distance, defined by the minimum number of edit operations, of removing and adding edges, in order to change one tree into another. From a coding theoretic perspective, codes over the tree distance are used for the correction of edge erasures and errors. However, studying this distance measure is important for many other applications that use trees and properties on their locality and the number of neighbor trees. Under this paradigm, the largest size of code over trees with a prescribed minimum tree distance is investigated. Upper bounds on these codes as well as code constructions are presented. A significant part of our study is dedicated to the problem of calculating the size of the ball of trees of a given radius. These balls are not regular and thus we show that while the star tree has asymptotically the smallest size of the ball, the maximum is achieved for the path tree.

Aprivate proximity retrieval(PPR) scheme is a protocol which allows a user to retrieve the identities of all records in a database that are within some distance$r$from the user’s record$x$. The user’sprivacyat each server is given by the fraction of the record$x$that is kept private. In this paper, this research is initiated and protocols that offer trade-offs between privacy, computational complexity, and storage are studied. In particular, we assume that each server stores a copy of the database and study the required minimum number of servers by our protocol which provides a given privacy level. Each server receives a query in the protocol and the set of queries forms a code. The main focus in the paper is dedicated to studying the family of codes generated by the set of queries. These codes will be shown to satisfy a specific covering property and will be calledprivate proximity retrieval intersection covering codes. In particular, since the query every server receives is a codeword, the goal is to minimize the number of codewords in such a code which is the minimum number of servers required by the protocol. These codes are closely related to a family of codes known ascovering designs. We introduce several lower bounds on the sizes of such codes as well as several constructions. This work focuses on the case when the records are binary vectors together with the Hamming distance. Other metrics such as the Johnson metric are also investigated.

Significant advances in biochemical technologies, such as synthesizing and sequencing devices, have made DNA a competitive medium for archival data storage. In this paper we analyze storage systems based on these macromolecules from an information theoretic perspective. Using an appropriate channel model for the synthesis and sequencing steps, we study the maximum achievable information density per nucleotide for reliable and error resilient data storage. The channel model features the main attributes that characterize DNA-based data storage. That is, information is synthesized onto many short DNA strands, and each strand is copied many times. Due to the storage and sequencing methods, the receiver draws strands from these synthesized strands in an uncontrollable manner, where it is possible that strands are drawn multiple times and also that some strands are not drawn at all. Additionally, due to imperfections, the obtained strands can contain errors. Here we prove the achievability of a recently published upper bound on the Shannon capacity of this channel for a large range of parameters by proposing and analyzing a decoder that clusters received strands according to their similarity and then efficiently estimates the original strands based on these clusters.

Three new constraints are introduced in this paper. These constraints are characterized by limitations on the Hamming weight of every subword of some fixed even length ℓ. In the (ℓ, δ)-locally-balanced constraint, the Hamming weight of every length-ℓ subword is bounded between ℓ/2 - δ and ℓ/2 + δ. The strong-(ℓ,δ)-locally-balanced constraint imposes the locally-balanced constraint for any subword whose length is at least ℓ. Lastly, the Hamming weight of every length-ℓ subword which satisfies the (ℓ, δ)-locally-bounded constraint is at most ℓ/2 - δ. It is shown that the capacity of the strong-(ℓ, δ)-locally-balanced constraint does not depend on the value of ℓ and is identical to the capacity of the (2δ + 1)-RDS constraint. The latter constraint limits the difference between the number of zeros and ones in every prefix of the word to be at most 2δ + 1. This value is also a lower bound on the capacity of the (ℓ, δ)-locally-balanced constraint, while a corresponding upper bound is given as well. Lastly, it is shown that if δ is not large enough, namely for δ <; √ℓ/2, then the capacity of the (ℓ, δ)-locally-bounded constraint approaches 1 as ℓ increases.

Partial MDS (PMDS) and sector-disk (SD) codes are classes of erasure codes that combine locality with strong erasure correction capabilities. We construct PMDS and SD codes where each local code is a bandwidth-optimal regenerating MDS code. The constructions require significantly smaller field size than the only other construction known in literature.

The sequence reconstruction problem, introduced by Levenshtein in 2001, considers a communication scenario where the sender transmits a codeword from some codebook and the receiver obtains multiple noisy reads of the codeword. The common setup assumes the codebook to be the entire space and the problem is to determine the minimum number of distinct reads that is required to reconstruct the transmitted codeword. Motivated by modern storage devices, we study a variant of the problem where the number of noisy reads N is fixed. Specifically, we design reconstruction codes that reconstruct a codeword from N distinct noisy reads. We focus on channels that introduce single edit error (i.e. a single substitution, insertion, or deletion) and their variants, and design reconstruction codes for all values of N. In particular, for the case of a single edit, we show that as the number of noisy reads increases, the number of redundant bits required can be gracefully reduced from logn + O(1) to loglogn + O(1), and then to O(1), where n denotes the length of a codeword. We also show that the redundancy of certain reconstruction codes is within one bit of optimality.

For DNA data storage to become a feasible technology, all aspects of the encoding and decoding pipeline must be optimized. Writing the data into DNA, which is known as DNA synthesis, is currently the most costly part of existing storage systems. As a step toward more efficient synthesis, we study the design of codes that minimize the time and number of required materials needed to produce the DNA strands. We consider a popular synthesis process that builds many strands in parallel in a step-by-step fashion using a fixed supersequence S. The machine iterates through S one nucleotide at a time, and in each cycle, it adds the next nucleotide to a subset of the strands. The synthesis time is determined by the length of S. We show that by introducing redundancy to the synthesized strands, we can significantly decrease the number of synthesis cycles. We derive the maximum amount of information per synthesis cycle assuming S is an arbitrary periodic sequence. To prove our results, we exhibit new connections to cost-constrained codes.

A covering code is a set of codewords with the property that the union of balls, suitably defined, around these codewords covers an entire space. Generally, the goal is to find the covering code with the minimum size codebook. While most prior work on covering codes has focused on the Hamming metric, we consider the problem of designing covering codes defined in terms of insertions and deletions. First, we provide new sphere-covering lower bounds on the minimum possible size of such codes. Then, we provide new existential upper bounds on the size of optimal covering codes for a single insertion or a single deletion that are tight up to a constant factor. Finally, we derive improved upper bounds for covering codes using R≥ 2 insertions or deletions. We prove that codes exist with density that is only a factor O(R log R) larger than the lower bounds for all fixed R. In particular, our upper bounds have an optimal dependence on the word length, and we achieve asymptotic density matching the best known bounds for Hamming distance covering codes.

Weakly-private information retrieval (WPIR) is a variant of the private information retrieval problem in which a user wants to efficiently retrieve a file stored across a set of servers while tolerating some information leakage on the identity of the requested file to the servers. In this paper, we consider WPIR from a single-server database where the information leakage is measured in terms of the mutual information (MI) or maximal leakage (MaxL) privacy metrics. In particular, we establish a connection between the WPIR problem and rate-distortion theory, and fully characterize the optimal tradeoff between the download cost and the allowed information leakage under the MI and MaxL metrics, settling the single-server WPIR capacity.

This paper studies reconstruction of strings based upon their substrings spectrum. Under this paradigm, it is assumed that all substrings of some fixed length are received and the goal is to reconstruct the string. While many existing works assumed that substrings are received error free, we follow in this paper the noisy setup of this problem that was first studied by Gabrys and Milenkovic. The goal of this study is twofold. First we study the setup in which not all substrings in the multispectrum are received, and then we focus on the case where the read substrings are not error free. In each case we provide specific code constructions of strings that their reconstruction is guaranteed even in the presence of failure in either model. We present efficient encoding and decoding maps and analyze the cardinality of the code constructions, while studying the cases where the rates of our codes approach 1.

A functional PIR array code is a coding scheme which encodes some s information bits into a t × m array such that every linear combination of the s information bits has k mutually disjoint recovering sets. Every recovering set consists of some of the array's columns while it is allowed to read at most ℓ encoded bits from every column in order to receive the requested linear combination of the information bits. Functional batch array codes impose a stronger property where every multiset request of k linear combinations has k mutually disjoint recovering sets. Given the values of s, k, t, ℓ, the goal of this paper is to study the optimal value of the number of columns m such that these codes exist. Several lower bounds are presented as well as explicit constructions for several of these parameters.

This paper studies the problem of reconstructing a word given several of its noisy copies. This setup is motivated by several applications, among them is reconstructing strands in DNA-based storage systems. Under this paradigm, a word is transmitted over some fixed number of identical independent channels and the goal of the decoder is to output the transmitted word or some close approximation. The main focus of this paper is the case of two deletion channels and studying the error probability of the maximum-likelihood (ML) decoder under this setup. First, it is discussed how the ML decoder operates. Then, we observe that the dominant error patterns are deletions in the same run or errors resulting from alternating sequences. Based on these observations, it is derived that the error probability of the ML decoder is roughly (3q - 1)/(q - 1) p2, when the transmitted word is any q-ary sequence and p is the channel's deletion probability. We also study the cases when the transmitted word belongs to the Varshamov Tenengolts (VT) code or the shifted VT code. Lastly, the insertion channel is studied as well. These theoretical results are verified by corresponding simulations.

Correcting insertions/deletions as well as substitution errors simultaneously plays an important role in DNA-based storage systems as well as in classical communications. This paper deals with the fundamental task of constructing codes that can correct a single insertion or deletion along with a single substitution. A non-asymptotic upper bound on the size of singledeletion single-substitution correcting codes is derived, showing that the redundancy of such a code of length n has to be at least 2 log n. The bound is presented both for binary and non-binary codes while an extension to single deletion and multiple substitutions is presented for binary codes. An explicit construction of single-deletion single-substitution correcting codes with at most 6 log n + 8 redundancy bits is derived. Note that the best known construction for this problem has to use 3-deletion correcting codes whose best known redundancy is roughly 24 log n.

In graph theory, a tree is one of the more popular families of graphs with a wide range of applications in computer science as well as many other related fields. While there are several distance measures over the set of all trees, we consider here the one which defines the so-called tree distance, defined by the minimum number of edit operations, of removing and adding edges, in order to change one tree into another. From a coding theoretic perspective, codes over the tree distance are used for the correction of edge erasures and errors. However, studying this distance measure is important for many other applications that use trees and properties on their locality and the number of neighbor trees. Under this paradigm, the largest size of code over trees with a prescribed minimum tree distance is investigated. Upper bounds on these codes as well as code constructions are presented. A significant part of our study is dedicated to the problem of calculating the size of the ball of trees of a given radius. These balls are not regular and thus we show that while the star tree has asymptotically the smallest size of the ball, the maximum is achieved for the line tree.

Lifted Reed-Solomon codes and multiplicity codes are two classes of evaluation codes that allow for the design of high-rate codes that can recover every codeword or information symbol from many disjoint sets. Recently, the underlying approaches have been combined to construct lifted bi-variate multiplicity codes, that can further improve on the rate. We continue the study of these codes by providing lower bounds on the rate and distance for lifted multiplicity codes obtained from polynomials in an arbitrary number of variables. Specifically, we investigate a subcode of a lifted multiplicity code formed by the linear span of m-variate monomials whose restriction to an arbitrary line in Fqmis equivalent to a low-degree uni-variate polynomial. We find the tight asymptotic behavior of the fraction of such monomials when the number of variables m is fixed and the alphabet sizeq=2ℓis large. For some parameter regimes, lifted multiplicity codes are then shown to have a better tradeoff between redundancy and the number of disjoint recovering sets for every codeword or information symbol than previously known constructions.

Write-once memory (WOM) is a storage device consisting of binary cells that can only increase their levels. A t-write WOM code is a coding scheme that makes it possible to write t times to a WOM without decreasing the levels of any of the cells. The sum-rate of a WOM code is the ratio between the total number of bits written to the memory during the t writes and the number of cells. It is known that the maximum possible sum-rate of a t-write WOM code is log(t + 1). This is also an achievable upper bound, both by information-theoretic arguments and through explicit constructions. While existing constructions of WOM codes are targeted at the sum-rate, we consider here two more figures of merit. The first one is the complexity of the encoding and decoding maps. The second figure of merit is the convergence rate, defined as the minimum code length n(δ) required to reach a point that is δ-close to the capacity region. One of our main results in this paper is a capacity-achieving construction of two-write WOM codes which has polynomial encoding/decoding complexity while the block length n(δ) required to be δ-close to capacity is significantly smaller than existing constructions. Using these two-write WOM codes, we then obtain three-write WOM codes that approach a sum-rate of 1.809 at relatively short block lengths. We also provide several explicit constructions of finite length three-write WOM codes; in particular, we achieve a sum-rate of 1.716 by using only 93 cells. Finally, we modify our two-write WOM codes to construct ε-error WOM codes of high rates and small probability of failure.

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.

Erasure codes play an important role in storage systems to prevent data loss. In this work, we study a class of erasure codes called Multi-Erasure Locally Recoverable Codes (ME-LRCs) for storage arrays. Compared to previous related works, we focus on the construction of ME-LRCs over small fields. Our main contribution is a general construction of ME-LRCs based on generalized tensor product codes, and an analysis of their erasure-correcting properties. A decoding algorithm tailored for erasure recovery is given, and correctable erasure patterns are identified. We then prove that our construction yields optimal ME-LRCs with a wide range of code parameters, and present some explicit ME-LRCs over small fields. Next, we show that generalized integrated interleaving (GII) codes can be treated as a subclass of generalized tensor product codes, thus defining the exact relation between these codes. Finally, ME-LRCs are investigated in a probabilistic setting. We prove that ME-LRCs based upon a generalized tensor product construction can achieve the capacity of a compound erasure channel consisting of a family of erasure product channels.

In a Private Information Retrieval (PIR) protocol, a user can download a file from a database without revealing the identity of the file to each individual server. A PIR protocol is called t-private if the identity of the file remains concealed even if t of the servers collude. Graph based replication is a simple technique, which is prevalent in both theory and practice, for achieving robustness in storage systems. In this technique each file is replicated on two or more storage servers, giving rise to a (hyper-)graph structure. In this paper we study private information retrieval protocols in graph based replication systems. The main interest of this work is understanding the collusion structures which emerge in the underlying graph. Our main contribution is a 2-replication scheme which guarantees perfect privacy from acyclic sets in the graph, and guarantees partial-privacy in the presence of cycles. Furthermore, by providing an upper bound, it is shown that the PIR rate of this scheme is at most a factor of two from its optimal value for regular graphs. Lastly, we extend our results to larger replication factors and to graph-based coding, a generalization of graph based replication that induces smaller storage overhead and larger PIR rate in many cases.

In this paper we study array-based codes over graphs for correcting multiple node failures. These codes have applications to neural networks, associative memories, and distributed storage systems. We assume that the information is stored on the edges of a complete undirected graph and a node failure is the event where all the edges in the neighborhood of a given node have been erased. A code over graphs is called ρ-node-erasure-correcting if it allows to reconstruct the erased edges upon the failure of any ρ nodes or less. We present a binary optimal construction for double-node-erasure correction together with an efficient decoding algorithm, when the number of nodes is a prime number. Furthermore, we extend this construction for triple-node-erasure-correcting codes when the number of nodes is a prime number and two is a primitive element in ℤn. These codes are at most a single bit away from optimality.

A functional k-Private Information Retrieval (k-PIR) code of dimension s consists of n servers storing linear combinations of s linearly independent information symbols. Any linear combination of the s information symbols can be recovered by k disjoint subsets of servers. The goal is to find the minimum number of servers for given k and s. We provide lower bounds on the minimum number of servers and constructions which yield upper bounds on this number. For k ≤ 4, exact bounds on this number are proved. Furthermore, we provide some asymptotic bounds. The problem coincides with the well known PIR problem based on a coded database to reduce the storage overhead, when each linear combination contains exactly one information symbol. If any multiset of size k of linear combinations from the linearly independent information symbols can be recovered by k disjoint subset of servers, then the servers form a functionalk-batch code. A functional k-batch code is a functional k-PIR code, where all the k linear combinations in the multiset are equal. We provide some bounds on the minimum number of servers for functional k-batch codes. In particular we present a random construction and a construction based on simplex codes, Write-Once Memory (WOM) codes, and Random I/O (RIO) codes.

A sequence s = (s1,⋯,sn) is called a (b, h)-constrained de Bruijn sequence if all substrings of length h starting within b consecutive positions are distinct. A set of (b, h)-constrained de Bruijn sequences is called a (b, h)-constrained de Bruijn code. A (b, h)-constrained de Bruijn sequence was constructed and used as a component of a code correcting multiple limited-shift-errors in racetrack memories. In this work, we show that a (b, h)-constrained de Bruijn code can correct deletions and sticky-insertions and also can determine the locations of these errors in an ℓ-symbol read channel. We also show that it is possible to use sequences from a (b, h)-constrained de Bruijn code to construct a code correcting shift-errors in racetrack memories. As a consequence, we improve the rates on previous known codes.It is shown in this work that a (b, h)-constrained de Bruijn code is a constrained code avoiding a set of specific patterns. Finally, we present some techniques to compute the maximum asymptotic rate and find some efficient encoding/decoding algorithms for (b, h)-constrained de Bruijn codes.

In this work, we propose and study a new class of non-binary rewriting codes, called write ℓ-step-up memories (WℓM) codes. From an information-theoretic point of view, this coding scheme is a generalization of non-binary write-once memories (WOM) codes. From a practical point of view, this coding scheme can be used not only to increase the lifetime of flash memories but also mitigate their over-shooting problem. We first provide an exact formula for the capacity region and the maximum sum-rate of WℓM codes. Lastly, we present several explicit constructions of high-rate WℓM codes with efficient encoding/decoding algorithms.

Private Information Retrieval (PIR) array codes were introduced by Fazeli et al. (2015) to reduce the storage overhead in designing PIR protocols. Blackburn and Etzion (2017) introduced the (virtual server) rate to quantify the storage overhead of the codes, and when s > 2 (here, 1/s is the proportion of the database storing in one server), they gave a general construction of PIR array codes with the highest rate known so far. In this paper, we generalize their construction and reduce the number of servers, while maintaining the rate. In order to give PIR array codes with significantly fewer servers, we also construct classes of codes with a smaller rate s/2s-1.

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.

A private proximity retrieval (PPR) scheme is a protocol which allows a user to retrieve the identities of all records in a database that are within some distance r from the user's record x. The user's privacy at each server is given by the fraction of the record x that is kept private. The distortion of a PPR scheme measures how accurately the user can calculate the identities of the desired files. We assume that each server stores a copy of the database. This paper studies protocols that offer trade-offs between perfect privacy and low computational complexity and storage.In this paper, this study is initiated. The work focuses on the case when the records are binary vectors together with the Hamming distance. In particular, for a given privacy level, we investigate the minimum number of servers that guarantee a prescribed distortion value. The collusions of pairs of servers as well as other distance measures are investigated.

Motivated by DNA-based data storage, we investigate a system where digital information is stored in an unordered set of several vectors over a finite alphabet. Each vector begins with a unique index that represents its position in the whole data set and does not contain data. This paper deals with the design of error-correcting codes for such indexed sets in the presence of substitution errors. We propose a construction that efficiently deals with the challenges that arise when designing codes for unordered sets. Using a novel mechanism, called anchoring, we show that it is possible to combat the ordering loss of sequences with only a small amount of redundancy, which allows to use standard coding techniques, such as tensor-product codes to correct errors within the sequences. We finally derive upper and lower bounds on the achievable redundancy of codes within the considered channel model and verify that our construction yields a redundancy that is close to the best possible achievable one. Our results surprisingly suggest that it requires less redundancy to correct errors in the indices than in the data part of vectors.

Private information retrieval (PIR) protocols make it possible to retrieve a file from a database without disclosing any information about the identity of the file being retrieved. These protocols have been rigorously explored from an information-theoretic perspective in recent years. While existing protocols strictly impose that no information is leaked on the file's identity, this work initiates the study of the tradeoffs that can be achieved by relaxing the requirement of perfect privacy. In case the user is willing to leak some information on the identity of the retrieved file, we study how the PIR rate, as well as the upload cost and access complexity, can be improved. For the particular case of replicated servers, we propose two weakly-private information retrieval schemes based on two recent PIR protocols and a family of schemes based on partitioning. Lastly, we compare the performance of the proposed schemes.

A new family of codes, calledclustering-correcting codes, is presented in this paper. This family of codes is motivated by the special structure of the data that is stored in DNA-based storage systems. The data stored in these systems has the form of unordered sequences, also calledstrands, and every strand is synthesized thousands to millions of times, where some of these copies are read back during sequencing. Due to the unordered structure of the strands, an important task in the decoding process is to place them in their correct order. This is usually accomplished by allocating part of the strand for an index. However, in the presence of errors in the index field, important information on the order of the strands may be lost. Clustering-correcting codes ensure that if the distance between the index fields of two strands is small, their data fields have large distance. It is shown how this property enables to place the strands together in their correct clusters even in the presence of errors. We present lower and upper bounds on the size of clustering-correcting codes and an explicit construction of these codes which uses only a single symbol of redundancy. The results are first presented for the Hamming metric and are then extended for the edit distance.

The sequence reconstruction problem corresponds to a model in which a sequence from some code is transmitted over several noisy channels. The channels are almost independent as it is only required that their outputs are different. The main problem under this paradigm is to determine the minimum number of channels required to reconstruct the transmitted sequence. This problem is equivalent to finding the maximum intersection size between two balls of any possible two inputs, where the balls are all possible channel outputs. Motivated by the error behavior in the DNA storage channel, this work extends this study to the case where the channels are prone to substitutions, insertions, and deletions. For the case of only substitutions, we also present a decoder of optimal complexity, which improves upon a recent construction of such a decoder. Lastly, it is also studied how the decoder is simplified in case there are more channels than the minimum required number.

In this paper we study array-based codes over graphs for correcting multiple node failures. These codes have applications to neural networks, associative memories, and distributed storage systems. We assume that the information is stored on the edges of a complete undirected graph and a node failure is the event where all the edges in the neighborhood of a given node have been erased. A code over graphs is called ρ-node-erasure-correcting if it allows to reconstruct the erased edges upon the failure of any ρ nodes or less. We present a binary optimal construction for double-node-erasure correction together with an efficient decoding algorithm, when the number of nodes is a prime number. Furthermore, we extend this construction for triple-node-erasure-correcting codes when the number of nodes is a prime number and two is a primitive element in Zn. These codes are at most a single bit away from optimality.

Private information retrieval has been reformulated in an information-theoretic perspective in recent years. The two most important parameters considered for a PIR scheme in a distributed storage system are the storage overhead and PIR rate. The complexity of the computations done by the servers for the various tasks of the distributed storage system is an important parameter in such systems which didn't get enough attention in PIR schemes. As a consequence, we take into consideration a third parameter, the access complexity of a PIR scheme, which characterizes the total amount of data to be accessed by the servers for responding to the queries throughout a PIR scheme. We use a general covering codes approach as the main tool for improving the access complexity. With a given amount of storage overhead, the ultimate objective is to characterize the tradeoff between the rate and access complexity of a PIR scheme. This covering codes approach raises a new interesting coding problem of generalized coverings similarly to the well-known generalized Hamming weights.

A functional k-PIR code of dimension s consists of n servers storing linear combinations of s linearly independent information symbols. Any linear combination of the s information symbols can be recovered by k disjoint subsets of servers (the reason for this somehow abused definition will be explained in the sequel). The goal is to find the smallest number of servers for given k and s. We provide lower bounds on the number of servers and constructions which yield upper bounds. For k ≤ 4 we provide exact bounds on the number of servers. Furthermore, we provide some asymptotic bounds. The problem coincides with the well known private information retrieval problem based on a coded database to reduce the storage overhead. If any multiset of size k of linear combinations from the linearly independent information symbols can be recovered by k disjoint subset of servers, then the servers form a functional k-batch code. A functional k-batch code is also a functional k-PIR, where all the k linear combinations in the multiset are equal. We provide some bounds on the number of servers for functional k-batch codes. In particular we present a random construction and a construction based on simplex codes, WOM codes, and RIO codes.

Non-volatile resistive memories, such as phase change memories and resistive random access memories, have attracted significant attention recently due to their scalability, speed, and rewritability. However, in order to use these memories in large-scale memory and storage systems, the limited endurance deficiency of these memories must be addressed. In a recent paper, we proposed a new coding scheme, called endurance-limited memories (ELM) codes, which increases the endurance of these memories by limiting the number of cell programming operations. Namely, an l-change t-write ELM code is a coding scheme that allows to write t messages into some n binary cells while guaranteeing that the number of times each cell is programmed is at most l. There are several models of these codes which depend upon the information that is available to the encoder and the decoder before each write. This information can be one of the following three options: 1. the number of times each cell has been programmed, 2. only the memory state before programming, or 3. no information is available on the cells' state or previous writes. In this paper, we study the models in which the decoder knows on each write the number of times each cell has been programmed before the last write, while for the encoder we consider the aforementioned three possibilities.

In this paper, we study a model that mimics the programming operation of memory cells. This model was first introduced by Lastras-Montanoet al.for continuous-alphabet channels, and later by Bunte and Lapidoth for discrete memoryless channels (DMC). Under this paradigm we assume that cells are programmed sequentially and individually. The programming process is modeled as transmission over a channel, such that it is possible to read the cell state in order to determine its programming success, and in case of programming failure, to reprogram the cell again. Reprogramming a cell can reduce the bit error rate, however this comes with the price of increasing the overall programming time and thereby affecting the writing speed of the memory. Aniterative programming schemeis an algorithm which specifies the number of attempts to program each cell. Given the programming channel and constraints on the average and maximum number of attempts to program a cell, we study programming schemes which maximize the number of bits that can be reliably stored in the memory. We extend the results by Bunte and Lapidoth and study this problem when the programming channel is either discrete-input memoryless symmetric channel (including the BSC,BEC, BI-AWGN) or the$Z$channel. For the BSC and the BEC our analysis is also extended for the case where the error probabilities on consecutive writes are not necessarily the same. Lastly, we also study a related model which is motivated by the synthesis process of DNA molecules.

Paved by recent advances in sequencing and synthesis technologies, DNA has evolved to a competitive medium for long-term data storage. In this paper we conduct an information theoretic study of the storage channel-the entity that formulates the relation between stored and sequenced strands. In particular, we derive an upper bound on the Shannon capacity of the channel. In our channel model, we incorporate the main attributes that characterize DNA-based data storage. That is, information is synthesized on many short DNA strands, and each strand is copied many times. Due to the storage and sequencing methods, the receiver draws strands from the original sequences in an uncontrollable manner, where it is possible that copies of the same sequence are drawn multiple times. Additionally, due to imperfections, the obtained strands can be perturbed by errors. We show that for a large range of parameters, the channel decomposes into sub-channels from each input sequence to multiple output sequences, so-called clusters. The cluster sizes hereby follow a Poisson distribution. Furthermore, the ordering of sub-channels is unknown to the receiver. Our results can be used to guide future experiments for DNA-based data storage by giving an upper bound on the achievable rate of any error-correcting code. We further give a detailed discussion and intuitive interpretation of the channel that provide insights about the nature of the channel and can inspire new ideas for error-correcting codes and decoding methods.

Partial MDS (PMDS) codes are a class of erasurecorrecting array codes that combine local correction of the rows with global correction of the array. An m × n array code is called an (r; s) PMDS code if each row belongs to an [n, n - r, r + 1] MDS code and the code can correct erasure patterns consisting of r erasures in each row together with s more erasures anywhere in the array. While a recent construction by Calis and Koyluoglu generates (r; s) PMDS codes for all r and s, its field size is exponentially large. In this paper, a family of PMDS codes with field size O (max{m, nr+s}s) is presented for the case where r = O(1), s = O(1).

Motivated by the error behavior in the DNA storage channel, in this paper, we extend the previously studied sequence reconstruction problem by Levenshtein. The reconstruction problem studies the model in which the information is read through multiple noisy channels, and the decoder, which receives all channel estimations, is required to decode the information. For the combinatorial setup, the assumption is that all the channels cause at most some t errors. Levenshtein considered the case in which all the channels have the same behavior, and we generalize this model and assume that the channels are not identical. Thus, different channels may cause different maximum numbers of errors. For example, we assume that there are N channels, which cause at most t1or t2errors, where t12, and the number of channels with at most t1errors is at least pN, for some fixed 0 <; p <; 1. If the information codeword belongs to a code with minimum distance d, the problem is then to find the minimum number of channels that guarantees successful decoding in the worst case. A different problem we study in this paper is where the number of channels is fixed, and the question is finding the minimum distance d that provides exact reconstruction. We study these problems and show how to apply them for the cases of substitutions and transpositions.

Mutually uncorrelated (MU) codes are a class of codes in which no proper prefix of one codeword is a suffix of another codeword. These codes were originally studied for synchronization purposes and recently, Yazdi et al. showed their applicability to enable random access in DNA storage. In this paper,we follow the research of Yazdi et al. and study MU codes along with their extensions to correct errors and balanced codes. We first review a well-known construction of MU codes and study the asymptotic behavior of its cardinality. This task is accomplished by studying a special class of run-length limited codes that impose the longest run of zeros to be at most some function of the codewords length. We also present an efficient algorithm for this class of constrained codes and show how to use this analysis for MU codes. Next, we extend the results on the run-length limited codes in order to study (dh, dm)-MU codes that impose a minimum Hamming distance of dh between different codewords and dmbetween prefixes and suffixes. In particular, we show an efficient construction of these codes with nearly optimal redundancy. We also provide similar results for the edit distance and balanced MU codes. Last, we draw connections to the problems of comma-free and prefix synchronized codes.

Synthesis of DNA molecules offers unprecedented advances in storage technology. Yet, the microscopic world in which these molecules reside induces error patterns that are fundamentally different from their digital counterparts. Hence, to maintain reliability in reading and writing, new coding schemes must be developed. In a reading technique called shotgun sequencing, a long DNA string is read in a sliding window fashion, and a profile vector is produced. It was recently suggested by Kiah et al. that such a vector can represent the permutation which is induced by its entries, and hence a rank-modulation scheme arises. Although this interpretation suggests high error tolerance, it is unclear which permutations are feasible and how to produce a DNA string whose profile vector induces a given permutation. In this paper, by observing some necessary conditions, an upper bound for the number of feasible permutations is given. Furthermore, a technique for deciding the feasibility of a permutation is devised. By using insights from this technique, an algorithm for producing a considerable number of feasible permutations is given, which applies to any alphabet size and any window length.

We (people) are memory machines. Our decision processes, emotions, and interactions with the world around us are based on and driven by associations to our memories. This natural association paradigm will become critical in future memory systems, namely, the key question will not be “How do I store more information?” but rather “Do I have the relevant information? How do I retrieve it?” The focus of this paper is to make a first step in this direction. We define and solve a very basic problem in associative retrieval. Given a word W, the words in the memory, which are t-associated with W, are the words in the ball of radius t around W. In general, given a set of words, say W, X, and Y, the words that are t-associated with 1W, X, Y are those in the memory that are within distance t from all the three words. Our main goal is to study the maximum size of the t-associated set as a function of the number of input words and the minimum distance of the words in memory- we call this value the uncertainty of an associative memory. In this paper, we consider the Hamming distance and derive the uncertainty of the associative memory that consists of all the binary vectors with an arbitrary number of input words. In addition, we study the retrieval problem, namely, how do we get the t-associated set given the inputs? We note that this paradigm is a generalization of the sequences reconstruction problem that was proposed by Levenshtein (2001). In this model, a word is transmitted over multiple channels. A decoder receives all the channel outputs and decodes the transmitted word. Levenshtein computed the minimum number of channels that guarantee a successful decoder-this value happens to be the uncertainty of an associative memory with two input words.

Error-correcting codes play an important role in storage systems to maintain data integrity. In this work, we propose a new class of linear error- correcting codes, called ladder codes, whose codeword structure consists of multiple codewords of certain component codes and also their shared redundancy. First, we give a general construction for an m-level ladder code, determine the code length and dimension, and also derive a lower bound d*Lon the minimum distance. Some examples of ladder codes are presented. Then, we study correctable error-erasure patterns of ladder codes and give a corresponding decoding algorithm. Finally, we compare a two-level ladder code with a concatenated code, and show that the former can outperform the latter in many cases. Ladder codes have potential to be used for data protection in flash memories where only a few pages may suffer from severe errors in a block.

In this work, we study limited-shift errors in racetrack memories and propose several schemes to combat these errors. There are two kinds of shift errors, namely under-shift errors, that can be modeled as sticky-insertions and limited-over-shift errors, that can be modeled as bursts of deletions of limited length. One approach to tackle the problem is to use deletion/sticky-insertion-correcting codes. Using this approach, we present a new family of asymptotically optimal codes that correct multiple bursts of deletions of limited length and any number of sticky insertions. We then study another approach that takes advantage of the special features of racetrack memories and the ability to add extra heads for redundancy. Here, we propose how to place the extra heads and construct codes to correct these shift errors.

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.

In this paper we study error-correcting codes for the storage of data in synthetic deoxyribonucleic acid (DNA). We investigate a storage model where a data set is represented by an unordered set of M sequences, each of length L. Errors within that model are a loss of whole sequences and point errors inside the sequences, such as insertions, deletions and substitutions. We derive Gilbert-Varshamov lower bounds and sphere packing upper bounds on achievable cardinalities of error-correcting codes within this storage model. We further propose explicit code constructions than can correct errors in such a storage system that can be encoded and decoded efficiently. Comparing the sizes of these codes to the upper bounds, we show that many of the constructions are close to optimal.

Resistive memories, such as phase change memories and resistive random access memories have attracted significant attention in recent years due to their better scalability, speed, rewritability, and yet non-volatility. However, their limited endurance is still a major drawback that has to be improved before they can be widely adapted in large-scale systems.In this work, in order to reduce the wearout of the cells, we propose a new coding scheme, called Endurance-Limited Memories (ELM) code, that increases the endurance of these memories by limiting the number of cell programming operations. Namely, an ℓ-change t-write ELM code is a coding scheme that allows to write t messages into some n binary cells while guaranteeing that each cell is programmed at most ℓ times. In case ℓ = 1 then these codes coincide with the well-studied write-once memory (WOM) codes. We study four models of these codes which depend upon whether the encoder knows, on each write, the number of times each cell was programmed or only knows its state. For the decoder, we consider two cases which depend upon whether the decoder knows the previous state of the memory or not. For two of these models we fully characterize the capacity regions and present partial results for another model. Although only one of the four models is suitable for resistive memories, we consider all four in order to carry out a complete information-theory study of endurance-limited codes.

In this work, we study a special case of the reconstruction problem in order to combat position errors in racetrack memories. In these memories, the information is stored in magnetic cells that can be sensed by shifting them under read heads. However, since this shifting operation is not error free, recent work has been dedicated towards correcting these so-called position errors, which manifest themselves as deletions and sticky insertions. A deletion is the event where the cells are over-shifted, and a sticky insertion occurs when the cells are not shifted.We first present a code construction that uses two heads to correct two deletions with at most log2(log2n) +4 redundant bits. This result improves upon a recent one that requires roughly log2n redundant bits. We then extend this construction to correct d deletions using d heads with at most log2(log2n) +c redundant bits. Lastly, we extend our results and derive codes for the classical reconstruction problem by Levenshtein over the insertion/deletion channel.

When sensitive data is stored in the cloud, the only way to ensure its secrecy is by encrypting it before it is uploaded. The emerging multi-cloud model, in which data is stored redundantly in two or more independent clouds, provides an opportunity to protect sensitive data with secret-sharing schemes. Both data-protection approaches are considered computationally expensive, but recent advances reduce their costs considerably: (1) Hardware acceleration methods promise to eliminate the computational complexity of encryption, but leave clients with the challenge of securely managing encryption keys. (2) Secure RAID, a recently proposed scheme, minimizes the computational overheads of secret sharing, but requires non-negligible storage overhead and random data generation. Each data-protection approach offers different tradeoffs and security guarantees. However, when comparing them, it is difficult to determine which approach will provide the best application-perceived performance, because previous studies were performed before their recent advances were introduced.

The problem of storing permutations in a distributed manner arises in several common scenarios, such as efficient updates of a large, encrypted, or compressed data set. This problem may be addressed in either a combinatorial or a coding approach. The former approach boils down to presenting large sets of permutations with locality, that is, any symbol of the permutation can be computed from a small set of other symbols. In the latter approach, a permutation may be coded in order to achieve locality. This paper focuses on the combinatorial approach. We provide upper and lower bounds for the maximal size of a set of permutations with locality, and provide several simple constructions which attain the upper bound. In cases where the upper bound is not attained, we provide alternative constructions using Reed-Solomon codes, permutation polynomials, and multi-permutations.

Switch codes, first proposed by Wang et al., are codes that are designed to increase the parallelism of data writing and reading processes in network switches. A network switch is required to write n incoming packets and read k outgoing packets while using m memory banks, each able to write and read one packet per time unit. Each set of n packets written to the switch simultaneously is called a generation. The objective is to store the packets in the banks such that every request of k packets, which can belong to previous generations, can be handled by reading at most one packet from every bank. In this paper, we study a new type of switch codes that can simultaneously deliver large packet request and good coding rate. These attractive features are achieved by relaxing the request model to a natural sub-class we call consecutive requests. For this new request model, we define a new type of codes called consecutive switch codes. These codes are studied in both the computational and combinatorial models, corresponding to whether the data can be encoded or not. For binary codes, we also study an intermediate model in which a coded packet is formed by the XOR operations of at most two input packets. We present several code constructions and prove the optimality of one family of these codes by providing the corresponding lower bound. Finally, we introduce a construction of conventional switch codes, which improves upon the best known results for the case n = k.

Racetrack memory is a new technology, which utilizes magnetic domains along a nanoscopic wire in order to obtain extremely high storage density. In racetrack memory, each magnetic domain can store a single bit of information, which can be sensed by a reading port (head). The memory is structured like a tape, which supports a shift operation that moves the domains to be read sequentially by the head. In order to increase the memory's speed, prior work studied how to minimize the latency of the shift operation, while the no less important reliability of this operation has received only a little attention. In this paper, we design codes, which combat shift errors in racetrack memory, called position errors, namely, shifting the domains is not an error-free operation and the domains may be over shifted or are not shifted, which can be modeled as deletions and sticky insertions. While it is possible to use conventional deletion and insertion-correcting codes, we tackle this problem with the special structure of racetrack memory, where the domains can be read by multiple heads. Each head outputs a noisy version of the stored data and the multiple outputs are combined in order to reconstruct the data. This setup is a special case of the reconstruction problem studied by Levenshtein, however, in our case, the position errors from different heads are correlated. We will show how to take advantage of this special feature of racetrack memories in order to construct codes correcting deletions and sticky insertions. In particular, under this paradigm, we will show that it is possible to correct, with at most a single bit of redundancy, d deletions with d+1 heads if the heads are well separated. Similar results are provided for burst of deletions, sticky insertions, and combinations of both deletions and sticky insertions.

The sequence reconstruction problem, first proposed by Levenshtein, models the setup in which a sequence from some set is transmitted over several channels, and the decoder receives the outputs from every channel. The channels are almost independent as it is only required that all outputs are different from each other. The main problem of interest is to determine the minimum number of channels required to reconstruct the transmitted sequence. In the combinatorial context, the problem is equivalent to finding the maximum intersection between two balls of radius t, where the distance between their centers is at least d. The setup of this problem was studied before for several error metrics such as the Hamming metric, the Kendalltau metric, and the Johnson metric. In this paper, we extend the study initiated by Levenshtein for reconstructing sequences over the deletion channel. While he solved the case where the transmitted sequence can be arbitrary, we study the setup, where the transmitted sequence belongs to a single-deletion-correcting code and there are t deletions in every channel. Under this paradigm, we study the minimum number of different channel outputs in order to construct a successful decoder.

Motivated by applications in DNA-based storage, we introduce the new problem of code design in the Damerau metric. The Damerau metric is a generalization of the Levenshtein distance which, in addition to deletions, insertions, and substitution errors also accounts for adjacent transposition edits. We first provide constructions for codes that may correct either a single deletion or a single adjacent transposition and then proceed to extend these results to codes that can simultaneously correct a single deletion and multiple adjacent transpositions. We conclude with constructions for joint block deletion and adjacent block transposition error-correcting codes.

Flash memory is prevalent in modern servers and devices. Coupled with the scaling down of flash technology, the popularity of flash memory motivates the search for methods to increase flash reliability and lifetime. Erasures are the dominant cause of flash cell wear, but reducing them is challenging because flash is a write-once medium— memory cells must be erased prior to writing. An approach that has recently received considerable attention relies on write-once memory (WOM) codes, designed to accommodate additional writes on write-once media. However, the techniques proposed for reusing flash pages with WOM codes are limited in their scope. Many focus on the coding theory alone, whereas others suggest FTL designs that are application specific, or not applicable due to their complexity, overheads, or specific constraints of multilevel cell (MLC) flash. This work is the first that addresses all aspects of page reuse within an end-to-end analysis of a general-purpose FTL on MLC flash. We use a hardware evaluation setup to directly measure the short- and long-term effects of page reuse on SSD durability and energy consumption, and show that FTL design must explicitly take them into account. We then provide a detailed analytical model for deriving the optimal garbage collection policy for such FTL designs, and for predicting the benefit from reuse on realistic hardware and workload characteristics.

In this work we study two families of codes with availability, namely private information retrieval (PIR) codes and batch codes. While the former requires that every information symbol has k mutually disjoint recovering sets, the latter asks this property for every multiset request of k information symbols. The main problem under this paradigm is to minimize the number of redundancy symbols. We denote this value by rp(n, k), rB(n, k), for PIR, batch codes, respectively, where n is the number of information symbols. Previous results showed that for any constant k, rp(n, k) = Θ(√n) and rB(n, k) = O(√n log(n)). In this work we study the asymptotic behavior of these codes for non-constant k and specifically for k = Θ(nϵ). We also study the largest value of k such that the rate of the codes approaches 1, and show that for all eP(n, nϵ) = o(n), while for batch codes, this property holds for all ϵ <; 0.5.

Racetrack memory is a new technology which utilizes magnetic domains along a nanoscopic wire in order to obtain extremely high storage density. In racetrack memory, each magnetic domain can store a single bit of information, which can be sensed by a reading port (head). The memory has a tape-like structure which supports a shift operation that moves the domains to be read sequentially by the head. In order to increase the memory's speed, prior work studied how to minimize the latency of the shift operation, while the no less important reliability of this operation has received only a little attention. In this work we design codes which combat shift errors in racetrack memory, called position errors. Namely, shifting the domains is not an error-free operation and the domains may be over-shifted or are not shifted, which can be modeled as deletions and sticky insertions. While it is possible to use conventional deletion and insertion-correcting codes, we tackle this problem with the special structure of racetrack memory, where the domains can be read by multiple heads. Each head outputs a noisy version of the stored data and the multiple outputs are combined in order to reconstruct the data. Under this paradigm, we will show that it is possible to correct, with at most a single bit of redundancy, d deletions with d + 1 heads if the heads are well-separated. Similar results are provided for burst of deletions, sticky insertions and combinations of both deletions and sticky insertions.

Write-once memory (WOM) is a storage device consisting of binary cells which can only increase their levels. A t-write WOM code is a coding scheme which allows to write t times to the WOM without decreasing the levels of the cells. The sum-rate of a WOM code is the ratio between the total number of bits written to the memory and the number of cells. It is known that the maximum sum-rate of a t-write WOM code is log(t + 1). This is also an achievable upper bound both by information theory arguments and explicit WOM code constructions. While existing constructions of WOM codes were targeted to increase the sum-rate, we consider here two more figures of merit in evaluating the constructions. The first one is the complexity of the encoding and decoding maps of the code. The second one is called the convergence rate, and is defined to be the minimum code length n(ε) in order to reach e close to a point in the capacity region. One of our main results in the paper is a specific capacity achieving construction for two-write WOM codes which has polynomial complexity and relatively short block length to be ε close to the capacity. Using these two-write WOM codes, we obtain three-write WOM codes that approach sum-rate 1.809 with relatively short block lengths. Finally, we provide another construction of three-write WOM that achieves sum-rate 1.71 by using only 100 cells.

Partial MDS (PMDS) codes are a class of erasure-correcting array codes which combine local correction of the rows with global correction of the array. An m × n array code is called an (r; s) PMDS code if each row belongs to an [n, n - r, r + 1] MDS code and the code can correct erasure patterns consisting of r erasures in each row together with s more erasures anywhere in the array. While a recent construction by Calis and Koyluoglu generates (r; s) PMDS codes for all r and s, its field size is exponentially large. In this paper, a family of PMDS codes with field size O(max{m, nr+s}s) is presented.

We prove that there exist non-linear binary cyclic codes that attain the Gilbert-Varshamov bound.

Motivated by the error behavior in DNA storage channels, in this work we extend the previously studied sequence reconstruction problem by Levenshtein. The reconstruction problem studies the model in which the information is read through multiple noisy channels, and the decoder, which receives all channel estimations, is required to decode the information. For the combinatorial setup, the assumption is that all the channels cause at most some t errors. However, since the channels do not necessarily have the same behavior, we generalize this model and assume that the channels are not identical and thus may cause a different maximum number of errors. For example, we assume that there are N channels that cause at most t1or t2errors, where t12, and the number of channels with at most t1errors is at least [pN], for some fixed 0 <; p <; 1. If the information codeword belongs to a code with minimum distance d, the problem is then to find the minimum number of channels that guarantees successful decoding in the worst case.

Mutually Uncorrelated (MU) codes are a class of codes in which no proper prefix of one codeword is a suffix of another codeword. These codes were originally studied for synchronization purposes and recently, Yazdi et al. showed their applicability to enable random access in DNA storage. In this work we follow the research of Yazdi et al. and study MU codes along with their extensions to correct errors and balanced codes. We first review a well known construction of MU codes and study the asymptotic behavior of its cardinality. Then, we present an efficient algorithm for MU codes with linear encoding and decoding complexity. Next, we extend these results for (dh, dm)-MU codes that impose a minimum Hamming distance of dh between different codewords and dmbetween prefixes and suffixes. Particularly we show an efficient construction of these codes with nearly optimal redundancy and draw connections to the problem of comma-free and prefix synchronized codes. Lastly, we provide similar results for the edit distance and balanced MU codes.

Synthesis of DNA molecules offers unprecedented advances in storage technology. Yet, the microscopic world in which these molecules reside induces error patterns that are fundamentally different from their digital counterparts. Hence, to maintain reliability in reading and writing, new coding schemes must be developed. In a reading technique called shotgun sequencing, a long DNA string is read in a sliding window fashion, and a profile vector is produced. It was recently suggested by Kiah et al. that such a vector can represent the permutation which is induced by its entries, and hence a rank modulation scheme arises. Although this interpretation suggests high error tolerance, it is unclear which permutations are feasible, and how to produce a DNA string whose profile vector induces a given permutation. In this paper, by observing some necessary conditions, an upper bound for the number of feasible permutations is given. Further, a technique for deciding the feasibility of a permutation is devised. By using this technique, an algorithm for producing a considerable number of feasible permutations is given, which applies to any alphabet size and any window length.

Motivated by systems where the information is represented by a graph, such as neural networks, associative memories, and distributed systems, we present in this work a new class of codes, called codes over graphs. Under this paradigm, the information is stored on the edges of an undirected graph, and a code over graphs is a set of graphs. A node failure is the event where all edges in the neighborhood of the failed node have been erased. We say that a code over graphs can tolerate ρ node failures if it can correct the erased edges of any ρ failed nodes in the graph. While the construction of such codes can be easily accomplished by MDS codes, their field size has to be at least), O(n2) when n is the number of nodes in the graph. In this work we present several constructions of codes over graphs with smaller field size. In particular, we present optimal codes over graphs correcting two node failures over the binary field, when the number of nodes in the graph is a prime number. We also present a construction of codes over graphs correcting ρ node failures for all ρ over a field of size at least (n + 1)/2 - 1, and show how to improve this construction for optimal codes when ρ = 2,3.

Batch codes, first introduced by Ishai, Kushilevitz, Ostrovsky, and Sahai, mimic a distributed storage of a set of n data items on m servers, in such a way that any batch of k data items can be retrieved by reading at most some t symbols from each server. Combinatorial batch codes, are replication-based batch codes in which each server stores a subset of the data items. In this paper, we propose a generalization of combinatorial batch codes, called multiset combinatorial batch codes (MCBCs), in which n data items are stored in m servers, such that any multiset request of k items, where any item is requested at most r times, can be retrieved by reading at most t items from each server. The setup of this new family of codes is motivated by recent work on codes which enable high availability and parallel reads in distributed storage systems. The main problem under this paradigm is to minimize the number of items stored in the servers, given the values of n, m, k, r, t, which is denoted by N(n, k, m, t; r). We first give a necessary and sufficient condition for the existence of MCBCs. Then, we present several bounds on N(n, k, m, t; r) and constructions of MCBCs. In particular, we determine the value of N(n, k, m, 1; r) for any n ≥ ⌊k - 1/r⌋ (k-1m) - (m - k + 1)A(m, 4, k - 2), where A(m, 4, k - 2) is the maximum size of a binary constant weight code of length m, distance four and weight k - 2. We also determine the exact value of N(n, k, m, 1; r) when r ϵ {k, k - 1} or k = m.

Racetrack memory is a new technology which utilizes magnetic domains along a nanoscopic wire in order to obtain extremely high storage density. In racetrack memory, each magnetic domain can store a single bit of information, which can be sensed by a reading port (head). The memory is structured like a tape which supports a shift operation that moves the domains to be read sequentially by the head. In order to increase the memory's speed, prior work studied how to minimize the latency of the shift operation, while the no less important reliability of this operation has received only a little attention. In this work we continue our recent study and design codes which combat shift errors in racetrack memory, called position errors. Namely, shifting the domains is not an error-free operation and the domains may be over-shifted or are not shifted, which can be modeled as deletions and sticky insertions. While it is possible to use conventional deletion and insertion-correcting codes, we tackle this problem with the special structure of racetrack memory, where the domains can be read by multiple heads. We will show how to take advantage of this special feature of racetrack memories in order to construct codes correcting deletions and sticky insertions.

In this work we continue the study of a new class of codes, called codes over graphs. Here we consider storage systems where the information is stored on the edges of a complete directed graph with n nodes. The failure model we consider is of node failures which are erasures of all edges, both incoming and outgoing, connected to the failed node. It is said that a code over graphs is a ρ-node-erasure-correcting code if it can correct the failure of any ρ nodes in the graphs of the code. While the construction of such optimal codes is an easy task if the field size is O(n2), our main goal in the paper is the construction of codes over smaller fields. In particular, our main result is the construction of optimal binary codes over graphs which correct two node failures with a prime number of nodes.

Write-once memory (WOM) is a storage device consisting of q-ary cells that can only increase their value. A WOM code is a coding scheme that allows writing multiple times to the memory without decreasing the levels of the cells. In the conventional model, it is assumed that the encoder can read the memory state before encoding, while the decoder reads only the memory state after encoding. However, there are three more models in this setup, which depend on whether the encoder and the decoder are informed or uninformed with the previous state of the memory. These four models were first introduced by Wolf et al., where they extensively studied the WOM capacity in these models for the binary case. In the non-binary setup, only the model, in which the encoder is informed and the decoder is not, was studied by Fu and Vinck. In this paper, we first present constructions of WOM codes in the models where the encoder is uninformed with the memory state (that is, the encoder cannot read the memory prior to encoding). We then study the capacity regions and maximum sum-rates of non-binary WOM codes for all four models. We extend the results by Wolf et al. and show that the capacity regions for the models in which the encoder is informed and the decoder is informed or uninformed in both the ϵ-error and the zero-error cases are all identical. We also find the ϵ-error capacity region; in this case, the encoder is uninformed and the decoder is informed and show that, in contrary to the binary case, it is a proper subset of the capacity region in the first two models. Several more results on the maximum sum-rate are presented as well.

We consider the communication of information in the presence of synchronization errors. Specifically, we consider permutation channels in which a transmitted codeword x = (x1, ... , xn) is corrupted by a permutation π ∈ Snto yield the received wordy = (y1, . . . , yn), where yi= xπ(i). We initiate the study of worst case (or zero-error) communication over permutation channels that distort the information by applying permutations π, which are limited to displacing any symbol by at most r locations, i.e., permutations π with weight at most r in the ℓ∞-metric. We present direct and recursive constructions, as well as bounds on the rate of such channels for binary and general alphabets. Specific attention is given to the case of r = 1.

Switch codes, first proposed by Wang et al., are codes that are designed to increase the parallelism of data writing and reading processes in network switches. A network switch consists of n input ports, k output ports, and m banks which store new arriving packets from the input ports in each time slot, called a generation. The objective is to store the packets in the banks such that every request of k packets by the output ports, which can be from previous generations, can be handled by reading at most one packet from every bank. In this paper we study a new type of switch codes that can simultaneously deliver large symbol requests and good coding rate. These attractive features are achieved by relaxing the request model to a natural sub-class we call consecutive requests. For this new request model we define a new type of codes called consecutive switch codes. These codes are studied in both the computational and combinatorial models, corresponding to whether the data can be encoded or not. We present several code constructions and prove the optimality of one family of these codes by providing the corresponding lower bound. Lastly, we introduce a construction of switch codes for the case n = k, which improves upon the best known results for this case.

We study the problem of write disturbs due to write sneak paths in memristor crossbar arrays. A write sneak path is a bit configuration in the array that causes a write of one cell to undesirably flip the value of another cell. We study the configurations that cause such write sneak paths, and characterize them in terms of tight constraints to prevent them. We show that thanks to the flexibility to choose the write order, the resulting constraints are milder compared to known similar ones for read sneak paths. In addition, we derive the array constraints when parallel write is allowed in the rows or column only, and in both the rows and columns.

The sequence-reconstruction problem, first proposed by Levenshtein, models a setup in which a sequence from some set is transmitted over several independent channels, and the decoder receives the outputs from every channel. The main problem of interest is to determine the minimum number of channels required to reconstruct the transmitted sequence. In the combinatorial context, the problem is equivalent to finding the maximum intersection between two balls of radius t where the distance between their centers is at least d. The setup of this problem was studied before for several error metrics such as the Hamming metric, the Kendall-tau metric, and the Johnson metric. In this paper, we extend the study initiated by Levenshtein for reconstructing sequences over the deletion channel. While he solved the case where the transmitted word can be arbitrary, we study the setup where the transmitted word belongs to a single-deletion-correcting code and there are t deletions in every channel. Under this paradigm, we study the minimum number of different channel outputs in order to construct a successful decoder.

We introduce the new problem of code design in the Damerau metric. The Damerau metric is a generalization of the Levenshtein distance which also allows for adjacent transposition edits. We first provide constructions for codes that may correct either a single deletion or a single adjacent transposition and then proceed to extend these results to codes that can simultaneously correct a single deletion and multiple adjacent transpositions. Bounds on the size of the codes and accompanying decoding algorithms are presented as well.

Write-once memory (WOM) is a storage device consisting of q-ary cells that can only increase their values. A WOM code is a scheme to write messages to the memory without decreasing the cells' levels. There are four models of WOM which depend on whether the encoder and decoder are informed or uninformed with the previous state of the memory. The WOM capacity of the four models was extensively studied by Wolf et al. for the binary case, however in the non-binary setup only the model, in which the encoder is informed and the decoder is not, was studied by Fu and Han Vinck. In this paper we study the capacity regions and maximum sum-rates of non-binary WOM codes for these four models. We extend the results by Wolf et al. and show that for the models in which the encoder is informed and the decoder is informed or uninformed the capacity region is the same both for the ε-error and the zero-error cases. We also find the ε-error capacity region in case the encoder is uninformed and the decoder is informed and show that, in contrary to the binary case, it is a proper subset of the capacity region in the first two models. Several more results on the maximum sum-rate are presented as well.

In this work, we study the performance of different decoding schemes for multilevel flash memories where each page in every block is encoded independently. We focus on the multi-level cell (MLC) flash memory, which is modeled as a two-user multiple access channel suffering from asymmetric noise. The uniform rate regions and sum rates of Treating Interference as Noise (TIN) decoding and Successive Cancelation (SC) decoding are investigated for a Program/Erase (P/E) cycling model and a data retention model. We examine the effect of different binary labelings of the cell levels, as well as the impact of further quantization of the memory output (i.e., additional read thresholds). Finally, we extend our analysis to the three-level cell (TLC) flash memory.

This paper studies codes that correct bursts of deletions. Namely, a code will be called a b-burst-correcting code if it can correct a deletion of any b consecutive bits. While the lower bound on the redundancy of such codes was shown by Levenshtein to be asymptotically log(n) + b - 1, the redundancy of the best code construction by Cheng et al. is b(log(n/b + 1)). In this paper we close on this gap and provide codes with redundancy at most log(n) + (b - 1) log(log(n)) + b - log(b). We also extend the burst deletion model to two more cases: 1. a deletion burst of at most b consecutive bits and 2. a deletion burst of size at most b (not necessarily consecutive). We extend our code construction for the first case and study the second case for b = 3, 4. The equivalent models for insertions are also studied and are shown to be equivalent to correcting the corresponding burst of deletions.

Batch codes, first studied by Ishai et al., are a coding scheme to encode n information bits into m buckets, in a way that every batch request of k bits can be decoded while at most one bit is read from each bucket. In this work we study the class of multiset primitive batch codes, in which every bucket stores a single bit and bits can be requested multiple times. We simply refer to these codes as batch codes. The main problem under this paradigm is to optimize the number of encoded bits, which is the number of buckets, for given n and k, and we denote this value by B(n, k). Since there are several asymptotically optimal constructions of these codes, we are motivated to evaluate their optimality by their redundancy. Thus we define the optimal redundancy of batch codes to be rB(n, k) ??? B(n, k) - n. Our main result in this paper claims that for any fixed k, rB(n, k) = O(√n log(n)).

This paper studies bounds and constructions of locally repairable codes (LRCs) with multiple localities so-called multiple-locality LRCs (ML-LRCs). In the simplest case of two localities some code symbols of an ML-LRC have a certain locality while the remaining code symbols have another one. We extend two bounds, the Singleton and the alphabet-dependent upper bound on the dimension of Cadambe-Mazumdar for LRCs, to the case of ML-LRCs with more than two localities. Furthermore, we construct Singleton-optimal ML-LRCs codes.

In this paper, we study the performance of different decoding schemes for multilevel flash memories where each page in every block is encoded independently. We focus on multi-level cell flash memory, which is modeled as a two-user multiple-access channel suffering from asymmetric noise. The uniform rate regions and sum rates of treating interference as noise decoding and successive cancelation decoding are investigated for a program/erase cycling model and a data retention model. We examine the effect of different binary labelings of the cell levels, as well as the impact of further quantization of the memory output (i.e., additional read thresholds). Finally, we extend our analysis to the three-level cell flash memory.

Random I/O (RIO) codes, recently introduced by Sharon and Alrod, is a coding scheme to improve the random input/output performance of flash memories. Multilevel flash memories require, on the average, more than a single read threshold in order to read a single logicalpage. This number is important to be optimized since it sets the read latency of flash memories. An (n, M, t) RIO code assumes that t pages are stored in n cells with t + 1 levels. The first page is read by applying a read threshold between levels t and t + 1. Similarly, the second page is read by applying a read threshold between levels t - 1 and t, and so on. As a consequence, if a cell reads as bit 1 for a page (say page m), the cell also reads as bit 1 for all the successive pages (m + 1, m + 2⋯). Therefore, Sharon and Alrod showed that the design of RIO codes is equivalent to the design of WOM codes. The latter family of codes attracted substantial attention in recent years in order to improve the lifetime of flash memories by allowing writing multiple messages to the memory without the need for an erase operation. In this paper, we notice two important distinctions between RIO codes and WOM codes. While in WOM codes, the messages are received one after the other and thus are not known all in advance, in RIO codes the information of all logical pages can be known in advance when programming the cells. Even though this knowledge does not improve the maximum sumrate of RIO codes, it allows the design of efficient high-rate codes with a moderate block length, which do not exist for WOM codes. We also study another family of RIO codes, called here partial RIO codes, that allow to find even more efficient codes while allowing to sense more than a single threshold to read some pages.

Partial MDS (PMDS) codes are erasure codes combining local (row) correction with global additional correction of entries, while sector-disk (SD) codes are erasure codes that address the mixed failure mode of current redundant arrays of independent disk (RAID) systems. It has been an open problem to construct general codes that have the PMDS and the SD properties, and previous work has relied on Monte-Carlo searches. In this paper, we present a general construction that addresses the case of any number of failed disks and in addition, two erased sectors. The construction requires a modest field size. This result generalizes previous constructions extending RAID 5 and RAID 6.

Motivated by the rank modulation scheme, a recent study by Sala and Dolecek explored the idea of constraint codes for permutations. The constraint studied by them is inherited by the inter-cell interference phenomenon in flash memories, where high-level cells can inadvertently increase the level of lowlevel cells. A permutation σ ∈ Snsatisfies the single-neighbor k-constraint if |σ(i + 1) - σ (i)| ≤ k for all 1 ≤ i ≤ n - 1. In this paper, this model is extended into two constraints. A permutation σ ∈ Snsatisfies the two-neighbor k-constraint if for all 2 ≤ i ≤ n-1, |σ(i)-σ(i-1)| ≤ k or |σ(i + 1)-σ(i)|≤k, and it satisfies the asymmetric two-neighbor k-constraint if for all 2 ≤ i ≤ n - 1, σ(i - 1) - σ(i)ϵ) and the capacity of the second constraint is 1 regardless for any positive k. We also extend our results and study the capacity of these two constraints combined with error-correcting codes in the Kendall τ-metric.

Multi-permutations and in particular permutations appear in various applications in an information theory. New applications, such as rank modulation for flash memories, have suggested the need to consider error-correcting codes for multi-permutations. In this paper, we study systematic error-correcting codes for multi-permutations in general and for permutations in particular. For a given number of information symbols k, and for any integer t, we present a construction of (k+r,k)systematic t-error-correcting codes, for permutations of length k+r, where the number of redundancy symbols r is relatively small. In particular, for a given t and for sufficiently large k, we obtain r=t+1, while a lower bound on the number of redundancy symbols is shown to be t. The same construction is also applied to obtain related systematic error-correcting codes for any types of multi-permutations.

In a memristor crossbar array, functioning as a memory array, a memristor is positioned on each row-column intersection, and its resistance, low or high, represents two logical states. The state of every memristor can be sensed by the current flowing through the memristor. In this paper, we study the sneak path problem in crossbar arrays, in which current can sneak through other cells, resulting in reading a wrong state of the memristor. Our main contributions are modeling the error channel induced by sneak paths, a new characterization of arrays free of sneak paths, and efficient methods to read the array cells while avoiding sneak paths. To each read method, we match a constraint on the array content that guarantees sneak-path free readout, determine the resulting capacity, and provide an efficient encoder that achieves the capacity.

Error-correcting codes for permutations have received considerable attention in the past few years, especially in applications of the rank modulation scheme for flash memories. While codes over several metrics have been studied, such as the Kendall τ, Ulam, and Hamming distances, no recent research has been carried out for erasures and deletions over permutations. In rank modulation, flash memory cells represent a permutation, which is induced by their relative charge levels. We explore problems that arise when some of the cells are either erased or deleted. In each case, we study how these erasures and deletions affect the information carried by the remaining cells. In particular, we study models that are symbol-invariant, where unaffected elements do not change their corresponding values from those in the original permutation, or permutation-invariant, where the remaining symbols are modified to form a new permutation with fewer elements. Our main approach in tackling these problems is to build upon the existing works of error-correcting codes and leverage them in order to construct codes in each model of deletions and erasures. The codes we develop are in certain cases asymptotically optimal, while in other cases, such as for codes in the Ulam distance, improve upon the state of the art results.

Locally repairable codes (LRCs) are a class of codes designed for the local correction of erasures. They have received considerable attention in recent years due to their applications in distributed storage. Most existing results on LRCs do not explicitly take into consideration the field size q, i.e., the size of the code alphabet. In particular, for the binary case, only a few results are known. In this paper, we present an upper bound on the minimum distance d of linear LRCs with availability, based on the work of Cadambe and Mazumdar. The bound takes into account the code length n, dimension k, locality r, availability t, and field size q. Then, we study the binary linear LRCs in three aspects. First, we focus on analyzing the locality of some classical codes, i.e., cyclic codes and Reed-Muller codes, and their modified versions, which are obtained by applying the operations of extend, shorten, expurgate, augment, and lengthen. Next, we construct LRCs using phantom parity-check symbols and multi-level tensor product structure, respectively. Compared with other previous constructions of binary LRCs with fixed locality or minimum distance, our construction is much more flexible in terms of code parameters, and gives various families of high-rate LRCs, some of which are shown to be optimal with respect to their minimum distance. Finally, the availability of LRCs is studied. We investigate the locality and availability properties of several classes of one-step majority-logic decodable codes, including cyclic simplex codes, cyclic difference-set codes, and 4-cycle free regular low-density parity-check codes. We also show the construction of a long LRC with availability from a short one-step majority-logic decodable code.

In this paper, we study a new model of defect memory cells, called partially stuck-at memory cells, which is motivated by the behavior of multi-level cells in non-volatile memories, such as flash memories and phase change memories. If a cell can store the q levels 0, 1,... ,q - 1, we say that it is partially stuck-at level s, where 1 ≤ s ≤ q -1, if it can only store values, which are at least s. We follow the common setup where the encoder knows the positions and levels of the partially stuckat cells whereas the decoder does not. Our main contribution in this paper is the study of codes for masking ii partially stuck-at cells. We first derive lower and upper bounds on the redundancy of such codes. The upper bounds are based on two trivial constructions. We then present three code constructions over an alphabet of size q, by first considering the case where the cells are partially stuck-at level s = 1. The first construction works for u <; q and is asymptotically optimal if ii + 1 divides q. The second construction uses the reduced row echelon form of matrices to generate codes for the case u ≥ q, and the third construction solves the case of arbitrary ii by using codes, which mask binary stuck-at cells. We then show how to generalize all constructions to arbitrary stuck levels. Furthermore, we study the dual defect model, in which cells cannot reach higher levels, and show that codes for partially stuck-at cells can be used to mask this type of defects as well. Last, we analyze the capacity of the partially stuck-at memory channel and study how far our constructions are from the capacity.

Symbol-pair read channels, in which the outputs of the read process are pairs of consecutive symbols, were recently studied by Cassuto and Blaum. This new paradigm is motivated by the limitations of the reading process in high density data storage systems. They studied error correction in this new paradigm, specifically, the relationship between the minimum Hamming distance of an error correcting code and the minimum pair distance, which is the minimum Hamming distance between symbol-pair vectors derived from codewords of the code. It was proved that for a linear cyclic code with minimum Hamming distance dH, the corresponding minimum pair distance is at least dH+3. In this paper, we show that, for a given linear cyclic code with a minimum Hamming distance dH, the minimum pair distance is at least dH+ (dH/2). We then describe a decoding algorithm, based upon a bounded distance decoder for the cyclic code, whose symbol-pair error correcting capabilities reflect the larger minimum pair distance. Finally, we consider the case where the read channel output is a larger number, b ≥3, of consecutive symbols, and we provide extensions of several concepts, results, and code constructions to this setting.

Inter-cell interference (ICI) is a significant cause of errors in flash memories. In two-level (SLC) flash memory, ICI arises when 1 0 1 patterns are programmed either in the horizontal or vertical directions. Since data pages are written sequentially in horizontal wordlines, one can mitigate the effects of horizontal ICI by use of conventional constrained codes that forbid the 1 0 1 pattern. This approach does not address the problem of vertical ICI, however. In this work, we present a row-by-row coding technique that eliminates vertical 1 0 1 patterns while preserving the sequential wordline programming order. This scheme, though efficient, necessarily suffers a rate loss of almost 20%. We therefore propose another coding scheme, combining a relaxed constraint on vertical 1 0 1 patterns with a systematic error correcting code, that can mitigate vertical ICI errors while achieving a higher overall code rate, provided that the vertical ICI error probability is sufficiently small.

Private information retrieval (PIR) protocols allow a user to retrieve a data item from a database without revealing any information about the identity of the item being retrieved. Specifically, in information-theoretic k-server PIR, the database is replicated among k non-communicating servers, and each server learns nothing about the item retrieved by the user. The cost of PIR protocols is usually measured in terms of their communication complexity, which is the total number of bits exchanged between the user and the servers. However, another important cost parameter is the storage overhead, which is the ratio between the total number of bits stored on all the servers and the number of bits in the database. Since single-server information-theoretic PIR is impossible, the storage overhead of all existing PIR protocols is at least 2 (or k, in the case of k-server PIR). In this work, we show that information-theoretic PIR can be achieved with storage overhead arbitrarily close to the optimal value of 1, without sacrificing the communication complexity. Specifically, we prove that all known k-server PIR protocols can be efficiently emulated, while preserving both privacy and communication complexity but significantly reducing the storage overhead. To this end, we distribute the n bits of the database among s + r servers, each storing n/s coded bits (rather than replicas). Notably, our coding scheme remains the same, regardless of the specific k-server PIR protocol being emulated. For every fixed k, the resulting storage overhead (s +r)/s approaches 1 as s grows; explicitly we have equation. Moreover, in the special case k = 2, the storage overhead is only 1 + 1/s. In order to achieve these results, we introduce and study a new kind of binary linear codes, called here k-server PIR codes. Finally, we show how such codes can be constructed from multidimensional cubic, from Steiner systems, and from one-step majority-logic decodable codes.

In this work, we present a new upper bound on the minimum distance d of linear locally repairable codes (LRCs) with information locality and availability. The bound takes into account the code length n, dimension k, locality r, availability t, and field size q. We use tensor product codes to construct several families of LRCs with information locality, and then we extend the construction to design LRCs with information locality and availability. Some of these codes are shown to be optimal with respect to their minimum distance, achieving the new bound. Finally, we study the all-symbol locality and availability properties of several classes of one-step majority-logic decodable codes, including cyclic simplex codes, cyclic difference-set codes, and 4-cycle free regular low-density parity-check (LDPC) codes. We also investigate their optimality using the new bound.

In this work we consider the communication of information in the presence of synchronization errors. Specifically, we consider permutation channels in which a transmitted codeword x = (x1, ..., xn) is corrupted by a permutation π ∈ Snto yield the received word y = (y1, ..., yn) where yi= xπ(i). We initiate the study of worst case (or zero error) communication over permutation channels that distort the information by applying permutations π which are limited to displacing any symbol by at most r locations, i.e. permutations π with weight at most r in the ℓ∞-metric. We present direct and recursive constructions, as well as bounds on the rate of such channels for binary and general alphabets. Specific attention is given to the case of r = 1.

Flash memory is a write-once medium in which re-programming cells requires first erasing the block that contains them. The lifetime of the flash is a function of the number of block erasures and can be as small as several thousands. To reduce the number of block erasures, pages, which are the smallest write unit, are rewritten out-of-place in the memory. A Write-once memory (WOM) code is a coding scheme which enables to write multiple times to the block before an erasure. However, these codes come with significant rate loss. For example, the rate for writing twice (with the same rate) is at most 0.77. In this paper, we study WOM codes and their tradeoff between rate loss and reduction in the number of block erasures, when pages are written uniformly at random. First, we introduce a new measure, called erasure factor, that reflects both the number of block erasures and the amount of data that can be written on each block. A key point in our analysis is that this tradeoff depends upon the specific implementation of WOM codes in the memory. We consider two systems that use WOM codes; a conventional scheme that was commonly used, and a new recent design that preserves the overall storage capacity. While the first system can improve the erasure factor only when the storage rate is at most 0.6442, we show that the second scheme always improves this figure of merit.

Write-once memory (WOM) is a storage device consisting of q-ary cells that can only increase their value. A WOM code is a coding scheme which allows one to write multiple times to the WOM without decreasing the levels of the cells. In the conventional model of WOM, it is assumed that the encoder can read the memory state before encoding, while the decoder reads only the memory state after encoding, but not before that. However, there are three more models in this setup. We follow an earlier work by Wolf et al. who studied the capacity results of all possible four models in which the encoder/decoder is or is not informed with the previous state of the memory before encoding, respectively. The two challenging models we study here assume that the encoder is uninformed with the memory state (that is, the encoder cannot read the memory prior to encoding). We show that if the decoder is also uninformed with the memory state before encoding, then codes in the Z channel provide constructions for the binary case, and codes correcting non-binary asymmetric errors are used for non-binary codes. In case the decoder is informed with the previous state, then erasure-correcting codes are invoked in the binary case, and codes in the Manhattan distance are used for the non-binary case.

Locally repairable codes (LRCs) are a class of codes designed for the local correction of erasures. They have received considerable attention in recent years due to their applications in distributed storage. Most existing results on LRCs do not explicitly take into consideration the field size q, i.e., the size of the code alphabet. In particular, for the binary case, only a few specific results are known by Goparaju and Calderbank. Recently, however, an upper bound on the dimension k of LRCs was presented by Cadambe and Mazumdar. The bound takes into account the length n, minimum distance d, locality r, and field size q, and it is applicable to both non-linear and linear codes. In this work, we first develop an improved version of the bound mentioned above for linear codes. We then focus on cyclic linear binary codes. By leveraging the cyclic structure, we notice that the locality of such a code is determined by the minimum distance of its dual code. Using this result, we investigate the locality of a variety of well known cyclic linear binary codes, e.g., Hamming codes and Simplex codes, and also prove their optimality with our improved bound for linear codes. We also discuss the locality of codes which are obtained by applying the operations of Extend, Shorten, Expurgate, Augment, and Lengthen to cyclic linear binary codes. Several families of such modified codes are considered and their optimality is addressed. Finally, we investigate the locality of Reed-Muller codes. Even though they are not cyclic, it is shown that some of the locality results for cyclic codes still apply.

One of the prominent properties of flash memories is their asymmetry between writing and erasing. When pages, which are the smallest write unit, are updated, they are written in a new copy rather than in place. As a result, every page can have more than one copy in the memory, its current version as well as some of its old invalid copies. Each invalid copy can be cleaned only when the block in which it resides is erased (blocks are the smallest erase unit and are typically in the order of hundreds of pages). This write property introduces redundancy in the memory, given by the invalid copies of the pages, and as a result can also affect the memory lifetime. In this paper we show how this inherent redundancy of invalid pages can be taken advantage of for the purpose of improving RAID solutions which are based upon Solid State Drives (SSDs). Our main contribution in the paper is a construction which shows how to improve the repair bandwidth of codes which are implemented on SSDs. We first show that with a single parity it is possible to transmit on the average roughly half of the data for rebuilding a single drive failure. We then show how these ideas can be extended for Zigzag codes with two parities and again improve their repair bandwidth.

We consider locally repairable codes over small fields and propose constructions of optimal cyclic and linear codes in terms of the dimension for a given distance and length. Four new constructions of optimal linear codes over small fields with locality properties are developed. The first two approaches give binary cyclic codes with locality two. While the first construction has availability one, the second binary code is characterized by multiple available repair sets based on a binary Simplex code. The third approach extends the first one to q-ary cyclic codes including (binary) extension fields, where the locality property is determined by the properties of a shortened first-order Reed- Muller code. Non-cyclic optimal binary linear codes with locality greater than two are obtained by the fourth construction.

Kulkarni and Kiyavash recently introduced a new method to establish upper bounds on the size of deletion-correcting codes. This method is based upon tools from hypergraph theory. The deletion channel is represented by a hypergraph whose edges are the deletion balls (or spheres), so that a deletion-correcting code becomes a matching in this hypergraph. Consequently, a bound on the size of such a code can be obtained from bounds on the matching number of a hypergraph. Classical results in hypergraph theory are then invoked to compute an upper bound on the matching number as a solution to a linear-programming problem: the problem of finding fractional transversal. The method by Kulkarni and Kiyavash can be applied not only for the deletion channel but also for other error channels. This paper studies this method in its most general setup. First, it is shown that if the error channel is regular and symmetric then the upper bound by this method coincides with the well-known sphere packing bound and thus is called here the generalized sphere packing bound. Even though this bound is explicitly given by a linear programming problem, finding its exact value may still be a challenging task. The art of finding the exact upper bound (or slightly weaker ones) is the assignment of weights to the hypergraph's vertices in a way that they satisfy the constraints in the linear programming problem. In order to simplify the complexity of the linear programming, we present a technique based upon graph automorphisms that in many cases significantly reduces the number of variables and constraints in the problem. We then apply this method on specific examples of error channels. We start with the Z channel and show how to exactly find the generalized sphere packing bound for this setup. Next studied is the nonbinary limited magnitude channel both for symmetric and asymmetric errors, where we focus on the single-error case. We follow up on the deletion channel, which was the original motivation of the work by Kulkarni and Kiyavash, and show how to improve upon their upper bounds for single-deletion-correcting codes. Since the deletion and grain-error channels have a similar structure for a single error, we also improve upon the existing upper bounds on single-grain error-correcting codes. Finally, we apply this method for projective spaces and find its generalized sphere packing bound for the single-error case.

This paper studies new bounds and code constructions that are applicable to the combinatorial granular channel model previously introduced by Sharov and Roth. We derive new bounds on the maximum cardinality of a grain-error-correcting code and propose constructions of codes that correct grain-errors. We demonstrate that a permutation of the classical group codes (e.g., Constantin-Rao codes) can correct a single grain-error. In many cases of interest, our results improve upon the currently best known bounds and constructions. Some of the approaches adopted in the context of grain-errors may have application to related channel models.

The current flash memory technology focuses on the cost minimization of its static storage capacity. However, the resulting approach supports a relatively small number of program-erase cycles. This technology is effective for consumer devices (e.g., smartphones and cameras) where the number of program-erase cycles is small. However, it is not economical for enterprise storage systems that require a large number of lifetime writes. The proposed approach in this paper for alleviating this problem consists of the efficient integration of two key ideas: 1) improving reliability and endurance by representing the information using relative values via the rank modulation scheme and 2) increasing the overall (lifetime) capacity of the flash device via rewriting codes, namely, performing multiple writes per cell before erasure. This paper presents a new coding scheme that combines rank-modulation with rewriting. The key benefits of the new scheme include: 1) the ability to store close to 2 bit per cell on each write with minimal impact on the lifetime of the memory and 2) efficient encoding and decoding algorithms that make use of capacity-achieving write-once-memory codes that were proposed recently.

Partial MDS (PMDS) codes are erasure codes combining local (row) correction with global additional correction of entries, while Sector-Disk (SD) codes are erasure codes that address the mixed failure mode of current RAID systems. It has been an open problem to construct general codes that have the PMDS and the SD properties, and previous work has relied on Monte-Carlo searches. In this paper, we present a general construction that addresses the case of any number of failed disks and in addition, two erased sectors. The construction requires a modest field size. This result generalizes previous constructions extending RAID 5 and RAID 6.

Motivated by the rank modulation scheme, a recent work by Sala and Dolecek explored the study of constraint codes for permutations. The constraint studied by them is inherited by the inter-cell interference phenomenon in flash memories, where high-level cells can inadvertently increase the level of low-level cells. In this paper, the model studied by Sala and Dolecek is extended into two constraints. A permutation σ ∈ Snsatisfies the two-neighbor k-constraint if for all 2 ≤ i ≤ n - 1 either |σ(i - 1) - σ(i)| ≤ k or |σ(i) - σ(i + 1)| ≤ k, and it satisfies the asymmetric two-neighbor k-constraint if for all 2 ≤ i ≤ n - 1, either σ(i-1)-σ(i)ε) and the capacity of the second constraint is 1 regardless to the value of k. We also extend our results and study the capacity of these two constraints combined with error-correction codes in the Kendall's τ metric.

The goal of this paper is to construct systematic error-correcting codes for permutations and multi-permutations in the Kendall's τ-metric. These codes are important in new applications such as rank modulation for flash memories. The construction is based on error-correcting codes for multi-permutations and a partition of the set of permutations into error-correcting codes. For a given large enough number of information symbols k, and for any integer t, we present a construction for (k + r, k) systematic t-error-correcting codes, for permutations from Sk+r, with less redundancy symbols than the number of redundancy symbols in the codes of the known constructions. In particular, for a given t and for sufficiently large k we can obtain r = t+1. The same construction is also applied to obtain related systematic error-correcting codes for multi-permutations.

Kulkarni and Kiyavash recently introduced a new method to establish upper bounds on the size of deletion-correcting codes. This method is based upon tools from hypergraph theory. The deletion channel is represented by a hypergraph whose edges are the deletion balls (or spheres), so that a deletion-correcting code becomes a matching in this hypergraph. Consequently, a bound on the size of such a code can be obtained from bounds on the matching number of a hypergraph. Classical results in hypergraph theory are then invoked to compute an upper bound on the matching number as a solution to a linear-programming problem: the problem of finding fractional transversals. The method by Kulkarni and Kiyavash can be applied not only for the deletion channel but also for other channels, and in particular for those where the error spheres sizes are not all the same. This paper studies this method in its most general setup. We first show that if the error channel is regular and symmetric then the upper bound by this method coincides with the well-known sphere packing bound and thus is called here the generalized sphere packing bound. Even though this bound is explicitly given by a linear programming problem, finding its exact value may still be a challenging task. The art of finding the exact upper bound or slightly weaker ones is the assignment of weights to the hypergraph's vertices in a way that the satisfy the constraints in the linear programming problem. Every valid assignment yields an upper bound and the goal is to find assignments that provide strong upper bounds. We show that for graphs which satisfy a monotonicity property it is possible to find a general formula for such an assignment. Lastly, in order to simplify the complexity of the linear programming, we present a technique based upon graph automorphisms that in many cases can significantly reduce the number of variables and constraints in the linear programming problem. All of our results will be demonstrated and calculated for the Z channel which will be a case study in our work.

In this paper we study a generalization of the sphere packing bound for channels that are not regular (the size of balls with a fixed radius is not necessarily the same). Our motivation to tackle this problem is originated by a recent work by Kulkarni and Kiyavash who introduced a method, based upon tools from hypergraph theory, to calculate explicit upper bounds on the cardinalities of deletion-correcting codes. Under their setup, the deletion channel is represented by a hypergraph such that every deletion ball is a hyperedge. Since every code is a matching in the hypergraph, an upper bound on the codes is given by an upper bound on the largest matching in a hypergraph. This bound, called here the generalized sphere packing bound, can be found by the solution of a linear programming problem. We similarly study and analyze specific examples of error channels. We start with the Z channel and show how to exactly find the generalized sphere packing bound for this setup. Next studied is the non-binary limited magnitude channel both for symmetric and asymmetric errors. We focus on the case of single error and derive upper bounds on the generalized sphere packing bound in this channel. We follow up on the deletion case, which was the original motivation of the work by Kulkarni and Kiyavash, and show how to improve upon their upper bounds for the single deletion case. Finally, we apply this method for projective spaces and find its generalized sphere packing bound for the single-error case.

Error-correcting codes for permutations have received a considerable attention in the past few years, especially in applications of the rank modulation scheme for flash memories. While several metrics have been studied like the Kendall's τ, Ulam, and Hamming distances, no recent research has been carried for erasures and deletions over permutations. The problems studied in this paper are motivated by a hardware implementation of the rank modulation codes. If the flash memory cells represent a permutation, which is modulated by their relative charge levels, then we explore the problems arise when some of the cells are either erased or deleted. In each case we study how these erasures and deletions affect the information carried by the remaining cells. In particular, the cells can either be stable and do not change their values in the permutation or unstable where the remaining cells form an induced permutation with less symbols. Yet another erasure model, called here soft erasures, assumes that all cells can be read, however the relative levels between some of the cells is not known. Our main approach in tackling these problems is to build upon the existing works of error-correcting codes in the three metrics mentioned above and leverage them in order to construct codes in each model of deletions and erasures. Lastly, we follow up on codes in the Ulam distance and improve upon the state of the art results.

Motivated by the rank modulation scheme for flash memories, we consider an information representation system with relative values (permutations) and study codes for correcting deletions. In contrast to the case of a deletion in a regular (with absolute values) representation system, a deletion in this new paradigm results in a new permutation over the remaining symbols. For example, the deletion of 3 (or 2) from (1, 3, 2, 4) yields (1, 2, 3); while the deletion of 1 yields (2, 1, 3). Codes for correcting deletions in permutations were studied by Levenshtein under a different model, however, he considered absolute values where the deletions are missing symbols. We study the single deletion relative-values model and prove that a code can correct a single deletion if and only if it can correct a single insertion. Using the concept of a signature of a permutation, we construct single-deletion correcting codes and prove that they are asymptotically optimal with respect to an upper bound that we derive. Finally, we describe an efficient decoding algorithm.

Random I/O (RIO) Codes, recently introduced by Sharon and Alrod, is a coding scheme to improve the random input/output performance of flash memories. Multi-level flash memories require, on the average, more than a single read threshold in order to read a single logical page. This number is important to be optimized since it sets the read latency of flash memories. An (n,M, t) RIO code assumes that t pages are stored in n cells with t + 1 levels. The first page is read by applying a read threshold between levels t and t + 1. Similarly, the second page is read by applying a read threshold between levels t - 1 and t, and so on. The read binary vectors for consecutive pages satisfy the property that the set of positions read with value 1 can only increase. Therefore, Sharon and Alrod showed also that the design of RIO codes is equivalent to the design of WOM codes. The latter family of codes attracted a lot of attention in recent years in order to improve the lifetime of flash memories by allowing to write multiple messages to the memory without the need for a physical erase. In this paper we notice two important distinctions between RIO codes and WOM codes. While in WOM codes the messages are received one after the other and thus are not known all in advance, in RIO codes the information of all logical pages can be known in advance when programming the cells. Even though this knowledge does not improve the capacity of RIO codes, it allows the design of efficient high-rate codes with a moderate block length, which are hard to be found for WOM codes. We also study another family of RIO codes, called here partial RIO Codes, that allow to find even more efficient codes in the tradeoff of reading more than a single threshold to read a page.

Inter-cell interference (ICI) is one of the main obstacles to precise programming (i.e., writing) of a flash memory. In the presence of ICI, the voltage level of a cell might increase unexpectedly if its neighboring cells are programmed to high levels. For q-ary cells, the most severe ICI arises when three consecutive cells are programmed to levels high - low - high, represented as (q-1)0(q-1), resulting in an unintended increase in the level of the middle cell and the possibility of decoding it incorrectly as a nonzero value. ICI-free codes are used to mitigate this phenomenon by preventing the programming of any three consecutive cells as (q-1)0(q-1). In this work, we extend ICI-free codes in two directions. First, we consider binary balanced ICI-free codes which, in addition to forbidding the 101 pattern, require the number of 0 symbols and 1 symbols to be the same. Using combinatorial methods, we determine the asymptotic information rate of these codes and show that the asymptotic rate loss due to the imposition of the balanced property is approximately 2%. Extensions to q-ary cells, for q > 2 are also discussed. Next, we consider q-ary ICI-free write-once-memory (WOM) codes that support multiple writes of a WOM while mitigating ICI effects. These codes forbid the appearance of the (q-1)0(q-1) pattern in any codeword used in any writing step. Using properties of two-dimensional constrained codes and generalized WOMs, we characterize the maximum sum-rate of t-write ICI-free WOM codes or, equivalently, the t-write sum-capacity of an ICI-free WOM.

To the body of works on rewrite codes for constrained memories, we add a comprehensive study in a direction that is especially relevant to practical storage. The subject of this paper is codes for the q-ary extension of the write-once memories model, with input sizes that are fixed throughout the write sequence. Seven code constructions are given with guarantees on the number of writes they can support. For the parameters addressed by the constructions, we also prove upper bounds on the number of writes, which prove the optimality of three of the constructions. We concentrate on codes with short block lengths to keep the complexity of decoding and updates within the feasibility of practical implementation. Even with these short blocks the constructed codes are shown to be within a small additive constant from capacity for an arbitrarily large number of input bits. Part of the study addresses a new rewrite model where some of the input bits can be updated multiple times in a write sequence (hot bits), while other are updated at most once (cold bits). We refer to this new model as hot/cold rewrite codes. It is shown that adding cold bits to a rewrite code has a negligible effect on the total number of writes, while adding an important feature of leveling the physical wear of memory cells between hot and cold input data.

Multilevel flash memory contains blocks of cells that represent data by the amount of charge stored in them. The cell writing - or programming - process applies specified voltages in a sequential manner, injecting charge to achieve a desired level. Reducing a cell level requires a costly block erasure, so programming only increases cell levels. Parallel programming, whereby a common voltage is applied to a group of cells to inject charge simultaneously, simplifies circuitry and increases programming speed. However, cell-to-cell variations and limited programming round can adversely affect its precision. In this paper, we consider algorithms for efficient cell programming. Since cell levels are quantized to a discrete set of values, our objective is to minimize the number of cells that are not quantized to their target levels. For a specified number of programming rounds, we derive an optimal parallel programming algorithm with complexity that is polynomial in the number of cells. We extend the algorithm to account for intercell interference, where the voltage applied to a cell can affect the level of adjacent cells. We then consider noisy programming of a single cell, with and without feedback about the cell level. In both scenarios, we present an algorithm that, for a given number of programming rounds, minimizes the probability of an incorrect cell level.

Flash memory is a nonvolatile computer memory comprising blocks of cells, wherein each cell can take on$q$different values or levels. While increasing the cell level is easy, reducing the level of a cell can be accomplished only by erasing an entire block. Since block erasures are highly undesirable, coding schemes—known as floating codes (or flash codes) and buffer codes—have been designed in order to maximize the number of times that information stored in a flash memory can be written (and rewritten) prior to incurring a block erasure. An$(n,k,t)_{q}$flash code$\BBC$is a coding scheme for storing$k$information bits in$n$cells in such a way that any sequence of up to$t$writes can be accommodated without a block erasure. The total number of available level transitions in$n$cells is$n(q{-}1)$, and the write deficiency of$\BBC$, defined as$\delta (\BBC)=n(q{-}1)-t$, is a measure of how close the code comes to perfectly utilizing all these transitions. In this paper, we show a construction of flash codes with write deficiency$O(qk\log k)$if$q\geqslant\log_{2}k$, and at most$O(k\log^{2}k)$otherwise. An$(n,r,\ell,t)_{q}$buffer code is a coding scheme for storing a buffer of$r~\ell$-ary symbols such that for any sequence of$t$symbols, it is possible to successfully decode the last$r$symbols that were written. We improve upon a previous upper bound on the maximum number of writes$t$in the case where there is a single cell to store the buffer. Then, we show how to improve a construction by Jiangthat uses multiple cells, where$n\geqslant 2r$.

Write-once memory (WOM) is a storage medium with memory elements, called cells, which can take on q levels. Each cell is initially in level 0 and can only increase its level. A t-write WOM code is a coding scheme, which allows one to store t messages to the WOM such that on consecutive writes every cell's level does not decrease. The sum-rate of the WOM code, which is the ratio between the total amount of information written in the t writes and number of memory cells, is bounded by log(t + 1). Our main contribution in this paper is a construction of binary three-write WOM codes with sum-rate approaching 1.885 for sufficiently large number of cells, whereas the upper bound is 2. This improves upon a recent construction of sum-rate 1.809. A key ingredient in our construction is a recent capacity achieving construction of two-write WOM codes, which uses the so-called Wozencraft ensemble of linear codes. In our construction, we encode information in the first and second write in a way that leaves a large number (roughly half) of the cells nonprogrammed. This allows us to use the above two-write construction in order to invoke a third write to the memory. We also give specific constructions of nonbinary two-write WOM codes and multiple writes, which give better sum-rate than the currently best known ones. In the construction of these codes, we build upon previous nonbinary constructions and show how tools such symbols relabeling can help in achieving high sum-rates.

Multipermutations appear in various applications in information theory. New applications such as rank modulation for flash memories and voting have suggested the need to consider error-correcting codes for multipermutations. The construction of codes is challenging when permutations are considered and it becomes even a harder problem for multipermutations. In this paper we discuss the general problem of error-correcting codes for multipermutations. We present some tight bounds on the size of error-correcting codes for several families of multipermutations. We find the capacity of the channels of multipermutations and characterize families of perfect codes in this metric which we believe are the only such perfect codes.

In a memristor crossbar array, a memristor is positioned on each row-column intersection, and its resistance, low or high, represents two logical states. The state of every memristor can be sensed by the current flowing through the memristor. In this work, we study the sneak path problem in crossbars arrays, in which current can sneak through other cells, resulting in reading a wrong state of the memristor. Our main contributions are a new characterization of arrays free of sneak paths, and efficient methods to read the array cells while avoiding sneak paths. To each read method we match a constraint on the array content that guarantees sneak-path free readout, and calculate the resulting capacity.

This paper has two goals. The first one is to discuss good codes for packing problems in the Lee and Manhattan metrics. The second one is to consider weighing matrices for some of these coding problems. Weighing matrices were considered as building blocks for codes in the Hamming metric in various constructions. In this paper we will consider mainly two types of weighing matrices, namely conference matrices and Hadamard matrices, to construct codes in the Lee (and Manhattan) metric. We will show that these matrices have some desirable properties when considered as generator matrices for codes in these metrics. Two related packing problems will be considered. The first one is to find good codes for error-correction (i.e. dense packings of Lee spheres). The second one is to transform the space in a way that volumes are preserved and each Lee sphere (or conscribed cross-polytope), in the space, will be transformed into a shape inscribed in a small cube.

This paper studies new bounds and constructions that are applicable to the combinatorial granular channel model previously introduced by Sharov and Roth. The main theme of the paper is that codes capable of correcting grain-errors are related to codes that correct insertions/deletions and codes that correct asymmetric errors. Using this insight, new bounds on the maximum cardinality of a grain-error correcting code are derived and constructions of codes that correct grain-errors are considered. It is also demonstrated that permutations of the classical group codes can correct a single grain-error. In several cases of interest, our results improve upon the currently best known bounds and constructions.

Current flash memory technology is focused on cost minimization of the stored capacity. However, the resulting approach supports a relatively small number of write-erase cycles. This technology is effective for consumer devices (smart-phones and cameras) where the number of write-erase cycles is small, however, it is not economical for enterprise storage systems that require a large number of lifetime writes. Our proposed approach for alleviating this problem consists of the efficient integration of two key ideas: (i) improving reliability and endurance by representing the information using relative values via the rank modulation scheme and (ii) increasing the overall (lifetime) capacity of the flash device via rewriting codes, namely, performing multiple writes per cell before erasure. We propose a new scheme that combines rank-modulation with rewriting. The key benefits of the new scheme include: (i) the ability to store close to 2 bits per cell on each write, and rewrite the memory close to q times, where q is the number of levels in each cell, and (ii) efficient encoding and decoding algorithms that use the recently proposed polar WOM codes.

In networked systems comprised of many agents, it is often required to reach a common operating point of all agents, termed the network consensus. We consider two iterative methods for reaching a ranking (ordering) consensus over a voter network, where the initial preference of every voter is of the form of a full ranking of candidates. The voters are allowed, one at a time and based on some random scheme, to change their votes to bring them “closer” to the opinions of selected subsets of peers. The first consensus method is based on changing votes one adjacent swap at a time; the second method is based on changing votes via averaging with the votes of peers, potentially leading to many adjacent swaps at a given time. For the first model, we characterize convergence points and conditions for convergence. For the second model, we prove convergence to a global ranking and derive the rate of convergence to this consensus.

This work studies memories with the goal of exploring the concept of in-memory computing. Our point of departure is the 1972 classical study on logical arrays by Akers. We demonstrate a number of new ways for these arrays to simultaneously store information and perform logical operations. We first generalize these arrays to non-binary alphabets. We then show how a special structure of these arrays can both store values and output a sorted version of them. In addition we show how the array can tolerate or detect errors in the stored information.

The typical paradigm in voting theory involves n voters and m candidates. Every voter ranks the candidates resulting in a permutation of the m candidates. A key problem is to derive the aggregate result of the voting. A popular method for vote aggregation is based on the Condorcet criterion. The Condorcet winner is the candidate who wins every other candidate by pairwise majority. However, the main disadvantage of this approach, known as the Condorcet paradox, is that such a winner does not necessarily exist since this criterion does not admit transitivity. This paradox is mathematically likely (if voters assign rankings uniformly at random, then with probability approaching one with the number of candidates, there will not be a Condorcet winner), however, in real life scenarios such as elections, it is not likely to encounter the Condorcet paradox. In this paper we attempt to improve our intuition regarding the gap between the mathematics and reality of voting systems. We study a special case where there is global intransitivity between all candidates. We introduce tools from information theory and derive an entropy-based characterization of global intransitivity. In addition, we tighten this characterization by assuming that votes tend to be similar; in particular they can be modeled as permutations that are confined to a sphere defined by the Kendalls τ distance.

The sequence-reconstruction problem was first proposed by Levenshtein in 2001. This problem studies the model where the same word is transmitted over multiple channels. If the transmitted word belongs to some code of minimum distance d and there are at most r errors in every channel, then the minimum number of channels that guarantees a successful decoder (under the assumption that all channel outputs are distinct) has to be greater than the largest intersection of two balls of radius r and with distance at least d between their centers. This paper studies the combinatorial problem of computing the largest intersection of two balls for two cases. In the first part we solve this problem in the Grassmann graph for all values of d and r. In the second part we derive similar results for permutations under Kendall's τ-metric for some special cases of d and r.

This paper has two goals. The first one is to discuss two related packing problems in the Lee and Manhattan metrics. One is to find good codes for error-correction (i.e., packings of Lee spheres) and the other is to transform the space in a way that volumes are preserved and each Lee sphere (or scaled cross-polytope) will be transformed into a shape inscribed in a small cube. The second goal is to consider weighing matrices for some of these coding problems. Weighing matrices have been used as building blocks for codes in the Hamming metric in various constructions. In this paper, we will consider mainly two types of weighing matrices, namely conference matrices and Hadamard matrices, to construct codes in the Lee (and Manhattan) metric. We will show that these matrices have some desirable properties when considered as generator matrices for codes in these metrics.

Flash memory is a promising new storage technology. Supported by empirical data collected from a Flash memory device, we propose a class of codes that exploits the asymmetric nature of the error patterns in a Flash device using tensor product operations. We call these codes graded bit-error-correcting codes. As demonstrated on the data collected from a Flash chip, these codes significantly delay the onset of errors and therefore have the potential to prolong the lifetime of the memory device.

Phase-change memory (PCM) is a promising nonvolatile solid-state memory technology. A PCM cell stores data by using its amorphous and crystalline states. The cell changes between these two states using high temperature. However, since the cells are sensitive to high temperature, it is important, when programming cells (i.e., changing cell levels), to balance the heat both in time and in space. In this paper, we study the time-space constraint for PCM, which was originally proposed by Jiang and coworkers. A code is called an (α, β, p)- constrained code if for any α consecutive rewrites and for any segment of β contiguous cells, the total rewrite cost of the β cells over those α rewrites is at most p. Here, the cells are binary and the rewrite cost is defined to be the Hamming distance between the current and next memory states. First, we show a general upper bound on the achievable rate of these codes which extends the results of Jiang and coworkers. Then, we generalize their construction for (α ≥ 1, β = 1, p = 1)-constrained codes and show another construction for (α = 1, β ≥ 1, p ≥ 1)-constrained codes. Finally, we show that these two constructions can be used to construct codes for all values of α, β, and p.

This paper proposes a NAND flash system that uses Write-Once Memory (WOM) codes to encode the data stored. It is shown through both analysis and simulation that, with proper parameters, flash memories which use WOM codes to encode data can achieve a lower write amplification than in a non-WOM-coded system. For example, in a 16-level per cell flash memory, when a two-write MLC WOM code is used with a total overprovisioning of 0.8, the write amplification is 15% lower than a non-WOM-coded system. A closed-form expression for the write amplification in a WOM-coded system is given for a system with a greedy garbage collection policy and a uniform random workload. The proposed expression is a function of the total overprovisioning factor, number of WOM code writes, and number of values per cell. The expression is applicable for both SLC and MLC flash.

We construct new WOM codes with practical design considerations. First the problem of 2 cell q-ary WOM codes is addressed with a construction that uses lattice tilings. The resulting codes for arbitrary numbers of input bits are shown to be within a small additive constant from the capacity. Then we introduce a new model of WOM codes that support data bits with different update requirements. Differentiation between frequently written (hot) bits and rarely written (cold) ones allows a large number of re-writes while leveling the wear between the hot and cold input bits.

Flash memory is a promising new storage technology. To fully utilize future multi-level cell Flash memories, it is necessary to develop error correction coding schemes attuned to the underlying physical characteristics of Flash. Based on a careful inspection of fine-grained, experimentally-collected error patterns of TLC (three bits per cell) Flash, we propose a mathematical model that captures the intracell variability, which is manifested by certain patterns of bit-errors. Error correction codes are constructed for this model based upon generalized tensor product codes. For fixed levels of redundancy, these codes are shown to exhibit substantially lower bit error rates than existing error correction schemes.

Multi-level flash memory cells represent data by the amount of charge stored in them. Certain voltages are applied to the flash memory cells to inject charges when programming and the cell level can be only increased during the programming process as a result of the high cost of block erasures. To achieve a high speed during writing, parallel programming is used, whereby a common voltage is applied to a group of cells to inject charges simultaneously. The voltage sharing simplifies the circuitry and increases the programming speed, but it also affects the precision of charge injection and limits the storage capacity of flash memory cells. Another factor that limits the precision of cell programming is the thermal electronics noise induced in charge injection. In this paper, we focus on noiseless parallel programming of multiple cells and noisy programming of a single cell. We propose a new criterion to evaluate the performance of the cell programming which is more suitable for flash memories in practice and then we optimize the parallel programming strategy accordingly. We then proceed to noisy programming and consider the two scenarios where feedback on cell levels is either available during programming or not. We study the optimization problem under both circumstances and present algorithms to achieve the optimal performance.

Write-once memory (WOM) is a binary storage medium in which each memory cell is initially in state 0 and can be irreversibly programmed to state 1. This paper studies the problem of writing multiple messages into a WOM. Instead of writing a new message (and obliterating old ones) as in the traditional setup, the user wishes to retain access to some of the previously written messages. The capacity region is studied and code constructions are proposed for three canonical cases.

Abstract—We (people) are memory machines. Our decision processes, emotions and interactions with the world around us are based on and driven by associations to our memories. This natural association paradigm will become critical in future memory systems, namely, the key question will not be “How do I store more information? ” but rather, “Do I have the relevant information? How do I retrieve it?” The focus of this paper is to make a first step in this direction. We define and solve a very basic problem in associative retrieval. Given a word W, the words in the memory that are t-associated with W are the words in the ball of radius t around W. In general, given a set of words, say W, X and Y, the words that are t-associated with {W, X, Y} are those in the memory that are within distance t from all the three words. Our main goal is to study the maximum size of the t-associated set as a function of the number of input words and the minimum distance of the words in memory- we call this value the uncertainty of an associative memory. We derive the uncertainty of the associative memory that consists of all the binary vectors with an arbitrary number of input words. In addition, we study the retrieval problem, namely, how do we get the t-associated set given the inputs? We note that this paradigm is a generalization of the sequences reconstruction problem that was proposed by Levenshtein (2001). In this model, a word is transmitted over multiple channels. A decoder receives all the channel outputs and decodes the transmitted word. Levenshtein computed the minimum number of channels that guarantee a successful decoder- this value happens to be the uncertainty of an associative memory with two input words. I.

Symbol-pair read channels, in which the outputs of the read process are pairs of consecutive symbols, were recently studied by Cassuto and Blaum. This new paradigm is motivated by the limitations of the reading process in high density data storage systems. They studied error correction in this new paradigm, specifically, the relationship between the minimum Hamming distance of an error correcting code and the minimum pair distance, which is the minimum Hamming distance between symbol-pair vectors derived from codewords of the code. It was proved that for a linear cyclic code with minimum Hamming distance dH, the corresponding minimum pair distance is at least dH+ 3. Our main contribution is proving that, for a given linear cyclic code with a minimum Hamming distance dH, the minimum pair distance is at least dH+ [dH/2]. We also describe decoding algorithms, based upon bounded distance decoders for the cyclic code, whose pair-symbol error correcting capabilities reflects the larger minimum pair distance. In addition, we consider the case where a read channel output is a prescribed number, b >; 2, of consecutive symbols and provide some generalizations of our results. We note that the symbol-pair read channel problem is a special case of the sequence reconstruction problem that was introduced by Levenshtein.

Write-once memory (WOM) is a storage medium with memory elements, called cells, which can take on q levels. Each cell is initially in level 0 and can only increase its level. A t-write WOM code is a coding scheme which allows one to store t messages to the WOM such that on consecutive writes every cell's level does not decrease. The sum-rate of the WOM code, which is the ratio between the total amount of information written in the t writes and the number of memory cells, is bounded by log2(t + 1). Our main contribution in this work is a construction of binary three-write WOM codes with sum-rate approaching 1.885 for sufficiently large number of cells, while the upper bound is 2. This improves upon a recent construction of sum-rate 1.809. We also give constructions of non-binary WOM codes which give better sum-rate than the currently best known ones.

A write-once memory (WOM) is a storage device that consists of cells that can take on$q$values, with the added constraint that rewrites can only increase a cell's value. A length-$n$,$t$-write WOM-code is a coding scheme that allows$t$messages to be stored in$n$cells. If on the$i$th write we write one of$M_{i}$messages, then the rate of this write is the ratio of the number of written bits to the total number of cells, i.e.,$\log_{2}M_{i}/n$. The sum-rate of the WOM-code is the sum of all individual rates on all writes. A WOM-code is called a fixed-rate WOM-code if the rates on all writes are the same, and otherwise, it is called a variable-rate WOM-code. We address two different problems when analyzing the sum-rate of WOM-codes. In the first one, called the fixed-rate WOM-code problem, the sum-rate is analyzed over all fixed-rate WOM-codes, and in the second problem, called the unrestricted-rate WOM-code problem, the sum-rate is analyzed over all fixed-rate and variable-rate WOM-codes. In this paper, we first present a family of two-write WOM-codes. The construction is inspired by the coset coding scheme, which was used to construct multiple-write WOM-codes by Cohenand recently by Wu, in order to construct from each linear code a two-write WOM-code. This construction improves the best known sum-rates for the fixed- and unrestricted-rate WOM-code problems. We also show how to take advantage of two-write WOM-codes in order to construct codes for the Blackwell channel. The two-write construction is generalized for two-write WOM-codes with$q$levels per cell, which is used with ternary cells to construct three- and four-write binary WOM-codes. This construction is used recursively in order to generate a family of$t$-write WOM-codes for all$t$. A further generalization of these$t$-write WOM-codes yields additional families of efficient WOM-codes. Finally, we show a recursive method that uses the previously constructed WOM-codes in order to construct fixed-rate WOM-codes. We conclude and show that the WOM-codes constructed here outperform all previously known WOM-codes for$2\leqslant t\leqslant 10$for both the fixed- and unrestricted-rate WOM-code problems.

A Write Once Memory (WOM) is a storage medium with binary memory elements, called cells, that can change from the zero state to the one state only once. Examples of WOMs include punch cards and optical disks. WOM-codes, introduced by Rivest and Shamir, permit the reuse of a WOM by taking into account the location of cells that have already been changed to the one state. The objective in designing WOM-codes is to use the fewest number of cells to store a specified number of information bits in each of several reuses of the memory. An [n,k,t] WOM-code C is a coding scheme for storing k information bits in n cells t times. At each write, the state of each cell can be changed, provided that the cell is changed from the zero state to the one state. The rate of C, defined by R(C) = kt/n, indicates the total amount of information that is possible to store in a cell in t writes. Two WOM-code constructions correcting a single cell-error were presented by Zemor and Cohen. In this paper, we present another construction of a single-error-correcting WOM-code with a better rate. Our construction can be adapted also for single-error-detection, double-error-correction, and triple-error-correction. For the last case, we use triple-error-correcting BCH-like codes, which were presented by Kasami and more recently described again by Bracken and Helleseth. Finally, we show two constructions that can be combined for the correction of an arbitrary number of errors.

Phase-change memory (PCM) is a promising non- volatile solid-state memory technology. A PCM cell stores data by using its amorphous and crystalline states. The cell changes between these two states using high temperature. However, since the cells are sensitive to high temperature, it is important, when programming cells, to balance the heat both in time and space. In this paper, we study the time-space constraint for PCM, which was recently proposed by Jiang et al. A code is called an (α, β, p)-constrained code if for any tx consecutive rewrites and for any segment of β contiguous cells, the total rewrite cost of the β cells over those a rewrites is at most p. Here, the cells are binary and the rewrite cost is defined to be the Hamming distance between the current and next memory states. First, we show a general upper bound on the achievable rate of these codes which extends the results of Jiang et al. Then, we generalize their construction for (α ≥ 1,β = 1,p = 1)-constrained codes and show another construction for (α = 1, β ≥, p≥1)- constrained codes. Finally, these two constructions are used to construct codes for all values of α, β, and p.

In multi-level flash memories, the dominant cell errors are asymmetric with limited-magnitude. With such an error model in mind, Cassuto et al. recently developed bounds and constructions for codes correcting t asymmetric errors with magnitude no more than ℓ. However, a more refined model of these memory devices reflects the fact that typically only a small number of errors have large magnitude while the remainder are of smaller magnitude. In this work, we study such an error model, in which at most t1errors of maximum magnitude ℓ1and at most t2errors of maximum magnitude ℓ2, with ℓ12, can occur. We adapt the analysis and code construction of Cassuto, et al. for the refined error model and assess the relative efficiency of the new codes. We then consider in more detail specific constructions for the case where t1= t2= 1, ℓ1= 1, and ℓ2>; 1.

A Write-Once Memory (WOM)-code is a coding scheme that allows information to be written in a memory block multiple times, but in a way that the stored values are not decreased across writes. This work studies non-binary WOM-codes with applications to flash memory. We present two constructions of non-binary WOM-codes that leverage existing high sum-rate WOM-codes defined over smaller alphabets. In many instances, these constructions provide the highest known sum-rates of the non-binary WOM-codes. In addition, we introduce a new class of codes, called level distance WOM-codes, which mitigate the difficulty of programming a flash memory cell by eliminating all small-magnitude level increases. We show how to construct such codes and state an upper bound on their sum-rate.

In this paper we construct multidimensional codes with high dimension. The codes can correct high dimensional errors which have the form of either small clusters, or confined to an area with a small radius. We also consider small number of errors in a small area. The clusters which are discussed are mainly spheres such as semi-crosses and crosses. Also considered are clusters with small number of errors such as 2-bursts, two errors in various clusters, and three errors on a line. Our main focus is on the redundancy of the codes when the most dominant parameter is the dimension of the code.

A Write Once Memory (WOM) is a storage medium with binary memory elements, called cells, that can change from the zero state to the one state only once. Examples of WOMs are punch cards, optical disks, and more recently flash memories. WOM-codes were first presented by Rivest and Shamir and are designed for efficiently storing and updating data in the WOM. A WC[n, k, t] WOM-Code CWis a coding scheme for storing k information bits in n cells t times. At each write, the state of each cell can be changed, provided that the cell is changed from the zero state to the one state. The WOM-Rate of CW, defined to be Rt(CW) = kt/n, indicates the total amount of information that is possible to store in a cell in t writes. Two WOM-code constructions that can correct a single cell-error were presented by Zémor and Cohen. In this paper, we present another construction of a single-error-correcting WOM-codes with a better WOM-rate. Our construction can be adjusted also for single-error-detection, double-error-correction, and triple-error-correction. For the latter case, we use triple-error-correcting BCH-like codes, which were showed by Kasami and more recently described again by Bracken and Helleseth.

Several new applications and a number of new mathematical techniques have increased the research on error-correcting codes in the Lee metric in the last decade. In this work we consider several coding problems and constructions of error-correcting codes in the Lee metric. First, we consider constructions of dense error-correcting codes in relatively small dimensions over small alphabets. The second problem we solve is construction of diametric perfect codes with minimum distance four. We will construct such codes over various lengths and alphabet sizes. The third problem is to transfer an n-dimensional Lee sphere with large radius into a shape, with the same volume, located in a relatively small box. Hadamard matrices play an essential role in the solutions for all three problems. A construction of codes based on Hadamard matrices will start our discussion. These codes approach the sphere packing bound for very high rate range and appear to be the best known codes over some sets of parameters.

Parallel programming is an important tool used in flash memories to achieve high write speed. In parallel programming, a common programm voltage is applied to many cells for simultaneous charge injection. This property significantly simplifies the complexity of the memory hardware, and is a constraint that limits the storage capacity of flash memories. Another important property is that cells have different hardness for charge injection. It makes the charge injected into cells differ even when the same program voltage is applied to them. In this paper, we study the parallel programming of flash memory cells, focusing on the above two properties. We present algorithms for parallel programming when there is information on the cells' hardness for charge injection, but there is no feedback information on cell levels during programming. We then proceed to the programming model with feedback information on cell levels, and study how well the information on the cells' hardness for charge injection can be obtained. The results can be useful for understanding the storage capacity of flash memories with parallel programming.

A Write Once Memory (WOM) is a storage medium with binary memory elements, called cells, that can change from the zero state to the one state only once. Examples of WOMs are punch cards, optical disks, and more recently flash memories. A t-write WOM-code is a coding scheme for storing t messages in n cells in such a way that each cell can change its value only from the zero state to the one state. The WOM-rate of a t-write WOM-code is the ratio of the total amount of information written to the WOM in t writes to the number of cells. In this paper we present a family of 2-write WOM-codes. It is shown how to construct from each linear code C a 2-write WOM-code. Then, we find 2-write WOM-codes that improve the best known WOM-rate with two writes. This scheme is proved to be capacity achieving when the parity check matrix of the linear code C is chosen uniformly at random. Finally, we show how to take advantage of 2-write WOM-codes in order to construct codes for the Blackwell channel.

Flash memory is a nonvolatile computer memory comprised of blocks of cells, wherein each cell is implemented as either NAND or NOR floating gate. NAND flash is currently the most widely used type of flash memory. In a NAND flash memory, every block of cells consists of numerous pages; rewriting even a single page requires the whole block to be erased and reprogrammed. Block erasures determine both the longevity and the efficiency of a flash memory. Therefore, when data in a NAND flash memory are reorganized, minimizing the total number of block erasures required to achieve the desired data movement is an important goal. This leads to the flash data movement problem studied in this paper. We show that coding can significantly reduce the number of block erasures required for data movement, and present several optimal or nearly optimal data-movement algorithms based upon ideas from coding theory and combinatorics. In particular, we show that the sorting-based (noncoding) schemes require$O(n\log n)$erasures to move data among$n$blocks, whereas coding-based schemes require only$O(n)$erasures. Furthermore, coding-based schemes use only one auxiliary block, which is the best possible and achieve a good balance between the number of erasures in each of the$n+1$blocks.

NAND flash memories are currently the most widely used flash memories. In a NAND flash memory, although a cell block consists of many pages, to rewrite one page, the whole block needs to be erased and reprogrammed. Block erasures determine the longevity and efficiency of flash memories. So when data is frequently reorganized, which can be characterized as a data movement process, how to minimize block erasures becomes an important challenge. In this paper, we show that coding can significantly reduce block erasures for data movement, and present several optimal or nearly optimal algorithms. While the sorting-based non-coding schemes require O(n log n) erasures to move data among n blocks, coding-based schemes use only O(n) erasures and also optimize the utilization of storage space.

Flash memory is a non-volatile computer memory comprised of blocks of cells, wherein each cell can take on q different values or levels. While increasing the cell level is easy, reducing the level of a cell can be accomplished only by erasing an entire block. Since block erasures are highly undesirable, coding schemes - known as floating codes or flash codes - have been designed in order to maximize the number of times that information stored in a flash memory can be written (and re-written) prior to incurring a block erasure. An (n, k, t)qflash code ¿ is a coding scheme for storing k information bits in n cells in such a way that any sequence of up to t writes (where a write is a transition 0 ¿ 1 or 1 ¿ 0 in any one of the k bits) can be accommodated without a block erasure. The total number of available level transitions in n cells is n(q-1), and the write deficiency of ¿, defined as ¿(¿) = n(q-1)-t, is a measure of how close the code comes to perfectly utilizing all these transitions. For k > 6 and large n, the best previously known construction of flash codes achieves a write defficiency of O(qk2). On the other hand, the best known lower bound on write deficiency is ¿(qk). In this paper, we present a new construction of flash codes that approaches this lower bound to within a factor logarithmic in k. To this end, we first improve upon the so-called ¿indexed¿ flash codes, due to Jiang and Bruck, by eliminating the need for index cells in the Jiang-Bruck construction. Next, we further increase the number of writes by introducing a new multi-stage (recursive) indexing scheme. We then show that the write defficiency of the resulting flash codes is O(qk log k) if q ¿ log2k, and at most O(k log2k) otherwise.

Despite flash memory's promise, it suffers from many idiosyncrasies such as limited durability, data integrity problems, and asymmetry in operation granularity. As architects, we aim to find ways to overcome these idiosyncrasies while exploiting flash memory's useful characteristics. To be successful, we must understand the trade-offs between the performance, cost (in both power and dollars), and reliability of flash memory. In addition, we must understand how different usage patterns affect these characteristics. Flash manufacturers provide conservative guidelines about these metrics, and this lack of detail makes it difficult to design systems that fully exploit flash memory's capabilities. We have empirically characterized flash memory technology from five manufacturers by directly measuring the performance, power, and reliability. We demonstrate that performance varies significantly between vendors, devices, and from publicly available datasheets. We also demonstrate and quantify some unexpected device characteristics and show how we can use them to improve responsiveness and energy consumption of solid state disks by 44% and 13%, respectively, as well as increase flash device lifetime by 5.2x.

We present several methods and constructions to generate binary codes for correction of a multidimensional cluster- error, whose shape can be a box-error, a Lee sphere error, or an error with an arbitrary shape. Our codes have very low redundancy, close to optimal, and a large range of parameters of arrays and clusters. Our main results are summarized as follows. 1) A construction of two-dimensional codes capable to correct a rectangular-error with considerably more flexible parameters from previously known constructions. This construction is easily generalized for D dimensions. 2) A novel method based on D colorings of the D -dimensional space for constructing D -dimensional codes correcting a D -dimensional cluster-error of various shapes. 3) A transformation of the D -dimensional space into another D -dimensional space in a way that a D -dimensional Lee sphere is transformed into a shape located in a D-dimensional box of a relatively small size. 4) Applying the coloring method to correct more efficiently a two-dimensional error whose shape is a Lee sphere. 5) A construction of D -dimensional codes capable to correct a D -dimensional cluster-error of size b in which the number of erroneous positions is relatively small compared to b. 6) We present a code which corrects a D -dimensional arbitrary cluster-error with relatively small redundancy.

A construction for D-dimensional binary codes of size n1timesn2timeshelliptimesnDcorrecting a single D-dimensional box error is presented. If the size of the box error is b1timesb2timeshelliptimesbD, biodd, 1les i les D, and B = PiiD=1bi, then the redundancy of the code is at most [log2(n1n2hellip nD)] +B + (D-2)[log2B] + [log2b1]. For a two-dimensional binary array of size n times n we present a code correcting an error whose shape is a Lee sphere with radius R. The redundancy of the code is at most [log2n2] + 2R2+ 2R + [2log2(2R+1)]+1. This is also the redundancy of a binary code which corrects an arbitrary two-dimensional cluster-error of size 2R+1. A generalization for D-dimensional code which corrects either D-dimensional error whose shape is a Lee sphere or an arbitrary cluster-error is also given.