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.

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.

Space-filling curves (SFC, for short) have been widely applied to index multi-dimensional data, which first maps the data to one dimension, and then a one-dimensional indexing method, e.g., the B-tree indexes the mapped data. Existing SFCs adopt a single mapping scheme for the whole data space. However, a single mapping scheme often does not perform well on all the data space. In this paper, we propose a new type of SFC called piecewise SFCs that adopts different mapping schemes for different data subspaces. Specifically, we propose a data structure termed the Bit Merging tree (BMTree) that can generate data subspaces and their SFCs simultaneously, and achieve desirable properties of the SFC for the whole data space. Furthermore, we develop a reinforcement learning-based solution to build the BMTree, aiming to achieve excellent query performance. To update the BMTree efficiently when the distributions of data and/or queries change, we develop a new mechanism that achieves fast detection of distribution shifts in data and queries, and enables partial retraining of the BMTree. The retraining mechanism achieves performance enhancement efficiently since it avoids retraining the BMTree from scratch. Extensive experiments show the effectiveness and efficiency of the BMTree with the proposed learning-based methods.

The proliferation of 3D scanning technology, particularly within autonomous driving, has led to an exponential increase in the volume of Point Cloud (PC) data. Given the rich semantic information contained in PC data, deep learning models are commonly employed for tasks such as object queries. However, current query systems that support PC data types do not process queries on semantic information. Consequently, there is a notable gap in research regarding the efficiency of invoking deep models for each PC data query, especially when dealing with large-scale models and datasets. To address this issue, this work aims to design an efficient approximate approach for supporting PC analysis queries, including PC retrieval and aggregate queries. In particular, we propose a novel framework that delivers approximate query results efficiently by sampling core PC frames within a constrained budget, thereby minimizing the reliance on deep learning models. This framework is underpinned by rigorous theoretical analysis, providing error-bound guarantees for the approximate results if the sampling policy is preferred. To achieve this, we incorporate a multi-agent reinforcement learning-based approach to optimize the sampling procedure, along with an innovative reward design leveraging spatio-temporal PC analysis. Furthermore, we exploit the spatio-temporal characteristics inherent in PC data to construct an index that accelerates the query process. Extensive experimental evaluations demonstrate that our proposed method, MAST, not only achieves accurate approximate query results but also maintains low query latency, ensuring high efficiency.

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.

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

To measure repair latency at helper nodes, we introduce a new metric called skip cost that quantifies the number of contiguous sections accessed on a disk. We provide explicit constructions of zigzag codes and fractional repetition codes that incur zero skip cost.

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.

Motivated by the use of trace codes in low-bandwidth repair, we investigate the decoding of a Reed-Solomon subcode whose information polynomials are characterized by a known sparse support. We ask: Can we correct more errors by leveraging the known structure of the information polynomial? We affirmatively respond to this query by introducing two schemes designed to complement any Reed-Solomon decoder. Our findings demonstrate better error-correcting capabilities than the naive way to decode based on the maximum degree of the information polynomial.

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.

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.

We generalize the problem of recovering a lost/erased symbol in a Reed-Solomon code to the scenario in which some side information about the lost symbol is known. The side information is represented as a set$S$of linearly independent combinations of the sub-symbols of the lost symbol. When$S=\varnothing$, this reduces to the standard problem of repairing a single codeword symbol. When$S$is a set of sub-symbols of the erased one, this becomes the repair problem with partially lost/erased symbol. We first establish that the minimum repair bandwidth depends on$\vert S\vert$and not the content of$S$and construct a lower bound on the repair bandwidth of a linear repair scheme with side information$S$We then consider the well-known subspace-polynomial repair schemes and show that their repair bandwidths can be optimized by choosing the right subspaces. Finally, we demonstrate several parameter regimes where the optimal bandwidths can be achieved for full-length Reed-Solomon codes.

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 consider the problem of evaluating distinct multivariate polynomials over several massive datasets in a distributed computing system with a single master node and multiple worker nodes. We focus on the general case when each multivariate polynomial is evaluated over its corresponding dataset and propose a generalization of the Lagrange Coded Computing framework (Yu et al., 2019) to perform all computations simultaneously while providing robustness against stragglers who do not respond in time, adversarial workers who respond with wrong computation and information-theoretic security of dataset against colluding workers. Our scheme introduces a small computation overhead which results in a reduction in download cost and also offers comparable resistance to stragglers over existing solutions. On top of it, we also propose two verification schemes to detect the presence of adversaries, which leads to incorrect results, without involving additional nodes.

Private Information Retrieval (PIR) protocols allow a client to retrieve any file of interest while keeping the files identity hidden from the database servers. While many existing PIR protocols assume servers to be honest but curious, we investigate the scenario of dishonest servers that provide incorrect answers to mislead clients into obtaining wrong results. We propose a unified framework for polynomial PIR protocols encompassing various existing protocols that optimize the download rate or total communication cost. We introduce a way to transform a polynomial PIR to a verifiable one without increasing the number of involved servers by doubling the queries. The security guarantees can be information-theoretic or computational, and the verification keys can be public or private. Moreover, in one of our protocols, the ratio between the additional download overhead associated with verification and the normal download cost approaches zero as the file size goes to infinity.

Recovery sets for vectors and subspaces are important in the construction of distributed storage system codes. These concepts are also interesting in their own right. In this paper, we consider the following very basic recovery question: what is the maximum number of possible pairwise disjoint recovery sets for each recovered element? The recovered elements in this work ared-dimensional subspaces of ak-dimensional vector space over$\mathbb {F}_{q}$. Each server stores one representative for each distinct one-dimensional subspace of thek-dimensional vector space, or equivalently a distinct point of PG$(k-1,q)$. As column vectors, the associated vectors of the stored one-dimensional subspaces form the generator matrix of the$[(q^{k} -1)/(q-1),k,q^{k-1}]$simplex code over$\mathbb {F}_{q}$. Lower bounds and upper bounds on the maximum number of such recovery sets are provided. It is shown that generally, these bounds are either tight or very close to being tight.

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

Motivated by applications in distributed storage, distributed computing, and homomorphic secret sharing, we study communication-efficient schemes for computing linear combinations of coded symbols. Specifically, we design low-bandwidth schemes that evaluate the weighted sum of ℓ coded symbols in a codewordc∈ Fn, when we are given access todof the remaining components inc. Formally, suppose that F is a field extension of B of degreet. Letcbe a codeword in a Reed-Solomon code of dimensionkand our task is to compute the weighted sum of ℓ coded symbols. In this paper, for somest, we provide an explicit scheme that performs this task by downloadingd(t-s) sub-symbols in B fromdavailable nodes, wheneverd≥ ℓ|B|s-ℓ +k. In many cases, our scheme outperforms previous schemes in the literature. Furthermore, we provide a characterization of evaluation schemes for general linear codes. Then in the special case of Reed-Solomon codes, we use this characterization to derive a lower bound for the evaluation bandwidth.

The synthesis of DNA strands remains the most costly part of the DNA storage system. Thus, to make DNA storage system more practical, the time and materials used in the synthesis process have to be optimized. We consider the most common type of synthesis process where multiple DNA strands are synthesized in parallel from a common alternating supersequence, one nucleotide at a time. The synthesis time or the number of synthesis cycles is then determined by the length of this common supersequence. In this model, we design quaternary codes that minimizes synthesis time that can correct deletions or insertions, which are the most prevalent types of error in arraybased synthesis. We also propose polynomial-time algorithms that encode binary strings into these codes whose rates are close to the capacity.

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

Motivated by applications in distributed storage, distributed computing, and homomorphic secret sharing, we study communication-efficient schemes for computing linear combinations of coded symbols. Specifically, we design low-bandwidth schemes that evaluate the weighted sum of ℓ coded symbols in a codeword ${\mathbf{c}} \in {\mathbb{F}^n}$, when we are given access to d of the remaining components in c. Formally, suppose that $\mathbb{F}$ is a field extension of $\mathbb{B}$ of degree t. Let c be a codeword in a Reed-Solomon code of dimension k and our task is to compute the weighted sum of ℓ coded symbols. In this paper, for some s < t, we provide an explicit scheme that performs this task by downloading d(t − s) sub-symbols in $\mathbb{B}$ from d available nodes, whenever $d \geq \ell |\mathbb{B}{|^s} - \ell + k$. In many cases, our scheme outperforms previous schemes in the literature. Furthermore, we provide a characterization of evaluation schemes for general linear codes. Then in the special case of Reed-Solomon codes, we use this characterization to derive a lower bound for the evaluation bandwidth.

Private Information Retrieval (PIR) schemes allow a client to retrieve any file of interest, while hiding the file identity from the database servers. In contrast to most existing PIR schemes that assume honest-but-curious servers, we study the case of dishonest servers. The latter provide incorrect answers and try to persuade the client to output the wrong result. We introduce several PIR schemes with information-theoretic privacy and result verification for the case of two servers. Security guarantees can be information-theoretical or computational, and the verification keys can be public or private. In this work, our main performance metric is the download rate.

We consider the problem of designing a Private Information Retrieval (PIR) scheme on m files replicated on k servers that can collude or, even worse, can return incorrect answers. Our goal is to correctly retrieve a specific message while keeping its identity private from the database servers. We consider the asymptotic information-theoretic capacity of this problem defined as the maximum ratio of the number of correctly retrieved symbols to the downloaded one for a large enough number of stored files. We propose an achievable scheme with a small file size and prove that such a file size is minimal for the fixed number of retrieved symbols, solving the problem pointed out by Banawan and Ulukus.A full version [1] of this paper is accessible at: https://arxiv.org/abs/2302.02230

We consider the repair scheme of Guruswami-Wootters for the Reed-Solomon code and ask: can we correctly repair a failed node in the presence of erroneous nodes? Equivalently, we consider the collection of downloaded traces as a code and investigate its code-distance properties. We propose three lower bounds on its minimum distance and study methods to efficiently correct errors close to these bounds.

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

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}$.

We consider the problem of evaluating arbitrary multivariate polynomials over several massive datasets in a distributed computing system with a single master node and multiple worker nodes. We focus on the general case when each multivariate polynomial is evaluated over its dataset and propose a generalization of the Lagrange Coded Computing framework (Yu et al. 2019) to provide robustness against stragglers who do not respond in time, adversarial workers who respond with wrong computation and information-theoretic security of dataset against colluding workers. Our scheme introduces a small computation overhead which results in a reduction in download cost and also offers comparable resistance to stragglers over existing solutions.

To index multi-dimensional data, space-filling curves (SFCs) have been used to map the data to one dimension, and then a one-dimensional indexing method such as the B-tree is used to index the mapped data. The existing SFCs all adopt a single mapping scheme for the whole data space. However, a single mapping scheme often does not perform well on all the data space. In this paper, we propose a new type of SFC called piecewise SFCs, which adopts different mapping schemes for different data subspaces. Specifically, we propose a data structure called Bit Merging tree (BMTree), which can generate data subspaces and their SFCs simultaneously and achieve desirable properties of the SFC for the whole data space. Furthermore, we develop a reinforcement learning based solution to build the BMTree, aiming to achieve excellent query performance. Extensive experiments show that our proposed method outperforms existing SFCs in terms of query performance.

In this work, we study two types of constraints on two-dimensional binary arrays. Given$p\in [{0,1}],\epsilon \in [{0,1/2}]$, we study 1) the$p$-bounded constraint: a binary vector of size$n$is said to be$p$-bounded if its weight is at most$pn$, and 2) the$\epsilon $-balanced constraint: a binary vector of size$n$is said to be$\epsilon $-balanced if its weight is within$\big [(1/2-\epsilon)n, (1/2+\epsilon)n\big]$. Such constraints are crucial in several data storage systems, those regard the information data as two-dimensional (2D) instead of one-dimensional (1D), such as the crossbar resistive memory arrays and the holographic data storage. In this work, efficient encoding/decoding algorithms are presented for binary arrays so that the weight constraint (either$p$-bounded constraint or$\epsilon $-balanced constraint) is enforced over every row and every column, regarded as 2D row-column (RC) constrained codes; or over every window (where each window refers to as a subarray consisting of consecutive rows and consecutive columns), regarded as 2D sliding-window (SW) constrained codes. While low-complexity designs have been proposed in the literature, mostly focusing on 2D RC constrained codes where$p=1/2$and$\epsilon =0$, this work provides efficient coding methods that work for both 2D RC constrained codes and 2D SW constrained codes, and more importantly, the methods are applicable for arbitrary values of$p$and$\epsilon $. Furthermore, for certain values of$p$and$\epsilon $, we show that, for sufficiently large array size, there exists linear-time encoding/decoding algorithm that incurs at most one redundant bit.

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}$.

We revisit the well-known Gilbert-Varshamov (GV) bound for constrained systems. In 1991, Kolesnik and Krachkovsky showed that GV bound can be determined via the solution of some optimization problem. Later, Marcus and Roth (1992) modified the optimization problem and improved the GV bound in many instances. In this work, we provide explicit numerical procedures to solve these two optimization problems and hence, compute the bounds. We then show the procedures can be further simplified when we plot the respective curves.

In this work, given n,ϵ > 0, two efficient encoding (decoding) methods are presented for mapping arbitrary data to (from) n×n binary arrays in which the weight of every row and every column is within [(1/2–ϵ)n, (1/2+ϵ)n], which is referred to as the ϵ-balanced constraint. The first method combines the divide and conquer algorithm and a modification of the Knuth’s balancing technique, resulting a redundancy of Θ(n) bits. On the other hand, for sufficiently large n, the second method uses the sequence replacement technique, which costs only 1 redundant bit. The latter method reduces significantly the redundancy of the best known encoder for two-dimensional p-bounded weight constrained codes from (n + 3) bits to a single bit.

Transmit a codeword x, that belongs to an (ℓ − 1)deletion-correcting code of length n, over a t-deletion channel for some 1 ≤ ℓ ≤ t < n. Levenshtein, in 2001, proposed the problem of determining N(n,ℓ,t) + 1, the minimum number of distinct channel outputs required to uniquely reconstruct x. Prior to this work, N(n,ℓ,t) is known only when ℓ ∈ {1,2}. Here, we provide an asymptotically exact solution for all values of ℓ and t. Specifically, we show that $N(n,\ell ,t) = \binom{{2\ell }}{\ell}/(t - \ell )!{n^{t - \ell }} - O\left( {{n^t}^{ - \ell - 1}} \right)$ and in the special instance where ℓ = t, we show that $N(n,\ell ,\ell ) = \binom{{2\ell }}{\ell}$. We also provide a conjecture on the exact value of N(n,ℓ,t) for all values of n, ℓ, and t.

The prevalence of GPS-enabled mobile devices and location-based services yield massive volume of spatial objects where each object contains information including geographical location, name, address, category and other attributes. This paper introduces a novel type of query termedexample-based spatial pattern matching(EPM) query. It takes as input a set of spatial objects, each of which is associated with one or more keywords and a location. These objects serve as an example that depicts the spatial pattern that users want to retrieve. The EPM query returns all sets of objects that match the spatial pattern. The EPM query can be used for applications like urban planning, scene recognition and similar region search. We propose an efficient algorithm and three pruning techniques to answer EPM queries. Furthermore, we provide an approximation guarantee for intermediate results of the algorithm. Our experimental evaluations on four real-world datasets demonstrate the effectiveness and efficiency of our proposed algorithm and techniques.

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.

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.

We study segmented edit channels where the channel input is divided into disjoint segments, and each segment suffers at most one error, either a deletion or an insertion. The model was first introduced by Liu and Mitzenmacher [2010] over the binary alphabet, and was extended for the q-ary alphabet by Abroshan et al. [2018]. In this work, we first propose an efficient construction for segments with less redundancy than previous works, hence significantly improving the redundancy over the entire sequence, for any q-ary alphabet where$q$≥ 3. Additionally, motivated by the applications of constrained codes in DNA-based data storage systems and energy harvesting communication channels, to reduce the probability of having errors, we also impose certain weight constraints in every segment instead of over the whole sequence. In particular, for DNA storage systems, besides error correction capability, our coding method guarantees that all segments in every codeword are almost GC-balanced.

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

A two-deletion correcting code of length$n$is defined to be a set of binary words such that a codeword can be uniquely identified from any one of its length- ($n-2$) subsequence. A two-deletion correcting code requires at least$2\log n+O(1)$, while the best known explicit construction uses$4\log n+o(\log n)$redundant bits. In this work, we study this coding problem in the framework of the sequence reconstruction problem and require the receiver to uniquely reconstruct a codeword from any$N\geqslant 2$of its length- ($n-2$) subsequences. Specifically, we provide an explicit code construction that uniquely reconstructs a codeword from any five of its length-($n-2$) subsequences, using only$2\log n+o(\log n)$redundant bits.

The bee-identification problem, formally defined by Tandon, Tan and Varshney (2019), requires the receiver to identify “bees” using a set of unordered noisy measurements. In this previous work, Tandon, Tan and Varshney studied error exponents and showed that decoding the measurements jointly results in a significantly smaller error exponent. Here, we study efficient ways of performing joint decoding. First, by reducing to the problem of finding perfect matching and minimum-cost matchings, we obtain joint decoders that run in time quadratic and cubic in the number of “bees” for the binary erasure (BEC) and binary symmetric channels (BSC), respectively. Next, by studying the matching algorithms in the context of channel coding, we further reduce the running times by using classical tools like peeling decoders and list-decoders. In particular, we show that our identifier algorithms when used with Reed-Muller codes terminates in almost linear and quadratic time for BEC and BSC, respectively.

An indel refers to a single insertion or deletion, while an edit refers to a single insertion, deletion or substitution. In this article, we investigate codes that correct either a single indel or a single edit and provide linear-time algorithms that encode binary messages into these codes of length n. Over the quaternary alphabet, we provide two linear-time encoders. One corrects a single edit with ⌈log n⌉+ O(loglog n) redundancy bits, while the other corrects a single indel with ⌈log n⌉+2 redundant bits. These two encoders are order-optimal. The former encoder is the first known order-optimal encoder that corrects a single edit, while the latter encoder (that corrects a single indel) reduces the redundancy of the best known encoder of Tenengolts (1984) by at least four bits. Over the DNA alphabet, we impose an additional constraint: the GC-balanced constraint and require that exactly half of the symbols of any DNA codeword to be either C or G. In particular, via a modification of Knuth's balancing technique, we provide a linear-time map that translates binary messages into GC-balanced codewords and the resulting codebook is able to correct a single indel or a single edit. These are the first known constructions of GC-balanced codes that correct a single indel or a single edit.

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.

The class of multiset combinatorial batch codes (MCBCs) was introduced by Zhang et al. (2018) as a generalization of combinatorial batch codes (CBCs), which are replication-based batch codes. The MCBCs allow multiple users to retrieve items in parallel in a distributed storage and a fundamental objective in this study is to determine the minimum total storage given certain requirements. We formulate linear programs so that the optimal solutions provide lower bounds on the total storage of MCBCs. Borrowing techniques from linear programming, we improve known lower bounds in some cases. Furthermore, for some parameters, we showed that these lower bounds are either tight or asymptotically tight by constructing the corresponding codes.

We propose new repair schemes for Reed-Solomon codes that use subspace polynomials and hence generalize previous works in the literature that employ trace polynomials. The Reed-Solomon codes are over \mathbb Fqland have redundancy r = n-k ≥ qm, 1 ≤ m ≤l, where n and k are the code length and dimension, respectively. In particular, for one erasure, we show that our schemes can achieve optimal repair bandwidths whenever n=qland r = qm, for all 1 ≤ m ≤l. For two erasures, our schemes use the same bandwidth per erasure as the single erasure schemes, forl/m is a power of q, and forl= qa, m=qb-1 > 1 ( a ≥ b ≥ 1), and for m ≥l/2 whenlis even and q is a power of two.

We propose coding techniques that simultaneously limit the length of homopolymers runs, ensure the GC-content constraint, and are capable of correcting a single edit error in strands of nucleotides in DNA-based data storage systems. In particular, for givenl, ∈ > 0, we propose simple and efficient encoders/decoders that transform binary sequences into DNA base sequences (codewords), namely sequences of the symbols A, T, C and G, that satisfy all of the following properties: 1) runlength constraint: the maximum homopolymer run in each codeword is at mostl; 2) GC-content constraint: the GC-content of each codeword is within [0.5-∈,0.5+∈]; 3) error-correction: each codeword is capable of correcting a single deletion, or single insertion, or single substitution error. While various combinations of these properties have been considered in the literature, this work provides generalizations of codes constructions that satisfy all the properties with arbitrary parameters ofland ∈. Furthermore, for practical values ofland ∈, we show that our encoders achieve higher rates than existing results in the literature and approach capacity. Our methods have low encoding/decoding complexity and limited error propagation.

A nucleotide substitution is said to occur when a base in {A, T} is substituted for a base in {C, G}, or vice versa. Recent experiment (Heckel et al. 2019) showed that a nucleotide substitution occurs with a significantly higher probability than other substitution errors. A nucleotide edit refers to a single insertion, deletion or nucleotide substitution. In this paper, we investigate codes that corrects a single nucleotide edit and provide linear-time algorithms that encode binary messages into these codes of length n. Specifically, we provide an order-optimal encoder which corrects a single nucleotide edit with log n + log log n + O(1) redundant bits. We also demonstrate that the codewords obey certain runlength constraints and that the code can be modified to accommodate certain GC-content constraints..

The linear complexity of a sequence s is one of the measures of its predictability. It represents the smallest degree of a linear recursion which the sequence satisfies. There are several algorithms to find the linear complexity of a periodic sequence s of length N (where N is of some given form) over a finite field Fqin O(N) symbol field operations. The first such algorithm is The Games-Chan Algorithm which considers binary sequences of period 2n, and is known for its extreme simplicity. We generalize this algorithm and apply it efficiently for several families of binary sequences. Our algorithm is very simple, it requires βN bit operations for a small constant β, where N is the period of the sequence. We make an analysis on the number of bit operations required by the algorithm and compare it with previous algorithms. In the process, the algorithm also finds the recursion for the shortest linear feedback shift-register which generates the sequence. Some other interesting properties related to shift-register sequences, which might not be too surprising but generally unnoted, are also consequences of our exposition.

Recovery sets for vectors and subspaces are important in constructions of distributed storage system codes. These concepts are also interesting in their own right. In this paper we consider the following very basic recovery question: what is the maximum number of possible pairwise disjoint recovery sets if the recovered element is a d-dimensional subspace and the elements stored are the one-dimensional subspaces of an n-dimensional vector space over GF(q). Lower and upper bounds on the number of such recovery sets are provided. It is shown that generally these bounds are either tight or very close of being tight.

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

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.

The imbalance of a binary word refers to the absolute difference between the number of ones and zeros in the word. Motivated by applications in DNA-based data storage and the success of polar codes, we study the problem of reducing imbalance in the codewords of a polar code. To this end, we adapt the technique of Mazumdar, Roth, and Vontobel by considering balancing sets that correspond to low-order Reed-Muller (RM) codes. Such balancing sets are likely to be included as subcodes in polar codes.Specifically, using the first-order RM code, we show that any message can be encoded into a length-n polar codeword with imbalance at most o(n) in O(nlogn)-time. We then reduce the imbalance even further using two methods. First, we constrain the ambient space $\mathbb{X}$ and analyze the imbalance that the first-order RM code can achieve for words in $\mathbb{X}$. We demonstrate that for codelengths up to 128, the first-order RM code achieves zero imbalance for appropriate choices of $\mathbb{X}$ that sacrifice only a few message bits. Second, we augment the balancing set by considering higher order RM codes. We give a simple recursive upper bound for the guaranteed imbalance of RM codes. We also prove that the second-order RM code $\mathbb{R}\mathbb{M}\left( {2,m} \right)$ balances all even-weight words for m ⩽ 5, while the RM code of order m − 3 balances all even-weight words for m ⩾ 5.

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.

In this paper, we first propose coding techniques for DNA-based data storage which account the maximum homopolymer runlength and the GC-content. In particular, for arbitrary ℓ,ε>0, we propose simple and efficient (ℓ,ε)-constrained encoders that transform binary sequences into DNA base sequences (codewords), that satisfy the following properties: · Runlength constraint: the maximum homopolymer run in each codeword is at most ℓ, · GC-content constraint: the GC-content of each codeword is within [0.5-ε, 0.5+ε]. For practical values of ℓ and ε, our codes achieve higher rates than the existing results in the literature. We further design efficient (ℓ, ε)-constrained codes with error-correction capability. Specifically, the designed codes satisfy the runlength constraint, the GC-content constraint, and can correct a single edit (i.e. a single deletion, insertion, or substitution) and its variants. To the best of our knowledge, no such codes are constructed prior to this work.

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

Tandem duplication is the process of inserting a copy of a segment of DNA adjacent to the original position. Motivated by applications that store data in living organisms, Jain et al. (2017) proposed the study of codes that correct tandem duplications. All code constructions are based on irreducible words. Such code constructions are almost optimal to combat tandem duplications of length at most k where k ≤ 3. However, the problem of designing efficient encoder/decoder for such codes has not been investigated. In addition, the method cannot be extended to deal with the case of arbitrary k, where k ≥ 4. In this work, we study efficient encoding/decoding methods for irreducible words over general q-ary alphabet. Our methods provide the first known efficient encoder/decoder for q-ary codes correcting tandem duplications of length at most k, where k ≤ 3. In particular, we describe an (1, m)-finite state encoder and show that when m = Θ(1/ε) and ϊ = Θ(1/ε), the encoder achieves rate that is ε away from the optimal rate. We also provide ranking/unranking algorithms for irreducible words and modify the algorithms to reduce the space requirements for the finite state encoder. Over the DNA alphabet (or quaternary alphabet), we also impose weight constraint on the codewords. In particular, a quaternary word is GC-balanced if exactly half of the symbols of are either C or G. Via a modification of Knuth's balancing technique, we provide an efficient method that translates quaternary messages into GC-balanced codewords and the resulting codebook is able to correct tandem duplications of length at most k, where k ≤ 3. In addition, we provide the first known construction of codes to combat tandem duplications of length at most k, where k ≥ 4. Such codes can correct duplication errors in linear-time and they are almost optimal in terms of rate.

In a bus with n wires, each wire has two states, `0' or `1', representing one bit of information. Whenever the state transitions from `0' to `1', or `1' to `0', joule heating causes the temperature to rise, and high temperatures have adverse effects on on-chip bus performance. Recently, the class of low-power cooling (LPC) codes was proposed to control such state transitions during each transmission. As suggested in earlier work, LPC codes may be used to control simultaneously both the peak temperature and the average power consumption of on-chip buses. Specifically, an (n, t, w)-LPC code is a coding scheme over n wires that (i) avoids state transitions on the t hottest wires (thus preventing the peak temperature from rising); and (ii) allows at most w state transitions in each transmission (thus reducing average power consumption). In this paper, for any fixed value of w, several constructions are presented for large LPC codes that can be encoded and decoded in time O(n log2(n/w)) along with the corresponding encoding/decoding schemes. In particular, we construct LPC codes of size (n/w)w-1, which are asymptotically optimal. We then modify these LPC codes to also correct errors in time O(n3). For the case where w is proportional to n, we further present a different construction of large LPC codes, based on a mapping from cooling codes to LPC codes. Using this construction, we obtain two families of LPC codes whose encoding and decoding complexities are O(n3).

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.

To equip DNA-based data storage with random-access capabilities, Yazdi et al. (2018) prepended DNA strands with specially chosen address sequences called primers and provided certain design criteria for these primers. We provide explicit constructions of error-correcting codes that are suitable as primer addresses and equip these constructions with efficient encoding algorithms. Specifically, our constructions take cyclic or linear codes as inputs and produce sets of primers with similar error-correcting capabilities. Using certain classes of BCH codes, we obtain infinite families of primer sets of length n, minimum distance d with (d + 1) log4n + O(1) redundant symbols. Our techniques involve reversible cyclic codes (1964), an encoding method of Tavares et al. (1971) and Knuth's balancing technique (1986). In our investigation, we also construct efficient and explicit binary balanced error-correcting codes and codes for DNA computing.

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.

The class of multiset combinatorial batch codes (MCBCs) was introduced by Zhang et al. (2018) as a generalization of combinatorial batch codes (CBCs). MCBCs allow multiple users to retrieve items in parallel in a distributed storage system and a fundamental objective in this study is to determine the minimum total storage given certain requirements.We formulate an integer linear programming problem so that its optimal solution provides a lower bound of the total storage of MCBCs. Borrowing techniques from linear programming, we improve known lower bounds in some cases and also, determine the exact values for some parameters.

An indel refers to a single insertion or deletion, while an edit refers to either a single insertion, deletion or substitution. We investigate codes that combat either a single indel or a single edit and provide linear-time algorithms that encode binary messages into these codes of length n. Over the quaternary alphabet, we provide two linear-time encoders. One corrects a single edit with 2⌈log n⌉ + 2 redundant bits, while the other corrects a single indel with ⌈log n⌉ + 2 redundant bits. The latter encoder reduces the redundancy of the best known encoder of Tenengolts (1984) by at least four bits. Over the DNA alphabet, exactly half of the symbols of a GC-balanced word are either C or G. Via a modification of Knuth's balancing technique, we provide a linear-time map that translates binary messages into GC-balanced codewords and the resulting codebook is able to correct a single edit. The redundancy of our encoder is 3⌈log n⌉ + 2 bits and this is the first known construction of a GC-balanced code that corrects a single edit.

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.

To equip DNA-based data storage with random-access capabilities, Yazdi et al. (2018) prepended DNA strands with specially chosen address sequences called primers and provided certain design criteria for these primers. We provide explicit constructions of error-correcting codes that are suitable as primer addresses and equip these constructions with efficient encoding algorithms. Specifically, our constructions take cyclic or linear codes as inputs and produce sets of primers with similar error-correcting capabilities. Using certain classes of BCH codes, we obtain infinite families of primer sets of length n, minimum distance d with (d + 1) log4n + O(1) redundant symbols. Our techniques involve reversible cyclic codes (1964), an encoding method of Tavares et al. (1971) and Knuth's balancing technique (1986). In our investigation, we also construct efficient and explicit binary balanced error-correcting codes.

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.

We apply the generalized sphere-packing bound to two classes of subblock-constrained codes. À la Fazeli et al. (2015), we make use of automorphisms to significantly reduce the number of variables in the associated linear programming problem. In particular, we study binary constant subblock-composition codes (CSCCs), characterized by the property that the number of ones in each subblock is constant, and binary subblock energy-constrained codes (SECCs), characterized by the property that the number of ones in each subblock exceeds a certain threshold. For CSCCs, we show that the optimization problem is equivalent to finding the minimum of N variables, where N is independent of the number of subblocks. We then provide closed-form solutions for the generalized sphere-packing bounds for t-error correcting CSCCs for t ∈ {1, 2, 3}. For SECCs, we provide closed-form solutions for the generalized sphere-packing bounds for single errors in certain special cases. We also obtain improved bounds on the optimal asymptotic rate for CSCCs and SECCs, and provide numerical examples to highlight the improvement.

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

We demonstrate that certain Johnson-type bounds are asymptotically exact for a variety of classes of codes, namely, constant-composition codes, nonbinary constant-weight codes, group divisible codes, and multiply constant-weight codes. We achieve this via an application of the theory of decomposition of edge-colored digraphs.

Tandem duplication in DNA is the process of inserting a copy of a segment of DNA adjacent to the original position. Motivated by applications that store data in living organisms, Jain et al. (2016) proposed the study of codes that correct tandem duplications to improve the reliability of data storage. We investigate algorithms associated with the study of these codes. Two words are said to be ⩽-confusable if there exists a sequence of tandem duplications for each word, where each duplication is of length at most k , such that the resulting two words after duplications are equal. For k =3, we demonstrate that the problem of deciding whether two words is ⩽3-confusable is linear-time solvable through a characterisation that can be checked efficiently. Combining with previous results, the decision problem is linear-time solvable for k ⩽ 3. We conjecture that this problem is undecidable for k > 3. Using insights gained from the algorithm, we study the size of tandem-duplication codes. We improve the previous known upper bound and then construct codes with larger sizes as compared to the previous constructions. We determine the sizes of optimal tandem-duplication codes for lengths up to 20, develop recursive methods to construct tandem-duplication codes for all word lengths, and compute explicit lower bounds for the size of optimal tandem-duplication codes for lengths from 21 to 30.

We investigate constant-composition constrained codes for the mitigation of intercell interference for multilevel cell flash memories with a dynamic threshold scheme. The first explicit formula for the maximum size of a q-ary F-avoiding code with a given composition and certain families of substrings F is presented. In addition, we provide methods to determine the asymptotic rate for F-avoiding codes with any composition ratio and to find the optimal composition ratio that maximizes the asymptotic rate. We also give the first efficient encoder/decoder for these q-ary constant-composition codes achieving the channel capacity, for all q values.

Tandem duplication is the process of inserting a copy of a segment of DNA adjacent to the original position. Motivated by applications that store data in living organisms, Jain et al. (2017) proposed the study of codes that correct tandem duplications. All code constructions are based on irreducible words. We study efficient encoding/decoding methods for irreducible words. First, we describe an (ℓ, m) -finite state encoder and show that when m=Θ(1/ε) and ℓ = Θ(1/ε), the encoder has rate that is ε away from the optimal. Next, we provide ranking/unranking algorithms for irreducible words and modify the algorithms to reduce the space requirements for the finite state encoder.

A class of low-power cooling (LPC) codes, to control simultaneously both the peak temperature and the average power consumption of interconnects, were introduced recently. An (n,t,w)-LPC code is a coding scheme over n wires that (A) avoids state transitions on the t hottest wires (cooling), and (B) limit the number of transitions to w in each transmission (low-power). A few constructions for large LPC codes that have efficient encoding and decoding schemes, are given. In particular, when w is fixed, we construct LPC codes of size (n/w)w-1and show that these LPC codes can be modified to correct errors efficiently. We further present a construction for large LPC codes based on a mapping from cooling codes to LPC codes.

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.

Tandon et al. (2017) introduced a coding theoretic framework to alleviate the problem of stragglers in distributed learning. Following Tandon et al., many authors provided explicit schemes that were able to compute a certain function using n - s replies from n workers in the worst case. In this work, we focus on reducing the expected delay. To reduce the expected delay, we modify existing schemes so that less than (n - s) replies are sufficient in most cases. In particular, we provide a simple modification to existing optimal schemes and demonstrate that with this modification, the expected delay time converges to the fundamental delay. Additionally, for specific parameters, we reduce the number of replies further so that the expected delay time converges faster to the fundamental delay.

Subblock-constrained codes are an important class of constrained codes, having applications in many diverse fields. In this paper, we provide closed-form expressions for the best known upper bounds on the asymptotic rates of subblock-constrained codes for a range of relative distance values via a generalized sphere-packing approach. In particular, we study binary subblock energy-constrained codes (SECCs), characterized by the property that the number of ones in each subblock exceeds a certain thresh-old, and binary constant subblock-composition codes (CSCCs), characterized by the property that the number of ones in each subblock is constant. Improved bounds on the optimal asymptotic rate for SECCs and CSCCs are obtained by applying a generalized sphere-packing approach and judiciously choosing appropriate constrained spaces for estimating asymptotic ball sizes. We also use numerical examples to highlight the improvement.

High temperatures have dramatic negative effects on interconnect performance and, hence, numerous techniques have been proposed to reduce the power consumption of on-chip buses. However, existing methods fall short of fully addressing the thermal challenges posed by high-performance interconnects. In this paper, we introduce new efficient coding schemes that make it possible to directly control the peak temperature of a bus by effectively cooling its hottest wires. This is achieved by avoiding state transitions on the hottest wires for as long as necessary until their temperature drops off. We also reduce the average power consumption by making sure that the total number of state transitions on all the wires is below a prescribed threshold. We show how each of these two features can be coded for separately or, alternatively, how both can be achieved at the same time. In addition, error-correction for the transmitted information can be provided while controlling the peak temperature and/or the average power consumption. In general, our cooling codes use n > k wires to encode a given k-bit bus. One of our goals herein is to determine the minimum possible number of wires n needed to encode k bits while satisfying any combination of the three desired properties. We provide full theoretical analysis in each case. In particular, we show that n = k+t +1 suffices to cool the t hottest wires, and this is the best possibility. Moreover, although the proposed coding schemes make use of sophisticated tools from combinatorics, discrete geometry, linear algebra, and coding theory, the resulting encoders and decoders are fully practical. They do not require significant computational overhead and can be implemented without sacrificing a large circuit area.

The class of geometric orthogonal codes (GOCs) was introduced by Doty and Winslow (2016) for more robust macrobonding in DNA origami. They observed that GOCs are closely related to optical orthogonal codes (OOCs). It is possible for GOCs to have size greater than OOCs of corresponding parameters due to slightly more relaxed constraints on correlations. However, the existence of GOCs exceeding the size of optimal OOCs of corresponding parameters has never been demonstrated. This paper gives the first infinite family of GOCs of size greater than optimal OOCs.

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.

Despite their exceptional error-correcting properties, Reed-Solomon (RS) codes have been overlooked in distributed storage applications due to the common belief that they have poor repair bandwidth. A naive repair approach would require for the whole file to be reconstructed in order to recover a single erased codeword symbol. In a recent work, Guruswami and Wootters (STOC'16) proposed a single erasure repair method for RS codes that achieves the optimal repair bandwidth amongst all linear encoding schemes. Their key idea is to recover the erased symbol by collecting a sufficiently large number of its traces, each of which can be constructed from a number of traces of other symbols. We extend the trace collection technique to cope with two and three erasures.

The study of subblock-constrained codes has recently gained attention due to their application in diverse fields. We present bounds on the size and asymptotic rate for two classes of subblock-constrained codes. The first class is binary constant subblock-composition codes (CSCCs), where each codeword is partitioned into equal sized subblocks, and every subblock has the same fixed weight. The second class is binary subblock energy-constrained codes (SECCs), where the weight of every subblock exceeds a given threshold. We present novel upper and lower bounds on the code sizes and asymptotic rates for the binary CSCCs and SECCs. For a fixed subblock length and small relative distance, we show that the asymptotic rate for CSCCs (respectively SECCs) is strictly lower than the corresponding rate for constant weight codes (CWCs) [respectively heavy weight codes (HWCs)]. Furthermore, for codes with high weight and low relative distance, we show that the asymptotic rate for CSCCs is strictly lower than that of SECCs, which contrasts with the fact that the asymptotic rate for the CWCs is equal to that of the HWCs. We also provide a correction to an earlier result by Chee et al. (2014) on the asymptotic CSCC rate. In addition, we present several numerical examples comparing the rates for the CSCCs and SECCs with those for the CWCs and HWCs.

We introduce the notion of weakly mutually uncorrelated (WMU) sequences, motivated by applications in DNA-based data storage systems and synchronization between communication devices. WMU sequences are characterized by the property that no sufficiently long suffix of one sequence is the prefix of the same or another sequence. WMU sequences used for primer design in DNA-based data storage systems are also required to be at large mutual Hamming distance from each other, have balanced compositions of symbols, and avoid primer-dimer byproducts. We derive bounds on the size of WMU and various constrained WMU codes and present a number of constructions for balanced, error-correcting, primer-dimer free WMU codes using Dyck paths, prefix-synchronized, and cyclic codes.

High temperatures have dramatic negative effects on interconnect performance. Numerous techniques have been proposed to reduce the power dissipation of on-chip buses but they fall short of fully addressing the thermal challenges posed by high-performance interconnects. We introduce new efficient coding schemes that directly control the peak temperature of a bus by effectively cooling its hottest wires. This is achieved by avoiding state transitions on the hottest wires for as long as necessary until their temperature drops off. At the same time, we reduce the average power consumption by ensuring that the total number of state transitions on all the wires is bounded. Our solutions call for redundancy: we use n > k wires to encode a given k-bit bus. Therefore, it is important to determine the minimum possible number of wires n needed to encode k bits while satisfying the desired properties. We provide full analysis in each case, and show that the number of additional wires required to cool the t hottest wires is negligible when k is large. Moreover, the resulting encoders and decoders are fully practical. They do not require significant computational overhead and can be implemented without sacrificing a large circuit area.

The class of geometric orthogonal codes (GOCs) were introduced by Doty and Winslow (2016) for more robust macro-bonding in DNA origami. They observed that GOCs are closely related to optical orthogonal codes (OOCs). It is possible for GOCs to have size greater than OOCs of corresponding parameters due to slightly more relaxed constraints on correlations. However, the existence of GOCs exceeding the size of optimal OOCs of corresponding parameters have never been demonstrated. This paper gives the first infinite family of GOCs of size greater than optimal OOCs.

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.

Despite their exceptional error-correcting properties, Reed-Solomon (RS) codes have been overlooked in distributed storage applications due to the common belief that they have poor repair bandwidth: A naive repair approach would require the whole file to be reconstructed in order to recover a single erased codeword symbol. In a recent work, Guruswami and Wootters (STOC'16) proposed a single-erasure repair method for RS codes that achieves the optimal repair bandwidth amongst all linear encoding schemes. We extend their trace collection technique to cope with two erasures.

The study of binary constant subblock-composition codes (CSCCs) has recently gained attention due to their application in diverse fields. These codes are a class of constrained codes where each codeword is partitioned into equal sized subblocks, and every subblock has the same fixed weight. We present novel upper and lower bounds on the asymptotic rate for binary CSCCs, using the sphere-packing and Gilbert-Varshamov (GV) type bounds, respectively. For a fixed subblock length and small code distance, we show that the asymptotic rate for CSCCs is strictly lower than the corresponding rate for constant weight codes (CWCs). We also provide a correction to an earlier result by Chee et al. (2014) on the asymptotic CSCC rate.

The subblock energy-constrained codes (SECCs) have recently been shown to be suitable candidates for simultaneous energy and information transfer, where bounds on SECC capacity were presented for communication over noisy channels. In this paper, we study binary SECCs with given error correction capability, by considering codes with a certain minimum distance. Binary SECCs are a class of constrained codes where each codeword is partitioned into equal sized subblocks, and every subblock has weight exceeding a given threshold. We present several upper and lower bounds on the optimal SECC code size, and also derive the asymptotic Gilbert-Varshamov (GV) and sphere-packing bounds for SECCs. A related class of codes are the heavy weight codes (HWCs) where the weight of each codeword exceeds a given threshold. We show that for a fixed subblock length, the asymptotic rate for SECCs is strictly lower than the corresponding rate for HWCs when the relative distance of the code is small. The rate gap between HWCs and SECCs denotes the penalty due to imposition of weight constraint per subblock, relative to the codeword based weight constraint.

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.

A recent study by one of the authors has demonstrated the importance of profile vectors in DNA-based data storage. We provide exact values and lower bounds on the number of profile vectors for finite values of alphabet size q, read length 1, and word length n. Consequently, we demonstrate that for q ≥ 2 and n ≤ q1/2-1, the number of profile vectors is at least qκnwith κ very close to 1. In addition to enumeration results, we provide a set of efficient encoding and decoding algorithms for certain families of profile vectors.

Multiply constant-weight codes (MCWCs) have been recently studied to improve the reliability of certain physically unclonable function response. In this paper, we give combinatorial constructions for the MCWCs, which yield several new infinite families of optimal MCWCs. Furthermore, we demonstrate that the Johnson-type upper bounds of the MCWCs are asymptotically tight for fixed Hamming weights and distances. Finally, we provide bounds and constructions of the 2-D MCWCs.

We introduce a new family of codes, termed asymmetric Lee distance (ALD) codes, designed to correct errors arising in DNA-based storage systems and systems with parallel string transmission protocols. ALD codes are defined over a quaternary alphabet and analyzed in this particular setting, but the derived results hold for other alphabet sizes as well. Our technical contributions are twofold. First, we derive upper bounds on the size of the codes under the ALD metric based on linear programming techniques. Second, we propose a number of code constructions, which imply lower bounds.

Network switches and routers scale in rate by distributing the packet read/write operations across multiple memory banks. Rate scaling is achieved so long as sufficiently many packets can be written and read in parallel. However, due to the non-determinism of the read process, parallel pending read requests may contend on memory banks, and thus significantly lower the switching rate. In this paper, we provide a constructive study of codes that guarantee fully parallel data reconstruction without contention. We call these codes “switch codes,” and construct three optimal switch-code families with different parameters. All the constructions use only simple XOR-based encoding and decoding operations, an important advantage when operated in ultra-high speeds. Switch codes achieve their good performance by spanning simultaneous disjoint local-decoding sets for all their information symbols. Switch codes may be regarded as an extreme version of the previously studied batch codes, where the switch version requires parallel reconstruction of all the information symbols.

A recent study by one of the authors has demonstrated the relevance of profile vectors in DNA-based data storage. We provide exact values and lower bounds on the number of profile vectors for finite values of alphabet size q, read length ℓ, and word length n. Consequently, we demonstrate that for q ≥ 3 and n = qaℓ, a = o(ℓ), the number of profile vectors is at least qκnfor some constant 0 < κ ≤ 1. In addition to enumeration results, we provide a set of efficient encoding and decoding algorithms for a family of profile vectors.

For certain families of substrings F, we provide a closed formula for the maximum size of a q-ary F-avoiding code with a given composition. In addition, we provide numerical procedures to determine the asymptotic information rate for F-avoiding codes with certain composition ratios. Using our procedures, we recover known results and compute the information rates for certain classes of F-avoiding constant-composition codes for 2 ≤ q ≤ 8. For these values of q, we find composition ratios such that the rates of F-avoiding codes with constant composition achieve the capacity of the F-avoiding channel.

We give the first known efficient encoder/decoder for q-ary constant-composition ICI-free codes achieving ICI channel capacity, for all q. Previously, the best result known is an efficient encoder/decoder for binary constant-weight ICI-free codes with more than 2% loss over ICI channel capacity.

We construct codes for the Chebyshev permutation channels whose study was initiated by Langberg et al. (2015). We establish several recursive code constructions and present efficient decoding algorithms for our codes. In particular, our constructions yield a family of binary codes of rate 0.643 when r = 1. The upper bound on the rate in this case is 2/3 and the previous highest rate is 0.609.

We introduce the notion of weakly mutually uncorrelated (WMU) sequences, motivated by applications in DNA-based storage systems and synchronization protocols. WMU sequences are characterized by the property that no sufficiently long suffix of one sequence is the prefix of the same or another sequence. In addition, WMU sequences used in DNA-based storage systems are required to have balanced compositions of symbols and to be at large mutual Hamming distance from each other. We present a number of constructions for balanced, error-correcting WMU codes using Dyck paths, Knuth's balancing principle, prefix synchronized and cyclic codes.

We consider the problem of storing and retrieving information from synthetic DNA media. We introduce the DNA storage channel and model the read process through the use of profile vectors. We provide an asymptotic analysis of the number of profile vectors and propose new asymmetric coding techniques to combat the effects of synthesis and sequencing noise. Furthermore, we construct two families of codes for this new channel model.

We consider the problem of synchronizing coded data in distributed storage networks undergoing insertion and deletion edits. We present modifications of distributed storage codes that allow updates in the parity-check values to be performed with one round of communication at low bit rates and with small storage overhead. Our main contributions are novel protocols for synchronizing frequently updated and semi-static data based on functional intermediary coding involving permutation and Vandermonde matrices.

We consider the locality of encoding and decoding operations in distributed storage systems (DSS), and propose a new class of codes, called locally encodable and decodable codes (LEDC), that provides a higher degree of operational locality compared to currently known codes. For a given locality structure, we derive an upper bound on the global distance and demonstrate the existence of an optimal LEDC for sufficiently large field size. In addition, we also construct two families of optimal LEDC for fields with size linear in code length.

We consider a new family of asymmetric Lee codes that arise in the design and implementation of DNA-based storage systems and systems with parallel string transmission protocols. The codewords are defined over a quaternary alphabet, although the results carry over to other alphabet sizes, and have symbol distances dictated by their underlying binary representation. Our contributions are two-fold. First, we derive upper bounds on the size of the codes under the asymmetric Lee distance measure based on linear programming techniques. Second, we propose code constructions which imply lower bounds.

We consider the problem of storing information on synthetic DNA media and associated coding paradigms. The focal question of our analysis it how to construct and enumerate sequences that may be discriminated based on their collection of substrings observed through two types of noisy sequencing channels. In particular, we consider DNA sequences with balanced GC content, needed for chemical stability and desirable hybridization properties. We show that restricted de Bruijn graphs and Ehrhart theory for rational polytopes provide a suitable framework for studying such combinatorial questions.

We consider the problem of synchronizing data in distributed storage networks under edits that include deletions and insertions. We present modifications of codes on distributed storage systems that allow updates in the parity-check values to be performed with one round of communication at low bit rates and a small storage overhead. Our main contributions are novel protocols for synchronizing both frequently updated and semi-static data, and protocols for data deduplication applications, based on intermediary coding using permutation and Vandermonde matrices.

In this paper, we study a construction of binary switch codes. A switch code is a code such that a multi-set request of information symbols can be simultaneously recovered from disjoint sets of codeword symbols. Our construction is optimal in the sense that it has the smallest codeword length given its average encoding degree, which is logarithmic in the code dimension. Moreover, the number of queries needed to recover any information symbol in the request is at most 2. As a result, our construction is the first family of switch codes with low encoding and decoding complexity.

We continue our study of a new family of asymmetric Lee codes that arise in the design and implementation of emerging DNA-based storage systems and systems which use parallel string transmission protocols. The codewords are defined over a quaternary alphabet, although the results carry over to other alphabet sizes, and have symbol distances dictated by their underlying binary representation. Our contributions include deriving new bounds for the size of the largest code in this metric based on Delsarte-like linear programming methods and describing new constructions for non-linear asymmetric Lee codes.

We consider the problem of assembling a sequence based on a collection of its substrings observed through a noisy channel. This problem of reconstructing sequences from traces was first investigated in the noiseless setting under the name of “Markov type” analysis. Here, we explain the connection between the problem and the problem of DNA synthesis and sequencing, and introduce the notion of a DNA storage channel. We analyze the number of sequence equivalence classes under the channel mapping and propose new asymmetric coding techniques to combat the effects of synthesis noise. In our analysis, we make use of Ehrhart theory for rational polytopes.

We demonstrate that certain Johnson-type bounds are asymptotically exact for a variety of classes of codes, namely, constant-composition codes, nonbinary constant-weight codes and multiply constant-weight codes. This was achieved via an interesting application of the theory of decomposition of edge-colored digraphs.

Flash memory is a nonvolatile memory technology that suffers from errors due to charge leakage, can tolerate limited erasures, and where erasures have to be performed in large blocks. We show that using cosets of a linear code can provide correction against uniform charge leakage, and can enhance the rewritability of flash memory which leads to fewer erasures. We introduce two coset coding schemes that are generalizations of the scheme in Jacobvitz et al. (2013). For the same worst case rewrite cost, we show that coset codes can encode more information than rank modulation codes. The average case performance of coset codes is demonstrated via numerical simulations.

Binary matrix codes with restricted row and column weights are a desirable method of coded modulation for power line communication. In this work, we construct such matrix codes that are obtained as products of affine codes - cosets of binary linear codes. Additionally, the constructions have the property that they are systematic. Subsequently, we generalize our construction to irregular product of affine codes, where the component codes are affine codes of different rates.

We introduce the class of multiply constant-weight codes to improve the reliability of certain physically unclonable function response, and extend classical coding methods to construct multiply constant-weight codes from known \(q\) -ary and constant-weight codes. We derive analogs of Johnson bounds and give constructions showing these bounds to be asymptotically tight up to a constant factor under certain conditions. We also examine the rates of multiply constant-weight codes and demonstrate that these rates are the same as those of constant-weight codes of corresponding parameters.

Coding in a new metric space, the Enomoto-Katona space, is considered recently in connection to the study of implication structures of functional dependencies and their generalizations in relational databases. The central problem here is the determination of C(n, k, d), the size of an optimal code of length n, weight k, and distance d in the Enomoto-Katona space. The value of C(n, k, d) is known only for some congruence classes of n when (k, d) ∈ {(2, 3), (3, 5)}. In this paper, we obtain new infinite families of optimal codes in the Enomoto-Katona space. In particular, C(n, k, 2k-1) is determined for all sufficiently large n satisfying either n ≡ 1 mod k and n(n-1) ≡ 0 mod 2k2, or n ≡ 0 mod k.

Single-tone frequency shift keying (FSK) modulation with permutation codes has been found to be useful in addressing the problem of narrowband noise disturbance in power line communications. However, this modulation scheme is restrictive since the number of frequencies used must be at least as large as the number of symbols in the permutation code. In this paper, we propose the use of multitone FSK and binary matrix codes to overcome this restriction. We construct infinite families of efficiently decodable matrix codes with rates and relative distances bounded away from zero, that uses only a logarithmic number of frequencies in the length of the code. Simulation results show that our multitone modulation scheme outperform single-tone modulation schemes.

The use of multiple frequency shift keying modulation with permutation codes addresses the problem of permanent narrowband noise disturbance in a power line communications system. In this paper, we extend this coded modulation scheme based on permutation codes to general codes and introduce an additional new parameter that more precisely captures a code's performance against permanent narrowband noise. As a result, we define a new class of codes, namely, equitable symbol weight codes, which are optimal with respect to this measure.

We study (symbol-pair) codes for symbol-pair read channels introduced recently by Cassuto and Blaum (2010). A Singleton-type bound on symbol-pair codes is established and infinite families of optimal symbol-pair codes are constructed. These codes are maximum distance separable (MDS) in the sense that they meet the Singleton-type bound. In contrast to classical codes, where all known q-ary MDS codes have length O(q), we show that q-ary MDS symbol-pair codes can have length Ω(q2). In addition, we completely determine the existence of MDS symbol-pair codes for certain parameters.

The study of codes for powerline communications has garnered much interest over the past decade. Various types of codes such as permutation codes, frequency permutation arrays, and constant composition codes have been proposed over the years. In this paper, we study a type of code called bounded symbol weight codes which was first introduced by Versfeld in 2005, and a related family of codes that we term constant symbol weight codes. We provide new upper and lower bounds on the size of bounded symbol weight and constant symbol weight codes. We also give direct and recursive constructions of codes for certain parameters.

A cross-bifix-free code is a set of words in which no prefix of any length of any word is the suffix of any word in the set. Cross-bifix-free codes arise in the study of distributed sequences for frame synchronization. We provide a new construction of cross-bifix-free codes which generalizes the construction by Bajic to longer code lengths and to any alphabet size. The codes are shown to be nearly optimal in size. We also establish new results on Fibonacci sequences, which are used in estimating the size of the cross-bifix-free codes.

The use of multiple frequency shift keying modulation with permutation codes addresses the problem of permanent narrowband noise disturbance in a power line communications (PLC) system. Equitable symbol weight codes was recently demonstrated to optimize the performance against narrowband noise in a general coded modulation scheme. This paper establishes the first infinite family of optimal equitable symbol weight codes with code lengths greater than alphabet size and whose relative narrowband noise error-correcting capabilities do not diminish to zero as the length grows. These families of codes meet the Plotkin bound. The construction method introduced is combinatorial and reveals interesting interplay with an extension of the concept of generalized balanced tournament designs from combinatorial design theory.

The use of multiple frequency shift keying modulation with permutation codes addresses the problem of permanent narrowband noise disturbance in a power line communications system. In this paper, we extend this coded modulation scheme based on permutation codes to general codes and introduce an additional new parameter that helps to more precisely capture a code's performance against permanent narrowband noise. As a result, we define a new class of codes, namely, equitable symbol weight codes, which are optimal with respect to this measure. In addition, we demonstrate via simulations that equitable symbol weight codes achieve lower symbol error rates than other codes of the same length and distance over the same alphabet.

We study (symbol-pair) codes for symbol-pair read channels introduced recently by Cassuto and Blaum (2010). A Singleton-type bound on symbol-pair codes is established and infinite families of optimal symbol-pair codes are constructed. These codes are maximum distance separable (MDS) in the sense that they meet the Singleton-type bound. In contrast to classical codes, where all known q-ary MDS codes have length O(q), we show that q-ary MDS symbol-pair codes can have length Ω(q2). We also construct equidistant cyclic MDS symbol-pair codes from Mendelsohn designs.