Codes correcting bursts of deletions and localized deletions have garnered significant research interest in recent years. One of the primary objectives is to construct codes with minimal redundancy. Currently, the best known constructions of q-ary codes correcting a burst of at most t deletions ((≤t)-burstdeletion correcting codes) achieve redundancy log n+8 log log n+ o(log log n) (for anyqandt) or log n +tlog log n + O(1) (for even q). For codes correcting singlet-localized-deletion, state-ofthe- art constructions attain redundancy log n+O 􀀀 t(log log n)2) (for any q and t) or log n + 2t log log n + O(1) (for even q). Here, n denotes the code-length, and q and t are fixed. These codes employ a position-estimation component to approximate error positions, augmented by additional constraints that enable error-correction given the information about error positions. In this work, we first generalize thet-localized-deletion model to a (t, T)-localized-deletion model and then explore code constructions for correcting such errors. We select codewords from the set of sequences whose differential sequences are strong-(ℓ, ϵ)- locally-balanced. By imposing a VT-type constraint and an L1- weight constraint on the differential sequences of codewords, we construct novel position-estimation codes. When q ≥ 2 and tqis even andtq-ary (≤t)- burst-deletion correcting code and a (t, T)-localized-deletion correcting code with redundancy log n+(t−1) log log n+O(1). In addition to improving previous redundancy, our technique is novel and leads to simpler position-estimation codes compared to earlier works. Finally, we present an efficient encoder that maps an arbitrary input sequence into a sequence whose differential sequence is strong-(ℓ, ϵ)-locally-balanced. To our knowledge, no prior algorithm for this specific task has been reported.

In this paper, we investigate codes designed to correct two bursts of deletions, where each burst has a length of exactlyb, whereb> 1. The previous best construction, achieved through the syndrome compression technique, had a redundancy of at most 7 logn+O(logn/ log logn) bits. In contrast, our work introduces a novel approach for constructing q-ary codes that attain a redundancy of at most 5 logn+O(log logn) bits for allb> 1 andq≥ 2. Additionally, for the case whereb= 1, we present a new construction of q-ary two-deletion correcting codes with a redundancy of 5 logn+ O(log logn) bits, for allq> 2.

Abstract In this paper, we focus on constructing unique-decodable and list-decodable codes for the recently studied (t, e)-composite-asymmetric error-correcting codes ((t, e)-CAECCs). Let $$\mathcal {X}$$ X be an $$m \times n$$ m × n binary matrix in which each row has Hamming weight w. If at most t rows of $$\mathcal {X}$$ X contain errors, and in each erroneous row, there are at most e occurrences of $$1 \rightarrow 0$$ 1 → 0 errors, we say that a (t, e)-composite-asymmetric error occurs in $$\mathcal {X}$$ X . For general values of m, n, w, t, and e, we propose new constructions of (t, e)-CAECCs with redundancy at most $$(t-1)\log (m) + O(1)$$ ( t - 1 ) log ( m ) + O ( 1 ) , where O(1) is independent of the code length m. In particular, this yields a class of (2, e)-CAECCs that are optimal in terms of redundancy. When m is a prime power, the redundancy can be further reduced to $$(t-1)\log (m) - O(\log (m))$$ ( t - 1 ) log ( m ) - O ( log ( m ) ) . To further increase the code size, we introduce a combinatorial object called a weak $$B_e$$ B e -set. When $$e = w$$ e = w , we present an efficient encoding and decoding method for our codes. Finally, we explore potential improvements by relaxing the requirement of unique decoding to list-decoding. We show that when the list size is t! or an exponential function of t, there exist list-decodable (t, e)-CAECCs with constant redundancy. When the list size is two, we construct list-decodable (3, 2)-CAECCs with redundancy $$\log (m) + O(1)$$ log ( m ) + O ( 1 ) .

We study codes that can correct backtracking errors during nanopore sequencing. In this channel, a sequence of lengthnover an alphabet of sizeqis being read by a sliding window of length$\ell $, where from each window we obtain only its composition. Backtracking errors cause some windows to repeat, hence manifesting as tandem-duplication errors of fixed lengthkin the$\ell $-read vector of window compositions. While existing constructions for duplication-correcting codes can be straightforwardly adapted to this model, even resulting in optimal codes, their asymptotic rate is hard to find. In the regime of unbounded number of duplication errors, we either give the exact asymptotic rate of optimal codes, or bounds on it, depending on the values ofk,$\ell $andq. In the regime of a constant number of duplication errors,t, we find the redundancy of optimal codes to be$t\log _{q} n+O(1)$when$\ell |k$, and only upper bounded by this quantity otherwise.

Motivated by applications in polymer-based data storage, we study the problem of reconstructing a string from part of its composition multiset. We give a full description of strings that cannot be uniquely reconstructed up to reversal from their multisets of all the prefix-suffix compositions. Leveraging this description, we prove that for alln⩾ 6, there exists a string of lengthnthat cannot be uniquely reconstructed up to reversal. Moreover, for alln⩾ 6, we explicitly construct the set consisting of all lengthnstrings that can be uniquely reconstructed up to reversal. As a byproduct, we obtain that any binary string can be constructed using Dyck strings and Catalan-Bertrand strings. For any given string s, we provide a method to explicitly construct the set of all strings with the same prefix-suffix composition multiset as s, as well as a formula for the size of this set. Furthermore, we construct two classes of composition codes that can respectively correct composition missing errors and mass-reducing substitution errors. In addition, we raise a new problem: reconstructing a string when only given its compositions of substrings of length at mostr. We give suitable codes under some conditions.

In this paper, we present a novel communication channel, called the absorption channel, inspired by information transmission in neurons. Our motivation comes from in-vivo nano-machines, emerging medical applications, and brain-machine interfaces that communicate over the nervous system. For any given finite alphabet, we give codes that can correct absorption errors. For the binary alphabet, we show that the known binary (multiple-)deletion correcting codes already provide a good solution. For a single-absorption error, we show that the Varshamov-Tenengolts codes provide a near-optimal code in our setting. When the alphabet size$q$is at least 3, we construct a single-absorption correcting code whose redundancy is at most$3\log _{q}(n)+O_{q}(1)$. Then, based on this code and ideas introduced by Gabrys et al. (2022), we give a second construction of single-absorption correcting codes with redundancy$\log _{q}(n)+12\log _{q}\log _{q}(n)+O_{q}(1)$, which is optimal up to an$O\left ({\log _{q}\log _{q}(n)}\right)$. Here,$O_{q}(1)$denotes a number dependent on$q$but independent of the code-length$n$. Finally, we apply the syndrome compression technique with pre-coding to obtain a subcode of the single-absorption correcting code. This subcode can combat multiple absorption errors and has low redundancy. For each setup, efficient encoders and decoders are provided.

In this paper, we present a novel communication channel, called the absorption channel, inspired by information transmission in neurons. Our motivation comes from invivo nano-machines, emerging medical applications, and brain-machine interfaces that communicate over the nervous system.For any given finite alphabet, we give codes that can correct absorption errors. For the binary alphabet, the known binary (multiple-)deletion correcting codes already provide a good solution. For single-absorption error, we prove that the Varshamov-Tenengolts codes can provide a near-optimal code in our setting. When the alphabet size q is at least 3, we first construct a single-absorption correcting code whose redundancy is at most 3 logq(n)+O(1). Then, based on this code and ideas introduced in [1], we give a second construction of single-absorption correcting codes with redundancy logq(n) + 12 logqlogq(n) + O(1), which is optimal up to an O(logqlogq(n)).Finally, we apply the syndrome compression technique with pre-coding to obtain a subcode of the single-absorption correcting code. This subcode can combat multiple-absorption errors and has low redundancy.

Reconstruction codes are generalizations of error-correcting codes that can correct errors by a given number of noisy reads. The study of such codes was initiated by Levenshtein in 2001 and developed recently due to applications in modern storage devices such as racetrack memories and DNA storage. The central problem on this topic is to design codes with redundancy as small as possible for a given number$N$of noisy reads. In this paper, the minimum redundancy of such codes for binary channels with exactly two insertions is determined asymptotically for all values of$N\ge 5$. Previously, such codes were studied only for channels with single edit errors or two-deletion errors.

This paper focuses on constructions of MDS self-dual codes from (extended) generalized Reed-Solomon (GRS) codes. Let$q = r^{2}$be an odd prime power. We show that, there exists a$q$-ary self-dual (extended) GRS code for each even length in the range$[{2r,3r-3}]$, and for each singly even length in the range$[3r-1,4r]$. This extends the only known consecutive range$[2,2r]$to$[{2,3r-3}]$for this case. Furthermore, our general constructions provide many MDS self-dual codes with new parameters which, to the best of our knowledge, were not reported before.

Splitter sets have been widely studied due to their applications in flash memories, and their close relations with lattice tilings and conflict avoiding codes. In this paper, we give necessary and sufficient conditions for the existence of nonsingular perfect splitter sets, B[-k1, k2](p) sets, where 0 ≤ k1≤ k2= 4. Meanwhile, constructions of nonsingular perfect splitter sets are given. When perfect splitter sets do not exist, we present four new constructions of quasi-perfect splitter sets. Finally, we give a connection between nonsingular splitter sets and Cayley graphs, and as a byproduct, a general lower bound on the maximum size of nonsingular splitter sets is given.