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

      Guess & Check Codes for Deletions, Insertions, and Synchronization

      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

          We consider the problem of constructing codes that can correct \(\delta\) deletions occurring in an arbitrary binary string of length \(n\) bits. Varshamov-Tenengolts (VT) codes are zero-error single deletion \((\delta=1)\) correcting codes, and have an asymptotically optimal redundancy. Finding similar codes for \(\delta \geq 2\) deletions is an open problem. We propose a new family of codes, that we call Guess & Check (GC) codes, that can correct, with high probability, up to \(\delta\) deletions occurring in a binary string. Moreover, we show that GC codes can also correct up to \(\delta\) insertions. GC codes are based on MDS codes and have an asymptotically optimal redundancy that is \(\Theta(\delta \log n)\). We provide deterministic polynomial time encoding and decoding schemes for these codes. We also describe the applications of GC codes to file synchronization.

          Related collections

          Most cited references10

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

          Asymptotically good codes correcting insertions, deletions, and transpositions

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

            On multiple insertion/deletion correcting codes

              Bookmark
              • Record: found
              • Abstract: not found
              • Conference Proceedings: not found

              Capacity Upper Bounds for the Deletion Channel

                Bookmark

                Author and article information

                Journal
                2017-05-24
                Article
                1705.09569
                f6389c7f-6269-4d59-a371-a50515bf62ff

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

                History
                Custom metadata
                Submitted to IEEE Transactions on Information Theory. arXiv admin note: text overlap with arXiv:1702.04466
                cs.IT math.IT

                Numerical methods,Information systems & theory
                Numerical methods, Information systems & theory

                Comments

                Comment on this article