Covering codes for the fixed length Levenshtein metric

封面

如何引用文章

全文:

开放存取 开放存取
受限制的访问 ##reader.subscriptionAccessGranted##
受限制的访问 订阅存取

详细

A covering code, or a covering, is a set of codewords such that the union of balls centered at these codewords covers the whole space. As a rule, the problem consists in nding the minimum of a covering code. For the classical Hamming metric, the size of the smallest covering code of a xed radius R is known up to a constant factor. A similar result has recently been obtained for codes with R insertions and codes with R deletions. In the present paper we study coverings of a space for the xed length Levenshtein metric, i.e., for R insertions and R deletions. For R = 1, 2 we prove new lower and upper bounds on the minimum cardinality of a covering code, which di er by a constant factor only.

作者简介

I. Vorobyev

Technische Universit�t M�nchen

Email: vorobyev.i.v@yandex.ru
Munich, Germany

参考

  1. Cohen G., Honkala I., Listyn S., Lobstein A. Covering Codes. Amsterdam: Elsevier, 1997.
  2. Smolensky R. On Representations by Low-Degree Polynomials // Proc. 34th Annu. Symp. on Foundations of Computer Science. Palo Alto, CA, USA. Nov. 3-5, 1993. P. 130-138. https://doi.org/10.1109/SFCS.1993.366874
  3. Pagh R. Locality-sensitive Hashing without False Negatives // Proc. 27th Annu. ACM-SIAM Symp. on Discrete Algorithms (SODA'2016). Arlington, VA, USA. Jan. 10-12, 2016. P. 1-9. https://doi.org/10.1137/1.9781611974331.ch1
  4. Micciancio D. Almost Perfect Lattices, the Covering Radius Problem, and Applications to Ajtai's Connection Factor // SIAM J.Comput. 2004. V. 34. № 1. P. 118-169. https://doi.org/10.1137/S0097539703433511
  5. Hämäläinen H., Honkala I., Litsyn S., Östergård P. Football Pools - A Game for Mathematicians // Amer. Math. Monthly. 1995. V. 102. № 7. P. 579-588. https://doi.org/10.2307/2974552
  6. Ceze L., Nivala J., Strauss K. Molecular Digital Data Storage Using DNA // Nat. Rev. Genet. 2019. V. 20. № 8. P. 456-466. https://doi.org/10.1038/s41576-019-0125-3
  7. Bornholt J., Lopez R., Carmean D.M., Ceze L., Seelig G., Strauss K. A DNA-Based Archival Storage System // Proc. 21st Int. Conf. on Architectural Support for Programming Languages and Operating Systems (ASPLOS'16). Atlanta, GA, USA. Apr. 2-6, 2016. P. 637-649. https://doi.org/10.1145/2872362.2872397
  8. Church G.M., Gao Y., Kosuri S. Next-Generation Digital Information Storage in DNA // Science. 2012. V. 337. № 6102. P. 1628. https://doi.org/10.1126/science.1226355
  9. Кабатянский Г.А., Панченко В.И. Упаковки и покрытия хэммингова пространства единичными шарами // Докл. АН СССР. 1988. Т. 303. № 3. С. 550-552. https://www.mathnet.ru/rus/dan7368
  10. Krivelevich M., Sudakov B., Vu V.H. Covering Codes with Improved Density // IEEE Trans. Inform. Theory. 2003. V. 49. № 7. P. 1812-1815. https://doi.org/10.1109/TIT.2003.813490
  11. Lenz A., Rashtchian C., Siegel P.H., Yaakobi E. Covering Codes Using Insertions or Deletions // IEEE Trans. Inform. Theory. 2020. V. 67. № 6. P. 3376-3388. https://doi.org/10.1109/TIT.2020.2985691
  12. Fazeli A., Vardy A., Yaakobi E. Generalized Sphere Packing Bound // IEEE Trans. Inform. Theory. 2015. V. 61. № 5. P. 2313-2334. https://doi.org/10.1109/TIT.2015.2413418
  13. Applegate D., Rains E.M., Sloane N.J.A. On Asymmetric Coverings and Covering Numbers // J. Combin. Des. 2003. V. 11. № 3. P. 218-228. https://doi.org/10.1002/jcd.10022
  14. Sala F., Dolecek L. Counting Sequences Obtained from the Synchronization Channel // Proc. 2013 IEEE Int. Symp. on Information Theory (ISIT'2013). Istanbul, Turkey. July 7-12, 2013. P. 2925-2929. https://doi.org/10.1109/ISIT.2013.6620761
  15. Hoeffding W. Probability Inequalities for Sums of Bounded Random Variables // J. Amer. Statist. Assoc. 1963. V. 58. № 301. P. 13-30. https://doi.org/10.2307/2282952. Reprinted in: The Collected Works of Wassily Hoeffding. New York: Springer, 1994. P. 409-426.
  16. Wang G., Wang Q. On the Size Distribution of Levenshtein Balls with Radius One, arXiv: 2204.02201 [cs.IT], 2022.
  17. He L., Ye M. The Size of Levenshtein Ball with Radius 2: Expectation and Concentration Bound // Proc. 2023 IEEE Int. Symp. on Information Theory (ISIT'2023). Taipei, Taiwan. June 25-30, 2023. P. 850-855. https://doi.org/10.1109/ISIT54713.2023.10206888
  18. Cooper J.N., Ellis R.B., Kahng A.B. Asymmetric Binary Covering Codes // J. Combin. Theory Ser. A. 2002. V. 100. № 2. P. 232-249. https://doi.org/10.1006/jcta.2002.3290
  19. Левенштейн В.И. Двоичные коды с исправлением выпадений, вставок и замещений символов // Докл. АН СССР. 1965. Т. 163. № 4. С. 845-848. https://www.mathnet.ru/rus/dan31411
  20. Levenshtein V.I. E cient Reconstruction of Sequences from Their Subsequences or Supersequences // J. Combin. Theory Ser. A. 2001. V. 93. № 2. P. 310-332. https://doi.org/10.1006/jcta.2000.3081

补充文件

附件文件
动作
1. JATS XML
下载

版权所有 © Russian Academy of Sciences, 2023