Sequence Reconstruction Over the Deletion Channel
Sequence Reconstruction Over the Deletion Channel
复制标题
删除通道上的序列重建
DOI：
10.1109/tit.2018.2800044
复制
发表时间：
2018
影响因子：
2.5
通讯作者：
Eitan Yaakobi
中科院分区：
文献类型：
--
作者：
Ryan Gabrys;Eitan Yaakobi
<italic>序列重构问题</italic>首先由Levenshtein提出，它模拟了这样一种设置：来自某个集合的序列在几个信道上传输，解码器接收来自每个信道的输出。通道几乎是独立的，因为它只需要所有输出彼此不同。感兴趣的主要问题是确定重建传输序列所需的最小信道数。在组合上下文中，这个问题等价于找到两个半径<inline-formula><tex-math notation="LaTeX">为t的</tex-math></inline-formula>球之间的最大交集，其中它们的中心之间的距离至少<inline-formula><tex-math notation="LaTeX">为d</tex-math></inline-formula>。这个问题的设置之前研究了几个误差度量，如汉明度量，肯德尔-τ度量，和约翰逊度量。在本文中，我们扩展了Levenshtein发起的研究重建序列删除通道。当他解决了传输序列可以是任意的情况下，我们研究的设置，其中传输序列属于一个单删除校正码，有<inline-formula><tex-math notation="LaTeX">$t$</tex-math></inline-formula>删除在每个通道。在这种范式下，我们研究了不同的通道输出的最小数量，以构建一个成功的解码器。
The <italic>sequence reconstruction problem</italic>, first proposed by Levenshtein, models the setup in which a sequence from some set is transmitted over several channels, and the decoder receives the outputs from every channel. The channels are almost independent as it is only required that all outputs are different from each other. The main problem of interest is to determine the minimum number of channels required to reconstruct the transmitted sequence. In the combinatorial context, the problem is equivalent to finding the maximum intersection between two balls of radius <inline-formula> <tex-math notation="LaTeX">$t$ </tex-math></inline-formula>, where the distance between their centers is at least <inline-formula> <tex-math notation="LaTeX">$d$ </tex-math></inline-formula>. The setup of this problem was studied before for several error metrics such as the Hamming metric, the Kendall-tau metric, and the Johnson metric. In this paper, we extend the study initiated by Levenshtein for reconstructing sequences over the deletion channel. While he solved the case where the transmitted sequence can be arbitrary, we study the setup, where the transmitted sequence belongs to a single-deletion-correcting code and there are <inline-formula> <tex-math notation="LaTeX">$t$ </tex-math></inline-formula> deletions in every channel. Under this paradigm, we study the minimum number of different channel outputs in order to construct a successful decoder.