Покрывающие коды для метрики Левенштейна фиксированной длины

Обложка

Цитировать

Полный текст

Открытый доступ Открытый доступ
Доступ закрыт Доступ предоставлен
Доступ закрыт Доступ платный или только для подписчиков

Аннотация

Покрывающим кодом или покрытием называется множество кодовых слов, такое что объединение шаров с центрами в этих кодовых словах покрывает все пространство. Как правило, задача состоит в минимизации мощности покрывающего кода. Для классической метрики Хэмминга размер минимального покрывающего кода фиксированного радиуса R известен с точностью до постоянного множителя. Аналогичный результат был недавно получен для кодов с R вставками и кодов с R удалениями. В данной статье изучаются покрытия пространства для метрики Левенштейна фиксированной длины, т.е. для R вставок и R удалений. Для R = 1 и 2 доказываются новые нижние и верхние оценки минимальной мощности покрывающего кода, которые отличаются лишь в константу раз.

Об авторах

Илья Викторович Воробьев

Технический университет Мюнхена

Email: vorobyev.i.v@yandex.ru
Мюнхен, Германия

Список литературы

  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
Скачать

© Российская академия наук, 2023