Thursday, August 30, 2012

anti-gray code fragment.

Given some index,

        int antigray;
        int vp = index >> 1;
        antigray = vp ^ (vp >> 1);
        antigray <<= 1;
        if ((index & 1) == 1) antigray ^= -1;

Produces a unique antigray code. There's likely going to be a simpler solution somewhere. Rather than shifting right, gray coding, shifting left, and inverting due to the original bit. But, it's the code solution to my Anti-Gray Codes and a pretty easy couple lines. And having found out that I needed something else for the question I was answering, I cut this bit, and didn't really want to lose it.

There are other gray codes than index ^ (index >> 1) but that's a really good derivation. My solution works for any gray codes. So this shouldn't be taken as the only optimally distant code. Also, there might be more distance possible between step-2 codes. It's maximally distant hamming distance is only for the very next and just previous code. But, the code after the next code, may end up being very similar to the current code. Solving for a code giving the maximally distant hamming distance beyond absolutely adjacent codes might not even be derivable through my method. Though, assuming one doesn't weight the code requirements such that step-2 codes being very maximally different could trump some slightly closer step-1 codes. The hamming distance pattern would be N, N-1, N, N-1 ... to which the anti-code would have to be a gray code.

The most distant step-2 code segments would require that with a hamming distance of 1, the same bit not be modified until all other bits are modified.

So the gray code to derive this would be something like:
0001 -- bit 1.
0011 -- bit 2.
0111 -- bit 3
1111 -- bit 4
1110 -- bit 1 - 4 distance.
1100 -- bit 2 - 4 distance.
1000 -- bit 3 - 4 distance.
1001 -- bit 1 - 3 distance.
1011 -- bit 2 - 3 distance.
1010 -- bit 1 - 2 distance (this might be an error).
0010 -- bit 4 - 7 distance.
0110 -- bit 3 - 5 distance.
0100 -- bit 2 - 4 distance.
0101 -- bit 1 - 4 distance.
1101 -- bit 4 - 4 distance.

Which would then derive to several different gray codes which should still have 1 hamming distance between step-2 codes, but hamming distances of 2 for step-4 codes. Though, it would have less hamming distance at step-3 codes, which may defeat the entire purpose and depending on how much more you value step codes from one another. But, maximizing step-4 and step-6 codes may well minimize step-3 and step-5 codes.  But,  should at the very least it should maintain a hamming distance above 2 for step-2, and step-3 and potentially step-4 codes, and maximally distant codes at step-1.

No comments: