- Код статьи
- 10.31857/S055529232302002X-1
- DOI
- 10.31857/S055529232302002X
- Тип публикации
- Статья
- Статус публикации
- Опубликовано
- Авторы
- Том/ Выпуск
- Том 59 / Номер выпуска 2
- Страницы
- 18-31
- Аннотация
- Покрывающим кодом или покрытием называется множество кодовых слов, такое что объединение шаров с центрами в этих кодовых словах покрывает все пространство. Как правило, задача состоит в минимизации мощности покрывающего кода. Для классической метрики Хэмминга размер минимального покрывающего кода фиксированного радиуса R известен с точностью до постоянного множителя. Аналогичный результат был недавно получен для кодов с R вставками и кодов с R удалениями. В данной статье изучаются покрытия пространства для метрики Левенштейна фиксированной длины, т.е. для R вставок и R удалений. Для R = 1 и 2 доказываются новые нижние и верхние оценки минимальной мощности покрывающего кода, которые отличаются лишь в константу раз.
- Ключевые слова
- покрывающие коды граница сферической упаковки метрика Левенштейна вероятностный метод
- Дата публикации
- 18.09.2025
- Год выхода
- 2025
- Всего подписок
- 0
- Всего просмотров
- 12
Библиография
- 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
