Generalized Gray codes with prescribed ends

Abstract: An

n

-bit Gray code is a sequence of all

n

-bit strings such that consecutive strings differ in a single bit. It is well-known that given

, an

n

-bit Gray code between

a l p h a

and

exists iff the Hamming distance

of

a l p h a

and

is odd. We generalize this classical result to

k

pairwise disjoint pairs

: if

is odd for all

i

and

k < n

, then the set of all

n

-bit strings can be partitioned into

k

sequences such that the

i

-th sequence leads from

a l p h a_{i}

to

and consecutive strings differ in a single bit. This holds for every

n > 1

with one exception in the case when

n = k + 1 = 4

. Our result is optimal in the sense that for every

n > 2

there are

n

pairwise disjoint pairs

with

odd for which such sequences do not exist.

Recommendations

Cites Work

Cited In (20)

This page was built for publication: Generalized Gray codes with prescribed ends