Interactive low-complexity codes for synchronization from deletions and insertions
Interactive low-complexity codes for synchronization from deletions and insertions
复制标题
用于同步删除和插入的交互式低复杂度代码
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
K. Ramchandran
中科院分区：
文献类型：
--
作者：
R. Venkataramanan;Hao Zhang;K. Ramchandran
研究了两个远程数据源的同步问题，这两个数据源由于删除和插入而导致不同步。这是一个重要的问题，因为少量的同步误差会在两个信源之间引起很大的汉明距离。目标是通过在两个源之间高效地使用无损双向链路来实现同步。在这项工作中，我们重点研究了以下模型。长度为n的二进制序列X被编辑以在远端产生序列，例如Y，其中编辑涉及随机删除和插入，可能以小的突发。问题是在信息交换最少的情况下使Y与X同步(就平均通信速率和平均交互通信轮数而言)。本文针对编辑次数远小于n的情况，提出了一种计算简单、通信复杂度接近最优的交互式算法。我们的算法通过将源序列有效地分割成仅包含单个删除/插入或单个突发删除/插入的片段来工作。然后使用基于Varshamov和Tenengolts的单删除校正信道码(VT码)的最佳单向同步码来同步这些片段中的每一个。
We study the problem of synchronization of two remotely located data sources, which are mis-synchronized due to deletions and insertions. This is an important problem since a small number of synchronization errors can induce a large Hamming distance between the two sources. The goal is to effect synchronization with the rate-efficient use of lossless bidirectional links between the two sources. In this work, we focus on the following model. A binary sequence X of length n is edited to generate the sequence at the remote end, say Y, where the editing involves random deletions and insertions, possibly in small bursts. The problem is to synchronize Y with X with minimal exchange of information (in terms of both the average communication rate and the average number of interactive rounds of communication). We focus here on the case where the number of edits is much smaller than n, and propose an interactive algorithm which is computationally simple and has near-optimal communication complexity. Our algorithm works by efficiently splitting the source sequence into pieces containing either just a single deletion/insertion or a single burst deletion/insertion. Each of these pieces is then synchronized using an optimal one-way synchronization code, based on the single-deletion correcting channel codes of Varshamov and Tenengolts (VT codes).