Об афинно несистематических кодах 1

Малюгин С.А.
Институт Математики СО РАН, Новосибирск

Пусть $\{0,1\}^n$ -- векторное пространство над полем из двух элементов $0$ и $1$. Сумму векторов ${\bf u},{\bf v}\in\{0,1\}^n$ обозначим через ${\bf u}\oplus {\bf v}$. Число ненулевых координат вектора ${\bf u}$ называется его весом. Совершенный код $C\subset\{0,1\}^n$ длины $n=2^k-1$ называется систематическим, если существует $k$-элементное подмножество $K\subset \{1,\dots ,n\}$ такое, что любые два неравных вектора ${\bf u},{\bf v}\in C$ различаются хотя бы в одной координате с номером, не принадлежащим $K$. В противном случае код $C$ называется несистематическим. В коде Хемминга $H^n$ рассмотрим подпространство $R_i$, порожденное всеми векторами веса 3 с $i$-й координатой, равной единице. Всевозможные смежные классы вида $R_i^{\bf u}=R_i\oplus {\bf u}$ $({\bf u}\in H^n)$ называются $i$-компонентами кода $H^n$, $i=1,\dots ,n$. Одна из основных конструкций нелинейных кодов состоит в том, что в коде $H^n$ сдвигаются по координате $i$ некоторые его попарно непересекающиеся $i$-компоненты. Хорошо известно, что код Хемминга $H^n$ -- систематический, но довольно долго стоял вопрос о существовании несистематических нелинейных совершенных кодов. Такие коды длины $n\geq 255$ были впервые построены в [1] сдвигами $i$-компонент кода $H^n$ для $i$, пробегающим все значения из $\{1,\dots ,n\}$. В [2] предложена модификация конструкции [1], позволяющая строить такие коды для всех $n\geq 63$. Для $n=15$ и $n=31$ несистематические коды были найдены с помощью компьтера, см. [2, 3]. В [4] получен критерий, с помощью которого можно устанавливать систематичность или несистематичность нелинейных кодов, получаемых из кода Хемминга сдвигами его непересекающихся компонент. В частности доказано, что для построения несистематического кода любой длины $n\geq 15$, достаточно сдвинуть в коде Хемминга всего семь непересекающихся компонент. Этот результат дает ответ на вопрос, поставленный К. Т. Фелпсом и М. Ли-Ваном [2].


Определение 1. Совершенный код $C$ длины $n=2^k-1$ называется афинно систематическим, если в пространстве $\{0,1\}^n$ существует $k$-мерное подпространство $L$ такое, что любой его смежный класс $L\oplus{\bf u}$ пересекается с кодом $C$ ровно по одному элементу. В противном случае код $C$ называем афинно несистематическим.


Такое усиление понятия несистематичности было предложено С. В. Августиновичем. Это свойство является афинным инвариантом кода, т. е. оно сохраняется при любых невырожденных афинных преобразованиях пространства $\{0,1\}^n$. Другими наиболее известными афинными инвариантами являются ранг кода и размерность его ядра. С. В. Августиновичем был также поставлен вопрос о существовании афинно несистематических кодов. Ответ на него дает следующая


Теорема 1. Все несистематические коды, которые получаются из кода Хемминга сдвигами семи непересекающихся компонент, являются афинно несистематическими.


Для любого $t$, $3\leq t\leq\log (n+1)$ введем более общее определение.


Определение 2. Совершенный код $C$ длины $n=2^k-1$ называем $t$-несистематическим, если для любого $t$-мерного подпространства $L\subset\{0,1\}^n$ существует смежный класс $L\oplus{\bf u}$, пересекающийся с кодом $C$ более чем по одному элементу.


При $t=k=\log (n+1)$ определения $t$-несистематичности и афинной несистематичности совпадают. Как оказалось, экстремальный случай $t=3$ тоже достижим.


Теорема 2. Пусть код $C$ длины $n$ получается из кода Хемминга сдвигами $m\leq n$ непересекающихся $i$-компонент для $i$ пробегающем $m$ различных значений. Код $C$ являются $3$-несистематическими тогда и только тогда, когда $m=n$.

Литература

1. Августинович С. В., Соловьева Ф. И. О несистематических совершенных двоичных кодах // Проблемы передачи информации. 1996. Т. 32, вып. 3. С. 47-50.
2. Phelps K. T., LeVan M. J. Nonsystematic perfect codes // SIAM J. Discrete Math. 1999. V. 12, N 1. P. 27-34.
3. Романов А. М. О несистематических совершенных кодах длины 15 // Дискрет. анализ и исслед. операций. Серия 1. 1997. Т. 4,  4. C. 75-78.
4. Малюгин С. А. Несистематические совершенные двоичные коды // Дискрет. анализ и исслед. операций. Серия 1. 2001. Т. 8,  1. C. 55-76.

Примечание

... кодах 1
Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (проект 99-01-00531) и Федеральной целевой программы ``Интеграция'' (объединенный проект АО-110).
Ваши комментарии
[SBRAS]
[Головная страница]
[Конференции]
[СО РАН]

© 2001, Сибирское отделение Российской академии наук, Новосибирск
© 2001, Объединенный институт информатики СО РАН, Новосибирск
© 2001, Институт вычислительных технологий СО РАН, Новосибирск
© 2001, Институт систем информатики СО РАН, Новосибирск
© 2001, Институт математики СО РАН, Новосибирск
© 2001, Институт цитологии и генетики СО РАН, Новосибирск
© 2001, Институт вычислительной математики и математической геофизики СО РАН, Новосибирск
© 2001, Новосибирский государственный университет
Дата последней модификации Friday, 07-Sep-2001 09:48:18 NOVST