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

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