?

Log in

single-track gray codes with evenly spaced heads - Benjamin C. Wiley Sittler [entries|archive|friends|userinfo]
Benjamin C. Wiley Sittler

[ website | bsittler ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

single-track gray codes with evenly spaced heads [Jan. 3rd, 2009|10:52 am]
Benjamin C. Wiley Sittler
[Tags|, , ]

Gray codes (so-called, despite having been used by Émile Baudot in the original Baudot code and its evolution, the International Telegraph Alphabet No. 1, many decades prior to Gray's patent) are good for many encoding applications because any two adjacent positions differ by exactly one bit, and the encoder wheels are trivial to construct by binary reflection. However, you can do better — by using a specially chosen sensor arrangement one can use a single encoder wheel which is sensed simultaneously at several points and decodes to a Gray code. The particular case where all the heads are evenly radially spaced is is called a single-track Gray code with evenly spaced heads — see Moshe Schwartz and Tuvi Etzion's The Structure of Single-Track Gray Codes for a good discussion and definition of this term.

Anyhow, I became curious about these codes yesterday, and wrote and refined a Python program to find them. Here are some of the codes it found: (hover over a block of codes to see the command used to find it)

=======V=======V=======V=======V=======V=======V
----------xxx------xxxx-----xxxxx-----xxxxxxxxxx
-----------xxxxxx----xxxxx----xxxxxx---xxxxxxxxx
-----------xxxx-----xxxxx----xxxxx----xxxxxxxxxx
-----------xxx------xxxxx----xxxxx-----xxxxxxxxx
-----------xx----xxxxx----xxxxxxxxxx---xxxxxxxxx
------------xxxxxx-----xx-----xxxxx--xxxxxxxxxxx
------------xxxxx----xxxxx----xxxxx----xxxxxxxxx
------------xxxxx------xxx----xxxxx--xxxxxxxxxxx
------------xxx-------xxxxxxxxxxx--xxxxxxx---xxx
------------xx----xxxxx----xxxxxxxxxx----xxxxxxx
------------xx-----xxxx--xxxxxxxxxxxx-----xxxxxx
------------xx-----xxxx---xxxxxxxxxxx----xxxxxxx
------------xx-----xxxx---xxxxxxx----xxxxxxxxxxx
------------xx-------xxxxxxxxxxxx--xxxx---xxxxxx
------------xx-------xxxxxxxxxx---xxxxxxx--xxxxx
-------------xxxxx--xxxxxxxxxxx----xxx---xxxxxxx
-------------xxxxx-------xx----xxxxx--xxxxxxxxxx
-------------xxxx--xxxxxxxxxxxx-----xx----xxxxxx
-------------xxxx---xxxxxxxxxxx----xxx----xxxxxx
-------------xxxx------xxxx---xxxx--xxxxxxxxxxxx
-------------xx--xxxxxxxxx--xxxxxxxxxx-----xxxxx
-------------xx---xxxxxxx--xxxxxxxxxxx------xxxx
-------------xx---xxxxxxx---xxxxxxxxxx-----xxxxx
-------------xx----xxx----xxxxxxx---xxxxxxxxxxxx
-------------xx-----xxxxxxxxxxxxx--xxx----xxxxxx
-------------xx-----xxxxx--xxxxxxx----xxxxxxxxxx
--------------xxxx--xxxxxxxxxxxxx----xx----xxxxx
--------------xxxx--xxxxx----xxxxxxxxxx----xxxxx
--------------xxxx---xxxx--xxxxxxxxx---xxxxxxxxx
--------------xxxx---xxxx---xxxxxxx----xxxxxxxxx
--------------xxxx---xx-----xxxxxxxxxxxxx--xxxxx
--------------xxxx-----xxxx--xxxx---xxxxxxxxxxxx
--------------xxxx-----xx---xxxxxxx--xxxxxxxxxxx
--------------xxxx-------xxx---xxxx--xxxxxxxxxxx
--------------xxx--xxxxxxx---xxxxxxxxxx-----xxxx
--------------xxx---xxxxxxxxxxxxxx-----xxxx--xxx
--------------xxx---xxxxxxxxxxx----xx-----xxxxxx
--------------xxx---xxx---xxxxxxxxx--xxxxxxxxxxx
--------------xxx---xxx----xxxxxxx---xxxxxxxxxxx
--------------xxx----xxxxxxxxxxxxxx----xxx--xxxx
--------------xxx----xxxxx--xxxxxxx----xxxxxxxxx
--------------xxx----xx----xxxxxxx--xxxxxxxxxxxx
---------------xxxx---xxxx---xxxxxxx-----xxxxxxx
---------------xxxx------xxx--xxxx---xxxxxxxxxxx
---------------xxx--xxxxx----xxxxxxxxx-----xxxxx
---------------xx--xxxxxxx---xxxxxxxxx------xxxx
---------------xx---xx-----xxxxxxx---xxxxxxxxxxx

=====V=====V=====V=====V=====V=====V
----------xxxx---xxxxxxxx--xxxxxxxxx
----------xxx--xxxxxxxx---------xxxx
-----------xxxx----xxxxxxx--xxxxxxxx
-----------xxx--------xxxxxxxxx--xxx
-----------xx---xxxxxxxxxx-------xxx
-----------xx--------xxxxx--xxxxxxxx
-------------xxx----xxxxxxx--xxxxxxx
-------------xx--xxxxx----xxxxxxxxxx
--------------xxx--xxx-----xxxxxxxxx
--------------xxx----xxxxxxx---xxxxx
--------------xxx-----xxxxxxxxx--xxx
--------------xx---xxxx----xxxxxxxxx
--------------xx-----xxxxxxxx--xxxxx
---------------xx--xxxxxxxxx----xxxx
---------------xx--xxx----xxxxxxxxxx
---------------xx---xxxxxxxx---xxxxx
---------------xx---xxxxx---xxxxxxxx
----------------xxxx---xx--xxxxxxxxx
----------------xxx--xxxxx---xxxxxxx
----------------xxx--xx---xxxxxxxxxx

=====V=====V=====V=====V=====V
--------xxx----xxxx---xxxxxxxx
--------xx-----xxxxxxxx--xxxxx
---------xxxx---xxxx---xxxxxxx
---------xxxx----xxx--xxxxxxxx
---------xx--xxxxxxxxx----xxxx
---------xx---xxxxxxxx---xxxxx
---------xx---xxxxx---xxxxxxxx
----------xxxx---xx--xxxxxxxxx
----------xxx--xxxxx---xxxxxxx
----------xxx--xx---xxxxxxxxxx

===V===V===V===V===V
-------xxx---xxxxxxx
-------xx-----xxxxxx
---------xx---xxxxxx
----------xxx--xxxxx

=V=V=V
---xxx

=V
-x

(Yes, I have written about Gray codes previously.)

edit: updated the program with a further heuristic and added results for 36 and 48 positions; also, the Gray code page at quirkfactory includes a 7-head, 126-position single-track Gray code.

edit: updated with an even better heuristic; results can now be computed even for 126-position single-track Gray codes in reasonable time.

linkReply

Comments:
[User Picture]From: kragen
2009-01-04 12:31 am (UTC)
That's fascinating! I never thought of that before. If you have motion, you can do better still: use a binary chain code and a single read head.
(Reply) (Thread)
[User Picture]From: bsittler
2009-01-04 04:09 am (UTC)
yes. it seems like Gray codes are mostly used for encoding position or angle when cold-start and/or non-moving detection is needed.

the Gray code page at quirkfactory includes a 7-head, 126-position single-track Gray code, and according to Wikipedia a 9-head, 360-position single-track Gray code was published in the paper which introduced such codes back in the mid-1990s. Unfortunately I can't find that paper or the sequence online anywhere, and so far my algorithm is not good enough to find even the 126-position code in reasonable runtime.
(Reply) (Parent) (Thread)
[User Picture]From: bsittler
2009-01-04 04:10 am (UTC)
oh, and note that "head" and "bit" are interchangeable here.
(Reply) (Parent) (Thread)
[User Picture]From: bsittler
2009-01-12 01:18 am (UTC)
oh, and it is fast enough now — i use a different method based on searching the space of all Gray codes matching the constraints of the equal head spacing.
(Reply) (Parent) (Thread)
From: (Anonymous)
2012-10-07 02:42 am (UTC)
Just found this, very impressive !
The multiple solutions allow choosing of best-strength mechanical one.

I've coded 36 or 48 STGC conversions into a small PLD, but the python does not generate 25, 42, 54, or 60 Periods,
it does seem to do 70,77,84.
I think 60 is valid, as I've seen that mentioned elsewhere, not so sure about 25,42,54 ?
(Reply) (Thread)
[User Picture]From: bsittler
2014-07-18 02:30 am (UTC)
It might be a bug in my code. I'm not sure, I haven't touched it in years (since I posted, basically) and don't remember whether its heuristics cause it to overlook valid solutions.

Were you interested in solutions with non-evenly-spaced heads?
(Reply) (Parent) (Thread)