Run length limited (RLL) sequences and codes have been studied extensively in coding theory for a long time. Several kinds of weight constrained RLL codes have gained attentions recently owing to their applications, especially in DNA-based data storage. In this work, we revisit the old problem of constant weight RLL codes and provide new efficient encoding/decoding algorithms of these optimal codes. In particular, we rank/unrank all constant weight RLL sequences in a certain order, called$d$-Gray order, where the Hamming distance between two consecutive sequences in the list is at most$d$. The list of all constant weight RLL sequences is called a constant weight RLL$d$-Gray code.

Non-binary codes correcting multiple deletions have recently attracted a lot of attention. In this work, we focus on multiplicity-free codes, a family of non-binary codes where all symbols are distinct. Our main contribution is a new explicit construction of such codes, based on set and permutation codes. We show that our multiplicity-free codes can correct multiple deletions and provide a decoding algorithm. We also show that, for a certain regime of parameters, our constructed codes have size larger than all the previously known non-binary codes correcting multiple deletions.

The coded trace reconstruction problem, where multiple noisy copies (traces) of an original message are used for recovery, has garnered significant attention. We investigate this problem under the specific constraints that the messages are permutations of length n and the errors are deletions. Our primary focus is the burst deletion model: given M > 1 traces, each resulting from the original permutation by deleting a single burst of at most t symbols. We present an explicit construction of a permutation code capable of uniquely recovering the original permutation from M = 2 distinct traces, each affected by a burst deletion of size up to t. Notably, this code achieves recovery with only constant redundancy (independent of n). Additionally, we explore a different scenario involving two arbitrary deletions per trace. For this model, we demonstrate that existing 1deletion correcting permutation codes are sufficient to guarantee unique recovery of the original permutation, provided at least M =5 distinct traces are available.

Abstract An ( n , R )-covering sequence is a cyclic sequence whose consecutive n -tuples form a code of length n and covering radius R . Using several construction methods improvements of the upper bounds on the length of such sequences for $$n \le 20$$ n ≤ 20 and $$1 \le R \le 3$$ 1 ≤ R ≤ 3 , are obtained. The definition is generalized in two directions. An ( n , m , R )-covering sequence code is a set of cyclic sequences of length m whose consecutive n -tuples form a code of length n and covering radius R . The definition is also generalized to arrays in which the $$m \times n$$ m × n sub-matrices form a covering code with covering radius R . We prove that asymptotically there are covering sequences that attain the sphere-covering bound up to a constant factor.

Codes in the Damerau-Levenshtein metric have received some attention by the research community recently owing to their applications in DNA-based data storage. In particular, Gabrys, Yaakobi, and Milenkovic designed a length-n code correcting a single deletion and s adjacent transpositions with at most$(1+2s)\log n$bits of redundancy. In this work, we consider a new setting where both deletions and asymmetric adjacent transpositions may occur. For asymmetric transpositions, at most$s^{+}0$-right shifts (i.e.,$01 \rightarrow 10$) and at most$s^ - 0$-left shifts (i.e.,$10 \rightarrow 01$) may occur. We present several constructions of the binary codes correcting these errors in various cases. In particular, we design a code correcting a single deletion,$s^{+}$right-shift, and$s^ - $left-shift errors with at most$(1+s)\log (n+s+1)+1$bits of redundancy where$s=s^{+}+s^ - $. In addition, we investigate uniquely-decodable codes correcting$t~0$-deletions and s adjacent transpositions with at most$(t+2s)\log n+o(\log n)$bits of redundancy. Then, we study the code for correcting$t~0$-deletions,$s^{+}$right-shift, and$s^ - $left-shift errors with list-decoding algorithms. Our main contribution here is the construction of a list-decodable code with list size$O(n^{s})$and with at most$(\max \{t,s+1\}) \log n+O(1)$bits of redundancy, where$s=s^{+}+s^ - $. We construct non-systematic codes for correcting$t_{\mathrm {b}}$blocks of 0-deletions with$\ell $-limited magnitude and s adjacent transpositions with redundancy at most$(2(t_{\mathrm {b}}+2s)+1)\log (n+1)+O(1)$bits and systematic codes with at most$((2(t_{\mathrm {b}}+2s)+1)(1+1/(\log (t_{\mathrm {b}}\ell +4)))\log (N+1)+O(\log \log N)$redundant bits in an N-length codeword.

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

Determining the optimal fidelity for the transmission of quantum information over noisy quantum channels is one of the central problems in quantum information theory. Recently, [Berta-Borderi-Fawzi-Scholz, Mathematical Programming, 2021] introduced an asymptotically converging semidefinite programming hierarchy of outer bounds for this quantity. However, the size of the semidefinite programs (SDPs) grows exponentially with respect to the level of the hierarchy, thus making their computation unscalable. In this work, by exploiting the symmetries in the SDP, we show that, for a fixed output dimension of the quantum channel, we can compute the SDP in time polynomial with respect to the level of the hierarchy and input dimension. As a direct consequence of our result, the optimal fidelity can be approximated with an accuracy of$\epsilon $in$\mathrm {poly}(1/\epsilon, \text {input dimension})$time, compared to the$\exp (1/\epsilon, \text {input dimension})$running time required for direct computation.

Permutation codes in the Ulam metric, which can correct multiple deletions, have been investigated extensively recently. In this work, we are interested in the maximum size of permutation codes in the Ulam metric and aim to design permutation codes that can correct multiple deletions with efficient decoding algorithms. We first present an improvement on the Gilbert–Varshamov bound of the maximum size of these permutation codes by analyzing the independence number of the auxiliary graph. The idea is widely used in various cases and our contribution in this section is to enumerate the number of triangles in the auxiliary graph and show that it is small enough. Next, we design permutation codes correcting multiple deletions with a decoding algorithm. In particular, the constructed permutation codes can correcttdeletions with at most (3t− 1) log(n+ 1) +o(logn) bits of redundancy wherenis the length of the code. Our construction is based on a new mapping that yields a new connection between permutation codes in the Hamming metric and permutation codes in various metrics. Furthermore, we construct permutation codes that correct multiple bursts of deletions using this new mapping. Finally, we extend the new mapping for multi-permutations and construct the best-known multi-permutation codes in the Ulam metric.

Given$d$defective items in a population of$n$items with$d\ll n$, in threshold group testing without gap, the outcome of a test on a subset of items is positive if the subset has at least$u$defective items and negative otherwise, where$1 \leq u \leq d$. The basic goal of threshold group testing is to quickly identify the defective items via a small number of tests. In non-adaptive design, all tests are designed indepen-dently and can be performed in parallel. The decoding time in the non-adaptive state-of-the-art work is a polynomial of$(d/u)^{u}(d/(d-u))^{d-u}, d$, and$\log n$. In this work, we present a novel design that significantly reduces the number of tests and the decoding time to polynomials of$\min\{u^{u},\ (d-u)^{d-u}\}, d$, and$\log n$. In particular, when$u$is a constant, the number of tests and the decoding time are$O(d^{3}(\log^{2}n)\log(n/d))$and$O(d^{3}(\log^{A}n)\log(n/d)+d^{2}(\log n)\log^{3}(n/d))$, respectively. For a special case when$u=2$, with non-adaptive design, the number of tests and the decoding time are$O(d^{3}(\log n)\log(n/d))$and$O(d^{2}(\text{log} n+\log^{2}(n/d)))$, respectively. Moreover, with 2-stage design, the number of tests and the decoding time are$O(d^{2}\log^{2}(n/d))$. The full version is available at [1].

An$(m, n, R)-\mathbf{de}$Bruijn covering array (dBCA) is a doubly periodic$M\times N$array over an alphabet of size$q$such that the set of all its$m\times n$windows form a covering code with radius$R$. An upper bound of the smallest array area of an$(m, n, R)-\mathbf{dBCA}$is provided using a probabilistic technique which is similar to the one that was used for an upper bound on the length of a de Bruijn covering sequence. A folding technique to construct a dBCA from a de Bruijn covering sequence or de Bruijn covering sequences code is presented. Several new constructions that yield shorter de Bruijn covering sequences and$(m, n, R)-\mathbf{dBCAs}$with smaller areas are also provided. These constructions are mainly based on sequences derived from cyclic codes, self-dual sequences, primitive polynomials, an interleaving technique, folding, and mutual shifts of sequences with the same covering radius. Finally, constructions of de Bruijn covering sequences codes are also discussed.

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

In DNA-based data storage, sequencing the stored DNA is essential in reading the stored data. Nanopore sequencing, an emerging sequencing technology, has attracted a lot of attention recently owing to their various advantages, in particular, it is portable, scalable, automated and rapid. However, several kinds of errors, including inter-symbol interference, noisy measurement, backtracking, and skipping, reduce the accuracy of the technology. Several coding schemes have been proposed recently to deal with various kinds of error sources, especially inter-symbol interference and noisy measurement. In this work, we focus on backtracking and skipping errors and aim to design a good coding scheme to combat these errors. We first note that backtracking and skipping errors can be modelled as synchronization errors, including duplication and deletion errors. Next, we propose new families of codes to locate and correct all synchronization errors caused by backtracking and skipping. The proposed codes are constrained codes avoiding prescribed set of patterns. Then, we focus on studying these constrained codes. In particular, we present a method to compute their maximal asymptotic rates. For illustration, we use experimental data available online to compute the numerical results for maximal asymptotic rates of these codes.

Window Weight Limited (WWL) strings and codes have been studied recently owing to their various applications, including DNA based storage and energy-harvesting. In this work, we proposed to study a new coding scheme, called WWL Gray code. This is a list of WWL strings in Gray order, that is, the Hamming distance of two consecutive strings in the list is one. We are the first to investigate the WWL Gray codes with efficient rankinglunranking algorithms. We show that the WWL Gray codes are useful in designing robust positioning sequences. Note that the robust positioning sequences have attracted a lot of attentions recently owing to their numerous applications, including quantum communications and robot localization. In this work, using the WWL Gray codes, we obtain robust positioning sequences with less redundancy compared to the best known results.

Sum-rank-metric codes have attracted lots of attention due to their numerous applications, including muti-shot linear network coding, space-time coding, and distributed storage systems. In this paper, we focus on constructing linear sum-rank-metric codes achieving Singleton bound, which are called maximum sum-rank distance (MSRD) codes. This family of codes is the analogue of maximum distance separable (MDS) codes in Hamming metric. We propose two constructions of linear MSRD codes with various matrix sizes. Each of them yields new MSRD codes with different parameter regimes, and one of them generalizes some recent results of Byrne et al. (2021) and Chen (2023). The block lengths and the matrix block sizes of our codes are not restricted to the sizes of the finite field. Our technique is mainly based on rank metric codes and their sub-codes of different minimum rank distances.

Our main goal in this work is to study permutation codes in the Levenshtein metric which can correct multiple deletions. Permutation codes in the Levenshtein metric are known to have a close relationship with those in Ulam and generalized Kendall-tau metrics. In this work, we present a new connection between different kinds of distances over two permu-tations' including Hamming, Levenshtein, Ulam, and generalized Kendall-tau distance. From this new connection and some known permutation codes in the Hamming metric, we obtain new permu-tation codes in Levenshtein, Ulam, and generalized Kendall-tau metrics with better size. In particular, we show that there exist permutation codes of length$n$for correcting$t$deletions with at most$(3t+1)\log n+o(\log n)$bits of redundancy. Furthermore, we present the construction of our permutation codes for correcting$t$deletions with a specific decoding process.

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

The run length limited de Bruijn (RLLdB) sequences have been studied recently owing to their application in communication systems. In each RLLdB sequence, all length-k substrings are distinct and each substring is a run length limited sequence, where there are at most s consecutive symbol 0’s. In previous work, the maximal length RLLdB sequence was designed only for the case s = 1.In this work, we propose to study a more generalised problem of constrained de Bruijn sequence, called weight bounded run length limited de Bruijn (WRdB) sequence. In each WRdB sequence, all length-k substrings are distinct and each length-k substring satisfies both constraints: the number of consecutive symbol 0’s is at most s, and the number of symbol 1’s is at least l. We aim to design a WRdB sequence with maximal length in all cases.Firstly, we build a constrained de Bruijn graph that represents a WRdB sequence and use some properties of the graph to show an upper bound on the maximal length of the sequence. Next, using Lyndon words, we present a construction of a WRdB sequence. Finally, we compute the length of the constructed WRdB sequence and show that it has the maximal length.

Codes for correcting sticky insertions/deletions and limited-magnitude errors have attracted significant attention due to their applications of flash memories, racetrack memories, and DNA data storage systems. In this paper, we first consider the error type of t sticky deletions with ℓ-limited-magnitude and propose a non-systematic code for correcting this type of error with redundancy 2t(1 − 1/p) • log(n + 1) + O(1), where p is the smallest prime larger than ℓ + 1. Next, we present a systematic code construction with an efficient encoding and decoding algorithm with redundancy $\frac{{\left\lceil {2t(1 - 1/p)} \right\rceil \cdot \left\lceil {\log p} \right\rceil }}{{\log p}}\log (n + 1) + O(\log \log n)$, where p is the smallest prime larger than ℓ + 1.

The main goal of group testing is to identify a small number of positive items among a large population of n items. In this work, we consider a new model of group testing in which the input items are linearly ordered, and the positives are subsets of small blocks (at unknown locations) of consecutive items over that order. When the number of blocks is at least one and at most k, and the number of items in a block is at most d, we show that there exists a deterministic and explicit design that can identify the positives with O(k2d log (n/d)) tests in O(poly(k, n/d)+kd) time. The number of tests in our proposed design is less than that of in standard combinatorial group testing by a factor of at least d/ log (kd). We also show that there exists a randomized design that can identify the positives with O(k(log (n/d)+d log k)) tests in O(k(log2(n/d)+k log k+d log k)) time with high probability.

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

An (n, d, b, k)q-robust locally positioning (RLP) sequence s is a q-ary sequence of length n where each subset of b consecutive windows of length k in s is a q-ary code of length k with minimum Hamming distance d. A set of these sequences is called an (n, d, b, k)q-robust locally positioning code. The RLP sequence is a generalization of a locally constrained de Bruijn sequence and a robust positioning sequence which have been studied recently owing to their various applications. In this work, we study the RLP sequences and codes with motivation from both practical and theoretical points of view. Firstly, these RLP sequences and codes are useful to combat a combination of substitutions and synchronization errors in the ℓ-symbol read channel. Secondly, the RLP code can be viewed as a combination of an error correcting code and a constrained code avoiding a set of patterns and as such they pose several interesting theoretical challenges in combinatorics, algorithms and coding theory. Finally, from the practical point of view, these sequences and codes have numerous applications, especially error-correction in racetrack memories.Owing to their applications in racetrack memories, we investigate (n, d, b, k)qRLP codes with small values of b and d. Numerous techniques are used to compute the maximal asymptotic rate (capacity) of these codes for given set of parameters. The numerical results are computed and tabulated. We also study these codes with large values of b and d for theoretical interests. In some cases, we can construct a code with only a single bit of redundancy.

Codes in the Damerau–Levenshtein metric have been studied recently owing to their applications in DNA-based data storage. In previous work, codes for correcting a single deletion and multiple adjacent transpositions were presented. In this work, we consider a new setting with the asymmetric Damerau–Levenshtein distance where both 0-deletions and adjacent transpositions occur. We first study uniquely-decodable codes and present an optimal code (in the sense that its redundancy is optimal up to a constant additive term) correcting a single 0-deletion or a single adjacent transposition with redundancy log n + 2 bits. Then, we present a construction of codes correcting t 0-deletions and s adjacent transpositions with at most (t + 2s) log n bits of redundancy. Next, we focus on list-decodable codes and construct a list-decodable code with list-size O(nmin{s+1,t}) and has at most (max{t, s + 1}) log n bits of redundancy.

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

Two dimensional (2D) error correcting codes have been investigated for a long time owing to their numerous applications. Recently, 2D codes correcting row-deletions and column-deletions, also known as criss-cross deletion correcting codes, have been studied as a generalisation of one dimensional deletion correcting codes. In this work, we show that 2D deletion correcting codes are useful to correct errors in racetrack memories. With motivation from both theoretical and practical point of view, we study these 2D codes and aim to improve the previous known results. Our first main result is a construction of an optimal (1,1)-criss-cross deletion correcting code with the redundancy is at most$2n+2\log n+o(\log n)$bits. Then, we also present a construction of an asymptotic optimal$(t_{r},\ t_{c})$-criss-cross deletion correcting code with less redundancy than the best known results. Furthermore, since a 2D binary code correcting multiple row-deletions is equivalent to a I1D q-ary code correcting multiple deletions with large$q$, we also improve some previous known results on 1D q-ary code correcting multiple deletions.

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

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.

Codes correcting pair-errors (substitutions) for symbol-pair read channels were introduced recently by Cassuto and Blaum(2011). In this work, we study codes correcting synchronization errors, including deletions and sticky-insertions, for symbol-pair read channels owing to their application in racetrack memory. We first investigate deletion-correcting-code in symbol-pair read channels and then construct several codes that are larger than known codes in classical deletion-channels. Finally, we examine codes correcting a combination of deletions and substitutions.

Permutation codes and multipermutation codes are widely studied due to various applications in information theory. Designing codes correcting deletion errors has been the main subject of works in the literature and to the best of our knowledge, there exist only optimal codes capable of correcting a single deletion in a permutation. In this paper, we construct several classes of permutation and multipermutation codes that are capable of correcting a burst deletion of length s ≥ 2, for both stable and unstable models. Efficient error decoders are provided to show the correctness of our constructions.

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

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

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

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.

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.

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

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

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.

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.

We construct permutation codes capable of correcting bursts of stable deletions. For correcting a single burst of exactly s stable deletions, our code has size sn!/((2s)!n)2, while the upper bound n!/s!(n - s + 1). We also construct permutation codes for the cases of single burst of up to s stable deletions, and up to b bursts of at most s stable deletions each.

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.

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 construct the first class of permutation codes that are capable of correcting a burst of up to s unstable deletions, for general s. Efficient decoding algorithms are presented to show the correctness of our constructions.

Permutation codes under the Cayley, Kendall tau, and Ulam metrics have been studied recently due to applications in flash memories. We consider permutation codes under more general metrics. We use breakpoints in permutations to gain additional insights to distances in codes. As a result, we construct codes under these general metrics that are larger than those previously known under more restricted metrics.