4 ms·

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 reflect

by rflrob 10y ago

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?

stonemetal 10y ago
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.
- tantalor 10y ago
  That sequence has 2^2=4 positions. I don't think rflrob meant "n = number of bits" but "n = number of codes".
  - stonemetal 10y ago
    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.
    - bryondowd 10y ago
      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.
default-kramer 10y ago
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.
deleted 10y ago
[deleted]
tantalor 10y ago
Any sequence has 2n codes. Example with 6: 000 100 110 111 101 001 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.
- Ericson2314 10y ago
  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
throwawaydbfif 10y ago
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
barbs 10y ago
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 :). 0110 0010 1010 1011 1111 1101 0101 0111 0011 0001 0000 0100
thcormen 10y ago
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
- seesomesense 10y ago
  Thank you for you post, and for your fine book on algorithms.
caf 10y ago
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: 0000 0001 0011 < 0010 < 0110 < 0111 < 0101 < 0100 < 1100 < 1101 < 1111 < 1110 < 1010 < 1011 < 1001 1000
unlikelymordant 10y ago
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-python.html http://www.jimblog.net/2017/01/generating-gray-codes-with-py...

by rflrob 10y ago

stonemetal 10y ago

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.

tantalor 10y ago
That sequence has 2^2=4 positions. I don't think rflrob meant "n = number of bits" but "n = number of codes".
- stonemetal 10y ago
  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.
  - bryondowd 10y ago
    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.

default-kramer 10y ago

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.

deleted 10y ago

[deleted]

tantalor 10y ago

Any sequence has 2n codes. Example with 6: 000 100 110 111 101 001 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.

Ericson2314 10y ago
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

throwawaydbfif 10y ago

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

barbs 10y ago

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 :). 0110 0010 1010 1011 1111 1101 0101 0111 0011 0001 0000 0100

thcormen 10y ago

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

seesomesense 10y ago
Thank you for you post, and for your fine book on algorithms.

caf 10y ago

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: 0000 0001 0011 < 0010 < 0110 < 0111 < 0101 < 0100 < 1100 < 1101 < 1111 < 1110 < 1010 < 1011 < 1001 1000

unlikelymordant 10y ago

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-python.html http://www.jimblog.net/2017/01/generating-gray-codes-with-py...