Blog
About

14
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      A Deterministic Polynomial-Time Protocol for Synchronizing from Deletions

      Preprint

      ,

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          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 \(\beta\). 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\beta\log \frac{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.

          Related collections

          Most cited references 12

          • Record: found
          • Abstract: not found
          • Article: not found

          A note on two problems in connexion with graphs

            Bookmark
            • Record: found
            • Abstract: not found
            • Article: not found

            Noiseless coding of correlated information sources

             D. Slepian,  J K Wolf (1973)
              Bookmark
              • Record: found
              • Abstract: not found
              • Article: not found

              The rate-distortion function for source coding with side information at the decoder

               A. D. Wyner,  J Ziv (1976)
                Bookmark

                Author and article information

                Journal
                02 July 2012
                2013-08-21
                1207.0290

                http://arxiv.org/licenses/nonexclusive-distrib/1.0/

                Custom metadata
                Accepted to the IEEE Transactions on Information Theory
                cs.IT math.IT

                Comments

                Comment on this article