0
$\begingroup$

I'm posting this as more of a theory/mathematic how-to followup to a stackoverflow question.

The non-iterative method for calculating graycode depends on Log2N bytes, to store position information for the next bit in the iteration sequence.
Specifically, the goal is to know the next bit to change without having to look at the current code.

However, for the 3 bit gray code, there's a iteration sequence 0,1,2,1,0,1,2,1 that can be represented with a much simpler function - maintain "0,1,2,1" in a register and rotate each time (as an example of a more general permutation).
To reduce the necessary state, this could be kept in two positions, starting 0,1 and a constant function of "xor, permute" applied: 0,3 => 1,0 => 2,1 => 3,2 => 0,3 (the bit to change being the first, and 3 handled as 1 since only 0,1,2 are valid)

Is it possible for graycodes to exist for higher values of N, such that the iteration function can be calculated with just a permutation operation?
If not, with permute/xor?
Is there a more general way to think of applying constant operations to define the state change?

  • 0
    You should define what a Gray code is, at least.2011-01-13
  • 0
    @Glen Wheeler, a Gray code of length 2^n has the property that neighbours differ in exactly one bit.2011-01-13
  • 0
    @frLich:The standard 3-bit Gray code is 0 1 3 2 6 7 5 4. How is this generated by your iteration sequence? I confess your question leaves me baffled.2011-01-13
  • 0
    @TonyK: I assume he is talking about $(n,k)$-Gray codes.2011-01-13
  • 0
    tony, that's the binary reflected gray code sequence - but this iteration sequence also produces a valid arrangement of the numbers -0,1,3,7,5,4,6,22011-01-13
  • 0
    @frLich: Yes, OK. But how do you get 0 1 3 7 5 4 6 2 from 0 1 2 1 0 1 2 1?2011-01-13
  • 0
    start with 0. XOR 001 (0) to get 1. XOR 010 (1) to get 3. XOR 100 (2) to get 7. XOR 010 (1) to get 5. The 0 1 2 1 .. is the bit to flip to get to the next code. My goal is to find sequences for longer N that have similar properties.2011-01-14
  • 0
    @TonyK: I know, I like to think of them as (Hamiltonian) cycles in an n-cube. I was suggesting that perhaps frLich could improve the question. I did a little work on Gray codes, but it isn't computationally efficient and so not applicable to this question. Shame ;).2011-01-14

2 Answers 2