Оптимальные двоичные коды из $\mathcal{C}_{D}$-кодов над некоммутативным кольцом

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

• ID статьи: 2510.09057
• Название: Optimal binary codes from $\mathcal{C}_{D}$-codes over a non-chain ring
• Авторы: Ankit Yadav, Ritumoni Sarma, Anuj Kumar Bhagat (Индийский технологический институт Дели)
• Классификация: cs.IT math.IT
• Дата публикации: 10 октября 2025 г. (препринт arXiv)
• Ссылка на статью: https://arxiv.org/abs/2510.09057v1

Аннотация

В данной работе исследуются коды подполя $\mathcal{C}_{D}^{(2)}$ из $\mathcal{C}_D$-кодов над некоммутативным кольцом $\mathcal{R} := \mathbb{F}_2[x,y]/\langle x^2, y^2, xy-yx\rangle$, где множество определения $D$ строится на основе симплициальных комплексов. Авторы определяют распределение веса Хэмминга и параметры $\mathcal{C}_D^{(2)}$ для различных $D$, выявляют несколько бесконечных семейств кодов, достигающих границы расстояния, и предоставляют достаточные условия для того, чтобы эти коды были минимальными и самоортогональными. Кроме того, из построенных двойных кодов получены два семейства сильно регулярных графов.

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

Предпосылки проблемы

1. Значимость кодов, оптимальных по расстоянию: Для фиксированных параметров $n$ и $k$ коды, оптимальные по расстоянию, достигают максимально возможной способности обнаружения и исправления ошибок, что является одной из основных целей теории кодирования.
2. Существующие методы конструирования:
   • Отображение Грея: построение кодов над конечными полями из кодов над конечными кольцами
   • Симплициальные комплексы: впервые введены Chang и Hyun для конструирования оптимальных линейных кодов
3. Ограничения предыдущих работ: Shi и Li в работе 27 исследовали распределение веса Ли $\mathcal{C}_D$-кодов над кольцом $\mathcal{R}$ и их образы при отображении Грея, но не рассматривали коды подполя.

Мотивация исследования

1. Улучшение параметров: Доказать, что двоичные коды подполя $\mathcal{C}_D^{(2)}$ имеют лучшие параметры по сравнению с двоичными образами Грея из работы 27
2. Совершенствование теории: Предоставить теоретические условия минимальности и самоортогональности для семейств кодов, основанных на симплициальных комплексах
3. Расширение приложений: Применить двойные коды к конструированию сильно регулярных графов

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

1. Определение распределения веса Хэмминга кодов подполя: Полная характеризация распределения веса $\mathcal{C}_D^{(2)}$ для различных множеств определения $D$, построенных на основе симплициальных комплексов
2. Конструирование нескольких семейств кодов, оптимальных по расстоянию: Выявление нескольких бесконечных семейств двоичных линейных кодов, оптимальных по расстоянию, некоторые из которых достигают границы Гризмера
3. Установление условий минимальности и самоортогональности: Предоставление достаточных условий для того, чтобы $\mathcal{C}_D^{(2)}$ были минимальными и самоортогональными кодами
4. Доказательство преимущества параметров: Демонстрация того, что коды подполя имеют лучшие параметры по сравнению с кодами образа Грея
5. Конструирование сильно регулярных графов: Использование двойных проективных кодов для конструирования двух семейств сильно регулярных графов

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

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

Исследование линейных кодов $\mathcal{C}_D$ над кольцом $\mathcal{R} = \mathbb{F}_2[x,y]/\langle x^2, y^2, xy-yx\rangle$, где:

• Множество определения $D$ строится на основе симплициальных комплексов
• Цель состоит в анализе свойств двоичного кода подполя $\mathcal{C}_D^{(2)}$

Теоретическая база

1. Структура кольца и базис

Каждый элемент кольца $\mathcal{R}$ может быть представлен как $a + bu + cv + duv$, где $a,b,c,d \in \mathbb{F}_2$, $u = x + \langle x^2, y^2\rangle$, $v = y + \langle x^2, y^2\rangle$.

Выбирается $\mathbb{F}_2$-базис $\mathcal{B} = \{b_1 = 1+u+v, b_2 = u+v, b_3 = u, b_4 = uv\}$.

2. Конструирование кода подполя

Использование $\mathbb{F}_2$-значного отображения следа $\tau: \mathcal{R} \to \mathbb{F}_2$: $\tau(a + bu + cv + duv) = a + b + c + d$

Теорема 3.3: Если $D = b_1D_1 + b_2D_2 + b_3D_3 + b_4D_4$, то $\mathcal{C}_D^{(2)}$ порождается матрицей: $G^{(2)} = \begin{pmatrix} G_1 + G_4 \\ G_3 \\ G_2 \\ G_1 \end{pmatrix}$

3. Формула вычисления веса

Для $(x_1,x_2,x_3,x_4) \in (\mathbb{F}_2^m)^4$ имеет место: $\text{wt}(c_D^{(2)}(x_1,x_2,x_3,x_4)) = \frac{|D|}{2} - \frac{1}{2}\sum_{d_1 \in D_1} (-1)^{(x_1+x_4)d_1} \sum_{d_2 \in D_2} (-1)^{x_3d_2} \sum_{d_3 \in D_3} (-1)^{x_2d_3} \sum_{d_4 \in D_4} (-1)^{x_1d_4}$

Основные технические инновации

1. Техника булевых функций

Определение булевой функции $\psi(\cdot | Y): \mathbb{F}_2^m \to \mathbb{F}_2$: $\psi(x_1 | Y) = \prod_{i \in Y}(1-\alpha_i) = \begin{cases} 1, & \text{если } \text{Supp}(x_1) \cap Y = \emptyset \\ 0, & \text{если } \text{Supp}(x_1) \cap Y \neq \emptyset \end{cases}$

2. Применение симплициальных комплексов

Использование свойств симплициального комплекса $\Delta_X$ и его дополнения $\Delta_X^c$: $\sum_{t \in \Delta_Y} (-1)^{x_1 t} = 2^{|Y|}\psi(x_1 | Y)$$\sum_{t \in \Delta_Y^c} (-1)^{x_1 t} = 2^m\delta_{0,x_1} - 2^{|Y|}\psi(x_1 | Y)$

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

Теоретическая верификация

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

Примеры верификации

Пример 4.8: $m=4$, $X=Y=Z=\emptyset$, $W=\{1,2,3\}$

• Получен двойной оптимальный двоичный линейный код с параметрами $[120, 7, 60]$
• Перечислитель весов: $x^{120} + 15x^{56}y^{64} + 112x^{60}y^{60}$
• Код является одновременно минимальным и самоортогональным, позволяет построить квантовый код коррекции ошибок $[[120, 106, 3]]$

Результаты экспериментов

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

Теорема 4.2 дает параметры кодов для 6 различных множеств определения:

1. Одинарные коды: $D = b_1\Delta_X + b_2\Delta_Y + b_3\Delta_Z + b_4\Delta_W$
   • Параметры: $[2^{|X|+|Y|+|Z|+|W|}, |X|+|Y|+|Z|+|W|, 2^{|X|+|Y|+|Z|+|W|-1}]$
   • Условие оптимальности по расстоянию: $|X|+|Y|+|Z|+|W| \geq 2$
2. Двойные коды: $D = b_1\Delta_X^c + b_2\Delta_Y + b_3\Delta_Z + b_4\Delta_W$ ($|X| < m$)
   • Параметры: $[(2^m-2^{|X|})2^{|Y|+|Z|+|W|}, m+|Y|+|Z|+|W|, (2^m-2^{|X|})2^{|Y|+|Z|+|W|-1}]$
   • Достигают границу Гризмера, оптимальны по расстоянию
3. Четверные коды: $D = b_1\Delta_X^c + b_2\Delta_Y^c + b_3\Delta_Z + b_4\Delta_W$
   • Параметры: $[(2^m-2^{|X|})(2^m-2^{|Y|})2^{|Z|+|W|}, 2m+|Z|+|W|, (2^m-2^{|X|}-2^{|Y|})2^{m+|Z|+|W|-1}]$
   • Условие оптимальности по расстоянию: $2^{|X|+|Y|+|Z|+|W|} \leq m+|Z|+|W|+\min\{|X|,|Y|\}$

Условия минимальности и самоортогональности

Теорема 4.7 предоставляет достаточные условия:

• Самоортогональность: когда вес каждого кодового слова кратен 4 (с использованием теоремы 2.2)
• Минимальность: когда $\frac{\text{wt}_{\min}}{\text{wt}_{\max}} > \frac{1}{2}$ (с использованием леммы 2.3)

Конструирование сильно регулярных графов

Теоремы 4.12 и 4.13 конструируют два семейства сильно регулярных графов:

• Первое семейство с параметрами: $(2^{m+|Y|+|Z|+|W|}, (2^m-2^{|X|})2^{|Y|+|Z|+|W|}, (2^m-2^{|X|+1})2^{|Y|+|Z|+|W|}, (2^m-2^{|X|})2^{|Y|+|Z|+|W|})$
• Второе семейство с параметрами: $(2^{m+|Y|+|Z|+|W|}, 2^{|X|+|Y|+|Z|+|W|}-1, 2^{|X|+|Y|+|Z|+|W|}-2, 0)$

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

Историческое развитие

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

Позиционирование вклада данной работы

• Расширение работы Shi и Li, переход от образов Грея к кодам подполя
• Предоставление более систематической теоретической базы
• Доказательство преимущества параметров и оптимальности

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

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

1. Успешное конструирование нескольких семейств двоичных линейных кодов, оптимальных по расстоянию
2. Установление теоретических критериев минимальности и самоортогональности
3. Доказательство преимущества параметров кодов подполя по сравнению с кодами образа Грея
4. Реализация приложений от теории кодирования к теории графов

Ограничения

1. Рассмотрены только симплициальные комплексы с единственным максимальным элементом
2. Расширение на комплексы с двумя максимальными элементами приводит к чрезмерно сложным вычислениям
3. Некоторые условия оптимальности по расстоянию являются довольно строгими

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

1. Исследование кодов подполя $\mathcal{C}_D$-кодов над различными алфавитами
2. Изучение симплициальных комплексов с двумя максимальными элементами
3. Поиск более общих условий оптимальности по расстоянию

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

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

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

Недостатки

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

Влияние

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

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

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

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

Статья цитирует 35 связанных работ, основные из которых:

• 27 Работа Shi, M. и Li, X. (прямое расширение в данной работе)
• 9 Основополагающая работа Chang, S. и Hyun, J.Y. по симплициальным комплексам
• 13 Классическая работа Hammons и др. по отображению Грея
• 12 Фундаментальная теория Griesmer о границах длины кода