Loading [MathJax]/jax/output/SVG/config.js
Проблемы передачи информации
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор
Правила для авторов

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS


Пробл. передачи информ.:
Год:
Том:
Выпуск:
Страница:
Найти




Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация

Проблемы передачи информации, 2023, том 59, выпуск 2, страницы 18–31
DOI: https://doi.org/10.31857/S055529232302002X (Mi ppi2395) 		 
Теория кодирования

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

И. В. Воробьев

Технический университет Мюнхена, Германия
PDF полного текста (229 kB) Первая страница
Список литературы:
PDF
HTML
DOI: https://doi.org/10.31857/S055529232302002X
Аннотация: Покрывающим кодом или покрытием называется множество кодовых слов, такое что объединение шаров с центрами в этих кодовых словах покрывает все пространство. Как правило, задача состоит в минимизации мощности покрывающего кода. Для классической метрики Хэмминга размер минимального покрывающего кода фиксированного радиуса $R$ известен с точностью до постоянного множителя. Аналогичный результат был недавно получен для кодов с $R$ вставками и кодов с $R$ удалениями. В данной статье изучаются покрытия пространства для метрики Левенштейна фиксированной длины, т.е. для $R$ вставок и $R$ удалений. Для $R=1$ и $2$ доказываются новые нижние и верхние оценки минимальной мощности покрывающего кода, которые отличаются лишь в константу раз.
Ключевые слова: покрывающие коды, граница сферической упаковки, метрика Левенштейна, вероятностный метод.
Финансовая поддержка Номер гранта
Российский научный фонд 22-41-02028
Исследование выполнено за счет гранта Российского научного фонда № 22-41-02028.
Поступила в редакцию: 14.10.2023
После переработки: 28.11.2023
Принята к печати: 28.11.2023
Англоязычная версия:
Problems of Information Transmission, 2023, Volume 59, Issue 2, Pages 86–98
DOI: https://doi.org/10.1134/S0032946023020023
Реферативные базы данных:
Тип публикации: Статья
УДК: 621.391 : 519.72
Образец цитирования: И. В. Воробьев, “Покрывающие коды для метрики Левенштейна фиксированной длины”, Пробл. передачи информ., 59:2 (2023), 18–31; Problems Inform. Transmission, 59:2 (2023), 86–98
Цитирование в формате AMSBIB
\RBibitem{Vor23}
\by И.~В.~Воробьев
\paper Покрывающие коды для метрики Левенштейна фиксированной длины
\jour Пробл. передачи информ.
\yr 2023
\vol 59
\issue 2
\pages 18--31
\mathnet{http://mi.mathnet.ru/ppi2395}
\crossref{https://doi.org/10.31857/S055529232302002X}
\edn{https://elibrary.ru/PPPXTQ}
\transl
\jour Problems Inform. Transmission
\yr 2023
\vol 59
\issue 2
\pages 86--98
\crossref{https://doi.org/10.1134/S0032946023020023}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/ppi2395
  • https://www.mathnet.ru/rus/ppi/v59/i2/p18
    • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Проблемы передачи информации Problems of Information Transmission
    Статистика просмотров:
    Страница аннотации:89
    PDF полного текста:1
    Список литературы:20
    Первая страница:10
     
      Обратная связь:
    math-net2025_04@mi-ras.ru     		 Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2025