A Deterministic Polynomial-Time Protocol for Synchronizing From Deletions

Author

Tabatabaei Yazdi, S. M. Sadegh ; Dolecek, Lara

Author_Institution

R&D Center, Qualcomm, Inc., San Diego, CA, USA

Volume

60

Issue

1

fYear

2014

fDate

Jan. 2014

Firstpage

397

Lastpage

409

Abstract

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 β. 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 βlog 1/β) 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.

Keywords

computational complexity; deterministic algorithms; probability; protocols; deletion channel; deterministic polynomial-time protocol; polynomial-time synchronization scheme; probability; two-way communication channel; Decoding; Error probability; Indexes; Parity check codes; Pattern matching; Protocols; Synchronization; Coding for synchronization; deletion channel; edits; synchronization; two-way communication;

fLanguage

English

Journal_Title

Information Theory, IEEE Transactions on

Publisher

ieee

ISSN

0018-9448

Type

jour

DOI

10.1109/TIT.2013.2279674

Filename

6587115