(original) (raw)

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 mge3m \ge 3mge3, length n=2spmn=2\sp mn=2spm, period 2spn−2n2\sp n-2n2spn−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