Search

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 (Cai et 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 of higher order constrained shifted VT code 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. [ABSTRACT FROM AUTHOR]

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

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 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. [ABSTRACT FROM AUTHOR]

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

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

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

In this paper, we study two families of codes with availability, namely, private information retrieval (PIR) codes and batch codes. While the former requires that every information symbol has $k$ mutually disjoint recovering sets, the latter imposes this property for each multiset request of $k$ information symbols. The main problem under this paradigm is to minimize the number of redundancy symbols. We denote this value by $r_{P}(n,k)$ and $r_{B}(n,k)$ , for PIR codes and batch codes, respectively, where $n$ is the number of information symbols. Previous results showed that for any constant $k$ , $r_{P}(n,k) = \Theta (\sqrt {n})$ and $r_{B}(n,k)= {\mathcal{ O}}(\sqrt {n}\log (n))$. In this paper, we study the asymptotic behavior of these codes for non-constant $k$ and specifically for $k=\Theta (n^\epsilon)$. We also study the largest value of $k$ such that the rate of the codes approaches 1 and show that for all $\epsilon < 1$ , $r_{P}(n,n^\epsilon) = o(n)$ and $r_{B}(n,n^\epsilon) = o(n)$. Furthermore, several more results are proved for the case of fixed $k$. [ABSTRACT FROM AUTHOR]

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

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

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

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

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

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

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