Статья: ПОКРЫВАЮЩИЕ КОДЫ ДЛЯ МЕТРИКИ ЛЕВЕНШТЕЙНА ФИКСИРОВАННОЙ ДЛИНЫ

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