Hacker News Reader

Comment by rflrob | Hacker News Reader

Am I missing something here, or is it only possible to easily generate Gray codes (or a similar Hamming distance 1 code if Gray refers specifically to a reflection generated code) for 2^n positions? Is there a way to do it for 12 positions like the article seems to mention? Or an odd number?

View on HN

My student, Jessica Fan, and I published a paper in the Allerton Conference in October 2015 on just this question.

You can create a Gray code for exactly the numbers 0 to n-1, for any n, by the following steps: 1. Create the binary reflected Gray code for the next higher power of 2. 2. Take just the first n numbers of that binary reflected Gray code. 3. Bitwise exclusive-or each of these n numbers in the Gray code with the binary representation of floor(n/2) (i.e., n shifted right by one bit).

To create a cyclic Gray code for exactly the numbers 0 to n-1, n must be even. (It's easy to prove that you cannot get a cyclic Gray code for odd n.) 1. Generate the Gray code for 0 to n/2-1, as above. 2. Concatenate the reflection of that Gray code to itself. 3. Shift each of the n numbers you now have left by one bit. The first half gives you all the even numbers 0 to n-2, with the Gray-code property. 4. Put a 1 in the least significant bit in the second half The second half gives you all the odd numbers 1 to n-1, again with the Gray-code property.

The whole sequence gives you 0 to n-1, with the Gray-code property, and it's cyclic.

If you'd like a PDF of the paper, email me: thc@cs.dartmouth.edu.

Tom Cormen Professor of Computer Science Dartmouth College

Thank you for you post, and for your fine book on algorithms.

Any sequence has 2n codes.

Example with 6:

Proof: Adjacent gray codes have hamming distance 1, so the graph of gray codes is cycle on a hypercube. All cycles on a hypercube graph are even, so every sequence of gray codes is even.

Ah, I was waiting for somebody to point out the wonderful math behind this!

Or rather, I was about to post about hypercubes and cycles myself :D

An odd number of positions is impossible because if your first position has an even number of 1's then your last position must have an odd number of 1's.

All even numbers should be possible though. For example, here is 6 positions: 000, 001, 011, 111, 110, 100 - and this strategy can generalize to any even number.

I had a go and worked out a Gray code for 12 positions. There's probably a neater solution, or even some sort of algorithm for generating this, but this seems to work :).

Check out monotonic grey codes, they are used for situations like this. As far as I understand it is possible to generate a code where each value only differs by one bit no matter the length, but generating them can be difficult

As long as the code has adjacent entries vary by only one bit it is unnecessary to use them all. The author gives the example [110, 010, 011, 111] of a code that is valid but doesn't use all 2^n possibilities.

That sequence has 2^2=4 positions. I don't think rflrob meant "n = number of bits" but "n = number of codes".

Ah, I see what you mean. [000, 001, 011, 111, 101, 100] is a grey code of length 6, so not power of two is possible. However trying to come up with an odd length code is a real head scratcher. It may not be possible in binary, but is easily accomplished in higher bases.

You couldn't do an odd number of codes, but if you have an odd number of positions, I suppose you could have one position represented by two adjacent codes. So, you could have a wheel with 5 equal pie slices, but on the reverse, one of those slices is divided in half, with a different encoding on each, that both resolve to the same value/result.

An algorithm that works for any even n is to generate the Gray code for the next highest power of 2 (in this case, 16) then pick the middle n symbols. Eg the 16 position Gray code, with the middle 12 symbols marked:

you can use a constraint solver to very quickly generate gray codes. I did a python example here using python-constraint: http://www.jimblog.net/2017/01/generating-gray-codes-with-py...

Reply on news.ycombinator.com