




















The central problem in sequence reconstruction is to find the minimum number of distinct channel outputs required to uniquely reconstruct the transmitted sequence. According to Levenshtein's work in 2001, this number is determined by the size of the maximum intersection between the error balls of any two distinct input sequences of the channel. In this work, we study the sequence reconstruction problem for single-deletion single-substitution channel, assuming that the transmitted sequence belongs to a $q$-ary code with minimum Hamming distance at least $2$, where $q\geq 2$ is any fixed integer. Specifically, we prove that for any two $q$-ary sequences of length $n$ and with Hamming distance $d\geq 2$, the size of the intersection of their error balls is upper bounded by $2qn-3q-2-δ_{q,2}$, where $δ_{i,j}$ is the Kronecker delta. We also prove the tightness of this bound by constructing two sequences the intersection size of whose error balls achieves this bound.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。