RUS  ENG
Full version
JOURNALS // Diskretnyi Analiz i Issledovanie Operatsii // Archive

Diskretn. Anal. Issled. Oper., 2017 Volume 24, Issue 2, Pages 5–17 (Mi da866)

This article is cited in 2 papers

On distance Gray codes

I. S. Bykova, A. L. Perezhoginab

a Novosibirsk State University, 2 Pirogov St., 630090 Novosibirsk, Russia
b Sobolev Institute of Mathematics, 4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia

Abstract: A Gray code of size $n$ is a cyclic sequence of all binary words of length $n$ such that two consecutive words differ exactly in one position. We say that the Gray code is a distance code if the Hamming distance between words located at distance $k$ from each other is equal to $d$. The distance property generalizes the familiar concepts of a locally balanced Gray code. We prove that there are no distance Gray codes with $d=1$ for $k>1$. Some examples of constructing distance Gray codes are given. For one infinite series of parameters, it is proved that there are no distance Gray codes. Tab. 5, bibliogr. 9.

Keywords: $n$-cube, Hamiltonian cycle, Gray code, uniform Gray code, antipodal Gray code.

UDC: 519.17

Received: 19.05.2016
Revised: 16.09.2016

DOI: 10.17377/daio.2017.24.545


 English version:
Journal of Applied and Industrial Mathematics, 2017, 11:2, 185–192

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024