paper

Reconstruction Codes for Deletions and Insertions: Connection, Distinction, and Construction

arXiv:2508.14386

Abstract

Let $B (\cdot)$ be an error ball function. A set of $q$ -ary sequences of length $n$ is referred to as an \emph{ $(n, q, N; B)$ -reconstruction code} if each sequence $x$ within this set can be uniquely reconstructed from any $N$ distinct elements within its error ball $B (x)$ . The main objective in this area is to determine or establish bounds for the minimum redundancy of $(n, q, N; B)$ -reconstruction codes, denoted by $I ¨ (n, q, N; B)$ . In this paper, we investigate reconstruction codes where the error ball is either the \emph{ $t$ -deletion ball} $D_{t} (\cdot)$ or the \emph{ $t$ -insertion ball} $I_{t} (\cdot)$ . Firstly, we establish a fundamental connection between reconstruction codes for deletions and insertions. For any positive integers $n, t, q, N$ , any $(n, q, N; I_{t})$ -reconstruction code is also an $(n, q, N; D_{t})$ -reconstruction code. This leads to the inequality $I ¨ (n, q, N; D_{t}) \leq I ¨ (n, q, N; I_{t})$ . Then, we identify a significant distinction between reconstruction codes for deletions and insertions when $N = O (n^{t - 1})$ and $t \geq 2$ . For deletions, we prove that $I ¨ (n, q, \frac{2 ( q - 1 ) ^{t - 1}}{q ^{t - 1} ( t - 1 )!} n^{t - 1} + O (n^{t - 2}); D_{t}) = O (1)$ , which disproves a conjecture posed in \cite{Chrisnata-22-IT}. For insertions, we show that $I ¨ (n, q, \frac{( q - 1 ) ^{t - 1}}{( t - 1 )!} n^{t - 1} + O (n^{t - 2}); I_{t}) = lo g lo g n + O (1)$ , which extends a key result from \cite{Ye-23-IT}. Finally, we construct $(n, q, N; B)$ -reconstruction codes, where $B \in {D_{2}, I_{2}}$ , for $N \in {2, 3, 4, 5}$ and establish respective upper bounds of $3 lo g n + O (lo g lo g n)$ , $3 lo g n + O (1)$ , $2 lo g n + O (lo g lo g n)$ and $lo g n + O (lo g lo g n)$ on the minimum redundancy $I ¨ (n, q, N; B)$ . This generalizes results previously established in \cite{Sun-23-IT}.