IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 45, NO.
7, NOVEMBER 1999 2383
The Structure of Single-Track Gray Codes
Moshe Schwartz and Tuvi Etzion, Senior Member, IEEE
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
2n codewords when n is a power of 2. This implies that the
known codes with 2n
���� 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 k-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-order words and the full-order self-dual words.
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 distinct
necklaces and a merging method for cyclic Gray codes based
on necklaces representatives.
Index Terms—Cyclic Gray codes, feedback shift-register, linear
complexity, necklaces, self-dual sequences, single-track codes.