Квазисовершенные коды в декартовом произведении некоторых графов

Основная информация

• ID статьи: 2510.13613
• Название: Quasi perfect codes in the cartesian product of some graphs
• Авторы: S. A. Mane, N. V. Shinde
• Классификация: math.CO (комбинаторика)
• Дата публикации: 15 октября 2025 г.
• Ссылка на статью: https://arxiv.org/abs/2510.13613

Аннотация

Важным вопросом в исследовании квазисовершенных кодов является возможность конструирования таких кодов для всех возможных длин n. В данной работе рассматривается эта проблема для конкретных значений n. Во-первых, при условии, что граф G допускает совершенный код, исследуется существование квазисовершенных кодов в декартовом произведении графа G с путём (или циклом). Во-вторых, исследуются квазисовершенные коды в декартовом произведении двух или трёх циклов $C_m\square C_n$ и $C_m\square C_n\square C_l$, а также в декартовом произведении двух или трёх путей $P_m\square P_n$ и $P_m\square P_n\square P_l$.

Исследовательский контекст и мотивация

1. Решаемая проблема: Данное исследование направлено на решение проблемы существования квазисовершенных кодов, в частности на разработку систематических методов конструирования квазисовершенных кодов в декартовых произведениях графов.
2. Значимость проблемы:
   • Совершенные коды играют центральную роль в теории исправления ошибок, но встречаются относительно редко
   • Гипотеза Голомба-Велча утверждает, что не существует совершенных кодов Ли с длиной n≥3 и e>1 для исправления e ошибок
   • Квазисовершенные коды как приближение к совершенным кодам имеют важное теоретическое и прикладное значение
3. Ограничения существующих методов:
   • Условия существования квазисовершенных кодов остаются достаточно строгими
   • Известно мало квазисовершенных кодов с радиусом покрытия больше 3
   • Отсутствуют систематические методы конструирования
4. Исследовательская мотивация: Разработка методов конструирования квазисовершенных кодов в декартовых произведениях G с конкретными графами на основе совершенных кодов в графе G.

Основные вклады

1. Предложен систематический метод конструирования квазисовершенных кодов на основе совершенных кодов: Если граф G допускает совершенный e-исправляющий код, то можно конструировать квазисовершенные e-исправляющие коды в G□Pn или G□Cn
2. Построены различные конкретные квазисовершенные коды:
   • Квазисовершенные 2-исправляющие коды в Pm□Pn□P6k-2 и Cm□Cn□C6k
   • Квазисовершенные коды в P4□P4□P4 на основе совершенных кодов в P2□P2□P2
3. Расширены известные результаты: Конструирование квазисовершенных кодов в Cn□Cn□Cl (3≤n≤19) с использованием известных квазисовершенных кодов в Cn□Cn
4. Предоставлена полная теоретическая база: Систематический анализ методов конструирования квазисовершенных кодов в декартовых произведениях путей и циклов

Подробное описание методов

Определение задачи

Для заданного графа G требуется конструировать квазисовершенные коды в его декартовом произведении G□Pn, G□Cn с путём Pn или циклом Cn. Код D называется t-квазисовершенным тогда и только тогда, когда он исправляет t ошибок и имеет радиус покрытия t+1.

Основные методы конструирования

1. Фундаментальная теорема конструирования (теорема 3.1)

Для совершенного e-исправляющего кода D в графе G:

• При e=1: возможно конструировать квазисовершенные 1-исправляющие коды в G□P3k и G□C3k
• При e≥2: возможно конструировать квазисовершенные e-исправляющие коды в G□P3 и G□C3

Метод конструирования:

D' = D ⊕ {1}

где ⊕ обозначает прямое произведение множеств.

2. Трёхмерное расширенное конструирование (теорема 3.2)

Для совершенного 2-исправляющего кода D1 в Pm□Pn конструируется квазисовершенный 2-исправляющий код в Pm□Pn□P6k-2:

Этапы:

1. Определить D2 = (0,3) + D1 (сдвинутый код)
2. Конструировать D = (D1⊕{0}) ∪ (D2⊕{3})
3. Расширить на большие размерности: C = ⋃(i=0 to k-1)(D1⊕{6i} ∪ D2⊕{6i+3})

3. Конструирование циклических произведений

Теорема 3.6: Конструирование квазисовершенного 1-исправляющего кода в C3□C6□C4k

D0 = {(0,0), (1,2), (2,4)}
D1 = {(2,1), (0,3), (1,5)}
C = ⋃(i=0 to k-1)(D0⊕{4i} ∪ D1⊕{4i+2})

Технические инновации

1. Послойная стратегия конструирования: Разложение высокомерного графа на низкомерные слои с применением известных совершенных кодов в каждом слое
2. Техника сдвига: Обеспечение минимального расстояния между кодовыми словами в разных слоях посредством надлежащих операций сдвига
3. Периодическое расширение: Реализация конструирования произвольного размера путём периодического повторения базовых строительных блоков

Экспериментальная установка

Методы верификации

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

1. Теоретическая верификация: Доказательство минимального расстояния и радиуса покрытия конструируемого кода
2. Компьютерная верификация: Для сложных случаев (например, некоторые параметры в теореме 4.4) используется компьютерный поиск

Критерии оценки

• Минимальное расстояние: Минимальное расстояние между любыми двумя кодовыми словами
• Радиус покрытия: Максимальное расстояние от любой вершины до ближайшего кодового слова
• Квазисовершенность: Верификация условия радиус покрытия = способность исправления + 1

Экспериментальные результаты

Основные результаты

1. Результаты теоремы 3.1:
   • При e=1 успешно построены квазисовершенные 1-исправляющие коды в G□P3k и G□C3k
   • При e≥2 успешно построены квазисовершенные e-исправляющие коды в G□P3 и G□C3
2. Результаты трёхмерного конструирования:
   • Построение квазисовершенных 2-исправляющих кодов в Pm□Pn□P6k-2 (теорема 3.2)
   • Построение квазисовершенных 2-исправляющих кодов в Cm□Cn□C6k (следствие 3.3)
3. Конкретные примеры:
   • Совершенный 1-исправляющий код в C6□C6□C2 (теорема 4.2)
   • Квазисовершенный 1-исправляющий код в C3□C6□C4k (теорема 3.6)

Сводная таблица конструирования

Анализ конкретных примеров

Статья предоставляет несколько конкретных примеров конструирования, таких как:

• На рисунке 1 показан квазисовершенный 1-исправляющий код в P4□P4□P4
• На рисунках 2-6 показаны конструирования квазисовершенных кодов в различных циклических произведениях

Связанные работы

1. Теория совершенных кодов: Основана на теории совершенных управляющих множеств Ливингстона и Стаута
2. Коды в метрике Ли: Направление исследований, мотивированное гипотезой Голомба-Велча
3. Конструирование квазисовершенных кодов: Работы АльБдаиви и других по конструированию в метрике Ли
4. Коды в теории графов: Теория исправляющих ошибки кодов на основе графовых расстояний

Заключение и обсуждение

Основные выводы

1. Успешно установлены систематические методы конструирования квазисовершенных кодов на основе совершенных кодов
2. Предоставлены явные конструирования квазисовершенных кодов для различных декартовых произведений графов
3. Расширены известные результаты о существовании квазисовершенных кодов

Ограничения

1. Методы конструирования зависят от существования совершенных кодов в базовом графе
2. Конструирование для некоторых диапазонов параметров требует компьютерной верификации
3. Применимость методов конструирования ограничена для общих декартовых произведений графов

Направления будущих исследований

1. Определение, для каких целых чисел n и графов G2 возможно конструировать квазисовершенные коды в декартовом произведении G1 с n копиями G2
2. Идентификация всех значений параметров (m,n,l), при которых Cm□Cn□Cl допускает квазисовершенный код
3. Обобщение на более широкие классы графов и метрические пространства

Глубокая оценка

Преимущества

1. Теоретическая строгость: Все конструирования имеют полные математические доказательства
2. Систематический подход: Предоставлена единая база конструирования
3. Практическая ценность: Методы конструирования применимы к различным конкретным случаям
4. Визуальная поддержка: Обширные иллюстрации помогают понять процесс конструирования

Недостатки

1. Ограничения области применения: Методы в основном применимы к декартовым произведениям путей и циклов
2. Вычислительная сложность: Верификация некоторых конструирований требует значительных вычислений
3. Оптимальность: Не обсуждается оптимальность построенных кодов

Влияние

1. Теоретический вклад: Предоставлены новые методы конструирования для теории квазисовершенных кодов
2. Перспективы применения: Потенциальное применение в сетевом кодировании и распределённом хранении данных
3. Масштабируемость: Методы конструирования служат основой для дальнейших исследований

Применимые сценарии

1. Сценарии, требующие развёртывания исправляющих ошибки кодов в регулярных сетевых топологиях
2. Контроль ошибок в многомерных сетях и сетях на торе
3. Проблемы размещения отказоустойчивых ресурсов в распределённых системах

Библиография

Статья цитирует 33 связанные работы, включая:

• Golomb & Welch (1970): Пионерские работы по совершенным кодам в метрике Ли
• AlBdaiwi & Bose (2003): Квазисовершенные коды расстояния Ли
• Livingston & Stout (1990): Теория совершенных управляющих множеств
• Множество недавних исследований по конструированию квазисовершенных кодов

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