科研之友
微信
新浪微博
Facebook
分享链接
摘要
In this paper, we consider a synchronization problem between nodes A and B that are connected through a two-way communication channel. Node A contains a binary file X of length n and node B contains a binary file Y that is generated by randomly deleting bits from X, by a small deletion rate beta. The location of deleted bits is not known to either node A or node B. We offer a deterministic, polynomial-time synchronization scheme between nodes A and B that needs a total of O(n beta log 1/beta) transmitted bits and reconstructs X at node B with probability of error that is exponentially low in the size of X. Orderwise, the rate of our scheme matches the optimal rate for this channel.
- 出版日期2014-1
