Levenshtein introduced the problem of constructing k -deletion correcting codes in 1966, proved that the optimal redundancy of those codes is $ {O}(k~\log ~{N})$ for constant k, and proposed an optimal redundancy single-deletion correcting code (using the so-called VT construction). However, the problem of constructing optimal redundancy k -deletion correcting codes remained open. Our key contribution is a major step towards a complete solution to this longstanding open problem for constant k . We present a k -deletion correcting code that has redundancy $8 {k}\log~{N} + {o}(\log~{N})$ when $ {k}= {o}(\sqrt {\log \log~{N}})$ and encoding/decoding algorithms of complexity $ {O}({N}^{2 {k}+1})$ .

Construction of capacity achieving deletion correcting codes has been a baffling challenge for decades. A recent breakthrough by Brakensiek et al ., alongside novel applications in DNA storage, have reignited the interest in this longstanding open problem. In spite of recent advances, the amount of redundancy in existing codes is still orders of magnitude away from being optimal. In this paper, a novel approach for constructing binary two-deletion correcting codes is proposed. By this approach, parity symbols are computed from indicator vectors (i.e., vectors that indicate the positions of certain patterns) of the encoded message, rather than from the message itself. Most interestingly, the parity symbols and the proof of correctness are a direct generalization of their counterparts in the Varshamov-Tenengolts construction. Our techniques require $7\log ({n})+ {o}(\log ({n}))$ redundant bits to encode an n-bit message, which is closer to optimal than previous constructions. Moreover, the encoding and decoding algorithms have ${O}({n})$ time complexity.

The problem of correcting deletions has received significant attention, partly because of the prevalence of these errors in DNA data storage. In this paper, we study the problem of correcting a consecutive burst of at most $t$ deletions in non-binary sequences. When the alphabet size $q$ is even, we first propose a non-binary code correcting a burst of at most 2 deletions for $q$ -ary alphabets. Afterwards, we extend this result to the case where the length of the burst can be at most $t$ where $t$ is a constant. Finally, we consider the setup where the sequences that are transmitted are permutations. The proposed codes are the largest known for their respective parameter regimes.

The interest in channel models in which the data is sent as an unordered set of binary strings has increased lately, due to emerging applications in DNA storage, among others. In this paper we analyze the minimal redundancy of binary codes for this channel under substitution errors, and provide several constructions, some of which are shown to be asymptotically optimal up to constants. The surprising result in this paper is that while the information vector is sliced into a set of unordered strings, the amount of redundant bits that are required to correct errors is order-wise equivalent to the amount required in the classical error correcting paradigm.

Racetrack memory is a tape-like structure where data is stored sequentially as a track of single-bit memory cells. The cells are accessed through read/write ports, called heads. When reading/writing the data, the heads stay fixed and the track is shifting. One of the main challenges in developing racetrack memory systems is the limited precision in controlling the track shifts, that in turn affects the reliability of reading and writing the data. A current proposal for combating deletions in racetrack memories is to use redundant heads per-track resulting in multiple copies (potentially erroneous) and recovering the data by solving a specialized version of a sequence reconstruction problem. Using this approach, k -deletion correcting codes of length n , with d ≥ 2 heads per-track, with redundancy log log n + 4 were constructed. However, the known approach requires that k ≤ d , namely, that the number of heads d is larger than or equal to the number of correctable deletions k . Here we address the question: What is the asymptotically optimal order of redundancy that can be achieved for a k -deletion code ( k is a constant) if the number of heads is fixed at d (due to implementation constraints)? One of our key results is an answer to this question, namely, we construct codes that can correct k deletions, for any k beyond the known limit of d . The codes have asymptotically 8 k log log n + o (log log n ) redundancy for d ≤ k ≤ 2 d – 1. In addition, when k ≥ 2 d , our codes have asymptotically 2 ⌊ k/d ⌋ log n + o (log n ) redundancy, that we prove it is order-wise optimal, specifically, we prove that the redundancy required for correcting k deletions is at least ⌊ k /2 d ⌋ log n + o (log n ). The encoding/decoding complexity of our codes is O ( n log ^2k+1 n ). Finally, we ask a general question: What is the order-wise optimal redundancy for codes correcting a combination of at most k deletions and insertions in a d -head racetrack memory? We prove that the redundancy used for a combination of k deletion and insertion errors is asymptotically the same as that needed in the case of k deletion errors.