ISSN 0555-2923

· Язык: ru

Статья: КОНСТРУКЦИИ И ИНВАРИАНТЫ ОПТИМАЛЬНЫХ КОДОВ В МЕТРИКЕ ЛИ (2023)

Читать

Читать онлайн

Предложены каскадный и свитчинговый методы построения совершенных и диаметральных совершенных кодов, исправляющих одну ошибку, в метрике Ли. Рассмотрены ранги и ядра диаметральных совершенных кодов, полученных свитчинговой конструкцией.

Ключевые фразы: метрика ли, совершенный код, диаметральный совершенный код, код васильева, код моллара, каскадная конструкция

Автор (ы): Могильных Иван Юрьевич

Соавтор (ы): Соловьева Фаина Ивановна

Журнал: ПРОБЛЕМЫ ПЕРЕДАЧИ ИНФОРМАЦИИ

Предпросмотр статьи

Идентификаторы и классификаторы

УДК: 519.725. Алгебраическая теория кодов, исправляющих ошибки
621.0. Теория машиностроения (машиноведение). Ядерная техника

Для цитирования:

МОГИЛЬНЫХ И. Ю., СОЛОВЬЕВА Ф. И. КОНСТРУКЦИИ И ИНВАРИАНТЫ ОПТИМАЛЬНЫХ КОДОВ В МЕТРИКЕ ЛИ // ПРОБЛЕМЫ ПЕРЕДАЧИ ИНФОРМАЦИИ. 2023. Т. 59 № 2

Текстовый фрагмент статьи

Исследования совершенных кодов в метрике Ли восходят к работе [1], в которой выдвинута гипотеза о несуществовании совершенных кодов в метрике Ли над алфавитами мощности больше 3, исправляющих более одной ошибки.

Параметры всех совершенных кодов, исправляющих одну ошибку, в метрике Ли, были перечислены в работе [2]. Для каждого набора допустимых параметров кодов показано существование линейного, т. е. образующего подгруппу относительно покоординатного сложения в Zq, совершенного кода. В работе [3] была предложена серия новых конструкций для нелинейных совершенных и диаметральных совершенных кодов, исправляющих одну ошибку. Некоторые из них являются вариантами известных конструкций совершенных кодов в метрике Хэмминга, таких как конструкция Соловьевой [4] для кодов в метрике Ли. В недавней работе [5] был развит конструктивный аппарат для построения совершенных и диаметральных совершенных кодов в метрике Ли. Многие предложенные в [5] конструкции используют разбиения на оптимальные коды. С помощью построения различных разбиений были получены рекордные оценки числа совершенных и диаметральных совершенных кодов в метрике Ли.

Моя история просмотров (1)

01. Статья: ИНВАРИАНТНЫЕ МЕРЫ ДЛЯ ПРОЦЕССОВ КОНТАКТОВ С ИНТЕНСИВНОСТЯМИ РОЖДЕНИЯ И ГИБЕЛИ, ЗАВИСЯЩИМИ ОТ СОСТОЯНИЯ

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

1. Golomb S.W., Welch L.R. Perfect Codes in the Lee Metric and the Packing of the Polyominoes // SIAM J. App. Math. 1970. V. 18. № 2. P. 302-317. DOI: 10.1137/0118025

2. AlBdaiwi B., Horak P., Milazzo L. Enumerating and Decoding Perfect Linear Lee Codes // Des. Codes Cryptogr. 2009. V. 52. № 2. P. 155-162. DOI: 10.1007/s10623-009-9273-3 EDN: BTPWID

3. Etzion T. Product Constructions for Perfect Lee Codes // IEEE Trans. Inform. Theory. 2011. V. 57. № 11. P. 7473-7481. DOI: 10.1109/TIT.2011.2161133

4. Соловьева Ф.И. О двоичных негрупповых кодах // Методы дискретного анализа в изучении булевых функций и графов. Вып. 37. Новосибирск: Ин-т матем. СО АН СССР, 1981. С. 65-76.

5. Соловьева Ф.И. Разбиения на совершенные коды в метриках Хэмминга и Ли // Пробл. передачи информ. 2022. Т. 58. № 3. С. 58-69. https://www.mathnet.ru/rus/ppi2375. EDN: EAJWAD

6. Могильных И.Ю. О q-ичных пропелинейных совершенных кодах на основе регулярных подгрупп общей аффинной группы // Пробл. передачи информ. 2022. Т. 58. № 1. С. 65-79. DOI: 10.31857/S0555292322010041 EDN: BIWIBU

7. Могильных И.Ю., Соловьева Ф.И. О весовом спектре класса кодов с параметрами кодов Рида - Маллера // Пробл. передачи информ. 2022. Т. 58. № 3. С. 33-44. https://www.mathnet.ru/rus/ppi2373. EDN: EAAOCA

8. Mollard M. Une novelle famille de 3-codes parfaits sur GF(q) // Discrete Math. 1984. V. 49. № 2. P. 209-212. DOI: 10.1016/0012-365X(84)90121-3

9. Romanov A.M. On Non-Full-Rank Perfect Codes over Finite Fields // Des. Codes Cryptogr. 019. V. 87. № 5. P. 995-1003. DOI: 10.1007/s10623-018-0506-1

10. Shi M., Krotov D.S. An Enumeration of 1-Perfect Ternary Codes // Discrete Math. 2023. V. 346. № 7. Paper No. 113437 (16 pp.). DOI: 10.1016/j.disc.2023.113437 EDN: PLXWRJ

11. Mogilnykh I.Yu., Solov’eva F.I. A Concatenation Construction for Propelinear Perfect Codes from Regular Subgroups of GA(r, 2) // Сиб. электрон. матем. изв. 2019. Т. 16. С. 1689-1702. DOI: 10.33048/semi.2019.16.119 EDN: VISHXH

12. Зиновьев В.А., Зиновьев Д.В. Об обобщенной каскадной конструкции кодов в модульной метрике и метрике Ли // Пробл. передачи информ. 2021. Т. 57. № 1. С. 81-95. DOI: 10.31857/S0555292321010046 EDN: YHVIXE

13. Bos A. Codes over Groups with Arbitrary Metrics // T.H.-Report 80-WSK-06, Dept. of Mathematics, Eindhoven Univ. of Technology. Eindhoven, The Netherlands, 1980.

14. Васильев Ю.Л. О негрупповых плотно упакованных кодах // Проблемы кибернетики. Т. 8. М.: Физматлит, 1962. С. 337-339.

15. Byrne E., Weger V. Bounds in the Lee Metric and Optimal Codes. https://arxiv.org/abs/2112.06635 [cs.IT], 2021.

16. Delsarte P. An Algebraic Approach to the Association Schemes of Coding Theory // Philips Res. Rep. Suppl. 1973. № 10 (97 pp.).

17. Ahlswede R., Aydinian H.K., Khachatrian L.H. On Perfect Codes and Related Concepts // Des. Codes Cryptogr. 2001. V. 22. № 3. P. 221-237. https://doi.org/10.1023/A:1008394205999. EDN: YZNDJF

18. Tamo I., Schwartz M. Correcting Limited-Magnitude Errors in the Rank-Modulation Scheme // IEEE Trans. Inform. Theory. 2010. V. 56. № 6. P. 2551-2560. DOI: 10.1109/TIT.2010.2046241

19. Mogilnykh I.Yu. q-ary Propelinear Perfect Codes from the Regular Subgroups of the GA(r, q) and Their Ranks. https://arxiv.org/abs/2112.08659 [math.CO], 2021.

20. Романов А.М. О совершенных кодах и кодах Рида - Маллера над конечными полями // Пробл. передачи информ. 2021. Т. 57. № 3. С. 3-16. DOI: 10.31857/S0555292321030013 EDN: YWOGGW

Выпуск

Т. 59 № 2 (2023)

Кол-во страниц: 119 страниц

Другие статьи выпуска

СУЩЕСТВОВАНИЕ ПОСЛЕДОВАТЕЛЬНОСТЕЙ, УДОВЛЕТВОРЯЮЩИХ РЕКУРРЕНТНЫМ СООТНОШЕНИЯМ БИЛИНЕЙНОГО ТИПА (2023)

Авторы: Илларионов Андрей Анатольевич

Рассматриваются последовательности {An}+∞n=−∞ элементов произвольного поля F, удовлетворяющие разложениям вида Am+nAm−n=a1(m)b1(n)+a2(m)b2(n), Am+n+1Am−n=a˜1(m)b˜1(n)+a˜2(m)b˜2(n), где a1, a2, b1, b2: Z→F. Доказываются результаты о существовании и единственности таких последовательностей. Полученные результаты используются для построения аналогов криптографических алгоритмов Диффи - Хеллмана и Эль-Гамаля. Задача дискретного логарифмирования ставится в группе (S,+), где множество S состоит из четверок S(n)=(An−1, An, An+1, An+2), n∈Z, а S(n)+S(m)=S(n+m).

Сохранить в закладках

ЭФФЕКТИВНОСТЬ ПЕРЕДАЧИ ДАННЫХ ПРИ АТАКАХ С ТОЧКИ ЗРЕНИЯ ВАРИАНТА ИЗОЛИРОВАННОЙ ЖЕСТКОСТИ (2023)

Авторы: Гао Вэй, Башконуш Хаджи Мехмет, Каттани Карло

Модель сетевого графа является удобным инструментом для анализа сетей передачи информации, где возможность передачи в условиях атаки на объект можно описывать с помощью дробных критических графов, а уязвимость сети можно измерять с помощью варианта параметра изолированной жесткости. Рассматривается как устойчивость сети, так и реализуемость передачи данных при повреждении узлов, и определяется граница на вариант изолированной жесткости для дробных (a, b, n)-критических графов, где параметр n означает количество поврежденных узлов в определенный момент времени. С помощью контрпримера доказывается точность полученной границы на вариант изолированной жесткости. Основной теоретический вывод позволяет находить оптимальное соотношение между производительностью и стоимостью при проектировании топологии сети.

Сохранить в закладках

ИНВАРИАНТНЫЕ МЕРЫ ДЛЯ ПРОЦЕССОВ КОНТАКТОВ С ИНТЕНСИВНОСТЯМИ РОЖДЕНИЯ И ГИБЕЛИ, ЗАВИСЯЩИМИ ОТ СОСТОЯНИЯ (2023)

Авторы: Жижина Елена Анатольевна, Пирогов Сергей Анатольевич

Рассматриваются процессы контактов на локально компактных сепарабельных метрических пространствах с неоднородными по пространству интенсивностями рождения и гибели. Формулируются условия на интенсивности, обеспечивающие существование инвариантных мер этих процессов. Одним из условий является так называемое условие критического режима. Для доказательства существования инвариантных мер использован подход, предложенный в предыдущей работе авторов. Подробно рассматривается маркированная модель контактов с компактным пространством марок (квазивидов), в которой интенсивности как рождения, так и гибели зависят от марок.

Сохранить в закладках

ГЕОМЕТРИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ ЭНТРОПИИ СОФИЧЕСКИХ СИСТЕМ (2023)

Авторы: Дворкин Григорий Дмитриевич

Рассматривается геометрический подход к понятию метрической энтропии. Обоснована возможность такого подхода для класса борелевских вероятностных инвариантных эргодических мер на софических системах, что является первым результатом такой общности для немарковских систем.

Сохранить в закладках

ПОЧТИ ИДЕАЛЬНЫЕ ПРЕДИКТОРЫ И КАУЗАЛЬНЫЕ ФИЛЬТРЫ ДЛЯ ДИСКРЕТНЫХ СИГНАЛОВ (2023)

Авторы: Докучаев Николай Геннадьевич

Представлены линейные предикторы и каузальные фильтры для дискретных сигналов, имеющих различные виды дегенерации спектра. Эти предикторы и фильтры основаны на аппроксимации идеальных некаузальных передаточных функций каузальными передаточными функциями, представленными многочленами от Z-преобразования дискретной функции Хевисайда.

Сохранить в закладках

ПОКРЫВАЮЩИЕ КОДЫ ДЛЯ МЕТРИКИ ЛЕВЕНШТЕЙНА ФИКСИРОВАННОЙ ДЛИНЫ (2023)

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

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

Сохранить в закладках

Издательство

Издательство: ИППИ РАН
Регион: Россия, Москва
Почтовый адрес: Большой Каретный пер., 19, стр. 1
Юр. адрес: Большой Каретный пер., 19, стр. 1
ФИО: Соболевский Андрей Николаевич (Директор)
E-mail адрес: director@iitp.ru
Контактный телефон: +7 (495) 6504274
Сайт: http:/iitp.ru

Все права на тексты и товарные знаки принадлежат их законным владельцам. Подробнее...

Сайт https://scinetwork.ru (далее – сайт) работает по принципу агрегатора – собирает и структурирует информацию из публичных источников в сети Интернет, то есть передает полнотекстовую информацию о товарных знаках в том виде, в котором она содержится в открытом доступе.

Сайт и администрация сайта не используют отображаемые на сайте товарные знаки в коммерческих и рекламных целях, не декларируют своего участия в процессе их государственной регистрации, не заявляют о своих исключительных правах на товарные знаки, а также не гарантируют точность, полноту и достоверность информации.

Все права на товарные знаки принадлежат их законным владельцам!

Сайт носит исключительно информационный характер, и предоставляемые им сведения являются открытыми публичными данными.

Администрация сайта не несет ответственность за какие бы то ни было убытки, возникающие в результате доступа и использования сайта.

Спасибо, понятно.