Document Open Access Logo

Efficiently Decodable Codes for the Binary Deletion Channel

Authors Venkatesan Guruswami, Ray Li

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2017.47.pdf
  • Filesize: 477 kB
  • 13 pages

Document Identifiers

Author Details

Venkatesan Guruswami
Ray Li

Cite As Get BibTex

Venkatesan Guruswami and Ray Li. Efficiently Decodable Codes for the Binary Deletion Channel. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 47:1-47:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.47

Abstract

In the random deletion channel, each bit is deleted independently with probability p. For the random deletion channel, the existence of codes of rate (1-p)/9, and thus bounded away from 0 for any p < 1, has been known. We give an explicit construction with polynomial time encoding and deletion correction algorithms with rate c_0 (1-p) for an absolute constant c_0 > 0.

Subject Classification

Keywords
  • Coding theory
  • Combinatorics
  • Synchronization errors
  • Channel capacity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Joshua Brakensiek, Venkatesan Guruswami, and Samuel Zbarsky. Efficient low-redundancy codes for correcting multiple deletions. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1884-1892, 2016. Google Scholar
  2. Boris Bukh, Venkatesan Guruswami, and Johan Håstad. An improved bound on the fraction of correctable deletions. IEEE Trans. Information Theory, 63(1):93-103, 2017. Google Scholar
  3. Suhas Diggavi and Matthias Grossglauser. On transmission over deletion channels. In Proceedings of the 39th Annual Allerton Conference on Communication, Control, and Computing, pages 573-582, 2001. Google Scholar
  4. Eleni Drinea and Michael Mitzenmacher. On lower bounds for the capacity of deletion channels. IEEE Transactions on Information Theory, 52(10):4648-4657, 2006. Google Scholar
  5. Eleni Drinea and Michael Mitzenmacher. Improved lower bounds for the capacity of i.i.d. deletion and duplication channels. IEEE Trans. Information Theory, 53(8):2693-2714, 2007. Google Scholar
  6. Dario Fertonani, Tolga M. Duman, and M. Fatih Erden. Bounds on the capacity of channels with insertions, deletions and substitutions. IEEE Trans. Communications, 59(1):2-6, 2011. URL: http://dx.doi.org/10.1109/TCOMM.2010.110310.090039.
  7. Venkatesan Guruswami and Ray Li. Efficiently decodable insertion/deletion codes for high-noise and high-rate regimes. In IEEE International Symposium on Information Theory, ISIT 2016, Barcelona, Spain, July 10-15, 2016, pages 620-624, 2016. URL: http://dx.doi.org/10.1109/ISIT.2016.7541373.
  8. Venkatesan Guruswami and Ray Li. Coding against deletions in oblivious and online models, 2017. Manuscript; arXiv abs/1612.06335. URL: http://arxiv.org/abs/1612.06335.
  9. Venkatesan Guruswami and Carol Wang. Deletion codes in the high-noise and high-rate regimes. IEEE Trans. Information Theory, 63(4):1961-1970, 2017. URL: http://dx.doi.org/10.1109/TIT.2017.2659765.
  10. Bernhard Haeupler and Amirbehshad Shahrasbi. Synchronization strings i: Codes for insertions and deletions approaching the singleton bound. To appear in STOC'17. http://arxiv.org/abs/1704.00807. Google Scholar
  11. Adam Kalai, Michael Mitzenmacher, and Madhu Sudan. Tight asymptotic bounds for the deletion channel with small deletion probabilities. In IEEE International Symposium on Information Theory, ISIT 2010, June 13-18, 2010, Austin, Texas, USA, Proceedings, pages 997-1001, 2010. URL: http://dx.doi.org/10.1109/ISIT.2010.5513746.
  12. Yashodhan Kanoria and Andrea Montanari. Optimal coding for the binary deletion channel with small deletion probability. IEEE Trans. Information Theory, 59(10):6192-6219, 2013. URL: http://dx.doi.org/10.1109/TIT.2013.2262020.
  13. Ian Kash, Michael Mitzenmacher, Justin Thaler, and John Ullman. On the zero-error capacity threshold for deletion channels. In Information Theory and Applications Workshop (ITA), pages 1-5, January 2011. Google Scholar
  14. Adam Kirsch and Eleni Drinea. Directly lower bounding the information capacity for channels with i.i.d.deletions and duplications. IEEE Trans. Information Theory, 56(1):86-102, 2010. URL: http://dx.doi.org/10.1109/TIT.2009.2034883.
  15. Vladimir I. Levenshtein. Binary codes capable of correcting deletions, insertions, and reversals. Dokl. Akad. Nauk, 163(4):845-848, 1965 (Russian). English translation in Soviet Physics Doklady, 10(8):707-710, 1966. Google Scholar
  16. Hugues Mercier, Vahid Tarokh, and Fabrice Labeau. Bounds on the capacity of discrete memoryless channels corrupted by synchronization and substitution errors. IEEE Trans. Information Theory, 58(7):4306-4330, 2012. URL: http://dx.doi.org/10.1109/TIT.2012.2191682.
  17. Michael Mitzenmacher. A survey of results for deletion channels and related synchronization channels. Probability Surveys, 6:1-33, 2009. Google Scholar
  18. Mojtaba Rahmati and Tolga M. Duman. Upper bounds on the capacity of deletion channels using channel fragmentation. IEEE Trans. Information Theory, 61(1):146-156, 2015. URL: http://dx.doi.org/10.1109/TIT.2014.2368553.
  19. Ramji Venkataramanan, Sekhar Tatikonda, and Kannan Ramchandran. Achievable rates for channels with deletions and insertions. IEEE Trans. Information Theory, 59(11):6990-7013, 2013. URL: http://dx.doi.org/10.1109/TIT.2013.2278181.
  20. S. M. Sadegh Tabatabaei Yazdi and Lara Dolecek. A deterministic polynomial-time protocol for synchronizing from deletions. IEEE Trans. Information Theory, 60(1):397-409, 2014. URL: http://dx.doi.org/10.1109/TIT.2013.2279674.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact