Gray-Codes with few tracks: Torsten Sillke, BI, 1 March 93
=========================== (a question of M. Brandestini)
Code for n=2:
0 0 1 1
0 1 1 0 (the code words are the collomns)
as you see, the rows are cyclic shifts.
If rows are cyclic shifts, they count as one track.
Code for n=3:
0 0 0 0 1 1 1 1
0 0 1 1 1 1 0 0
0 1 1 0 0 1 1 0
as you see, the first two rows are cyclic shifts.
This property has the reflected Gray code for all n.
But the other rows are different.
Codes for n=4:
0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0
0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0
0 0 0 0 1 1 1 0 0 1 1 0 0 1 1 1
0 1 1 0 0 1 1 1 0 0 0 0 1 1 1 0
the first and second as the third and forth row are cyclic shifts.
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0
0 0 1 1 1 1 0 0 0 1 1 0 0 1 1 0
0 1 1 0 0 1 1 0 0 0 1 1 1 1 0 0
the first and second as the third and forth row are cyclic shifts.
For n=4 this are the essential different solutions with only two
different tracks (rows).
---------------------------------------------------------------------
Question: How many tracks do you need to construct a n-bit Gray code?
---------------------------------------------------------------------
Lemma: A Gray code with k-bits can be extended with 2^i Bits
through one track, if 0 <= i <= k-1.
Proof by example: expansion of a 4-bit code with 4 bits.
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 the first 4 rows are the old code
0 0 1 1 1 1 0 0 0 1 1 0 0 1 1 0 set 0 -> 0000000000000000
0 1 1 0 0 1 1 0 0 0 1 1 1 1 0 0 and 1 -> 1111111111111111
w W x X y Y z Z w W x X y Y z Z
x X y Y z Z w W x X y Y z Z w W
y Y z Z w W x X y Y z Z w W x X
z Z w W x X y Y z Z w W x X y Y
the parts w to z are a 4 bit Gray code and W to Z their reflection.
The code begins with the null word. There are other possebilities as
you see for the above 4 bit codes, which are extendions of the 2 bit
code.
w.W = 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0.0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0
x.X = 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0.0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0
y.Y = 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0.0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0
z.Z = 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1.1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0
This lemma gives 1-track codes for 1, 2 bit,
2-track codes for 3, 4 bit,
3-track codes for 5, 6, 7, 8 and 12 bit.
Question: Are there Gray-codes, where a track is not used a power of two?
Application:
This is interesting for analog-digital-converters (goniometer),
which can be build more compact, if they had fewer tracks.
Update 1997:
------------
In the meantime several constructions for single track Gray codes
have been developed. But these don't have length 2^n.
Restrictions for Singlee-Track Gray Codes:
- It is necessary that 2n | period.
Maximal periods which have be constructed:
n period
1 2
2 4
3 6
4 8*
5 30
6 60
7 126
8 240*
The stared entries don't match the upper bound by the restriction above.
The first open case is n=8.
?????????????????????????????????????????????????????????????????????
??? There may be a single track gray code for n=8 and length 256. ???
?????????????????????????????????????????????????????????????????????
References:
T. Etzion, K. G. Paterson;
Near Optimal Single-Track Gray Codes,
IEEE Trans. on Information Theory, 42:3 (May 1996) 779-789
Zbl 857.94006
(Zbl Review: Single-track Gray codes are a special class of Gray codes
which have advantages over conventional Gray codes in certain quantization
and coding applications. The problem of constructing high period
single-track Gray codes is considered. Three iterative constructions are
given, along with a heuristic method for obtaining good seed-codes.
In combination, these yield many families of very high period single-track
Gray codes. In particular, for $m \ge 3$, length $n=2\sp m$,
period $2\sp n-2n$ codes are obtained.
Keywords: Gray codes; quantization)
A. P. Hiltgen, K. G. Paterson, M. Brandestini;
Single-track Gray codes,
IEEE Trans. on Information Theory, 42:5 (1996) 1555-1561
Zbl 857.94007
(Zbl Review: A particular class of Gray codes, called single-track Gray
codes, is introduced. These codes have advantages over conventional
Gray codes in certain practical applications. A simple construction
for single-track Gray codes is given and it is shown how to obtain such
codes for a large range of parameters of practical interest.
Keywords: encoding; angle measurement; quantization; Gray codes)
----------------------------------------------------------------------
mailto:sillke@mathematik.uni-bielefeld.de