Some New Constructions of q-ary Codes for Correcting a Burst of at Most t Deletions ^†

Abstract

In this paper, we construct q-ary codes for correcting a burst of at most t deletions, where $t,q\ge 2$ are arbitrarily fixed positive integers. We consider two scenarios of error correction: the classical error correcting codes, which recover each codeword from one read (channel output), and the reconstruction codes, which allow to recover each codeword from multiple channel reads. For the first scenario, our construction has redundancy $\log n+8\log \log n+o\left(\log \log n\right)$ bits, encoding complexity $O\left(q^{7t}n{\left(\log n\right)}^3\right)$ and decoding complexity $O\left(n\log n\right)$. For the reconstruction scenario, our construction can recover the codewords with two reads and has redundancy $8\log \log n+o\left(\log \log n\right)$ bits. The encoding complexity of this construction is $O\left(q^{7t}n{\left(\log n\right)}^3\right)$, and decoding complexity is $O\left(q^{9t}{\left(n\log n\right)}^3\right)$. Both of our constructions have lower redundancy than the best known existing works. We also give explicit encoding functions for both constructions that are simpler than previous works.

1. Introduction

The study of deletion/insertion correcting codes, which originated in the 1960s, has made a great progress in recent years, encouraged by their application to DNA-based data storage. One of the basic problems in this area is construction of codes with low redundancy and low encoding/decoding complexity, where the redundancy of a q-ary $(q\ge 2)$ code $\mathcal{C}$ of length n is defined as $n-{\log }_q\left|\mathcal{C}\right|$, measured in q-ary symbols, or $(n-{\log }_q|\mathcal{C}\left|\right)\log q$, measured in bits (in this paper, for simplicity, for any real $x>0$, we write ${\log }_{2}x=\log x$). The optimal redundancy of a q-ary t-deletion correcting code of length n was proved to be asymptotically between $t\log n+t\log q+o\left(\log qn\right)$ and $2t\log n+t\log q+o\left(\log qn\right)$ [1]. In general, codes with a redundancy matching the upper bound can be constructed by graph-coloring method. However, the encoding complexity of such a construction is exponential in n. In practice, the construction of codes with polynomial encoding complexity (also called explicit construction) and low redundancy is an interesting research problem.

The famous VT codes were proved to be a family of single-deletion correcting binary codes, and are asymptotically optimal in redundancy [2]. The VT construction was generalized to nonbinary single-deletion correcting codes in [3] and, recently, a different version of nonbinary VT codes was proposed in [4] using differential vector, with asymptotically optimal redundancy and efficient encoding/decoding. Works on binary and nonbinary codes for correcting multiple deletions can be found in [5,6,7,8,9,10,11,12,13] and the references therein.

Burst deletions and insertions, which means that deletions and insertions occur at consecutive positions in a string, are a class of error that can be found in many applications, such as DNA-based data storage and file synchronization. For the binary case, the maximal cardinality of a t-burst-deletion correcting code (i.e., a code that can correct a burst of exactly t deletions) is proved to be asymptotically upper bounded by $2^{n-t+1}/n$ [14], so its redundancy is asymptotically lower bounded by $\log n+t-1$. Several constructions of binary codes correcting a burst of exactly t deletions were reported in [15,16], where the construction in [16] achieves an optimal redundancy of $\log n+(t-1)\log \log n+k-\log k$. A more general class, i.e., codes correcting a burst of at most t deletions, were also constructed in the same paper [16], and this construction was improved in [17] to achieve a redundancy of $\lceil \log t\rceil \log n+(t(t+1)/2-1)\log \log n+c_t$ for some constant $c_t$ that only depends on t. In [18], by using VT constraint and shifted VT constraint in the so-called $(\mathit{p},\delta )$-dense strings, binary codes correcting a burst of at most t deletions were constructed, with an optimal redundancy of $\log n+t(t+1)/2\log \log n+c_t^{\prime }$, where $c_t^{\prime }$ is a constant depending only on t.

In recent parallel works [12,19], q-ary codes correcting a burst of at most t deletions were constructed for even integer $q>2$, with redundancy $\log n+O\left(\log q\log \log n\right)$ or, more specifically, $\log n+(8\log q+9)\log \log n+{\gamma }_t^{\prime }+o\left(\log \log n\right)$ bits for some constant ${\gamma }_t^{\prime }$ that only depends on t. The basic techniques in [12,19] are to represent each q-ary string as a binary matrix whose columns are the binary representation of the entries of the corresponding q-ary string. Strings of length n are constructed such that the first row of their matrix representation is $(\mathit{p},\delta )$-dense. Then, the first row of their matrix representation is protected by a binary burst deletion correcting code of length n and the other rows are protected by binary burst deletion correcting codes of length not greater than $2\delta$, which results in a construction with $\log n+O\left(\log q\log \log n\right)$ bits of redundancy. A different construction of q-ary codes correcting a burst of at most t deletions was reported in a more recent work [4], which has redundancy $\log n+O\left(t^2\log \log n\right)+O\left(t\log q\right)$.

A relaxed model of error correction, called sequence reconstruction, also received great attention from researchers (e.g., see [20,21,22,23,24,25,26,27,28,29,30,31,32]). Unlike the classical error correcting codes, in the sequence reconstruction model, the receiver is allowed to reconstruct the original transmitted sequence from multiple noisy reads (channel outputs). This model is suitable for DNA data storage because current synthesis and sequencing technologies can generate many (possibly erroneous) reads for each DNA strand, and so each stored DNA strand can be recovered by its many erroneous copies. Sequence reconstruction for deletion, insertion, transposition, and substitution was first studied in [20,21], where the minimum number of reads for exact reconstruction of uncoded sequence was computed. Coded sequence reconstruction for deletion channel was considered recently in [23], where it was assumed that a codeword of a single-deletion-correcting code is transmitted over the t-deletion channels, and the minimum number of distinct reads required to uniquely reconstruct the transmitted sequence was computed. The more general problem, i.e., the minimum number of reads for reconstruction of a codeword of an $(\ell -1)$-deletion-correcting code of length n transmitted over the t-deletion channels for some $1\le \ell \le t<n$, was solved in [27]. The dual problem, i.e., designing codes (called reconstruction codes) for reconstruction of a sequence with fixed number of reads for deletion channel, was also considered in recent years. A construction of binary reconstruction codes for two reads and with $\log \log n+O\left(1\right)$ bits of redundancy under single-deletion channel was presented in [24], and this construction was generalized in [28] to q-ary single-edit channel for $q\ge 2$. Binary reconstruction codes under 2-deletion channel were constructed in [29,30]. It was shown in [30] that $3\log n+o\left(\log n\right)$ bits of redundancy is sufficient for two reads, and $\log n+o\left(\log n\right)$ bits of redundancy is sufficient for five reads. Reconstruction codes under single-burst-insertion/deletion/edit channel were considered in [31], where for the channel suffering from a single burst of at most t deletions, a family of q-ary codes for two reads with $t(t+1)/2\log \log n+O\left(1\right)$ bits of redundancy were constructed.

In this paper, we propose some new constructions of q-ary codes for correcting a burst of at most t deletions for any fixed positive integers t and $q\ge 2$. We consider both the classical error correcting codes and the reconstruction codes. In our constructions, we consider q-ary $(\mathit{p},\delta )$-dense strings (sequences), which are generalization of the binary $(\mathit{p},\delta )$-dense strings defined in [18], and give an efficient algorithm for encoding and decoding of q-ary $(\mathit{p},\delta )$-dense strings. For the classical burst-deletion correcting codes, a VT-like function is used to locate the deletions within an interval of length not greater than $3\delta$, which results in $\log n$ bits of redundancy. In addition, two functions are used to recover the substring destroyed by deletions, which results in $8\log \log n+o\left(\log \log n\right)$ bits of redundancy (in this paper, the term $o\left(\log \log n\right)$ may depends on q and t. However, since q and t are assumed to be fixed positive integers, they are omitted). Thus, the total redundancy of our construction is $\log n+8\log \log n+o\left(\log \log n\right)$ bits. Compared to previous works, the redundancy of our new construction is independent of q and t in the second term. An explicit encoding function is given, which is simpler than previous works and has complexity $O\left(q^{7t}n{\left(\log n\right)}^3\right)$. The decoding complexity is $O\left(n\log n\right)$.

We also construct reconstruction codes for correcting a burst of at most t deletions from two reads and with redundancy $8\log \log n+o\left(\log \log n\right)$ bits, which is lower than the construction in [31]. We give an explicit encoding function for such codes with encoding complexity $O\left(q^{7t}n{\left(\log n\right)}^3\right)$ and decoding complexity $O\left(q^{9t}{\left(n\log n\right)}^3\right)$.

In Section 2, we introduce related notations and concepts, and present some basic constructions that will be used in our new constructions. In Section 3, we study $(\mathit{p},\delta )$-dense q-ary strings. A new construction of classical q-ary burst-deletion correcting codes is given in Section 4, and q-ary codes for correcting burst deletions from two reads is given in Section 5. Finally, the paper is concluded in Section 6.

2. Preliminaries

Let $[m,n]=\{m,m+1,\dots ,n\}$ for any two integers m and n, such that $m\le n$, and call $[m,n]$ an interval. If $m>n$, then let $[m,n]=Ø$. For simplicity, we denote $\left[n\right]=[1,n]$ for any positive integer n. The size of a set S is denoted by $\left|S\right|$.

Given any integer $q\ge 2$, let ${\Sigma }_q=\{0,1,2,\cdots ,q-1\}$. For any sequence (also called a string or a vector) $\mathit{x}\in {\Sigma }_q^n$, n is called the length of $\mathit{x}$, and denote $\left|\mathit{x}\right|=n$. We will denote $\mathit{x}=(x_1,x_2,\dots ,x_n)$ or $\mathit{x}=x_1{x}_2\cdots x_n$. For any set $I=\{i_1,i_2,\dots ,i_m\}\subseteq \left[n\right]$ such that $i_1<i_2<\cdots <i_m$, denote $x_I=x_{i_1}{x}_{i_2}\cdots x_{i_m}$, and call $x_I$ a subsequence of $\mathit{x}$. If $I=[i,j]$ for some $i,j\in [1,n]$ such that $i\le j$, then $x_I=x_{[i,j]}=x_i{x}_{i+1}\cdots x_j$ is called a substring of $\mathit{x}$. We say that $\mathit{x}$ contains $\mathit{p}($ or $\mathit{p}$ is contained in $\mathit{x})$ if $\mathit{p}$ is a substring of $\mathit{x}$. For any $\mathit{x}\in {\Sigma }_q^n$ and $\mathit{y}\in {\Sigma }_q^{n^{\prime }}$, we use $\mathit{x}\mathit{y}$ to denote their concatenation, i.e., $\mathit{x}\mathit{y}=x_1{x}_2\cdots x_n{y}_1{y}_2\cdots y_{n^{\prime }}$. We also use notations such as ${\mathit{x}}_0,{\mathit{x}}_1,\cdots ,{\mathit{x}}_k$ to denote substrings of a sequence $\mathit{x}$. For example, the notation $\mathit{x}={\mathit{x}}_1{\mathit{x}}_2\cdots {\mathit{x}}_k$ means that the sequence $\mathit{x}$ consists of k substrings ${\mathit{x}}_1,{\mathit{x}}_2,\cdots ,{\mathit{x}}_k$.

Let $t\le n$ be a nonnegative integer. For any $\mathit{x}\in {\Sigma }_q^n$, let ${\mathcal{D}}_t\left(\mathit{x}\right)$ denote the set of subsequences of $\mathit{x}$ of length $n-t$, and let ${\mathcal{B}}_t\left(\mathit{x}\right)$ denote the set of subsequences $\mathit{y}$ of $\mathit{x}$ that can be obtained from $\mathit{x}$ by a burst of t deletions, that is, $\mathit{y}=x_{\left[n\right]\setminus D}$ for some interval $D\subseteq \left[n\right]$ of length $t$ (i.e., $D=[i,i+t-1]$ for some $i\in [n-t+1])$. Moreover, let ${\mathcal{B}}_{\le t}\left(\mathit{x}\right)={\bigcup }_{t^{\prime }=0}^t{\mathcal{B}}_{t^{\prime }}\left(\mathit{x}\right)$, i.e., ${\mathcal{B}}_{\le t}\left(\mathit{x}\right)$ is the set of subsequences of $\mathit{x}$ that can be obtained from $\mathit{x}$ by a burst of at most t deletions. Clearly, ${\mathcal{B}}_1\left(\mathit{x}\right)={\mathcal{D}}_1\left(\mathit{x}\right)$ and ${\mathcal{B}}_t\left(\mathit{x}\right)\subseteq {\mathcal{D}}_t\left(\mathit{x}\right)$ for $t\ge 2$.

A code $\mathcal{C}\subseteq {\Sigma }_q^n$ is said to be a t-deletion correcting code if, for any codeword $\mathit{x}\in \mathcal{C}$, given any $\mathit{y}\in {\mathcal{D}}_t\left(\mathit{x}\right)$, $\mathit{x}$ can be uniquely recovered from $\mathit{y}$; the code $\mathcal{C}\subseteq {\Sigma }_q^n$ is said to be capable of correcting a burst of at most t deletions if, for any $\mathit{x}\in \mathcal{C}$, given any $\mathit{y}\in {\mathcal{B}}_{\le t}\left(\mathit{x}\right)$, $\mathit{x}$ can be uniquely recovered from $\mathit{y}$. More generally, let $\mathcal{B}\in \{{\mathcal{D}}_t,{\mathcal{B}}_{\le t}\}$ and N be a positive integer. A code $\mathcal{C}\subseteq {\Sigma }_q^n$ is said to be an $(n,N,\mathcal{B})$-reconstruction code if, for any codeword $\mathit{x}\in \mathcal{C}$, $\mathit{x}$ can be uniquely recovered from any given N distinct sequences in $\mathcal{B}\left(\mathit{x}\right)$. In this case, we also say that $\mathit{x}$ can be uniquely recovered from N reads in $\mathcal{B}\left(\mathit{x}\right)$. If $N=1$, then an $(n,N,\mathcal{B})$-reconstruction code degenerates to the classical error correcting code for the error pattern $\mathcal{B}$.

For any code $\mathcal{C}\subseteq {\Sigma }_q^n$, the redundancy of $\mathcal{C}$ is defined as $n-{\log }_q\left|\mathcal{C}\right|$ measured in q-ary symbols or $\log q(n-{\log }_q|\mathcal{C}\left|\right)$ measured in bits. Clearly, if there is an encoding function that maps each length-k sequence (message) to a length-n codeword in $\mathcal{C}$, then the redundancy of $\mathcal{C}$ is $n-k$. In this paper, we will always assume that q and t are fixed (i.e., q and t are constant with respect to $n)$.

A convenient way for constructing deletion correcting codes is to construct some sketches such that for sufficiently many sequences, each can be recovered from its (known) sketches and one of its subsequence obtained by (a burst of) at most t deletions. The VT syndrome is a sketch for correcting a single deletion, which is defined as follows. For each $\mathit{c}=(c_1,c_2,\cdots ,c_n)\in {\Sigma }_2^n$, the VT syndrome of $\mathit{c}$ is defined as

$$\mathsf{VT}\left(\mathit{c}\right)=\sum _{i=1}^{n}i{c}_{i}mod(n+1).$$

It was proved in [2] that for any $\mathit{c}\in {\Sigma }_2^n$, given $\mathsf{VT}\left(\mathit{c}\right)$ and any $\mathit{y}\in {\mathcal{D}}_1\left(\mathit{c}\right)$, one can uniquely recover $\mathit{x}$.

Suppose $q>2$. For each $\mathit{x}=(x_1,x_2,\cdots ,x_n)\in {\Sigma }_q^n$, let $\varphi \left(\mathit{x}\right)=(\varphi {\left(\mathit{x}\right)}_1,\varphi {\left(\mathit{x}\right)}_2,\cdots ,\varphi {\left(\mathit{x}\right)}_n)\in {\Sigma }_2^n$ be such that, for each $i\in [2,n]$, $\varphi {\left(\mathit{x}\right)}_i=1$ if $x_i\ge x_{i-1}$ and $\varphi {\left(\mathit{x}\right)}_i=0$ if $x_i<x_{i-1}$. Moreover, let $\varphi {\left(\mathit{x}\right)}_1=0$ for all $\mathit{x}\in {\Sigma }_q^n.($ one can also let $\varphi {\left(\mathit{x}\right)}_1=1$ for all $\mathit{x}\in {\Sigma }_q^n)$. Then, there are q-ary codes constructed in [3] for correcting a single deletion.

Lemma 1.

[3] For any $\mathit{x}\in {\Sigma }_q^n$, given $\mathsf{VT}\left(\varphi {\left(\mathit{x}\right)}_{[2,n]}\right)$, $\mathsf{Sum}\left(\mathit{x}\right)$ and any $\mathit{y}\in {\mathcal{D}}_1\left(\mathit{x}\right)$, one can uniquely recover $\mathit{x}$, where $\varphi {\left(\mathit{x}\right)}_{[2,n]}=(\varphi {\left(\mathit{x}\right)}_2,\cdots ,\varphi {\left(\mathit{x}\right)}_n)$ and

$$\mathsf{Sum}\left(\mathit{x}\right)=\sum _{i=1}^n{x}_{i}modq.$$

2.1. A Construction of q-ary Burst-Deletion Codes

For codes correcting burst deletions, the following lemma gives a q-ary version the construction in [33] to q-ary codes $(q>2)$, and will be used in our new construction.

Lemma 2.

For any positive integer m, there exists a function

$$h_{\mathrm{syn}}:{\Sigma }_q^m\to {\Sigma }_q^{4{\log }_{q}m+o\left({\log }_{q}m\right)},$$

computable in time $O\left(q^t{m}^3\right)$, such that $h_{\mathrm{syn}}\left(\mathit{x}\right)\ne h_{\mathrm{syn}}\left({\mathit{x}}^{\prime }\right)$ for any distinct $\mathit{x},{\mathit{x}}^{\prime }\in {\Sigma }_q^m$ with ${\mathcal{B}}_{\le t}\left(\mathit{x}\right)\cap {\mathcal{B}}_{\le t}\left({\mathit{x}}^{\prime }\right)\ne Ø$.

Proof. 

The function $h_{\mathrm{syn}}$ can be constructed by the syndrome compression technique developed in [33].

For each $\mathit{x}\in {\Sigma }_q^m$, let ${\mathcal{N}}_t\left(\mathit{x}\right)$ be the set of all ${\mathit{x}}^{\prime }\in {\Sigma }_q^m\setminus \left\{\mathit{x}\right\}$, such that ${\mathcal{B}}_{\le t}\left(\mathit{x}\right)\cap {\mathcal{B}}_{\le t}\left({\mathit{x}}^{\prime }\right)\ne Ø$. By simple counting, we have

$$\begin{array}{c}\hfill |{\mathcal{N}}_t\left(\mathit{x}\right)|\le t{m}^2{q}^t.\end{array}$$

(1)

We first construct a function $\overline{h}:{\Sigma }_q^m\to [0,2^{\overline{R}}-1]$ satisfying: 1) $\overline{R}={\displaystyle \frac{t(t+1)}{2}}\left(\log m+\log q\right)$; and 2) $\overline{h}\left(\mathit{x}\right)\ne \overline{h}\left({\mathit{x}}^{\prime }\right)$ for any $\mathit{x}\in {\Sigma }_q^m$ and any ${\mathit{x}}^{\prime }\in {\mathcal{N}}_t\left(\mathit{x}\right)$. Specifically, $\overline{h}$ is constructed as follows: For each $t^{\prime }\in \left[t\right]$ and $j\in \left[t^{\prime }\right]$, let

$${\overline{h}}_{t^{\prime },j}\left(\mathit{x}\right)=\left(\mathsf{VT}\left(\varphi {\left(x_{I_{t^{\prime },j}}\right)}_{[2,m_{t^{\prime },j}]}\right),\mathsf{Sum}\left(x_{I_{t^{\prime },j}}\right)\right),$$

where $I_{t^{\prime },j}=\{\ell \in \left[m\right]:\ell \equiv jmod{t}^{\prime }\}$ and $m_{t^{\prime },j}=\left|I_{t^{\prime },j}\right|$. Then, let

$$\overline{h}=\left({\overline{h}}_{1,1},{\overline{h}}_{2,1},{\overline{h}}_{2,2},\cdots ,{\overline{h}}_{t,1},{\overline{h}}_{t,2},\cdots ,{\overline{h}}_{t,t}\right).$$

Clearly, $|I_{t^{\prime },j}|\le \lceil {\displaystyle \frac{m}{t^{\prime }}}\rceil$ and so, when represented as a binary sequence, the length $|\overline{h}\left(\mathit{x}\right)|$ of $\overline{h}\left(\mathit{x}\right)$ satisfies the following (throughout this paper, for any given $q\ge 2$, if needed, we will view a positive integer m as a q-ary sequence which is the q-base representation of m, and conversely, we also view a q-ary sequence $\mathit{z}$ as a positive integer whose q-base representation is $\mathit{z}$):

$$\begin{array}{cc}\hfill |\overline{h}\left(\mathit{x}\right)|& =\sum _{t^{\prime }=1}^t\sum _{j=1}^{t^{\prime }}\left|{\overline{h}}_{t^{\prime },j}\left(\mathit{x}\right)\right|\hfill \\ \hfill & \le \sum _{t^{\prime }=1}^t\sum _{j=1}^{t^{\prime }}\left(\log ⌈{\displaystyle \frac{m}{t^{\prime }}}⌉+\log q\right)\hfill \\ \hfill & \le {\displaystyle \frac{t(t+1)}{2}}\left(\log m+\log q\right)\hfill \\ & =\overline{R}.\hfill \end{array}$$

Hence, viewed as a positive integer, we have $\overline{h}\left(\mathit{x}\right)\in [0,2^{\overline{R}}-1]$ for any $\mathit{x}\in {\Sigma }_q^m$. Moreover, for each $t^{\prime }\in \left[t\right]$, if $\mathit{y}\in {\mathcal{B}}_{t^{\prime }}\left(\mathit{x}\right)$, then we have $y_{I_{t^{\prime },j}^{\prime }}\in {\mathcal{D}}_1\left(x_{I_{t^{\prime },j}}\right)$ for each $j\in \left[t^{\prime }\right]$, where $I_{t^{\prime },j}^{\prime }=\{\ell \in [n-t^{\prime }]:\ell \equiv j\left(\mathrm{mod}{t}^{\prime }\right)\}$. By Lemma 1, $x_{I_{t^{\prime },j}}$ can be recovered from ${\overline{h}}_{t^{\prime },j}\left(\mathit{x}\right)$ and $y_{I_{t^{\prime },j}^{\prime }}$, and so $\mathit{x}$ can be recovered from $\mathit{y}$ and $\overline{h}\left(\mathit{x}\right)$. Equivalently, for any ${\mathit{x}}^{\prime }\in {\mathcal{N}}_t\left(\mathit{x}\right)$, we have $\overline{h}\left(\mathit{x}\right)\ne \overline{h}\left({\mathit{x}}^{\prime }\right)$.

For each $\mathit{x}\in {\Sigma }_q^m$, let $\mathcal{P}\left(\mathit{x}\right)$ be the set of all positive integers j such that j is a divisor of $|\overline{h}\left(\mathit{x}\right)-\overline{h}\left({\mathit{x}}^{\prime }\right)|$ for some ${\mathit{x}}^{\prime }\in {\mathcal{N}}_t\left(\mathit{x}\right)$. By the same discussions as in the proof of [33] (Lemma 4), we can obtain $\left|\mathcal{P}\left(\mathit{x}\right)\right|\le 2^{\log |{\mathcal{N}}_t\left(\mathit{x}\right)|+o\left(\log m\right)}\le O\left(q^t{m}^3\right)$. (Note that q and t are assumed to fixed integers and, by (1), $\left|{\mathcal{N}}_t\right(\mathit{x}\left)\right|\le t{m}^2{q}^t)$. So, by brute force search, one can find, in time $2^{\log |{\mathcal{N}}_t\left(\mathit{x}\right)|+o\left(\log m\right)}\le O\left(q^t{m}^3\right)$, a positive integer $\alpha \left(\mathit{x}\right)\le 2^{\log |{\mathcal{N}}_t\left(\mathit{x}\right)|+o\left(\log m\right)}$ such that $\alpha \left(\mathit{x}\right)\notin \mathcal{P}\left(\mathit{x}\right)$. Let $h_{\mathrm{syn}}\left(\mathit{x}\right)=(\alpha \left(\mathit{x}\right),\overline{h}\left(\mathit{x}\right)mod\alpha \left(\mathit{x}\right))$. Then, we have $h_{\mathrm{syn}}\left(\mathit{x}\right)\ne h_{\mathrm{syn}}\left({\mathit{x}}^{\prime }\right)$ for all ${\mathit{x}}^{\prime }\in {\mathcal{N}}_t\left(\mathit{x}\right)$. Equivalently, $h_{\mathrm{syn}}\left(\mathit{x}\right)\ne h_{\mathrm{syn}}\left({\mathit{x}}^{\prime }\right)$ for any distinct $\mathit{x},{\mathit{x}}^{\prime }\in {\Sigma }_q^n$ with ${\mathcal{B}}_{\le t}\left(\mathit{x}\right)\cap {\mathcal{B}}_{\le t}\left({\mathit{x}}^{\prime }\right)\ne Ø$.

Finally, since $\alpha \left(\mathit{x}\right)\le 2^{\log |{\mathcal{N}}_t\left(\mathit{x}\right)|+o\left(\log m\right)}$ is a positive integer, and by (1), $|{\mathcal{N}}_t\left(\mathit{x}\right)|\le t{m}^2{q}^t$, so viewed as a q-ary sequence, we have $h_{\mathrm{syn}}\left(\mathit{x}\right)\in {\Sigma }_q^{4{\log }_{q}m+o\left({\log }_{q}m\right)}$.    □

Clearly, for any $\mathit{x}\in {\Sigma }_q^m$, given $h_{\mathrm{syn}}\left(\mathit{x}\right)$ and any $\mathit{y}\in {\mathcal{B}}_{\le t}\left(\mathit{x}\right)$, one can uniquely recover $\mathit{x}$. This is because for any $\mathit{x}\ne {\mathit{x}}^{\prime }\in {\Sigma }_q^m$ such that $\mathit{y}\in {\mathcal{B}}_{\le t}\left({\mathit{x}}^{\prime }\right)$, we have $\mathit{y}\in {\mathcal{B}}_{\le t}\left(\mathit{x}\right)\cap {\mathcal{B}}_{\le t}\left({\mathit{x}}^{\prime }\right)$, so ${\mathcal{B}}_{\le t}\left(\mathit{x}\right)\cap {\mathcal{B}}_{\le t}\left({\mathit{x}}^{\prime }\right)\ne Ø$ and by Lemma 2, we have $h_{\mathrm{syn}}\left(\mathit{x}\right)\ne h_{\mathrm{syn}}\left({\mathit{x}}^{\prime }\right)$. Thus, $\mathit{x}$ is uniquely determined by $h_{\mathrm{syn}}\left(\mathit{x}\right)$ and $\mathit{y}$.

2.2. Bounded Burst-Deletion Correction

We give a construction for correcting a single burst-deletion given the knowledge that the location of the deleted symbols are within an interval of length $\rho$.

Given a positive integer $\rho$, we define a collection of intervals

$${\mathcal{L}}_{\rho }=\{L_j:j=1,2,\cdots ,⌈n/\rho ⌉-1\}$$

such that

$$L_j=\{\begin{array}{c}[(j-1)\rho +1,(j+1)\rho ],\mathrm{for}j\in \{1,\cdots ,⌈n/\rho ⌉-2\},\hfill \\ [(j-1)\rho +1,n],\mathrm{for}j=⌈n/\rho ⌉-1.\hfill \end{array}$$

(2)

The following remark is easy to see.

Remark 1.

The intervals in ${\mathcal{L}}_{\rho }$ satisfy the following:

1) 

For any interval $L\subseteq \left[n\right]$ of length $\left|L\right|\le \rho$, there is a (not necessarily unique) $j_0\in [⌈n/\rho ⌉-1]=\{1,2,\cdots ,⌈n/\rho ⌉-1\}$, such that $L\subseteq L_{j_0}$.

2) 

$L_j\cap L_{j^{\prime }}=Ø$ for all $j,j^{\prime }\in [1,⌈n/\rho ⌉-1]$, such that $|j-j^{\prime }|\ge 2$.

Construction 1: Let $h:{\Sigma }_q^m\to {\Sigma }_q^{R_m}$ be a function for any positive integer m, where $R_m$ is a positive integer depending on $m,q$ and t, such that $h\left(\mathit{z}\right)\ne h\left({\mathit{z}}^{\prime }\right)$ for any distinct $\mathit{z},{\mathit{z}}^{\prime }\in {\Sigma }_q^m$ with ${\mathcal{B}}_{\le t}\left(\mathit{z}\right)\cap {\mathcal{B}}_{\le t}\left({\mathit{z}}^{\prime }\right)\ne Ø$. Let ${\mathcal{L}}_{\rho }=\{L_j:j=1,2,\cdots ,⌈n/\rho ⌉-1\}$, such that each $L_j$ is defined by (2). For each $\mathit{x}\in {\Sigma }_q^n$ and each $\ell \in \{0,1\}$, let

$$\begin{array}{c}\hfill {\tilde{h}}_{\rho }^{(\ell )}\left(\mathit{x}\right)=\sum _{\begin{array}{c}j\in [1,⌈n/\rho ⌉-1\}:\\ j\equiv \ell \mathrm{mod}2\end{array}}h\left(x_{L_j}\right)\left(\mathrm{mod}{q}^{R_{2\rho }}\right).\end{array}$$

(3)

The modular operation $\left(\mathrm{mod}{q}^{R_{2\rho }}\right)$ in (3) is performed on the result of the summation, but not on each $h\left(x_{L_j}\right)$.

Lemma 3.

Suppose $\mathit{x}\ne {\mathit{x}}^{\prime }\in {\Sigma }_q^n$. Suppose there exists an interval $L\subseteq \left[n\right]$ of length $\left|L\right|\le \rho$ and two intervals $D,D^{\prime }\subseteq L$ of size $\left|D\right|=|D^{\prime }|\le t$, such that $x_{\left[n\right]\setminus D}=x_{\left[n\right]\setminus D^{\prime }}^{\prime }$. Then, we have ${\tilde{h}}_{\rho }^{(\ell )}\left(\mathit{x}\right)\ne {\tilde{h}}_{\rho }^{(\ell )}\left({\mathit{x}}^{\prime }\right)$ for some $\ell \in \{0,1\}$.

Proof. 

By (2), for each $j\in \{1,2,\cdots ,⌈n/\rho ⌉-1\}$, the length $|L_j|$ of $L_j$ satisfies $\left|L_j\right|\le 2\rho$. So, for any $\mathit{x}\in {\Sigma }_q^m$, the length $\left|h\right(x_{L_j}\left)\right|$ of $h\left(x_{L_j}\right)$ (as a q-ary sequence) satisfies $\left|h\right(x_{L_j}\left)\right|=R_{2|L_j|}\le R_{2\rho }$, which implies that (as an integer),

$$h\left(x_{L_j}\right)<q^{R_{2\rho }}.$$

Since $\left|L\right|\le \rho$, by 1) of Remark 1, there is a $j_0\in [⌈n/\rho ⌉-1]=\{1,2,\cdots ,⌈n/\rho ⌉-1\}$, such that $L\subseteq L_{j_0}$. Let $\ell \in \{0,1\}$ be such that $\ell \equiv j_0\mathrm{mod}2$, and let

$${\Lambda }_{\ell }=\{j\in [1,⌈n/\rho ⌉-1]:j\equiv j_0\mathrm{mod}2\}.$$

Then, by 2) of Remark 1, $L_j\cap L_{j_0}=Ø$ for all $j\in {\Lambda }_{\ell }\setminus \left\{j_0\right\}$. Further, by assumption of $D,D^{\prime }$ and L, we have $x_{L_{j_0}\setminus D}=x_{L_{j_0}\setminus D^{\prime }}^{\prime }\in {\mathcal{B}}_{\le t}\left(x_{L_{j_0}}\right)\cap {\mathcal{B}}_{\le t}\left(x_{L_{j_0}}^{\prime }\right)$ and $x_{L_j}=x_{L_j}^{\prime }$ for all $j\in {\Lambda }_{\ell }\setminus \left\{j_0\right\}$. Therefore, we have

$$h\left(x_{L_{j_0}}^{\prime }\right)\ne h\left(x_{L_{j_0}}\right)$$

and

$$h\left(x_{L_j}^{\prime }\right)=h\left(x_{L_j}\right),\forall j\in {\Lambda }_{\ell }\setminus \left\{j_0\right\}.$$

By the above discussions, and by Construction 1, we can obtain that ${\tilde{h}}_{\rho }^{(\ell )}\left(\mathit{x}\right)\ne {\tilde{h}}_{\rho }^{(\ell )}\left({\mathit{x}}^{\prime }\right)$, which completes the proof.    □

Remark 2.

Let h be the function $h_{syn}$ constructed in Lemma 2. Then, we have $R_{2\rho }=4{\log }_q\left(2\rho \right)+o\left({\log }_q\left(2\rho \right)\right)$. Moreover, by Lemma 2, h is computable in time $O\left(q^t{\left(2\rho \right)}^3\right)$.

3. Pattern Dense Sequences

The concept of $(\mathit{p},\delta )$-dense sequences was introduced in [18], and was used to construct binary codes with redundancy $\log n+{\displaystyle \frac{t(t+1)}{2}}\log \log n+c_t$ for correcting a burst of at most t deletions, where n is the message length and $c_t$ is a constant only depending on t. In this section, we generalize the $(\mathit{p},\delta )$-density to q-ary sequences and derive some important properties for these sequences that will be used in our new construction in the next section.

The q-ary $(\mathit{p},\delta )$-dense sequences can be defined similarly to the binary $(\mathit{p},\delta )$-dense sequences as follows.

Definition 1.

Let $d\le \delta \le n$ be three positive integers and $\mathit{p}\in {\Sigma }_q^d$ called a pattern. A sequence $\mathit{x}\in {\Sigma }_q^n$ is said to be $(\mathit{p},\delta )$-dense if each substring of $\mathit{x}$ of length δ contains at least one $\mathit{p}$. The indicator vector of $\mathit{x}$ with respect to $\mathit{p}$ is a vector

$${\mathbb{1}}_{\mathit{p}}\left(\mathit{x}\right)=\left({\mathbb{1}}_{\mathit{p}}{\left(\mathit{x}\right)}_1,{\mathbb{1}}_{\mathit{p}}{\left(\mathit{x}\right)}_2,\dots ,{\mathbb{1}}_{\mathit{p}}{\left(\mathit{x}\right)}_n\right)\in {\Sigma }_2^n$$

such that, for each $i\in \left[n\right]$, ${\mathbb{1}}_{\mathit{p}}{\left(\mathit{x}\right)}_i=1$ if $x_{[i,i+d-1]}=\mathit{p}$, and ${\mathbb{1}}_{\mathit{p}}{\left(\mathit{x}\right)}_i=0$ otherwise.

In this section, we will always let $(d=2t)$

$$\mathit{p}=0^t{1}^t$$

and view $\mathit{p}=0^t{1}^t\in {\Sigma }_q^{2t}$ for any $q\ge 2$. Moreover, from Definition 1, we have the following simple remark.

Remark 3.

Each sequence $\mathit{x}\in {\Sigma }_q^n$ can be written as the form $\mathit{x}={\mathit{x}}_0\mathit{p}{\mathit{x}}_1\mathit{p}{\mathit{x}}_2\mathit{p}\cdots {\mathit{x}}_{m-1}\mathit{p}{\mathit{x}}_m$ for some $m\ge 0$, such that each ${\mathit{x}}_i$, $i\in [0,m]$, is a (possibly empty) string that does not contain $\mathit{p}$. Moreover, $\mathit{x}$ is $(\mathit{p},\delta )$-dense if and only if it satisfies the following: (1) the lengths of ${\mathit{x}}_0$ and ${\mathit{x}}_m$ are not greater than $\delta -2t$; and (2) the length of each ${\mathit{x}}_i$, $i\in [1,m-1]$, is not greater than $\delta +1-4t$.

In [18], the VT syndrome of ${\mathrm{a}}_{\mathit{p}}\left(\mathit{x}\right)$ was used to bound the location of deletions for $(\mathit{p},\delta )$-dense $\mathit{x}$, where ${\mathrm{a}}_{\mathit{p}}\left(\mathit{x}\right)$ is a vector of length $n_{\mathit{p}}\left(\mathit{x}\right)+1$, whose i-th entry is the distance between positions of the i-th and $(i+1)$-st 1 in the string $(1,{\mathbb{1}}_{\mathit{p}}\left(\mathit{x}\right),1)$, and $n_{\mathit{p}}\left(\mathit{x}\right)$ is the number of 1s in ${\mathbb{1}}_{\mathit{p}}\left(\mathit{x}\right)$. In this paper, we prove that the VT syndrome of ${\mathbb{1}}_{\mathit{p}}\left(\mathit{x}\right)$ plays the same role. Specifically, for each $\mathit{x}\in {\Sigma }_q^n$, let

$$\begin{array}{c}\hfill a_0\left(\mathit{x}\right)=\sum _{i=1}^n{\mathbb{1}}_{\mathit{p}}{\left(\mathit{x}\right)}_i\end{array}$$

(4)

and

$$\begin{array}{c}\hfill a_1\left(\mathit{x}\right)=\sum _{i=1}^{n}i·{\mathbb{1}}_{\mathit{p}}{\left(\mathit{x}\right)}_i\end{array}$$

(5)

where ${\mathbb{1}}_{\mathit{p}}\left(\mathit{x}\right)$ is the indicator vector of $\mathit{x}$ with respect to $\mathit{p}$, as defined in Definition 1. Then, we have the following lemma.

Lemma 4.

Suppose $\mathit{x}\in {\Sigma }_q^n$ is $(\mathit{p},\delta )$-dense. For any $t^{\prime }\in \left[t\right]$ and any $\mathit{y}\in {\mathcal{B}}_{t^{\prime }}\left(\mathit{x}\right)$, given $a_0\left(\mathit{x}\right)\left(\mathrm{mod}4\right)$ and $a_1\left(\mathit{x}\right)\left(\mathrm{mod}2n\right)$, one can find, in time $O\left(n\right)$, an interval $L\subseteq \left[n\right]$ of length $\left|L\right|\le 3\delta$, such that $\mathit{y}=x_{\left[n\right]\setminus D}$ for some interval $D\subseteq L$ of size $\left|D\right|=t^{\prime }=\left|\mathit{x}\right|-\left|\mathit{y}\right|$ (in fact, we can require that the length of L is at most δ. However, the proof for $\left|L\right|\le \delta$ needs more careful discussions).

Proof. 

Let $a_0\left(\mathit{x}\right)=m$ and $a_0\left(\mathit{y}\right)=m^{\prime }$. Then, by Remark 3, $\mathit{x}$ and $\mathit{y}$ can be written as the following form:

$$\mathit{x}={\mathit{x}}_0{0}^t{1}^t{\mathit{x}}_1{0}^t{1}^t{\mathit{x}}_2\cdots 0^t{1}^t{\mathit{x}}_{m-1}{0}^t{1}^t{\mathit{x}}_m$$

and

$$\mathit{y}={\mathit{y}}_0{0}^t{1}^t{\mathit{y}}_1{0}^t{1}^t{\mathit{y}}_2\cdots 0^t{1}^t{\mathit{y}}_{m^{\prime }-1}{0}^t{1}^t{\mathit{y}}_{m^{\prime }}$$

where ${\mathit{x}}_i$ and ${\mathit{y}}_j$ do not contain $\mathit{p}=0^t{1}^t$ for each $i\in [0,m]$ and $j\in [0,m^{\prime }]$. We denote

$$u_i=|{\mathit{y}}_0{0}^t{1}^t{\mathit{y}}_1{0}^t{1}^t\cdots {\mathit{y}}_{i-1}{0}^t{1}^t|,\forall i\in [1,m^{\prime }]$$

and

$$v_i=|{\mathit{y}}_0{0}^t{1}^t{\mathit{y}}_1{0}^t{1}^t\cdots {\mathit{y}}_i|,\forall i\in [0,m^{\prime }].$$

Additionally, let $u_0=0$. Clearly, for each $i\in [0,m^{\prime }]$, we have $u_i\le v_i$ and ${\mathit{y}}_i=y_{[u_i+1,v_i]}$. Moreover, for each $i\in [0,m^{\prime }-1]$, each $j_i\in [u_i,v_i]$ and $j_{i+1}\in [u_{i+1},v_{i+1}]$, we have

$$\begin{array}{c}\hfill j_{i+1}-j_i\ge u_{i+1}-v_i\ge 2t.\end{array}$$

(6)

Note that a burst of $t^{\prime }\le t$ deletions may destroy at most two ps or create at most one $\mathit{p}$, so ${\Delta }_0\triangleq m-m^{\prime }\in \{-1,0,1,2\}$ and ${\Delta }_0$ can be computed from $a_0\left(\mathit{x}\right)-a_0\left(\mathit{y}\right)$. We need to consider the following four cases according to ${\Delta }_0$.

Case 1: ${\Delta }_0=2$. Then, $m^{\prime }=m-2$ and there is an $i_{\mathrm{d}}\in [0,m^{\prime }]$ such that $|{\mathit{x}}_{i_{\mathrm{d}}+1}|\le t^{\prime }-2$ and $\mathit{y}$ can be obtained from $\mathit{x}$ by deleting a substring $1^{t_1}{\mathit{x}}_{i_{\mathrm{d}}+1}{0}^{t_0}$ for some $t_0,t_1>0$, such that $|{\mathit{x}}_{i_{\mathrm{d}}+1}|+t_0+t_1=t^{\prime }$. More specifically, ${\mathit{y}}_{i_{\mathrm{d}}}={\mathit{x}}_{i_{\mathrm{d}}}{0}^t{1}^{t-t_1}{0}^{t-t_0}{1}^t{\mathit{x}}_{i_{\mathrm{d}}+2}$. Clearly, we have $2\le t^{\prime }\le t$ and $x_{[u_{i_{\mathrm{d}}}+1,v_{i_{\mathrm{d}}}+t^{\prime }]}={\mathit{x}}_{i_{\mathrm{d}}}{0}^t{1}^t{\mathit{x}}_{i_{\mathrm{d}}+1}{0}^t{1}^t{\mathit{x}}_{i_{\mathrm{d}}+2}$. It is sufficient to let $L=[u_{i_{\mathrm{d}}}+1,v_{i_{\mathrm{d}}}+t^{\prime }]$, but we still need to find $i_{\mathrm{d}}$.

Consider ${\mathbb{1}}_{\mathit{p}}\left(\mathit{x}\right)$ and ${\mathbb{1}}_{\mathit{p}}\left(\mathit{y}\right)$. By Definition 1, ${\mathbb{1}}_{\mathit{p}}\left(\mathit{x}\right)$ can be obtained from ${\mathbb{1}}_{\mathit{p}}\left(\mathit{y}\right)$ by $t^{\prime }$ insertions and two substitutions in the substring ${\mathbb{1}}_{\mathit{p}}{\left(\mathit{y}\right)}_{[u_{i_{\mathrm{d}}}+1,v_{i_{\mathrm{d}}}]}$: inserting $t^{\prime }$ 0s and substituting two 0s by two 1s. Then, by (5), we can obtain

$$\begin{array}{c}\hfill a_1\left(\mathit{x}\right)=a_1\left(\mathit{y}\right)+{\lambda }_1\left(i_{\mathrm{d}}\right)+{\lambda }_2\left(i_{\mathrm{d}}\right)+(m^{\prime }-i_{\mathrm{d}})t^{\prime }\end{array}$$

(7)

where ${\lambda }_1\left(i_{\mathrm{d}}\right),{\lambda }_2\left(i_{\mathrm{d}}\right)\in [u_{i_{\mathrm{d}}}+1,v_{i_{\mathrm{d}}}+t^{\prime }]$ are the locations of the two substitutions. To find $i_{\mathrm{d}}$, we define a function ${\xi }_2$ as follows: for every $i\in [0,m^{\prime }]$, let

$${\xi }_2\left(i\right)=a_1\left(\mathit{y}\right)+2(u_i+1)+(m^{\prime }-i)t^{\prime }.$$

Then, for each $i\in [0,m^{\prime }-1]$, we can obtain ${\xi }_2(i+1)-{\xi }_2\left(i\right)=2(u_{i+1}-u_i)-t^{\prime }\ge 4t-t^{\prime }>0$, where the first inequality comes from (6). So, for each $i\in [0,m^{\prime }-1]$, we have

$$\begin{array}{c}\hfill a_1\left(\mathit{y}\right)<{\xi }_2\left(i\right)<{\xi }_2(i+1)\le {\xi }_2\left(m^{\prime }\right)<a_1\left(\mathit{y}\right)+2n,\end{array}$$

(8)

where the last inequality comes from the simple observation that ${\xi }_2\left(m^{\prime }\right)=a_1\left(\mathit{y}\right)+2(u_{m^{\prime }}+1)<a_1\left(\mathit{y}\right)+2n$.

By definition of ${\xi }_2$ and $a_1$, we can obtain

$$\begin{array}{cc}\hfill {\xi }_2(i_{\mathrm{d}}+1)-a_1\left(\mathit{x}\right)& =2(u_{i_{\mathrm{d}}+1}+1)-{\lambda }_1\left(i_{\mathrm{d}}\right)-{\lambda }_2\left(i_{\mathrm{d}}\right)-t^{\prime }\hfill \\ \hfill & \stackrel{\left(\mathrm{i}\right)}{\ge }2u_{i_{\mathrm{d}}+1}+2-2(v_{i_{\mathrm{d}}}+t^{\prime })-t^{\prime }\hfill \\ \hfill & \stackrel{\left(\mathrm{ii}\right)}{\ge }4t+2-3t^{\prime }\hfill \\ & >0\hfill \end{array}$$

where (i) holds because ${\lambda }_1\left(i_{\mathrm{d}}\right),{\lambda }_2\left(i_{\mathrm{d}}\right)\in [u_{i_{\mathrm{d}}}+1,v_{i_{\mathrm{d}}}+t^{\prime }]$, and (ii) is obtained from (6). On the other hand, by (7), $a_1\left(\mathit{x}\right)-{\xi }_2\left(i_{\mathrm{d}}\right)={\lambda }_1\left(i_{\mathrm{d}}\right)+{\lambda }_2\left(i_{\mathrm{d}}\right)-2(u_{i_{\mathrm{d}}}+1)\ge 0$ (noticing that ${\lambda }_1\left(i_{\mathrm{d}}\right),{\lambda }_2\left(i_{\mathrm{d}}\right)\in [u_{i_{\mathrm{d}}}+1,v_{i_{\mathrm{d}}}+t^{\prime }])$. Hence, we can obtain

$$\begin{array}{c}\hfill {\xi }_2\left(i_{\mathrm{d}}\right)\le a_1\left(\mathit{x}\right)<{\xi }_2(i_{\mathrm{d}}+1).\end{array}$$

(9)

By (8) and (9), $i_{\mathrm{d}}$ and L can be found as follows: Compute

$$\mu \triangleq a_1\left(\mathit{x}\right)\left(\mathrm{mod}2n\right)-a_1\left(\mathit{y}\right)\left(\mathrm{mod}2n\right)$$

and

$${\mu }_i\triangleq {\xi }_2\left(i\right)\left(\mathrm{mod}2n\right)-a_1\left(\mathit{y}\right)\left(\mathrm{mod}2n\right)$$

for i from 0 to $m^{\prime }$. Then, we can find an $i_{\mathrm{d}}\in [0,m^{\prime }]$ such that ${\mu }_{i_{\mathrm{d}}}\le \mu <{\mu }_{i_{\mathrm{d}}+1}$, where ${\mu }_{m^{\prime }+1}=2n$. Let $L=[u_{i_{\mathrm{d}}}+1,v_{i_{\mathrm{d}}}+t^{\prime }]$. Note that $x_{[u_{i_{\mathrm{d}}}+1,v_{i_{\mathrm{d}}}+t^{\prime }]}={\mathit{x}}_{i_{\mathrm{d}}}{0}^t{1}^t{\mathit{x}}_{i_{\mathrm{d}}+1}{0}^t{1}^t{\mathit{x}}_{i_{\mathrm{d}}+2}$ and $\mathit{x}$ is $(\mathit{p},\delta )$-dense, so by Remark 3, the length of L satisfies $\left|L\right|=|{\mathit{x}}_{i_{\mathrm{d}}}{0}^t{1}^t{\mathit{x}}_{i_{\mathrm{d}}+1}{0}^t{1}^t{\mathit{x}}_{i_{\mathrm{d}}+2}|\le 3(\delta +1-4t)+4t\le 3\delta$, where the last inequality holds because $2\le t^{\prime }\le t$.

Case 2: ${\Delta }_0=1$. Then, $m^{\prime }=m-1$ and, similarly to Case 1, there is an $i_{\mathrm{d}}\in [0,m^{\prime }]$ such that ${\mathit{y}}_{i_{\mathrm{d}}}$ can be obtained from ${\mathit{x}}_{i_{\mathrm{d}}}{0}^t{1}^t{\mathit{x}}_{i_{\mathrm{d}}+1}$ by deleting $t^{\prime }$ symbols and the pattern $0^t{1}^t$ is destroyed. Clearly, $x_{[u_{i_{\mathrm{d}}}+1,v_{i_{\mathrm{d}}}+t^{\prime }]}={\mathit{x}}_{i_{\mathrm{d}}}{0}^t{1}^t{\mathit{x}}_{i_{\mathrm{d}}+1}$, and it is sufficient to let $L=[u_{i_{\mathrm{d}}}+1,v_{i_{\mathrm{d}}}+t^{\prime }]$. To find $i_{\mathrm{d}}$, consider ${\mathbb{1}}_{\mathit{p}}\left(\mathit{y}\right)$ and ${\mathbb{1}}_{\mathit{p}}\left(\mathit{x}\right)$. By Definition 1, ${\mathbb{1}}_{\mathit{p}}\left(\mathit{x}\right)$ can be obtained from ${\mathbb{1}}_{\mathit{p}}\left(\mathit{y}\right)$ by $t^{\prime }$ insertions and one substitution in the substring ${\mathbb{1}}_{\mathit{p}}{\left(\mathit{y}\right)}_{[u_{i_{\mathrm{d}}}+1,v_{i_{\mathrm{d}}}]}$: inserting $t^{\prime }$ 0s and substituting a 0 by a 1. By (5), we can obtain

$$\begin{array}{c}\hfill a_1\left(\mathit{x}\right)=a_1\left(\mathit{y}\right)+\lambda \left(i_{\mathrm{d}}\right)+(m^{\prime }-i_{\mathrm{d}})t^{\prime }\end{array}$$

(10)

where $\lambda \left(i_{\mathrm{d}}\right)\in [u_{i_{\mathrm{d}}}+1,v_{i_{\mathrm{d}}}+t^{\prime }]$ is the location of the substitution. For every $i\in [0,m^{\prime }]$, let

$${\xi }_1\left(i\right)=a_1\left(\mathit{y}\right)+(u_i+1)+(m^{\prime }-i)t^{\prime }.$$

Then, for each $i\in [0,m^{\prime }-1]$, we have ${\xi }_1(i+1)-{\xi }_1\left(i\right)=u_{i+1}-u_i-t^{\prime }\ge 2t-t^{\prime }>0$, and so we can further obtain

$$\begin{array}{c}\hfill a_1\left(\mathit{y}\right)<{\xi }_1\left(i\right)<{\xi }_1(i+1)\le {\xi }_1\left(m^{\prime }\right)\le a_1\left(\mathit{y}\right)+n.\end{array}$$

(11)

By definition of ${\xi }_1$ and $a_1$, we can obtain ${\xi }_1(i_{\mathrm{d}}+1)-a_1\left(\mathit{x}\right)=u_{i_{\mathrm{d}}+1}+1-\lambda \left(i_{\mathrm{d}}\right)-t^{\prime }>u_{i_{\mathrm{d}}+1}+1-(v_i+t^{\prime })-t^{\prime }\ge 2t+1-2t^{\prime }>0$. On the other hand, by (10), $a_1\left(\mathit{x}\right)-{\xi }_1\left(i_{\mathrm{d}}\right)=\lambda \left(i_{\mathrm{d}}\right)-(u_{i_{\mathrm{d}}}+1)\ge 0$. Hence, we can obtain

$$\begin{array}{c}\hfill {\xi }_1\left(i_{\mathrm{d}}\right)\le a_1\left(\mathit{x}\right)<{\xi }_1(i_{\mathrm{d}}+1).\end{array}$$

(12)

By (11) and (12), L can be found as follows: Compute

$$\mu \triangleq a_1\left(\mathit{x}\right)\left(\mathrm{mod}2n\right)-a_1\left(\mathit{y}\right)\left(\mathrm{mod}2n\right)$$

and

$${\mu }_i\triangleq {\xi }_1\left(i\right)\left(\mathrm{mod}2n\right)-a_1\left(\mathit{y}\right)\left(\mathrm{mod}2n\right)$$

for i from 0 to $m^{\prime }$. Let $i_{\mathrm{d}}\in [0,m^{\prime }]$ be such that ${\mu }_{i_{\mathrm{d}}}\le \mu <{\mu }_{i_{\mathrm{d}}+1}$. Then, let $L=[u_{i_{\mathrm{d}}}+1,v_{i_{\mathrm{d}}}+t^{\prime }]$, where ${\mu }_{m^{\prime }+1}=2n$. Note that $x_{[u_{i_{\mathrm{d}}}+1,v_{i_{\mathrm{d}}}+t^{\prime }]}={\mathit{x}}_{i_{\mathrm{d}}}{0}^t{1}^t{\mathit{x}}_{i_{\mathrm{d}}+1}$ and $\mathit{x}$ is $(\mathit{p},\delta )$-dense, so by Remark 3, $\left|L\right|=|{\mathit{x}}_{i_{\mathrm{d}}}{0}^t{1}^t{\mathit{x}}_{i_{\mathrm{d}}+1}|\le 2(\delta +1-4t)+2t<2\delta$.

Case 3: ${\Delta }_0=0$. Then, $m^{\prime }=m$. For every $i\in [0,m]$, let

$${\xi }_0\left(i\right)=a_1\left(\mathit{y}\right)+(m-i)t^{\prime }.$$

Note that $\mathit{x}$ contains m copies of $0^t{1}^t$, so we have $n\ge 2tm>m{t}^{\prime }$. Therefore, for each $i\in [0,m-1]$, we can obtain

$$\begin{array}{c}\hfill a_1\left(\mathit{y}\right)+n>a_1\left(\mathit{y}\right)+m{t}^{\prime }\ge {\xi }_0\left(i\right)>{\xi }_0(i+1)\ge a_1\left(\mathit{y}\right).\end{array}$$

(13)

As ${\Delta }_0=0$, there are two ways to obtain $\mathit{y}$ from $\mathit{x}$:

1)

There is an $i_{\mathrm{d}}\in [0,m]$ such that ${\mathit{y}}_{i_{\mathrm{d}}}$ can be obtained from ${\mathit{x}}_{i_{\mathrm{d}}}$ by a burst of $t^{\prime }$ deletions. Correspondingly, by Definition 1, ${\mathbb{1}}_{\mathit{p}}\left(\mathit{x}\right)$ can be obtained from ${\mathbb{1}}_{\mathit{p}}\left(\mathit{y}\right)$ by inserting $t^{\prime }$ 0s into ${\mathbb{1}}_{\mathit{p}}{\left(\mathit{y}\right)}_{[u_{i_{\mathrm{d}}}+1,v_{i_{\mathrm{d}}}]}$. Therefore, we have

$$\begin{array}{c}\hfill a_1\left(\mathit{x}\right)=a_1\left(\mathit{y}\right)+(m-i_{\mathrm{d}})t^{\prime }={\xi }_0\left(i_{\mathrm{d}}\right).\end{array}$$

(14)

2)

There is an $i_{\mathrm{d}}\in [0,m-1]$ such that ${\mathit{x}}_{i_{\mathrm{d}}}{0}^t{1}^t{\mathit{x}}_{i_{\mathrm{d}}+1}={\mathit{y}}_{i_{\mathrm{d}}}{0}^{t+t_0}{1}^{t+t_1}{\mathit{y}}_{i_{\mathrm{d}}+1}$ for some $t_0,t_1\in [1,t^{\prime }-1]$, such that $t_0+t_1=t^{\prime }$, and ${\mathit{y}}_{i_{\mathrm{d}}}{0}^t{1}^t{\mathit{y}}_{i_{\mathrm{d}}+1}$ is obtained from ${\mathit{x}}_{i_{\mathrm{d}}}{0}^t{1}^t{\mathit{x}}_{i_{\mathrm{d}}+1}$ by deleting the substring $0^{t_0}{1}^{t_1}$. By Definition 1, ${\mathbb{1}}_{\mathit{p}}\left(\mathit{x}\right)$ can be obtained from ${\mathbb{1}}_{\mathit{p}}\left(\mathit{y}\right)$ by inserting $t_0$ 0s in ${\mathbb{1}}_{\mathit{p}}{\left(\mathit{y}\right)}_{[u_{i_{\mathrm{d}}}+1,v_{i_{\mathrm{d}}}]}$ and $t_1$ 0s in ${\mathbb{1}}_{\mathit{p}}{\left(\mathit{y}\right)}_{[v_{i_{\mathrm{d}}}+2,v_{i_{\mathrm{d}}+2t}]}$. Therefore, we have

$$a_1\left(\mathit{x}\right)=a_1\left(\mathit{y}\right)+t_0+(m-i_{\mathrm{d}}-1)t^{\prime }.$$

By definition of ${\xi }_0$, we have ${\xi }_0\left(i_{\mathrm{d}}\right)-a_1\left(\mathit{x}\right)=t^{\prime }-t_0>0$ and $a_1\left(\mathit{x}\right)-{\xi }_0(i_{\mathrm{d}}+1)=t_0>0$. So, we can obtain

$$\begin{array}{c}\hfill {\xi }_0\left(i_{\mathrm{d}}\right)>a_1\left(\mathit{x}\right)>{\xi }_0(i_{\mathrm{d}}+1)\end{array}$$

(15)

For both cases, if $i_{\mathrm{d}}\in [0,m-1]$, then we can $L=[u_{i_{\mathrm{d}}}+1,v_{i_{\mathrm{d}}}+2t+t^{\prime }]$; if $i_{\mathrm{d}}=m$, then we can let $L=[u_m+1,n]$. Note that $x_{[u_{i_{\mathrm{d}}}+1,v_{i_{\mathrm{d}}}+2t+t^{\prime }]}={\mathit{x}}_{i_{\mathrm{d}}}{0}^t{1}^t$ and $x_{[u_m+1,n]}={\mathit{x}}_m$, and since $\mathit{x}$ is $(\mathit{p},\delta )$-dense, then by Remark 3, we have $\left|L\right|=|{\mathit{x}}_{i_{\mathrm{d}}}{0}^t{1}^t|\le 2\delta$ or $\left|L\right|=|{\mathit{x}}_m|\le 2\delta$. Moreover, by (13), (14), and (15), $i_{\mathrm{d}}$ (and so $L)$ can be found as follows: Compute

$$\mu \triangleq a_1\left(\mathit{x}\right)\left(\mathrm{mod}2n\right)-a_1\left(\mathit{y}\right)\left(\mathrm{mod}2n\right)$$

and

$${\mu }_i\triangleq {\xi }_0\left(i\right)\left(\mathrm{mod}2n\right)-a_1\left(\mathit{y}\right)\left(\mathrm{mod}2n\right)$$

for i from 0 to m. Then, we can always find an $i_{\mathrm{d}}\in [0,m]$, such that ${\mu }_{i_{\mathrm{d}}}\ge \mu >{\mu }_{i_{\mathrm{d}}+1}$, which is what we want.

Case 4: ${\Delta }_0=-1$. Then, $m^{\prime }=m+1$ and there is an $i_{\mathrm{d}}\in [0,m^{\prime }-1]$ such that ${\mathit{x}}_{i_{\mathrm{d}}}={\mathit{y}}_{i_{\mathrm{d}}}{0}^{t_0}\mathit{s}{0}^{t-t_0}{1}^t{\mathit{y}}_{i_{\mathrm{d}}+1}$ or ${\mathit{x}}_{i_{\mathrm{d}}}={\mathit{y}}_{i_{\mathrm{d}}}{0}^t{1}^{t_1}\mathit{s}{1}^{t-t_1}{\mathit{y}}_{i_{\mathrm{d}}+1}$, where $t_0\in [1,t]$, $t_1\in [1,t-1]$ and $\mathit{s}\in {\Sigma }_q^{t^{\prime }}$, and $\mathit{y}$ can be obtained from $\mathit{x}$ by deleting $\mathit{s}$. In this case, we can let $L=[v_{i_{\mathrm{d}}}+1,v_{i_{\mathrm{d}}}+2t+t^{\prime }]$, and can obtain $\left|L\right|=2t+t^{\prime }<\delta$. To find $i_{\mathrm{d}}$, we consider ${\mathbb{1}}_{\mathit{p}}\left(\mathit{x}\right)$ and ${\mathbb{1}}_{\mathit{p}}\left(\mathit{y}\right)$. By Definition 1, ${\mathbb{1}}_{\mathit{p}}\left(\mathit{x}\right)$ can be obtained from ${\mathbb{1}}_{\mathit{p}}\left(\mathit{y}\right)$ by inserting $t^{\prime }$ 0s into ${\mathbb{1}}_{\mathit{p}}{\left(\mathit{y}\right)}_{[v_{i_{\mathrm{d}}+1},v_{i_{\mathrm{d}}}+2t]}$ and substituting ${\mathbb{1}}_{\mathit{p}}{\left(\mathit{y}\right)}_{v_{i_{\mathrm{d}}}+1}=1$ by a 0. Therefore, we have

$$\begin{array}{c}\hfill a_1\left(\mathit{x}\right)=a_1\left(\mathit{y}\right)-(v_{i_{\mathrm{d}}}+1)+(m^{\prime }-1-i_{\mathrm{d}})t^{\prime }.\end{array}$$

(16)

For every $i\in [0,m^{\prime }-1]$, let

$${\xi }_{-1}\left(i\right)=a_1\left(\mathit{y}\right)-(v_i+1)+(m^{\prime }-1-i)t^{\prime }.$$

Then, for each $i\in [0,m^{\prime }-2]$, we have ${\xi }_{-1}\left(i\right)-{\xi }_{-1}(i+1)=v_{i+1}-v_i-t^{\prime }>0$, where the inequality is obtained from (6). Moreover, we have ${\xi }_{-1}\left(0\right)=a_1\left(\mathit{y}\right)-1+(m^{\prime }-1)t^{\prime }<a_1\left(\mathit{y}\right)+2t{m}^{\prime }<a_1\left(\mathit{y}\right)+n$ and ${\xi }_{-1}(m^{\prime }-1)=a_1\left(\mathit{y}\right)-(v_{m^{\prime }-1}+1)>a_1\left(\mathit{y}\right)-n$. So, for each $i\in [0,m^{\prime }-2]$, we can obtain

$$\begin{array}{c}\hfill a_1\left(\mathit{y}\right)+n>{\xi }_{-1}\left(i\right)>{\xi }_{-1}(i+1)>a_1\left(\mathit{y}\right)-n.\end{array}$$

(17)

By (16), and by the definition of ${\xi }_{-1}$, we have $a_1\left(\mathit{x}\right)={\xi }_{-1}\left(i_{\mathrm{d}}\right)$. So, by (17), $i_{\mathrm{d}}$ (and so $L)$ can be found by the following process: For i from 0 to $m^{\prime }-1$, compute ${\xi }_{-1}\left(i\right)$. Then, we can always find an $i_{\mathrm{d}}\in [0,m^{\prime }-1]$ such that ${\xi }_{-1}\left(i_{\mathrm{d}}\right)\left(\mathrm{mod}2n\right)=a_1\left(\mathit{x}\right)\left(\mathrm{mod}2n\right)$, which is what we want.

Thus, one can always find the expected interval $L\subseteq \left[n\right]$. From the above discussions, it is easy to see that the time complexity for finding such L is $O\left(n\right)$.    □

In the rest of this section, we will use the so-called sequence replacement (SR) technique to construct q-ary $(\mathit{p},\delta )$-dense strings with only one symbol of redundancy for $\delta =2t{q}^{2t}\lceil \log n\rceil$. The SR technique, which has been widely used in the literature (e.g., see [19,34,35,36]), is an efficient method for constructing strings with or without some constraints on their substrings. In this paper, to apply the SR technique to construct $(\mathit{p},\delta )$-dense strings, each length-$\delta$ string that does not contain $\mathit{p}$ needs to be compressed to a shorter sequence, which can be realized by the following lemma.

Lemma 5.

Let $\delta =2t{q}^{2t}\lceil \log n\rceil$ and $\mathcal{S}\subseteq {\Sigma }_q^{\delta }$ be the set of all sequences of length δ that do not contain $\mathit{p}=0^t{1}^t$. For $n\ge q^{{\displaystyle \frac{6t+3-{\log }_{q}e}{0.4}}}$, there exists an invertible function

$$g:\mathcal{S}\to {\Sigma }_q^{\delta -\lceil {\log }_{q}n\rceil -6t-2}$$

such that g and $g^{-1}$ are computable in time $O\left(\delta \right)$.

Proof. 

The proof follows the same idea of Proposition 1 of [19], and is replicated here for completeness.

As each $\mathit{s}\in \mathcal{S}$ has length $\delta =2t{q}^{2t}\lceil \log n\rceil$ and does not contain $\mathit{p}$, then $\mathcal{S}$ can be viewed as a subset of ${\left({\Sigma }_q^{2t}\setminus \left\{\mathit{p}\right\}\right)}^{q^{2t}\lceil \log n\rceil }$, and we have

$$\begin{array}{cc}\hfill {\log }_q\left|\mathcal{S}\right|& \le {\log }_q{\left(q^{2t}-1\right)}^{q^{2t}\lceil \log n\rceil }\hfill \\ \hfill & =\left(2t\right)q^{2t}\lceil \log n\rceil +\lceil \log n\rceil {\log }_q{\left(1-{\displaystyle \frac{1}{q^{2t}}}\right)}^{q^{2t}}\hfill \\ \hfill & \stackrel{\left(\mathrm{i}\right)}{\le }\left(2t\right)q^{2t}\lceil \log n\rceil +(\log n+1){\log }_q\left({\displaystyle \frac{1}{e}}\right)\hfill \\ \hfill & =\delta -{\log }_{q}n\log e-{\log }_{q}e\hfill \\ \hfill & \le \delta -1.4{\log }_{q}n-{\log }_{q}e\hfill \\ \hfill & \stackrel{\left(\mathrm{ii}\right)}{\le }\delta -\lceil {\log }_{q}n\rceil -6t-2,\hfill \end{array}$$

where (i) comes from the fact that ${\left(1-{\displaystyle \frac{1}{x}}\right)}^x<{\displaystyle \frac{1}{e}}$ for $x\ge 1$, and (ii) holds when $0.4{\log }_{q}n+{\log }_{q}e\ge 6t+3$, i.e., $n\ge q^{{\displaystyle \frac{6t+3-{\log }_{q}e}{0.4}}}$. Thus, each sequence in $\mathcal{S}$ can be represented by a q-ary sequence of length $\delta -\lceil {\log }_{q}n\rceil -6t-2$, which gives an invertible function $g:\mathcal{S}\to {\Sigma }_q^{\delta -\lceil {\log }_{q}n\rceil -6t-2}$.

The computation of g and $g^{-1}$ involve conversion of integers in $[0,{\left(q^{2t}-1\right)}^{q^{2t}\lceil \log n\rceil }-1]$ between $(q^{2t}-1)$-base representation and q-base representation, so have time complexity $O\left(2t{q}^{2t}\lceil \log n\rceil \right)=O\left(\delta \right)$.    □

In the rest of this section, we will always let

$$\delta =2t{q}^{2t}\lceil \log n\rceil .$$

As we are interested in large n, we will always assume that $n\ge q^{{\displaystyle \frac{6t+3-{\log }_{q}e}{0.4}}}$. The following lemma gives a function for encoding q-ary strings to $(\mathit{p},\delta )$-dense strings.

Lemma 6.

There exists an invertible function, denoted by $\mathsf{EncDen}:{\Sigma }_q^{n-1}\to {\Sigma }_q^n$, such that for every $\mathit{u}\in {\Sigma }_q^{n-1}$, $\mathit{x}=\mathsf{EncDen}\left(\mathit{u}\right)$ is $(\mathit{p},\delta )$-dense. Both $\mathsf{EncDen}$ and its inverse, denoted by $\mathsf{DecDen}$, are computable in $O\left(n\log n\right)$ time.

Proof. 

Let g be the function constructed in Lemma 5. The functions $\mathsf{EncDen}$ and $\mathsf{DecDen}$ are described by Algorithms 1 and 2, respectively, where each integer $i\in \left[n\right]$ is also viewed as a q-ary string of length $\lceil \log n\rceil$ which is the q-base representation of i.

The correctness of Algorithm 1 can be proved as follows:

1)

In the initialization step, if $\tilde{\mathit{u}}=u_{[n-\delta +2t,n-1]}$ contains $\mathit{p}$ then, clearly, $\mathit{x}$ has length n. If $\tilde{\mathit{u}}=u_{[n-\delta +2t,n-1]}$ does not contain $\mathit{p}$, then

$$\mathit{x}=(u_{[1,n^{\prime }]},\mathit{p},\mathit{p},g\left((\tilde{\mathit{u}},0^{2t})\right),0^{\lceil {\log }_{q}n\rceil +3})$$

and so $\left|\mathit{x}\right|=n^{\prime }+4t+\left|g\left((\tilde{\mathit{u}},0^{2t})\right)\right|+\lceil {\log }_{q}n\rceil +3=n$, where $n^{\prime }=n-\delta +2t-1$, and by Lemma 5, $|g\left((\tilde{\mathit{u}},0^{2t})\right)|=\delta -\lceil {\log }_{q}n\rceil -6t-2$. So, at the end of the initialization step, $\mathit{x}$ has length n. Moreover, $x_{[n^{\prime }+1,n^{\prime }+2t]}=\mathit{p}$, and the substring $x_{[n^{\prime }+2t+1,n]}$ has length $\le \delta -4t+1$.

2)

In each round of the replacement step, if $\tilde{\mathit{x}}\triangleq x_{[i,i+\delta -1]}$ does not contain $\mathit{p}$ for some $i\in [1,n^{\prime }-\delta +1]$, then by Lemma 5, $|(\mathit{p},\mathit{p},i,g\left(\tilde{\mathit{x}}\right),0,1^{2t},0)|=\delta =|x_{[i,i+\delta -1]}|$, so by replacement, the length of the appended string equals to the length of the deleted substring, and hence the length of $\mathit{x}$ keeps unchanged.

3)

At the beginning of each round of the replacement step, we have $x_{[n^{\prime }+1,n^{\prime }+2t]}=\mathit{p}$, so for $i\in [n^{\prime }+2t-\delta +1,n^{\prime }]$, the substring $x_{[i,i+\delta -1]}$ contains $\mathit{p}$. Equivalently, if $\tilde{\mathit{x}}\triangleq x_{[i,i+\delta -1]}$ does not contain $\mathit{p}$ for some $i\in [n^{\prime }-\delta +2,n^{\prime }]$, then it must be that $i\in [n^{\prime }-\delta +2,n^{\prime }+2t-\delta ]$. In this case, $|(\mathit{p},\mathit{p},i,g\left((x_{[i,n^{\prime }]},0^{\ell })\right),0,1^{2t-\ell },0)|=\delta -\ell =|x_{[i,n^{\prime }]}|$, so by replacement, the length of the appended string equals to the length of the deleted substring, and hence the length of $\mathit{x}$ keeps unchanged.

4)

By 1), 2) and 3), the substring $x_{[n^{\prime }+1,n-\delta +1]}$ is always of the form $\mathit{p}\mathit{u}\mathit{p}\mathit{p}\mathit{v}\cdots \mathit{p}\mathit{p}\mathit{w}$, where all substrings $\mathit{u},\mathit{v},\cdots ,\mathit{w}$ have a length not greater than $\delta +1-4t$. So, by Remark 3, for each $i\in [n^{\prime }+1,n-\delta +1]$, the substring $x_{[i,i+\delta -1]}$ contains $\mathit{p}$.

5)

At the end of each round of the replacement step, the value of $n^{\prime }$ strictly decreases, so the While loop will end after at most n rounds, and at this time, for each $i\in [1,n^{\prime }]$, the substring $x_{[i,i+\delta -1]}$ contains $\mathit{p}$, which combining with 4) implies that $\mathit{x}$ is $(\mathit{p},\delta )$-dense.

The correctness of Algorithm 2 can be easily seen from Algorithm 1, so $\mathsf{DecDen}$ is the inverse of $\mathsf{EncDen}$.

Note that Algorithms 1 and 2 have at most n rounds of replacement, and in each round, $g$ (resp. $g^{-1})$ needs to be computed, which has time complexity $O\left(\delta \right)=O\left(\log n\right)$ by Lemma 5, so the total time complexity of Algorithms 1 and 2 is $O\left(n\log n\right)$.    □

Algorithm 1: The function $\mathsf{EncDen}$ for encoding to $(\mathit{p},\delta )$-dense sequence

1:  Input:   $\mathit{u}\in {\Sigma }_q^{n-1}$ 2:  Output: $\mathit{x}=\mathsf{EncDen}\left(\mathit{u}\right)\in {\Sigma }_q^n$ such that $\mathit{x}$ is $(\mathit{p},\delta )$-dense 3:  (Initialization Step:) 4:  Let $\tilde{\mathit{u}}=u_{[n-\delta +2t,n-1]}$. 5:  if $\tilde{\mathit{u}}$ contains $\mathit{p}$ then 6:       let $n^{\prime }$ be the smallest $i\in [n-\delta +2t-1,n-2]$ such that $u_{[i+1,i+2t]}=\mathit{p}$, and let $\mathit{x}=(\mathit{u},1)$; 7:  else 8:       let $n^{\prime }=n-\delta +2t-1$ and $\mathit{x}=(u_{[1,n^{\prime }]},\mathit{p},\mathit{p},g\left((\tilde{\mathit{u}},0^{2t})\right),0^{\lceil {\log }_{q}n\rceil +3})$. 9:  end if 10:  (Replacement Step:) 11:  while there exists an $i\in [1,n^{\prime }]$ such that $\tilde{\mathit{x}}\triangleq x_{[i,i+\delta -1]}$ does not contain $\mathit{p}$ do 12:      if $i\in [1,n^{\prime }-\delta +1]$ then 13:           delete $x_{[i,i+\delta -1]}$ from $\mathit{x}$ and append $(\mathit{p},\mathit{p},i,g\left(\tilde{\mathit{x}}\right),0,1^{2t},0)$ to $\mathit{x}$; let $n^{\prime }=n^{\prime }-\delta$. 14:      end if 15:      if $i\in [n^{\prime }-\delta +2,n^{\prime }]$ then 16:           delete $x_{[i,n^{\prime }]}$ from $\mathit{x}$ and append $(\mathit{p},\mathit{p},i,g\left((x_{[i,n^{\prime }]},0^{\ell })\right),0,1^{2t-\ell },0)$ to $\mathit{x}$, where $\ell \triangleq \delta -|x_{[i,n^{\prime }]}|$ satisfying $1\le \ell \le 2t-1$; let $n^{\prime }=i-1$. 17:      end if 18:  end while 19:  Return  $\mathit{x}=\mathsf{EncDen}\left(\mathit{u}\right)$.

Algorithm 2: The function $\mathsf{DecDen}$ for decoding of $(\mathit{p},\delta )$-dense sequence

1:  Input:   $\mathit{x}=\mathsf{EncDen}\left(\mathit{u}\right)\in {\Sigma }_q^n$ 2:  Output:  $\mathit{u}\in {\Sigma }_q^{n-1}$ 3:  while $x_{[n-{\ell }^{\prime }-2,n]}={01}^{{\ell }^{\prime }}0$ for some ${\ell }^{\prime }\in [1,2t]$ do 4:       let $\tilde{\mathit{u}}$ be obtained from $g^{-1}\left(x_{[n-\delta +6t-{\ell }^{\prime }+1+\lceil {\log }_{q}n\rceil ,n-{\ell }^{\prime }-2]}\right)$ by deleting the last $2t-{\ell }^{\prime }$ symbols; delete the last $\delta +{\ell }^{\prime }-2t$ symbols of $\mathit{x}$ and insert $\tilde{\mathit{u}}$ at the position i of $\mathit{x}$ such that $i=x_{[n-\delta +6t-{\ell }^{\prime }+1,n-\delta +6t-{\ell }^{\prime }+\lceil \log n\rceil ]}$. 5:  end while 6:  if  $x_n=x_{n-1}=0$  then 7:       let $\tilde{\mathit{u}}$ be obtained from $g^{-1}\left(x_{[n-\delta +6t,n-\lceil {\log }_{q}n\rceil -3]}\right)$ by deleting the last $2t$ 0s and let $\mathit{u}=(x_{[1,n-\delta +2t-1]},\tilde{\mathit{u}})$. 8:  end if 9:  if  $x_n=1$  then 10:      let $\mathit{u}=x_{[1,n-1]}$. 11:  end if 12:  Return  $\mathit{u}=\mathsf{DecDen}\left(\mathit{x}\right)$.

The Algorithm 1 is obtained by modifying the Algorithm 2 of [19], which is for binary sequences but for our purpose we need apply it to q-ary sequences.

4. Burst-Deletion Correcting $\mathit{q}$-ary Codes

In this section, we still let

$$\delta =2t{q}^{2t}\lceil \log n\rceil .$$

Based on $(\mathit{p},\delta )$-dense sequences, for any fixed positive integers t and $q\ge 2$, we will construct a family of q-ary codes that can correct a burst of at most t deletions. The basic idea of our construction is as follows: For each $(\mathit{p},\delta )$-dense sequence $\mathit{x}$, use the sketches $a_0\left(\mathit{x}\right)$ and $a_1\left(\mathit{x}\right)$ (defined by (4) and (5), respectively) to locate the deletions within an interval of length $3\delta$. Then, use the functions ${\tilde{h}}_{\rho }^{\left(0\right)}\left(\mathit{x}\right),{\tilde{h}}_{\rho }^{\left(1\right)}\left(\mathit{x}\right)$ constructed in Construction 1 to uniquely recover $\mathit{x}$.

Let $h:{\Sigma }_q^m\to {\Sigma }_q^{R_m}$ be a sketch function for any positive integer m, where $R_m$ is a positive integer depending on $m,q$ and t, such that $h\left(\mathit{z}\right)\ne h\left({\mathit{z}}^{\prime }\right)$ for any distinct $\mathit{z},{\mathit{z}}^{\prime }\in {\Sigma }_q^m$ with ${\mathcal{B}}_{\le t}\left(\mathit{z}\right)\cap {\mathcal{B}}_{\le t}\left({\mathit{z}}^{\prime }\right)\ne Ø$. For each $\mathit{x}\in {\Sigma }_q^n$, let

$$\begin{array}{c}\hfill f\left(\mathit{x}\right)=\left(a_0\left(\mathit{x}\right)\left(\mathrm{mod}4\right),a_1\left(\mathit{x}\right)\left(\mathrm{mod}2n\right),{\tilde{h}}_{\rho }^{\left(0\right)}\left(\mathit{x}\right),{\tilde{h}}_{\rho }^{\left(1\right)}\left(\mathit{x}\right)\right)\end{array}$$

(18)

such that $a_0\left(\mathit{x}\right)$ is defined by (4), $a_1\left(\mathit{x}\right)$ is defined by (5), ${\tilde{h}}_{\rho }^{\left(0\right)}\left(\mathit{x}\right)$ and ${\tilde{h}}_{\rho }^{\left(1\right)}\left(\mathit{x}\right)$ are obtained by Construction 1 with $\rho =3\delta =6t{q}^{2t}\lceil \log n\rceil$.

Lemma 7.

Let f be the function given by (18). If $\mathit{x}\in {\Sigma }_q^n$ is $(\mathit{p},\delta )$-dense, then given $f\left(\mathit{x}\right)$ and any $\mathit{y}\in {\mathcal{B}}_{\le t}\left(\mathit{x}\right)$, one can uniquely recover $\mathit{x}$.

Proof. 

First, since $\mathit{x}$ is $(\mathit{p},\delta )$-dense, then by Lemma 4, given $a_0\left(\mathit{x}\right)\left(\mathrm{mod}4\right)$ and $a_1\left(\mathit{x}\right)\left(\mathrm{mod}2n\right)$, one can find an interval L of length $\left|L\right|\le 3\delta =\rho$, such that $\mathit{y}=x_{\left[n\right]\setminus D}$ for some interval $D\subseteq L$ of size $t^{\prime }=n-\left|\mathit{y}\right|$. Moreover, suppose ${\mathit{x}}^{\prime }\in {\Sigma }_q^n$, such that $\mathit{y}=x_{\left[n\right]\setminus D^{\prime }}^{\prime }$ for some interval $D^{\prime }\subseteq L$ of size $t^{\prime }=n-\left|\mathit{y}\right|$. Then, by Lemma 3, we have ${\tilde{h}}_{\rho }^{(\ell )}\left(\mathit{x}\right)\ne {\tilde{h}}_{\rho }^{(\ell )}\left({\mathit{x}}^{\prime }\right)$ for some $\ell \in \{0,1\}$. Thus, given $f\left(\mathit{x}\right)=(a_0\left(\mathit{x}\right)\left(\mathrm{mod}4\right),a_1\left(\mathit{x}\right)\left(\mathrm{mod}2n\right),{\tilde{h}}_{\rho }^{\left(0\right)}\left(\mathit{x}\right),{\tilde{h}}_{\rho }^{\left(1\right)}\left(\mathit{x}\right))$ and any $\mathit{y}\in {\mathcal{B}}_{\le t}\left(\mathit{x}\right)$, one can uniquely recover $\mathit{x}$. □

Using the function f, we can give an encoding function of a q-ary code that can correct a burst of at most t deletions.

Lemma 8.

Let f be the function given by (18) and $f_q\left(\mathit{x}\right)$ be the q-ary representation of $f\left(\mathit{x}\right)$. Let

$$\begin{array}{cc}\hfill \mathcal{E}:{\Sigma }_q^{n-1}& \to {\Sigma }_q^{n+r}\hfill \\ \hfill \mathit{u}& \mapsto \left(\mathit{x},0^{t}1,f_q\left(\mathit{x}\right)\right)\hfill \end{array}$$

(19)

such that $\mathit{x}=\mathsf{EncDen}\left(\mathit{u}\right)$ and $r=t+1+|f_q\left(\mathit{x}\right)|$. Then, for each $\mathit{z}=\mathcal{E}\left(\mathit{u}\right)$, given any $\mathit{y}\in {\mathcal{B}}_{\le t}\left(\mathit{z}\right)$, one can uniquely recover $\mathit{x}$ (and so $\mathit{z})$.

Proof. 

Let $t^{\prime }=\left|\mathit{z}\right|-\left|\mathit{y}\right|$. Suppose $D=[i_{\mathrm{d}},i_{\mathrm{d}}+t^{\prime }-1]\subseteq [1,n+r]$ is an interval such that $\mathit{y}=z_{[n+r]\setminus D}$. If there is more than one interval D such that $\mathit{y}=z_{[n+r]\setminus D}$, then we consider the D with the smallest $i_{\mathrm{d}}$. Clearly, we have $i_{\mathrm{d}}\in [1,n+r-t^{\prime }+1]$. If $i_{\mathrm{d}}\in [1,n+t+1-t^{\prime }]$, then $y_{n+t+1-t^{\prime }}=z_{n+t+1}=1$; if $i_{\mathrm{d}}\in [n+t+2-t^{\prime },n+r-t^{\prime }+1]$, then $y_{n+t+1-t^{\prime }}=z_{n+t+1-t^{\prime }}=0$. So, we have the following two cases.

Case 1: $y_{n+t+1-t^{\prime }}=1$. Then, $i_{\mathrm{d}}\in [1,n+t-t^{\prime }+1]$. We need further to consider the following three subcases.

Case 1.1: $y_{[n+1-t^{\prime },n+1+t-t^{\prime }]}=0^{t}1$. In this case, it must be that $D\subseteq [1,n]$. Therefore, we have $y_{[1,n-t^{\prime }]}\in {\mathcal{B}}_{t^{\prime }}\left(\mathit{x}\right)$ and $y_{[n+t+2-t^{\prime },n+r-t^{\prime }]}=f_q\left(\mathit{x}\right)$. By Lemma 7, $\mathit{x}$ can be recovered from $y_{[1,n-t^{\prime }]}$ and $y_{[n+t+2-t^{\prime },n+r-t^{\prime }]}$ correctly.

Case 1.2: There is a $t^{\prime \prime }\in [1,t^{\prime }-1]$ such that $y_{[n+1-t^{\prime }+t^{\prime \prime },n+1+t-t^{\prime }]}=0^{t-t^{\prime \prime }}1$ and $y_{n-t+t^{\prime \prime }}\ne 0$. In this case, it must be that $D=[n+1-t^{\prime }+t^{\prime \prime },n+t^{\prime \prime }]$. Therefore, $y_{[1,n+1-t^{\prime }+t^{\prime \prime }]}=x_{[1,n+1-t^{\prime }+t^{\prime \prime }]}\in {\mathcal{B}}_{t^{\prime }-t^{\prime \prime }}\left(\mathit{x}\right)$ and $y_{[n+t+2-t^{\prime },n+r-t^{\prime }]}=f_q\left(\mathit{x}\right)$. By Lemma 7, $\mathit{x}$ can be recovered from $y_{[1,n+1-t^{\prime }+t^{\prime \prime }]}$ and $y_{[n+t+2-t^{\prime },n+r-t^{\prime }]}$ correctly.

Case 1.3: $y_{[n+1,n+1+t-t^{\prime }]}=0^{t-t^{\prime }}1$ and $y_n\ne 0$. In this case, it must be that $D\subseteq [n+1,n+t]$. Therefore, $y_{[1,n]}=\mathit{x}$.

Case 2: $y_{n+t+1-t^{\prime }}=0$. Then, we have $i_{\mathrm{d}}\in [n+t+2-t^{\prime },n+r-t^{\prime }+1]$ and $\mathit{x}=y_{[1,n]}$.

Thus, one can always uniquely recover $\mathit{x}$ from $\mathit{y}$. □

Theorem 1.

There exists a q-ary code of length n capable of correcting a burst of at most t deletions, which has redundancy $\log n+8\log \log n+o\left(\log \log n\right)$ bits, encoding complexity $O\left(q^{7t}n{\left(\log n\right)}^3\right)$ and decoding complexity $O\left(n\log n\right)$.

Proof. 

In Construction 1, let h be the function $h_{\mathrm{syn}}$ given by Lemma 2 and let ${\mathcal{C}}_{\mathrm{syn}}$ be the code with the encoding function $\mathcal{E}$ constructed in Lemma 8. Then, ${\mathcal{C}}_{\mathrm{syn}}\subseteq {\Sigma }_q^n$ is a code capable of correcting a burst of at most t deletions.

The redundancy of ${\mathcal{C}}_{\mathrm{syn}}$ is $1+r=1+t+1+|f_q\left(\mathit{x}\right)|=t+2+|f_q\left(\mathit{x}\right)|$ in q-ary symbols. We now evaluate $|f_q\left(\mathit{x}\right)|$. By Lemma 2, we have $R_{2\rho }=4{\log }_q\left(2\rho \right)+o\left({\log }_q\left(2\rho \right)\right)$. Moreover, since $\rho =6t{q}^{2t}\lceil \log n\rceil$, then for $\ell \in \{0,1\}$, by (3) and Remark 2, the length $|{\tilde{h}}_{\rho }^{(\ell )}\left(\mathit{x}\right)|$ of ${\tilde{h}}_{\rho }^{(\ell )}\left(\mathit{x}\right)$ (as a q-ary string) satisfies

$$\begin{array}{cc}\hfill |{\tilde{h}}_{\rho }^{(\ell )}\left(\mathit{x}\right)|& <R_{2\rho }\hfill \\ & =4{\log }_q\left(12t{q}^{2t}\lceil \log n\rceil \right)+o\left({\log }_q\left(12t{q}^{2t}\lceil \log n\rceil \right)\right)\hfill \\ & =4{\log }_q\log n+o\left({\log }_q\log n\right).\hfill \end{array}$$

So, by (4) and (5), the length $|f_q\left(\mathit{x}\right)|$ of $f_q\left(\mathit{x}\right)$ (as a q-ary string) satisfies

$$\begin{array}{cc}\hfill |f_q\left(\mathit{x}\right)|& ={\log }_{q}4+{\log }_q\left(2n\right)+|{\tilde{h}}_{\rho }^{\left(0\right)}\left(\mathit{x}\right)|+|{\tilde{h}}_{\rho }^{\left(1\right)}\left(\mathit{x}\right)|\hfill \\ & \le {\log }_{q}n+8{\log }_q\log n+o\left({\log }_q\log n\right).\hfill \end{array}$$

Thus, the redundancy of ${\mathcal{C}}_{\mathrm{syn}}$, measured in bits, is $(t+2+|f_q\left(\mathit{x}\right)\left|\right)\log q\le \log n+8\log \log n+o\left(\log \log n\right)$.

Consider the encoding complexity of ${\mathcal{C}}_{\mathrm{syn}}$. Note that, by (3) and Remark 2, ${\tilde{h}}_{\rho }^{\left(0\right)}\left(\mathit{x}\right)$ and ${\tilde{h}}_{\rho }^{\left(1\right)}\left(\mathit{x}\right)$ are computable in time $O\left(n{q}^t{\left(2\rho \right)}^3\right)=O\left(n{q}^t{\left(12t{q}^{2t}\lceil \log n\rceil \right)}^3\right)=O\left(q^{7t}n{\left(\log n\right)}^3\right)$. Then, by (4), (5), and (18), $f\left(\mathit{x}\right)$ is computable in time $O\left(q^{7t}n{\left(\log n\right)}^3\right)$. Moreover, by Lemma 6, the mapping $\mathsf{EncDen}$ is computable in $O\left(n\log n\right)$ time, so by (19), the encoding complexity of ${\mathcal{C}}_{\mathrm{syn}}$ is $O\left(q^{7t}n{\left(\log n\right)}^3\right)$.

For the decoding complexity of ${\mathcal{C}}_{\mathrm{syn}}$, by Lemma 6, the inverse of $\mathsf{EncDen}$ is computable in $O\left(n\log n\right)$ time, so by the proof of Lemma 8, we only need to consider the complexity of recovering $\mathit{x}$ from $f\left(\mathit{x}\right)$ and any given $\mathit{y}\in {\mathcal{B}}_{\le t}\left(\mathit{x}\right)$. By Lemma 4 and 1) of Remark 1, one can locate the deletions within an interval $L_{j_0}$ in time $O\left(n\right)$ using $a_0\left(\mathit{x}\right)\left(\mathrm{mod}4\right)$ and $a_1\left(\mathit{x}\right)\left(\mathrm{mod}2n\right)$. Then, $\mathit{x}$ can be recovered by brute force searching in time $O\left(\left(2\rho q^t\right)\left(q^t{\left(2\rho \right)}^3\right)\right)=O\left(q^{8t}{\left(\log n\right)}^4\right)$. In fact, there are $|L_{j_0}|·q^t$ candidate sequences for $\mathit{x}$, and for each candidate sequence ${\mathit{x}}^{\prime }$, we need to verify whether $h_{\mathrm{syn}}\left(x_{L_{j_0}}^{\prime }\right)=h_{\mathrm{syn}}\left(x_{L_{j_0}}\right)$, which takes time $O\left(q^t\right|L_{j_0}{|}^3)$ by Lemma 2. Hence, the time of brute force searching is

$$O\left(\left(\right|L_{j_0}|·q^t\left)\right(q^t|L_{j_0}{|}^3)\right)\le O\left(\left(2\rho q^t\right)\left(q^t{\left(2\rho \right)}^3\right)\right),$$

where the inequality holds because $\left|L_{j_0}\right|\le 2\rho$. Thus, the decoding complexity of ${\mathcal{C}}_{\mathrm{syn}}$ is $O\left(n\log n\right)$. □

5. Correcting Burst-Deletion with Two Reads

In this section, we construct a family of codes correcting a burst of at most t deletions with 2 reads. Our construction improves the construction in [31] in redundancy. We first recall the concept of period of a sequence.

Suppose $T\le m$ are two positive integers and $\mathit{x}\in {\Sigma }_q^m$. We say that T is a period of $\mathit{x}$ if $x_i=x_{i+T}$ for any $i\in [1,m-T]$.

The following two simple observations are easy to see and will be used in our construction.

Observation 1: Let $\mathit{x},{\mathit{x}}^{\prime }\in {\Sigma }_q^n$ and $t^{\prime }\in \left[t\right]$. Suppose $D=[i_{\mathrm{d}},i_{\mathrm{d}}+t^{\prime }-1],D^{\prime }=[i_{\mathrm{d}}^{\prime },i_{\mathrm{d}}^{\prime }+t^{\prime }-1]\subseteq \left[n\right]$ such that $i_{\mathrm{d}}\le i_{\mathrm{d}}^{\prime }$. Then, $x_{\left[n\right]\setminus D}=x_{\left[n\right]\setminus D^{\prime }}^{\prime }$ if and only if the following holds:

$$\begin{array}{c}\hfill x_i^{\prime }=\left\{\begin{array}{c}{x}_i,\mathrm{for}i\in [1,i_{\mathrm{d}}-1],\hfill \\ x_{i+t^{\prime }},\mathrm{for}i\in [i_{\mathrm{d}},i_{\mathrm{d}}^{\prime }-1],\hfill \\ x_i,\mathrm{for}i\in [i_{\mathrm{d}}^{\prime }+t^{\prime },n].\hfill \end{array}\right.\end{array}$$

Observation 2: Let $\mathit{x}\in {\Sigma }_q^n$ and $t^{\prime }\in \left[t\right]$. Suppose $J\subseteq \left[n\right]$ is an interval such that $\left|J\right|\ge t^{\prime }$ and the substring $x_J$ of $\mathit{x}$ has period $t^{\prime }$. Then, for any $D=[i_{\mathrm{d}},i_{\mathrm{d}}+t^{\prime }-1]\subseteq J$ and $D^{\prime }=[i_{\mathrm{d}}^{\prime },i_{\mathrm{d}}^{\prime }+t^{\prime }-1]\subseteq J$, we have $x_{\left[n\right]\setminus D}=x_{\left[n\right]\setminus D^{\prime }}$.

Our construction will use $(\mathit{p},\delta )$-dense sequences for $\mathit{p}=0^{t+1}{1}^{t+1}$. To apply Lemma 6 to construct $(\mathit{p},\delta )$-dense sequences, we need to let $\delta =2(t+1)q^{2(t+1)}\lceil \log n\rceil$. Then, by Lemma 6, there exists an invertible function $\mathsf{EncDen}:{\Sigma }_q^{n-1}\to {\Sigma }_q^n$, such that $\mathit{x}=\mathsf{EncDen}\left(\mathit{u}\right)$ is $(\mathit{p},\delta )$-dense for every $\mathit{u}\in {\Sigma }_q^{n-1}$. Moreover, both $\mathsf{EncDen}$ and its inverse $\mathsf{DecDen}$ are computable in $O\left(n\log n\right)$ time. Thus, in this section, we always assume that

$$\mathit{p}=0^{t+1}{1}^{t+1}\mathrm{and}\delta =2(t+1)q^{2(t+1)}\lceil \log n\rceil .$$

Suppose $\mathit{x}\in {\Sigma }_q^n$ is $(\mathit{p},\delta )$-dense and $J\subseteq \left[n\right]$ is an interval of length $\left|J\right|\ge \delta$. By Definition 1, there exists an $i_0\in J$ such that $J_0\triangleq [i_0,i_0+2(t+1)-1]\subseteq J$ and $x_{J_0}=\mathit{p}=0^{t+1}{1}^{t+1}$. For any positive integer $T\le 2t$, let $i_0^{\prime }=i_0+t+1-T$ if $T\le t$, and let $i_0^{\prime }=i_0$ if $T\ge t+1$. Then, $[i_0^{\prime },i_0^{\prime }+T]\subseteq J_0\subseteq J$ and $x_{i_0^{\prime }}=0\ne 1=x_{i_0^{\prime }+T}$. Thus, T is not a period of $x_J$. In other words, we have the following remark.

Remark 4.

Suppose $\mathit{x}\in {\Sigma }_q^n$ is $(\mathit{p},\delta )$-dense, where $\mathit{p}=0^{t+1}{1}^{t+1}$ and $\delta =2(t+1)q^{2(t+1)}\lceil \log n\rceil$. Then, the length of any substring of $\mathit{x}$ of period $T\le 2t$ is at most δ.

Lemma 9.

Suppose $\mathit{x}\ne {\mathit{x}}^{\prime }\in {\Sigma }_q^n$ are both $(\mathit{p},\delta )$-dense. If $|{\mathcal{B}}_{\le t}\left(\mathit{x}\right)\cap {\mathcal{B}}_{\le t}\left({\mathit{x}}^{\prime }\right)|\ge 2$, then there exists an interval $J\subseteq \left[n\right]$ of length $\left|J\right|\le \delta +t$ and two intervals $D,D^{\prime }\subseteq J$ of size $\left|D\right|=\left|D^{\prime }\right|\le t$, such that $x_{\left[n\right]\setminus D}=x_{\left[n\right]\setminus D^{\prime }}^{\prime }$.

Proof. 

Suppose $\mathit{y},{\mathit{y}}^{\prime }\in {\mathcal{B}}_{\le t}\left(\mathit{x}\right)\cap {\mathcal{B}}_{\le t}\left({\mathit{x}}^{\prime }\right)$ and $\mathit{y}\ne {\mathit{y}}^{\prime }$. Then, $\mathit{y}=x_{\left[n\right]\setminus D_1}=x_{\left[n\right]\setminus D_1^{\prime }}^{\prime }$ for some intervals $D_1,D_1^{\prime }\subseteq \left[n\right]$ of size $t_1\triangleq \left|D_1\right|=\left|D_1^{\prime }\right|\le t$, and ${\mathit{y}}^{\prime }=x_{\left[n\right]\setminus D_2}=x_{\left[n\right]\setminus D_2^{\prime }}^{\prime }$ for some intervals $D_2,D_2^{\prime }\subseteq \left[n\right]$ of size $t_2\triangleq \left|D_2\right|=\left|D_2^{\prime }\right|\le t$. For convenience in the discussions, we denote

$$D_j=[i_j,i_j+t_j-1]\mathrm{and}{D}_j^{\prime }=[i_j^{\prime },i_j^{\prime }+t_j-1],j=1,2.$$

If $|i_j-i_j^{\prime }|\le \delta$ for some $j\in \{1,2\}$, then let $D=D_j$, $D^{\prime }=D_j^{\prime }$ and $J=[\lambda ,{\lambda }^{\prime }+t_j-1]$ such that $\lambda =min\{i_j,i_j^{\prime }\}$ and ${\lambda }^{\prime }=max\{i_j,i_j^{\prime }\}$. Clearly, J, D, and $D^{\prime }$ satisfy the desired conditions. So, in the following, we assume that $|i_j-i_j^{\prime }|>\delta$ for each $j\in \{1,2\}$.

By the symmetry of $\mathit{x}$ and ${\mathit{x}}^{\prime }(\mathit{y}$ and ${\mathit{y}}^{\prime })$, we can assume

$$i_1<i_1^{\prime }\mathrm{and}{t}_2\le t_1.$$

Since $\mathit{y}=x_{\left[n\right]\setminus D_1}=x_{\left[n\right]\setminus D_1^{\prime }}^{\prime }$, where $D_1=[i_1,i_1+t_1-1]$, $D_1^{\prime }=[i_1^{\prime },i_1^{\prime }+t_1-1]$ and $i_1<i_1^{\prime }$, we can obtain from Observation 1 that

$$\begin{array}{c}\hfill x_i^{\prime }=\left\{\begin{array}{c}{y}_i=x_i,\mathrm{for}i\in [1,i_1-1],\hfill \\ y_i=x_{i+t_1},\mathrm{for}i\in [i_1,i_1^{\prime }-1],\hfill \\ y_{i-t_1}=x_i,\mathrm{for}i\in [i_1^{\prime }+t_1,n].\hfill \end{array}\right.\end{array}$$

(20)

Similarly, since ${\mathit{y}}^{\prime }=x_{\left[n\right]\setminus D_2}=x_{\left[n\right]\setminus D_2^{\prime }}^{\prime }$, where $D_2=[i_2,i_2+t_2-1]$ and $D_2^{\prime }=[i_2^{\prime },i_2^{\prime }+t_2-1]$, we have

• If $i_2<i_2^{\prime }$, then according to Observation 1,

  $$\begin{array}{c}\hfill x_i^{\prime }=\left\{\begin{array}{c}{y}_i^{\prime }=x_i,\mathrm{for}i\in [1,i_2-1],\hfill \\ y_i^{\prime }=x_{i+t_2},\mathrm{for}i\in [i_2,i_2^{\prime }-1],\hfill \\ y_{i-t_2}^{\prime }=x_i,\mathrm{for}i\in [i_2^{\prime }+t_2,n].\hfill \end{array}\right.\end{array}$$

  (21)
• If $i_2>i_2^{\prime }$, then according to Observation 1,

  $$\begin{array}{c}\hfill x_i^{\prime }=\left\{\begin{array}{c}{y}_i^{\prime }=x_i,\mathrm{for}i\in [1,i_2^{\prime }-1],\hfill \\ y_{i-t_2}^{\prime }=x_{i-t_2},\mathrm{for}i\in [i_2^{\prime }+t_2,i_2+t_2-1],\hfill \\ y_i^{\prime }=x_i,\mathrm{for}i\in [i_2+t_2,n].\hfill \end{array}\right.\end{array}$$

  (22)

Let

$$I_1=[i_1,i_1^{\prime }+t_1-1]\mathrm{and}{I}_2=[{\overline{i}}_2,{\overline{i}}_2^{\prime }+t_2-1],$$

where ${\overline{i}}_2=min\{i_2,i_2^{\prime }\}$ and ${\overline{i}}_2^{\prime }=max\{i_2,i_2^{\prime }\}$. Then, by (20), (21), and (22), we can easily obtain the following claim.

Claim 1: For all $i\in \left[n\right]\setminus (I_1\cap I_2)$, we have $x_i=x_i^{\prime }$.

Since $\mathit{x}\ne {\mathit{x}}^{\prime }$, by Claim 1, we have $I_1\cap I_2\ne Ø$. If $|I_1\cap I_2|\le t$ then, clearly, $J=D=D^{\prime }=I_1\cap I_2$ satisfies the desired conditions. So, in the following, we only need to consider $|I_1\cap I_2|>t$. We have the following two cases.

Case 1: $i_2<i_2^{\prime }$. Then, $min\{i_2,i_2^{\prime }\}=i_2$ and $max\{i_2,i_2^{\prime }\}=i_2^{\prime }$, and so $I_2=[i_2,i_2^{\prime }+t_2-1]$ and $I_1\cap I_2=[\lambda ,{\lambda }^{\prime }]$, where $\lambda =max\{i_1,i_2\}$ and ${\lambda }^{\prime }=min\{i_1^{\prime }+t_1-1,i_2^{\prime }+t_2-1\}$. We need to further divide this case into the following two subcases.

Case 1.1: $t_2<t_1$. Let $D=[\lambda ,\lambda +t_2-1]$ and $D^{\prime }=[{\lambda }^{\prime }-t_2+1,{\lambda }^{\prime }]$. Then, $D,D^{\prime }\subseteq J$ and $|D|=|D^{\prime }|\le t$. Note that by Claim 1, $x_i^{\prime }=x_i$ for every $i\in \left[n\right]\setminus (I_1\cap I_2)=\left[n\right]\setminus [\lambda ,{\lambda }^{\prime }]$, and by (20), $x_i^{\prime }=x_{i+t_2}$ for every $i\in [\lambda ,{\lambda }^{\prime }-t_2]$. So, according to Observation 1, we can obtain

$$x_{\left[n\right]\setminus D}=x_{\left[n\right]\setminus D^{\prime }}^{\prime }.$$

Moreover, by (20) and (21), $x_i=x_{i-t_2}^{\prime }=x_{i-t_2+t_1}$ for every $i\in [\lambda +t_2,{\lambda }^{\prime }-t_1+t_2]$. So, $x_{[\lambda +t_2,{\lambda }^{\prime }]}$ has period $t_1-t_2$, and by Remark 4, $\left|\right[\lambda +t_2,{\lambda }^{\prime }\left]\right|\le \delta$. Hence, we have

$$\left|J\right|=|I_1\cap I_2|=\left|\right[\lambda ,{\lambda }^{\prime }\left]\right|\le \delta +t_2\le \delta +t.$$

Case 1.2: $t_2=t_1$. We will prove that this case is impossible by contradiction. Without loss of generality, assume $i_1\le i_2$. Since $|I_1\cap I_2|>t$, then $I_1\cap I_2=[i_2,{\tilde{i}}_1^{\prime }]$ and $i_2\le {\tilde{i}}_1^{\prime }-t$, where ${\tilde{i}}_1^{\prime }=min\{i_1^{\prime },i_2^{\prime }\}$. By (20) and (21), we have

$$x_i=x_i^{\prime }=x_{i+t_1}$$

for every $i\in [i_1,i_2-1]$, i.e., $x_{[i_1,i_2+t_1-1]}$ has period $t_1$. So, we can obtain $\mathit{y}=x_{\left[n\right]\setminus [i_1,i_1+t_1-1]}=x_{\left[n\right]\setminus [i_2,i_2+t_1-1]}={\mathit{y}}^{\prime }$ (according to Observation 2), which contradicts to the assumption that $\mathit{y}\ne {\mathit{y}}^{\prime }$.

Case 2: $i_2>i_2^{\prime }$. In this case, $I_2=[i_2^{\prime },i_2+t_2-1]$ and we have $I_1\cap I_2=[\lambda ,{\lambda }^{\prime }]$, where $\lambda =max\{i_1,i_2^{\prime }\}$ and ${\lambda }^{\prime }=min\{i_1^{\prime }+t_1-1,i_2+t_2-1\}$. Let $D=[\lambda ,\lambda +t_1-1]$ and $D^{\prime }=[{\lambda }^{\prime }-t_1+1,{\lambda }^{\prime }]$. Then, $D,D^{\prime }\subseteq J$ and $\left|D\right|=\left|D^{\prime }\right|\le t$. Note that by Claim 1, $x_i^{\prime }=x_i$ for every $i\in \left[n\right]\setminus (I_1\cap I_2)=\left[n\right]\setminus [\lambda ,{\lambda }^{\prime }]$, and by (20), $x_i^{\prime }=x_{i+t_1}$ for every $i\in [\lambda ,{\lambda }^{\prime }-t_1]$. So, according to Observation 1, we can obtain

$$x_{\left[n\right]\setminus D}=x_{\left[n\right]\setminus D^{\prime }}^{\prime }.$$

Moreover, by (20) and (22), we can obtain

$$x_i=x_{i+t_2}^{\prime }=x_{i+t_2+t_1}$$

for every $i\in [\lambda ,{\lambda }^{\prime }-t_1-t_2]$. Hence, $x_{[\lambda ,{\lambda }^{\prime }]}$ is a substring of $\mathit{x}$ of period $t_1+t_2$. By Remark 4, $\left|\right[\lambda ,{\lambda }^{\prime }\left]\right|\le \delta$, so $\left|J\right|=|I_1\cap I_2|=\left|\right[\lambda ,{\lambda }^{\prime }\left]\right|\le \delta \le \delta +t$. □

For $n=30$, we give three examples of $\mathit{y}$ and ${\mathit{y}}^{\prime }$, satisfying conditions of the different cases in the proof of Lemma 9.

Example 1.

Suppose $\mathit{y}=x_{\left[n\right]\setminus D_1}=x_{\left[n\right]\setminus D_1^{\prime }}^{\prime }$ and ${\mathit{y}}^{\prime }=x_{\left[n\right]\setminus D_2}=x_{\left[n\right]\setminus D_2^{\prime }}^{\prime }$, where $D_1=\{4,5,6,7\}$, $D_1^{\prime }=\{27,28,29,30\}$, $D_2=\{1,2\}$ and $D_2^{\prime }=\{23,24\}$. Here, we have $i_1=4,i_1^{\prime }=27$ and $t_1=4$; $i_2=1,i_2^{\prime }=23$ and $t_2=2$. Then, conditions of Case 1.1 are satisfied, and $J=I_1\cap I_2=[4,24]$. Figure 1a is an illustration of this case. We can easily find that $x_i^{\prime }=x_{i+2}$ for every $i\in [4,22]$ and $x_i^{\prime }=x_i$ for every $i\in \left[n\right]\setminus J$. So, by Observation 1, $x_{\left[n\right]\setminus \{4,5\}}=x_{\left[n\right]\setminus \{23,24\}}^{\prime }$. Moreover, $x_i=x_{i-2}^{\prime }=x_{i+2}$ for every $i\in [6,22]$, so the substring $x_{[6,24]}$ of $\mathit{x}$ has period 2.

Example 2.

Suppose $\mathit{y}=x_{\left[n\right]\setminus D_1}=x_{\left[n\right]\setminus D_1^{\prime }}^{\prime }$ and ${\mathit{y}}^{\prime }=x_{\left[n\right]\setminus D_2}=x_{\left[n\right]\setminus D_2^{\prime }}^{\prime }$, where $D_1=\{1,2,3,4\}$, $D_1^{\prime }=\{17,18,19,20\}$, $D_2=\{9,10,11,12\}$ and $D_2^{\prime }=\{27,28,29,30\}$. Here, we have $i_1=1,i_1^{\prime }=17$, $i_2=9,i_2^{\prime }=27$ and $t_1=t_2=4$. Then, conditions of Case 1.2 are satisfied. Figure 1b is an illustration of this case. We can find that $x_i=x_i^{\prime }=x_{i+4}$ for every $i\in [1,8]$, i.e., $x_{[1,12]}$ has period 4. So, by Observation 2, we have $\mathit{y}=x_{\left[n\right]\setminus D_1}=x_{\left[n\right]\setminus D_2}={\mathit{y}}^{\prime }$.

Example 3.

Suppose $\mathit{y}=x_{\left[n\right]\setminus D_1}=x_{\left[n\right]\setminus D_1^{\prime }}^{\prime }$ and ${\mathit{y}}^{\prime }=x_{\left[n\right]\setminus D_2}=x_{\left[n\right]\setminus D_2^{\prime }}^{\prime }$, where $D_1=\{7,8,9,10\}$, $D_1^{\prime }=\{27,28,29,30\}$, $D_2=\{24,25,26\}$ and $D_2^{\prime }=\{1,2,3\}$. Here, we have $i_1=7,i_1^{\prime }=27$ and $t_1=4$; $i_2=24,i_2^{\prime }=1$ and $t_2=3$. Then, conditions of Case 2 are satisfied and $J=I_1\cap I_2=[7,26]$. Figure 1c is an illustration of this case. We can easily find that $x_i^{\prime }=x_{i+4}$ for every $i\in [7,22]$, and $x_i^{\prime }=x_i$ for every $i\in \left[n\right]\setminus J$. So by Observation 1, $x_{\left[n\right]\setminus \{7,8,9,10\}}=x_{\left[n\right]\setminus \{23,24,25,26\}}^{\prime }$. Moreover, $x_i=x_{i+3}^{\prime }=x_{i+7}$ for every $i\in [7,19]$, i.e., $x_{[7,26]}$ has period 7.

In the following, we give a construction of q-ary codes for correcting a burst of at most t deletions with two reads. Let

$$\rho =\delta +t=2(t+1)q^{2(t+1)}\lceil \log n\rceil +t$$

and ${\mathcal{L}}_{\rho }=\{L_j:j=1,2,\cdots ,⌈n/\rho ⌉-1\}$ be defined by (2). For each $\ell \in \{0,1\}$, let the function ${\tilde{h}}_{\rho }^{(\ell )}$ be obtained from Construction 1 by letting h be the function $h_{\mathrm{syn}}$ given by Lemma 2. Then, let

$$\begin{array}{c}\hfill \tilde{f}\left(\mathit{x}\right)=\left({\tilde{h}}_{\rho }^{\left(0\right)}\left(\mathit{x}\right),{\tilde{h}}_{\rho }^{\left(1\right)}\left(\mathit{x}\right)\right).\end{array}$$

(23)

Lemma 10.

For each $\mathit{x}\in {\Sigma }_q^n$, the function $\tilde{f}\left(\mathit{x}\right)$ is computable in time $O\left(q^{7t}n{\left(\log n\right)}^3\right)$, and when viewed as a binary string, the length $|\tilde{f}\left(\mathit{x}\right)|$ of $\tilde{f}\left(\mathit{x}\right)$ satisfies

$$|\tilde{f}\left(\mathit{x}\right)|\le 8\log \log n+o\left(\log \log n\right).$$

Moreover, if $\mathit{x}$ is $(\mathit{p},\delta )$-dense, then given $\tilde{f}\left(\mathit{x}\right)$ and any two distinct $\mathit{y},{\mathit{y}}^{\prime }\in {\mathcal{B}}_{\le t}\left(\mathit{x}\right)$, one can uniquely recover $\mathit{x}$.

Proof. 

Note that $\left|L_j\right|\le 2\rho =4(t+1)q^{2(t+1)}\lceil \log n\rceil +2t$ for each j. Then, by (3) and by Remark 2, the functions ${\tilde{h}}_{\rho }^{\left(0\right)}\left(\mathit{x}\right)$ and ${\tilde{h}}_{\rho }^{\left(1\right)}\left(\mathit{x}\right)$ are computable in time

$$O\left(n{q}^t{\left(2\rho \right)}^3\right)=O\left(q^{7t}n{\left(\log n\right)}^3\right).$$

Hence, by (23), $\tilde{f}\left(\mathit{x}\right)$ is computable in time $O\left(q^{7t}n{\left(\log n\right)}^3\right)$.

Again by (3) and by Remark 2, the length of $\tilde{f}\left(\mathit{x}\right)$ (viewed as a binary string) satisfies

$$\begin{array}{cc}\hfill |\tilde{f}\left(\mathit{x}\right)|& = |{\tilde{h}}_{\rho }^{\left(0\right)}\left(\mathit{x}\right)|+|{\tilde{h}}_{\rho }^{\left(1\right)}\left(\mathit{x}\right)|\hfill \\ & =2\log q^{R_{2\rho }}\hfill \\ & =2\log q^{4{\log }_q\left(2\rho \right)+o\left({\log }_q\left(2\rho \right)\right)}\hfill \\ & =8\log \log n+o\left(\log \log n\right),\hfill \end{array}$$

where the last equality comes from the assumption that $\rho =\delta +t=2(t+1)q^{2(t+1)}\lceil \log n\rceil +t$.

Finally, we prove that if $\mathit{x}\in {\Sigma }_q^n$ is $(\mathit{p},\delta )$-dense, then given $\tilde{f}\left(\mathit{x}\right)$ and any two distinct $\mathit{y},{\mathit{y}}^{\prime }\in {\mathcal{B}}_{\le t}\left(\mathit{x}\right)$, one can uniquely recover $\mathit{x}$. It suffices to prove that for any $(\mathit{p},\delta )$-dense $\mathit{x},{\mathit{x}}^{\prime }\in {\Sigma }_q^n$, if $\left|{\mathcal{B}}_{\le t}\right(\mathit{x})\cap {\mathcal{B}}_{\le t}({\mathit{x}}^{\prime }\left)\right|\ge 2$, then $\tilde{f}\left(\mathit{x}\right)\ne \tilde{f}\left({\mathit{x}}^{\prime }\right)$. This can be proved as follows. By Lemma 9, there exists an interval $J\subseteq \left[n\right]$ of length $\left|J\right|\le \delta +t=\rho$ and two intervals $D,D^{\prime }\subseteq J$ of size $\left|D\right|=|D^{\prime }|\le t$, such that $x_{\left[n\right]\setminus D}=x_{\left[n\right]\setminus D^{\prime }}^{\prime }$. Then, by Lemma 3, we have ${\tilde{h}}_{\rho }^{(\ell )}\left(\mathit{x}\right)\ne {\tilde{h}}_{\rho }^{(\ell )}\left({\mathit{x}}^{\prime }\right)$ for some $\ell \in \{0,1\}$. Therefore, by (23), we have $\tilde{f}\left(\mathit{x}\right)\ne \tilde{f}\left({\mathit{x}}^{\prime }\right)$. □

Theorem 2.

Let ${\tilde{\mathcal{C}}}_{\mathrm{syn}}$ be the code with the encoding function

$$\begin{array}{cc}\hfill \tilde{\mathcal{E}}:{\Sigma }_q^{n-1}& \to {\Sigma }_q^{n+r}\hfill \\ \hfill \mathit{u}& \mapsto \left(\mathit{x},\mathit{w}\right)\hfill \end{array}$$

(24)

where $\mathit{x}=\mathsf{EncDen}\left(\mathit{u}\right)$, $\mathit{w}=\left(0^{t}1,x_{[n-t+1,n]},{\tilde{f}}_q\left(\mathit{x}\right)\right)$, and $r=\left|\mathit{w}\right|=2t + 1 + |{\tilde{f}}_q\left(\mathit{x}\right)|$. Then, ${\tilde{\mathcal{C}}}_{\mathrm{syn}}$ is an $(n,2,{\mathcal{B}}_{\le t})$-reconstruction code with redundancy $8\log \log n+o\left(\log \log n\right)$ bits, encoding complexity $O\left(q^{7t}n{\left(\log n\right)}^3\right)$ and decoding complexity $O\left(q^{9t}{\left(n\log n\right)}^3\right)$.

Proof. 

We first prove that ${\tilde{\mathcal{C}}}_{\mathrm{syn}}$ is an $(n,2,{\mathcal{B}}_{\le t})$-reconstruction code. We need to prove that for each codeword $\mathit{z}=\tilde{\mathcal{E}}\left(\mathit{u}\right)=\left(\mathit{x},0^{t}1,x_{[n-t+1,n]},{\tilde{f}}_q\left(\mathit{x}\right)\right)\in {\tilde{\mathcal{C}}}_{\mathrm{syn}}$, given any distinct $\mathit{y},{\mathit{y}}^{\prime }\in {\mathcal{B}}_{\le t}\left(\mathit{z}\right)$, one can uniquely recover $\mathit{x}$.

Let $\mathit{y}=z_{[n+r]\setminus D}$, where $D\subseteq [n+r]$ is an interval of size $t^{\prime }=\left|D\right|=\left|\mathit{z}\right|-\left|\mathit{y}\right|$. By the same discussions as in the proof of Lemma 8, exactly one of the following three cases holds:

Case 1: $D\subseteq [n+1,n+r]$. In this case, we have $\mathit{x}=y_{[1,n]}$.

Case 2: There exists a $t^{\prime \prime }\in [t^{\prime }-1]$ such that $D\subseteq [n-t^{\prime }+t^{\prime \prime }+1,n+t^{\prime \prime }]$. In this case, $y_{[1,n+1-t^{\prime }+t^{\prime \prime }]}=x_{[1,n+1-t^{\prime }+t^{\prime \prime }]}$ and $y_{[n+t+2-t^{\prime },n+2t+1-t^{\prime }]}=z_{[n+t+2,n+2t+1]}=x_{[n-t+1,n]}$. So, $\mathit{x}=(y_{[1,n+1-t]},y_{[n+t+2-t^{\prime },n+2t+1-t^{\prime }]})$.

Case 3: $D\subseteq \left[n\right]$. In this case, we have $y_{[n-t^{\prime }]}\in {\mathcal{B}}_{\le t}\left(\mathit{x}\right)$ and $y_{[n+2t+1-t^{\prime },n+r-t^{\prime }]}={\tilde{f}}_q\left(\mathit{x}\right)$.

Similarly, for ${\mathit{y}}^{\prime }\in {\mathcal{B}}_{\le t}\left(\mathit{z}\right)$, either $\mathit{x}$ can be recovered from ${\mathit{y}}^{\prime }$ or ${\mathit{y}}^{\prime }=z_{[n+r]\setminus D^{\prime }}$ for some interval $D^{\prime }\subseteq \left[n\right]$ of size $\left|D^{\prime }\right|=\left|\mathit{z}\right|-\left|{\mathit{y}}^{\prime }\right|\le t$. Suppose $\mathit{y}=z_{[n+r]\setminus D}$ and ${\mathit{y}}^{\prime }=z_{[n+r]\setminus D^{\prime }}$ for some intervals $D,D^{\prime }\subseteq \left[n\right]$. Then, $y_{[n-|D\left|\right]},y_{[n-|D^{\prime }\left|\right]}^{\prime }\in {\mathcal{B}}_{\le t}\left(\mathit{x}\right)$ and $y_{[n+2t+1-|D^{\prime }|,n+r-|D^{\prime }\left|\right]}^{\prime }={\tilde{f}}_q\left(\mathit{x}\right)$. Moreover, we must have $y_{[n-|D\left|\right]}\ne y_{[n-|D^{\prime }\left|\right]}^{\prime }$, because otherwise, from (24), we will obtain $\mathit{y}=(y_{[n-|D\left|\right]},\mathit{w})=(y_{[n-|D^{\prime }\left|\right]}^{\prime },\mathit{w})={\mathit{y}}^{\prime }$, which contradicts to the assumption that $\mathit{y}\ne {\mathit{y}}^{\prime }$. By Lemma 10, $\mathit{x}$ can be uniquely recovered from $\mathit{y}$ and ${\mathit{y}}^{\prime }$.

Thus, we proved that, given any distinct $\mathit{y},{\mathit{y}}^{\prime }\in {\mathcal{B}}_{\le t}\left(\mathit{z}\right)$, one can uniquely recover $\mathit{x}$ (and so $\mathit{z})$, which implies that ${\tilde{\mathcal{C}}}_{\mathrm{syn}}$ is an $(n,2,{\mathcal{B}}_{\le t})$-reconstruction code.

By (24), the redundancy of ${\tilde{\mathcal{C}}}_{\mathrm{syn}}$ is $r+1=t+2+\left|{\tilde{f}}_q\left(\mathit{x}\right)\right|$ in q-ary symbols, which is at most $8\log \log n+o\left(\log \log n\right)$ bits by Lemma 10.

The encoding complexity of ${\tilde{\mathcal{C}}}_{\mathrm{syn}}$ comes from the complexity of computing ${\tilde{f}}_q\left(\mathit{x}\right)$, which is $O\left(q^{7t}n{\left(\log n\right)}^3\right)$ by Lemma 10. The decoding complexity of ${\tilde{\mathcal{C}}}_{\mathrm{syn}}$ by brute force searching is at most $O\left({\left(n{q}^t\right)}^2{q}^{7t}n{\left(\log n\right)}^3\right)=O\left(q^{9t}{\left(n\log n\right)}^3\right)$. □

6. Conclusions and Discussions

We proposed new constructions of q-ary codes correcting a burst of at most t deletions, for both classical error correcting codes and reconstruction codes. By using q-ary $(\mathit{p},\delta )$-dense strings and bounded burst-deletion correcting codes, our constructions reduce the code redundancy in the $\log \log n$ term and have simpler encoding functions, compared to existing works.

A more general problem is to construct q-ary $(n,N,{\mathcal{D}}_t)$-reconstruction codes, i.e., q-ary reconstruction codes of length n for t-deletion channel with N reads. Note that the best known explicit construction (regarding the redundancy) for classical t-deletion correcting binary codes of length n has redundancy $(4t-1)\log n+o\left(\log n\right)$ [11]. So, we are interested in constructing q-ary $(n,N,{\mathcal{D}}_t)$-reconstruction codes, for any fixed q and t, of length n and with redundancy $k\log n+o\left(\log n\right)$ bits for some positive integer k such that $1\le k<4t-1$ and N depends only on k and t (and is independent of n).