Anti-Gray Codes


#1

This isn’t oF-specific, but I think people here will have some insight.

Gray codes are an ordering of binary numbers that allow adjacent numbers to have only 1-bit of difference. For example, where n is the number of digits:

  
  
n = 3  
000  
001  
011  
010  
110  
111  
101  
100  
  

(There’s a simple algorithm for generating these: http://en.wikipedia.org/wiki/Gray-codes#Constructing-an-n-bit-gray-code)

I’m looking for an ordering such that nearby codes have a large hamming-distance between each other. The closer codes are to each other, the bigger the distance should be.

I don’t know if there’s an optimal way to design this so that there’s a steady dropoff (e.g., i+1 distance is always n/2, i+2 is always n/3, i+2 is n/4, etc…), or if it’s more gaussian, or what. Or even if there is a regular way to do it.

One algorithm I’ve considered so far is iterating through Gray codes with an odd increment. E.g., stepping through n=4 in increments of 5 yields:

  
  
0000 3 4 1  
0111 1 4 1  
1111 3 2 1  
1000 3 2 1  
0110 3 4 1  
1101 1 4 1  
1001 3 2 1  
0010 3 2 1  
1100 3 4 1  
1011 1 4 1  
0011 3 2 1  
0100 3 2 1  
1010 3 4 1  
0001 1 4 1  
0101 3 2 1  
1110 3 2 1  
  

Which isn’t terrible, but it’s very irregular.

Any insight, comments, questions, etc. would be appreciated!


#2

Hey Kyle, I guess you’re gonna get the largest hamming distance when you XOR the number with 2^n-1.

So could you not:

  • start with 0
  • xor that with 2^n-1 (which will give you 1111 for n=4)
  • xor that again with 2^n-1 and add 1 (so you get 0001)
  • xor again (1110)
  • xor again and add 2 (0011)
  • xor again (1100)
  • xor again and add 3 (0111)
    etc.

#3

but then the hamming distance between i and i+2 will be 1

btw, kyle, what do you want this for? you should totally try some genetic algorithm there to look for the optimal solution :wink:


#4

XOR is good for forcing adjacent (i+1) codes to have a large hamming distance, but it means that codes at i+2 are very similar. Also, your algorithm repeats itself after 10 codes:

  
  
0000 4 1  
1111 3 1  
0001 4 1  
1110 3 1  
0011 4 2  
1100 2 2  
0110 4 2  
1001 2 2  
1010 4 2  
0101 2 ...  
1111 ...  
  


#5

yea I thought Kyle wanted to have the entries so that the hamming distance between adjacent entries were as maximum as possible (i.e. kinda like sorted on hamming distance).

Genetic would indeed work, and could be interesting to implement.

Kyle, is this just a personal challenge or is there actually a useful application for this ? :stuck_out_tongue:


#6

[quote author=“arturo”]btw, kyle, what do you want this for? you should totally try some genetic algorithm there to look for the optimal solution :slight_smile:

I’d like to use this for a few things I’m working on that involve iterating through every possible combination of things, but I want to do it in a more interesting way than just counting up in binary (Every-Icon is an interesting idea, but not very interesting to look at). So I thought of adding the constraint: “nearby occurrences must be as different from each other as possible”. I’d say maintaining someone’s interest is a practical application :slight_smile:


#7

nice!

yeah, perhaps the genetic thing won’t give the best general solution but comparing the solution for some different spaces can give you a clue about what the general formula can be.


#8

I’m getting closer with this. Here are two algorithms that give very high hamming distances for odd numbered neighbors, and lower hamming distances for even numbered neighbors:

shift-invert + alternate
Start with: (0, 1)
Shift the entire sequence over and invert it: (0, 1, 1, 0)
Add an alternating (0, 1…) as the first bit: (00, 11, 01, 10)
Repeat for however many bits you need.

For 4 bits this gives:

0000
1111
1000
0111
1100
0011
0100
1011
1110
0001
0110
1001
0010
1101
1010
0101

mirror + alternate
Start with: (0, 1)
Mirror the entire sequence: (0, 1, 1, 0)
Add an alternating (0, 1…) as the first bit: (00, 11, 01, 10)

For 4 bits this gives:

0000
1111
1000
0111
0100
1011
1100
0011
0010
1101
1010
0101
0110
1001
1110
0001

There are two other 4 bit enumerations I’m trying to reverse engineer into an algorithm:

0000
1001
1010
0011
1100
0101
0110
1111
0111
1110
1101
0100
1011
0010
0001
1000

And:

0000
1111
0001
1110
0011
1100
0010
1101
0110
1001
0111
1000
0101
1010
0100
1011

Notice that when you work backwards from enumerations, the column number/bit position doesn’t matter.

Which reminds me, it’s interesting to count how many 4-bit enumerations there are given these kind of symmetries.

  • 4!=24 different versions of each enumeration due to column ordering
  • 2 different versions due to inversion (flipping all the bits)
  • 2^n = 16 different versions due to rotation (starting with different numbers)
  • 2 different versions due to direction (counting in different directions)

But that’s only 1536 different symmetric variations. 16!/1536 still equals 20,922,789,888,000. And once you find a good enumeration (which I have, via evolutionary search) you still need to understand how you might construct it!


#9

Take any gray code. Shift all the bits to the left by 1. Double the list. And alternate XOR flips. Done. You have an anti-gray code.

Take gray code.
0
1

Shift all the bits to the left by 1.
00
10

Double the list.
00
00
10
10

Alternate XOR flips.
00
11
10
01

The reason this works is because gray codes by definition have the minimal amount of distance. Xor flips have the maximum (they flip every bit). If you interweave them you will have maximum, maximum -1, maximum, maximum -1, maximum, maximum -1… which is an optimal anti-gray code. Also note, you don’t really *need* to shift the bits to the left. You can introduce a zero *anywhere*, so long as you do it consistently. Watch, I’ll do it with the middle digit.

00,01,11,10
-> 000,001,101,100
-> 000,000,001,001,101,101,100,100
-> 000,111,001,110,101,010,100,011 (perfect anti-grey code).


#10

I think you are looking for a perfect hashing function.
cryptographic hashes are pretty well distributed.
try this on the command line for an example:

for n in {1…20}; do echo $n | md5; done


#11

No. I know hashing. The entire point of anti-gray code is to make the hamming distance as far away from the previous value as can be done. That’s not a hash where you could have any result so long as it’s consistent and pretty evenly distributes, it’s like gray code (which has a minimal hamming distance) but in reverse.

Image you want a series of colors and rather than a random set of colors (what a hash would give you). You want colors which are as distinct from all other colors as possible, not just from the previous color but from all previous colors. Mentally you can go through the list 0x000000 0xFFFFFF 0x0000FF 0xFFFF00, this isn’t a random set but a very specific ordering which, interestingly enough, requires anti-gray codes (it’s the reason I solved the proof from gray codes, there’s a lot of intellectual work there). I was running searches and came across Kyle’s post here, also his flickr picture of him solving it on paper. Even noted his mistake on list 1, position 8. The better solution is 0-7 the same, 8-16 reversed.


#12

Hi Kyle,
I know you wrote this post many many years ago, but I just stumbled across it.
You might be interested in my blog post:

where I discuss solving a well known sampling problem called fractional design.
As part of it, I proposed a method of constructing open /infinite sequence of anti-gray codes.