| Abstract: |
Single-track Gray codes are cyclic Gray codes with
codewords of length $n$, such that all the
$n$ tracks which correspond to the $n$ distinct
coordinates of the codewords are cyclic shifts of the
first track. We investigate the structure of such binary
codes and show that there is no such code with $2^n$
codewords when $n$ is a power of 2. This implies that the known
codes with $2^n -2n$ codewords, when $n$ is a power of 2,
are optimal. This result is then generalized to codes
over $GF(p)$, where $p$ is a prime. A subclass of
single-track Gray codes, called single-track Gray codes
with evenly spaced heads, is also defined. All known
systematic constructions for single-track Gray codes
result in codes from this subclass. We investigate this
class and show it has a strong connection with two
classes of sequences, the full-period necklaces and the
full-period self-dual necklaces. We present an
iterative construction for binary single-track Gray codes
which are asymptotically optimal if an infinite family of
asymptotically optimal seed-codes exists. This construction
is based on an effective way to generate a large set
of nonequivalent necklaces and a merging method for
cyclic Gray codes based on necklaces representatives.
|