Friday, August 17, 2012

Anti-gray codes. How to derive them.

Do you need a series such that the next item in the series has the maximum amount of bits different from the previous one. You need an anti-gray code. Gray codes are codes like that where the next digit only varies by 1. To make an anti gray code:

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).

Update:
Source fragment if you just want blackbox code.