2012/07/02 by S. M. Sadegh Tabatabaei Yazdi, Lara Dolecek, Yazdi, S. M. Sadegh Tabatabaei +1 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Cellular Automata and Applications #Cooperative Communication and Network Coding #DNA and Biological Computing #FOS: Computer and information sciences #Information Theory (cs.IT) #cs.IT #math.IT
paper · pdf · doi:10.48550/arxiv.1207.0290
Accepted to the IEEE Transactions on Information Theory
openalex publication_date 2012/07/02 · arxiv created 2013/08/21 · arxiv updated 2013/08/22 · openalex created_date 2022/10/03 · openalex updated_date 2026/07/28
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 synchronization scheme between nodes A and B that needs a total of O(nβlog \frac1β) 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.