Том 24, номер 2, 2017 г., Стр. 5-17

УДК 519.17
Быков И. С., Пережогин А. Л.
О дистанционных кодах Грея

Аннотация:
Кодом Грея размерности $n$ называется циклическая последовательность всех бинарных слов длины $n$ такая, что два соседних слова отличаются ровно в одном символе. Назовём $n$-мерный код Грея дистанционным кодом, если расстояние Хэмминга между словами, находящимися в коде на растоянии $k$, равно $d$. Свойство дистанционности обобщает известное понятие локальной равномерности кодов Грея. Доказано, что не существует дистанционных кодов Грея с параметром $d$ = 1 при $k > 1$. Приведены примеры конструкций для построения дистанционных кодов Грея. Для одной бесконечной серии наборов параметров доказано, что дистанционных кодов Грея не существует.
Табл. 5, библиогр. 7.

Ключевые слова: $n$-мерный куб, гамильтонов цикл, код Грея, равномерный код Грея, антиподальный код Грея.

DOI: 10.17377/daio.2017.24.545

Быков Игорь Сергеевич ²
Пережогин Алексей Львович ^1,2
1. Институт математики им. С. Л. Соболева,
пр. Коптюга, 4, 630090 Новосибирск, Россия
2. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: patrick.no10@gmail.com, pereal@math.nsc.ru

Статья поступила 19 мая 2016 г.
Исправленный вариант — 16 сентября 2016 г.

Литература

[1] Быков И. С. О локально равномерных кодах Грея // Дискрет. анализ и исслед. операций. 2016. Т. 23, № 1. С. 51–64.

[2] Евдокимов А. А. О нумерации подмножеств конечного множества // Методы дискретного анализа в решении комбинаторных задач: Сб. науч. тр. Новосибирск: Ин-т математики СО АН СССР, 1980. Вып. 34. С. 8–26.

[3] Пережогин А. Л. Об автоморфизмах циклов в $n$-мерном булевом кубе // Дискрет. анализ и исслед. операций. 2007. T. 14, № 3. С. 67–79.

[4] Chang G. J., Eu S.-P., Yeh C.-H. On the $(n, t)$-antipodal Gray codes // Theor. Comput. Sci. 2007. Vol. 374, No. 1–3. P. 82–90.

[5] Goddyn L., Gvozdjak P. Binary Gray codes with long bit runs // Electron. J. Comb. 2003. Vol. 10, No. R27. P. 1–10.

[6] Goddyn L., Lawrence G. M., Nemeth E. Gray codes with optimized run lengths // Util. Math. 1988. Vol. 34. P. 179–192.

[7] Killian C., Savage C. Antipodal Gray codes // Discrete Math. 2002. Vol. 281. P. 221–236.

[8] Knuth D. E. The art of computer programming. Reading, MA: Addison- Wesley, 2004.

[9] Savage C. A survey of combinatorial Gray codes // SIAM Rev. 1996. Vol. 39, No. 4. P. 605–629.