Sequence Reconstruction over the Deletion Channel

Fengxing Zhu · 2025

Read Sequence Reconstruction over the Deletion Channel by Fengxing Zhu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-01071.txt.

Introduction

Fengxing Zhu studies sequence reconstruction over a deletion channel, a communication setting where symbols can vanish from a transmitted binary codeword. The record notes the main mistake in an earlier version has been corrected. The receiver sees several distinct outputs, each missing up to a fixed number of symbols, and wants to narrow the original message down to a short list of candidates.

Zhu determines the minimum number of channel outputs needed to guarantee such a list reconstruction. The key step is computing the largest possible intersection of several deletion balls, the sets of outputs that different candidate codewords could produce after deletions. Knowing that intersection size exactly pins down when the received outputs can still be consistent with too many candidates.

Catalog record

CREATORFengxing Zhu
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE37 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-01071

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Sequence Reconstruction over the Deletion Channel Thanks: Institute for Systems Research and Department of ECE, University of Maryland, College Park, MD 20742, USA, [email protected]. Supported in part by NSF grant CCF 2330909. Fengxing Zhu Abstract . In this paper, we consider the Levenshtein’s sequence reconstruction problem in the case where the transmitted codeword is chosen from { 0 , 1 } n \{0,1\}^{n} and the channel can delete up to t t symbols from the transmitted codeword. We determine the minimum number of channel outputs (assuming that they are distinct) required to reconstruct a list of size ℓ − 1 \ell-1 of candidate sequences, one of which corresponds to the original transmitted sequence. More specifically, we determine the maximum possible size of the intersection of ℓ ⩾ 3 \ell\geqslant 3 deletion balls of radius t t centered at x 1 , x 2 , … , x ℓ x_{1},x_{2},\dots,x_{\ell} , where x i ∈ { 0 , 1 } n x_{i}\in\{0,1\}^{n} for all i ∈ { 1 , 2 , … , ℓ } i\in\{1,2,\dots,\ell\} and x i ≠ x j x_{i}\neq x_{j} for i ≠ j i\neq j , with n ⩾ t + ℓ − 1 n\geqslant t+\ell-1 and t ⩾ 1 t\geqslant 1 . 1. Introduction The study of sequence reconstruction was initiated by Levenshtein in [ 6 , 5 ] , where a sender transmits a codeword x over multiple noisy channels. The receiver observes the outputs of these channels and attempts to uniquely reconstruct the transmitted codeword x . For the fixed codebook \mathcal{C} and the channel the main task is to determine the minimum number of channel outputs required to guarantee unique reconstruction. The motivation for the sequence reconstruction problem originates from biology and chemistry, where traditional redundancy-based error correction methods are unsuitable. In recent years, the problem has regained attention due to its strong relevance to information retrieval in advanced storage technologies. In such systems, the stored data may consist of a single copy that is read multiple times or several redundant copies of the same information [ 4 , 15 ] . This problem [ 4 ] is particularly significant in the context of DNA data storage [ 16 , 2 ] , where numerous noisy copies of DNA strands are available, and the objective is to accurately reconstruct the original information from these imperfect observations. This sequence reconstruction problem has been extensively studied under various channels. Hirschberg and Regnier in [ 13 ] derived tight bounds on the number of string subsequences. In [ 6 , 5 ] , Levenshtein obtained the minimum number of channel outputs for the deletion and insertion channel required for unique reconstruction for the case where \mathcal{C} consists of all binary vectors of length n . Gabrys and Yaakobi [ 3 ] later solved the sequence reconstruction problem over the t -deletion channel, where \mathcal{C} consists of binary vectors such that d_{L}(x,y)\geqslant 2 for x,y\in\mathcal{C} , with d_{L}(x,y) being the Levenshtein distance between x and y . More recently, Pham, Goyal, and Kiah [ 11 ] obtained a complete asymptotic solution for this problem where \mathcal{C} consists of binary vectors such that d_{L}(x,y)\geqslant\ell for x,y\in\mathcal{C} . The sequence reconstruction problem has also been studied under other channel models besides the deletion channel. Sala, Gabrys, Schoeny, and Dolecek [ 12 ] solved this problem for the insertion channel, assuming the codebook \mathcal{C} consists of q -ary vectors satisfying d_{L}(x,y)\geqslant\ell for all distinct x,y\in\mathcal{C} . Abu-Sini and Yaakobi [ 1 ] investigated the reconstruction problem for channels involving a single deletion combined with multiple substitutions, as well as channels involving a single insertion combined with a single substitution. A variant of the sequence reconstruction problem allows the decoder to output a list of possible sequences instead of a unique reconstruction. Yaakobi and Bruck [ 14 ] studied this problem for channels introducing substitution errors. In particular, they investigated the maximum intersection of m Hamming balls of radius t centered at x_{1},x_{2},\dots,x_{m} , where d_{H}(x_{i},x_{j})\geqslant d for i\neq j . Junnila, Laihonen, and Lehtilä [ 7 , 8 ] analyzed the list size when the channel introduces substitution errors with t=e+\ell , where e is the error-correcting capability of a binary code \mathcal{C} . More recently, they extended these results from the binary case to the q -ary case in [ 9 ] . In this paper we focus on the deletion channel. Formally, when a a codeword of length n is sent through a t -deletion channel, a subsequence of length n-t is received. A t -deletion correcting code \mathcal{C} is a subset of length- n binary vectors such that for any vector x\in\mathcal{C} , x can be uniquely identified from any length- (n-t) subsequence of x . More specifically, we study the minimum number of t -deletion channel outputs (assuming they are distinct) required to reconstruct a list of size \ell-1 of candidate sequences, one of which corresponds to the original transmitted sequence when \mathcal{C}=\{0,1\}^{n} . In other words, we determine the maximum possible size of the intersection of \ell\geqslant 3 deletion balls of radius t centered at x_{1},x_{2},\dots,x_{\ell} , where x_{i}\in\{0,1\}^{n} for all i\in\{1,2,\dots,\ell\} and x_{i}\neq x_{j} for i\neq j , with n\geqslant t+\ell-1 and t\geqslant 1 . 2. Definitions and Preliminaries Let x be a binary sequence of length n over \mathbb{F}_{2}^{n} . The deletion ball of radius t centered at x\in\mathbb{F}_{2}^{n} is define to be \mathcal{D}_{t}(x)=\{y\in\mathbb{F}_{2}^{n-t}|y\textrm{ is a subsequence of }x\}. For any two sequences x_{1} and x_{2} , their Levenshtein distance is t if \mathcal{D}_{t}(x_{1})\cap\mathcal{D}_{t}(x_{2})\neq\emptyset and \mathcal{D}_{t-1}(x_{1})\cap\mathcal{D}_{t-1}(x_{2})=\emptyset Let a_{n}\in\mathbb{F}_{2}^{n} be an alternating sequences where its first bit is 1. For 0<t<n , we denote the maximum size of a deletion ball of radius t , by D(n,t) ,i.e D(n,t)=\max_{x\in\mathbb{F}_{2}^{n}}|\mathcal{D}_{t}(x)|. From [ 6 ] and [ 5 ] , we know that D(n,t)=|\mathcal{D}_{t}(a_{n})|=\sum_{i=0}^{t}\binom{n-t}{i} and also D(n,t)=D(n-1,t)+D(n-2,t-1). Note that D(n,n)=1 and D(n,t)=0 if t<0 or n<t . Due to Levenshtein in [ 6 ] and [ 5 ] , we have \max_{x_{1}\neq x_{2},x_{1},x_{2}\in\mathbb{F}_{2}^{n}}|\mathcal{D}_{t}(x_{1})\cap\mathcal{D}_{t}(x_{2})|=2D(n-2,t-1). In this paper we will study N(n,\ell,t):=\max_{x_{1}\neq x_{2}...\neq x_{\ell};x_{1},x_{2},...,x_{\ell}\in\mathbb{F}_{2}^{n}}|\mathcal{D}_{t}(x_{1})\cap\mathcal{D}_{t}(x_{2})...\cap\mathcal{D}_{t}(x_{\ell})|, where \ell\geqslant 3 , n\geqslant t+\ell-1 and t\geqslant 1 . Specifically, we establish the following theorem. Theorem 1 . For \ell\geqslant 3 , n\geqslant t+\ell-1 and t\geqslant 1 , we have that \displaystyle N(n,\ell,t)=\sum_{i=1}^{\ell-2}D(n-2i,t-i)+2D(n-2(\ell-1),t-(\ell-1)). We will adopt the techniques and analysis from [ 3 ] and [ 11 ] to prove Theorem 1 . In particular, in order to prove the upper bound in Theorem 1 , we will use induction similar to that in [ 3 ] and [ 11 ] . Specifically, we will prove it by induction on n,\ell,t . The case where \ell=3 , t\geqslant 1 and n\geqslant t+\ell-1 will serve as part of the base case. We could use the case \ell=2 as a base case but in the proof of the general case there are certain places where \ell\geqslant 4 is necessary and also we feel it is instructive to give the proof for \ell=3 . Before proceeding, we need to give some definitions and state some lemmas that will be used very often in our analysis. Let \chi\subset\mathbb{F}_{2}^{n} be a set and v a sequence of length at most n . We denote by \chi^{v} the

Read the complete text