标题： 二进制重构码纠正一位删除和一位替换 显示英文标题

标题： Binary Reconstruction Codes for Correcting One Deletion and One Substitution

摘要： 在本文中，我们研究了能够纠正一次删除和一次替换的二进制重构码。 我们定义 \emph{单删除单替换球} 函数 $ \mathcal{B} $ 是从一个序列到可以通过执行一次删除和一次替换得到的一组序列的映射。 二进制 \emph{$(n,N;\mathcal{B})$-重构代码} 被定义为长度为$ n $ 的二进制序列的集合，使得任意两个不同的码字的单删除单替换球的交集大小严格小于$ N $。 此性质确保每个码字可以从其单删除单替换球中的$ N $个不同的元素唯一地重构。 我们的主要贡献在于证明当$ N $设置为$ 4n - 8 $、$ 3n - 4 $、$2n+9$、$ n+21 $、$31$和$7$时，二进制$(n,N;\mathcal{B})$-重构码的冗余度可以分别为$0$、$1$、$2$、$ \log\log n + 3 $、$\log n + 1 $和$ 3\log n + 4 $，其中对数是以2为底的。 显示英文摘要

摘要： In this paper, we investigate binary reconstruction codes capable of correcting one deletion and one substitution. We define the \emph{single-deletion single-substitution ball} function $ \mathcal{B} $ as a mapping from a sequence to the set of sequences that can be derived from it by performing one deletion and one substitution. A binary \emph{$(n,N;\mathcal{B})$-reconstruction code} is defined as a collection of binary sequences of length $ n $ such that the intersection size between the single-deletion single-substitution balls of any two distinct codewords is strictly less than $ N $. This property ensures that each codeword can be uniquely reconstructed from $ N $ distinct elements in its single-deletion single-substitution ball. Our main contribution is to demonstrate that when $ N $ is set to $ 4n - 8 $, $ 3n - 4 $, $2n+9$, $ n+21 $, $31$, and $7$, the redundancy of binary $(n,N;\mathcal{B})$-reconstruction codes can be $0$, $1$, $2$, $ \log\log n + 3 $, $\log n + 1 $, and $ 3\log n + 4 $, respectively, where the logarithm is on base two.