View Question
 Question
 Subject: gray codes Category: Science > Math Asked by: gw-ga List Price: \$5.00 Posted: 25 Oct 2003 21:08 PDT Expires: 24 Nov 2003 20:08 PST Question ID: 269739
 ```There are multiple "gray code" schemes. The most popular can be generated with a function such as: function IntToGray(const Value: Cardinal): Cardinal; begin Result := Value xor (Value shr 1); end; And undone with: function GrayToInt(const Value: Cardinal): Cardinal; begin Result := Value; Result := Result xor (Result shr 1); Result := Result xor (Result shr 2); Result := Result xor (Result shr 4); Result := Result xor (Result shr 8); Result := Result xor (Result shr 16); end; With this scheme, if one were to encode all integers sequentially, one would find that bit 0 (the least significant bit) toggles 1/2 the time, bit 1 toggles 1/4 the time, bit 2 toggles 1/8 the time, etc. I am curious if there exists such a scheme in which each bit toggles with equal probability. I realize this probably requires hard-coding the word size (number of bits) into the generating function. If possible, provide an algorithm for either the general case or for 8-bit words. A reverse algorithm would also be appreciated.``` Request for Question Clarification by mathtalk-ga on 25 Oct 2003 22:22 PDT ```Hi, gw-ga: It is trivial, but what about the "encoding" in which every bit toggles with 100% probability? Or, of course, with zero. If you want a scheme in which all bits "toggle" with 50% probability, assuming of course a fixed word size, then I can post such a scheme as an answer. regards, mathtalk-ga``` Clarification of Question by gw-ga on 25 Oct 2003 23:12 PDT ```I don't think I phrased my question as best I could. Forget probabilities for a moment. Is there an N-bit gray encoding scheme such that each bit changes state a total of (2^N)/N times as the input value varies from 0 to (2^N)-1, for arbitrary N or N = 8? Keeping in mind that only one of the N bits may change state between any two consecutive input values, to meet the definition of a gray code.``` Request for Question Clarification by mathtalk-ga on 26 Oct 2003 08:51 PST ```Likewise my "clarification request" fails to have much clarity, but it elicited from you the important observation that N must divide 2^N, which restricts interest to the cases with N a power of 2. As I'm sure you've noticed for yourself, for N = 1,2 the required property (equal numbers of changes in each bit location) can be easily (unavoidably!) satisfied. The next case of interest N = 4 (a Hamiltonian cycle on a tesseract) seems nontrivial. I can see a search method that would quickly (modulo a bit of programming) determine whether or not such a "Gray code" is possible, involving a search space of roughly 5^8 = 390,625 paths, many of which can be pruned out. I'm not sure whether a negative result for N = 4 would have much predictive value for N = 8. Perhaps the extra room in higher dimensions increases the likelihood of success, but my initial intuition is that the balancing of bit changes will prove impossible for N > 2. It's an interesting question, and I'd love to be proven wrong... regards, mathtalk-ga``` Clarification of Question by gw-ga on 29 Oct 2003 05:40 PST ```Alternatively, I wonder if there is an algorithm to generate a sequence that minimizes the total number of bit changes, yet each bit changes *approximately* equally often, with sometimes more than one bit changing between consecutive entries in the sequence.``` Request for Question Clarification by mathtalk-ga on 30 Oct 2003 06:39 PST ```Hi, gw-ga: I finished my programming for the 4-bit case last night, and to my amazement such a Gray code really does exist! Here's one solution (asterisks mark the beginning and wrap-around ending at 0000): CODE BIT 0000* CHG 0001 1 0011 2 0010 1 0110 3 0111 1 1111 4 1011 3 1001 2 1101 3 0101 4 0100 1 1100 4 1110 2 1010 3 1000 2 0000* 4 in which the bit changes are equally distributed among the positions. Given the vastly expanded number of possibilities for 8 bits, I have to change my mind and conjecture that these codes will exist for all power-of-2 number of bit cases. If you like I can (as an Answer) outline the algorithm I used to search for a 4-bit solution and make some estimates of the complexity of searching for an 8-bit solution using the same approach. regards, mathtalk-ga``` Clarification of Question by gw-ga on 30 Oct 2003 11:14 PST ```It is very neat that you found a 4-bit example. My intuition agrees with yours that a example for 8 bits must also exist. While a brute-force search algorithm isn't what I'd hoped for, I will accept it as an answer as I don't have a practical application for this knowledge just yet, but I do have some ideas; I posted this question more out of curiosity than need. When the time comes I could always use a lookup table in lieu of a generating function. I appreciate your enthusiasm for the question and I will leave a tip for you.``` Clarification of Question by gw-ga on 30 Oct 2003 11:26 PST ```Actually, it would seem trivial to create an 8-bit sequence based off your existing 4-bit sequence. The upper 4 bits could increment to the next 4-bit pattern every 16 elements, and the sequence of the lower nibble would simply reverse every 16 elements. entry #16 would be 0001 1000 entry #17 would be 0001 1010 entry #18 would be 0001 1110 ... entry #30 would be 0001 0001 entry #31 would be 0001 0000 entry #32 would be 0011 0000 etc.``` Clarification of Question by gw-ga on 30 Oct 2003 11:42 PST ```function Encode(const X: Byte): Byte; const Table: array[0..15] of Byte = ( \$0, \$1, \$3, \$2, \$6, \$7, \$F, \$B, \$9, \$D, \$5, \$4, \$C, \$E, \$A, \$8); var UpperNibble: Byte; LowerNibble: Byte; begin LowerNibble := X and \$F; UpperNibble := X shr 4; Result := Table[UpperNibble] shl 4; if (Odd(UpperNibble)) then Result := Result + (Table[15 - LowerNibble]) else Result := Result + Table[LowerNibble]; end; 0: 00000000 1: 00000001 2: 00000011 3: 00000010 4: 00000110 5: 00000111 6: 00001111 7: 00001011 8: 00001001 9: 00001101 10: 00000101 11: 00000100 12: 00001100 13: 00001110 14: 00001010 15: 00001000 16: 00011000 17: 00011010 18: 00011110 19: 00011100 20: 00010100 21: 00010101 22: 00011101 23: 00011001 24: 00011011 25: 00011111 26: 00010111 27: 00010110 28: 00010010 29: 00010011 30: 00010001 31: 00010000 32: 00110000 33: 00110001 34: 00110011 35: 00110010 36: 00110110 37: 00110111 38: 00111111 39: 00111011 40: 00111001 41: 00111101 42: 00110101 43: 00110100 44: 00111100 45: 00111110 46: 00111010 47: 00111000 48: 00101000 49: 00101010 50: 00101110 51: 00101100 52: 00100100 53: 00100101 54: 00101101 55: 00101001 56: 00101011 57: 00101111 58: 00100111 59: 00100110 60: 00100010 61: 00100011 62: 00100001 63: 00100000 64: 01100000 65: 01100001 66: 01100011 67: 01100010 68: 01100110 69: 01100111 70: 01101111 71: 01101011 72: 01101001 73: 01101101 74: 01100101 75: 01100100 76: 01101100 77: 01101110 78: 01101010 79: 01101000 80: 01111000 81: 01111010 82: 01111110 83: 01111100 84: 01110100 85: 01110101 86: 01111101 87: 01111001 88: 01111011 89: 01111111 90: 01110111 91: 01110110 92: 01110010 93: 01110011 94: 01110001 95: 01110000 96: 11110000 97: 11110001 98: 11110011 99: 11110010 100: 11110110 101: 11110111 102: 11111111 103: 11111011 104: 11111001 105: 11111101 106: 11110101 107: 11110100 108: 11111100 109: 11111110 110: 11111010 111: 11111000 112: 10111000 113: 10111010 114: 10111110 115: 10111100 116: 10110100 117: 10110101 118: 10111101 119: 10111001 120: 10111011 121: 10111111 122: 10110111 123: 10110110 124: 10110010 125: 10110011 126: 10110001 127: 10110000 128: 10010000 129: 10010001 130: 10010011 131: 10010010 132: 10010110 133: 10010111 134: 10011111 135: 10011011 136: 10011001 137: 10011101 138: 10010101 139: 10010100 140: 10011100 141: 10011110 142: 10011010 143: 10011000 144: 11011000 145: 11011010 146: 11011110 147: 11011100 148: 11010100 149: 11010101 150: 11011101 151: 11011001 152: 11011011 153: 11011111 154: 11010111 155: 11010110 156: 11010010 157: 11010011 158: 11010001 159: 11010000 160: 01010000 161: 01010001 162: 01010011 163: 01010010 164: 01010110 165: 01010111 166: 01011111 167: 01011011 168: 01011001 169: 01011101 170: 01010101 171: 01010100 172: 01011100 173: 01011110 174: 01011010 175: 01011000 176: 01001000 177: 01001010 178: 01001110 179: 01001100 180: 01000100 181: 01000101 182: 01001101 183: 01001001 184: 01001011 185: 01001111 186: 01000111 187: 01000110 188: 01000010 189: 01000011 190: 01000001 191: 01000000 192: 11000000 193: 11000001 194: 11000011 195: 11000010 196: 11000110 197: 11000111 198: 11001111 199: 11001011 200: 11001001 201: 11001101 202: 11000101 203: 11000100 204: 11001100 205: 11001110 206: 11001010 207: 11001000 208: 11101000 209: 11101010 210: 11101110 211: 11101100 212: 11100100 213: 11100101 214: 11101101 215: 11101001 216: 11101011 217: 11101111 218: 11100111 219: 11100110 220: 11100010 221: 11100011 222: 11100001 223: 11100000 224: 10100000 225: 10100001 226: 10100011 227: 10100010 228: 10100110 229: 10100111 230: 10101111 231: 10101011 232: 10101001 233: 10101101 234: 10100101 235: 10100100 236: 10101100 237: 10101110 238: 10101010 239: 10101000 240: 10001000 241: 10001010 242: 10001110 243: 10001100 244: 10000100 245: 10000101 246: 10001101 247: 10001001 248: 10001011 249: 10001111 250: 10000111 251: 10000110 252: 10000010 253: 10000011 254: 10000001 255: 10000000 256: 00000000``` Clarification of Question by gw-ga on 30 Oct 2003 12:08 PST ```A slightly more elegant 4-bit sequence would be the following. bit 0 toggles every 2nd entry starting with 1 bit 1 toggles every 4th entry starting with 2 bit 2 toggles every 8th entry starting with 4 bit 3 toggles every 16th entry starting with 8 1: 0000 2: 0001 3: 0011 4: 0010 5: 0110 6: 0111 7: 0101 8: 0100 9: 1100 10: 1101 11: 1111 12: 1110 13: 1010 14: 1011 15: 1001 16: 1000 Thanks so much for your help and inspiration. :) I consider this question answered.``` Clarification of Question by gw-ga on 30 Oct 2003 12:09 PST ```Unfortunately it seems I can't rate the answer and leave a tip until you post a comment as the final answer.``` Clarification of Question by gw-ga on 30 Oct 2003 12:18 PST ```I feel like an idiot now, I completely forgot about the bit balancing. My solutions don't work in that regard. :>``` Clarification of Question by gw-ga on 31 Oct 2003 19:47 PST ```I worked out an algorithm to search for gray code sequences that meet my criteria. It seems that if one enforces the first code to be 0000 and the second code to be 0001, then there are 96 four-bit gray code sequences with bit balancing. My program finds them in about one second on a 2GHz machine. Changing a constant in the program adapts it to search for an 8-bit solution, however it will probably take a considerably long time to finish.```
 ```Hi, gw-ga: The 96 solutions you found agree with the ones my programs found. My original program enforced a narrower range of solutions, namely that not only is the lowest order bit set first, as in your solutions, but in fact the order in which bits are first toggled agrees with the order of the bit locations (1 bit first, 2 bit before 4 bit, 8 bit last). With this restriction there are only 16 solutions. The 96 seen in your programs output correspond to the 3! = 6 times as many solutions obtained by permuting the high order three bits (uniformly, among all codes). Here is a short Prolog program that can compute all 96 of the 4 bit solutions: distCodeBits(16,_,_,_,_,M,M) :- !. distCodeBits(J,L0,L1,L2,L3,M,P) :- not(L0 = [_,_,_,_|_]), changeBit(1,M,N), I is J + 1, distCodeBits(I,[J|L0],L1,L2,L3,N,P). distCodeBits(J,L0,L1,L2,L3,M,P) :- not(L1 = [_,_,_,_|_]), changeBit(2,M,N), I is J + 1, distCodeBits(I,L0,[J|L1],L2,L3,N,P). distCodeBits(J,L0,L1,L2,L3,M,P) :- not(L2 = [_,_,_,_|_]), changeBit(4,M,N), I is J + 1, distCodeBits(I,L0,L1,[J|L2],L3,N,P). distCodeBits(J,L0,L1,L2,L3,M,P) :- not(L3 = [_,_,_,_|_]), changeBit(8,M,N), I is J + 1, distCodeBits(I,L0,L1,L2,[J|L3],N,P). changeBit(B,[H|T],[Hb,H|T]) :- Hb is H xor B, not(is_member(Hb,T)). given the "goal" of satisfying: distCodeBits(1,[0],[],[],[],[1],M). The idea is that the first argument "counts" up to 16, and at each step before the last, a new "bit change" is alotted to one of the four bit positions. These allocations are "remembered" in the lists held in the next four arguments, while the resulting codes are added sequentially to the list in the next to last argument. When the final count 16 is reached, the final argument gets bound to the same list represented in the next to last argument, and we're done. Prolog has a mechanism called "backtracking" which allows it to find all the solutions with no additional programming. My first program's approach to searching for solutions was an attempt to cut down on the size of the search space by focusing on the limited possibilities for the bits in the least significant position. It then proceeded basically to determine all the bits in the 2's position, the 4's position, the 8's position. However when I began to think about scaling up to the 8 bit case, the number of possibilities for all bits in the least significant position expands by roughly nine orders of magnitude, from 25 possibilities in the 4 bit case (for just the first bits!) to what I suspect turns out to be: 121 * 121 * 61 * 61 * 21 * 21 = 24,025,310,001 possibilities for the first column of bits. Cutting down the total size of the search space is not necessarily the immediate concern in trying to find solutions quickly. More important is usually the introduction of constraint checks early in the search which tend to knock out large swaths of "search space" that would eventually turn out to be untenable. In this respect I found, after exercising "ingenuity" in the first version of my program, that there was a natural advantage to the structure of a "brute force" program, partly realized in the version shown above, in being able to do those "knockout" checks earlier on in the search. The "ingenuity" of my first approach finds its way into the framework of the "brute force" approach in what I hope will turn out to be a nice way to tackle the 8 bit approach. I'll post an update this weekend when I get some computational results. regards, mathtalk-ga``` Request for Answer Clarification by gw-ga on 06 Nov 2003 09:42 PST ```Here's an interesting reference for this problem: http://www.combinatorics.org/Volume_3/PDFFiles/v3i1r25.pdf You can ignore this clarification request, I just wanted to add a comment, Google doesn't display an 'add comment' button for me since I'm the one who posted the question.``` Clarification of Answer by mathtalk-ga on 07 Nov 2003 07:16 PST ```Thanks, gw-ga, for the very interesting reference. I'll try to scoot into the local university library this weekend to look up the paper they cite from Congressus Numerantium, where apparently a general solution for n = power of 2 is given. I'll post what I find as a comment. I must admit I've found the 8-bit computation daunting. I misestimated the number of possibilities for the first "column" arrangements by many orders of magnitude. Assuming the 0,1 start as previously, there are: C(111,15)^2 possibilities (such that there are no consecutive changes in that same column and a total of 128 bits of each parity), and this is roughly 1.85E+36. Hopefully those other authors have discovered a more algebraic way of tackling these designs. --mathtalk```