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

blogswput

blogswput

Answered question

2022-09-17

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?

Answer & Explanation

Koen Henson

Koen Henson

Beginner2022-09-18Added 17 answers

The iteration function at stage t is the highest power of 2 that divides 𝑡 (this will result in a somewhat different code than yours, but still goes over all numbers, changing only one bit at a time). In general, since there are n possible bits to flip, you will have to store at least log 2 n bits in memory (if you're not allowed to look at the actual counter).
Some processors have a machine instruction that calculates this "highest power of 2 dividing a number", or perhaps something similar like "leading zero". This is an efficient way to implement Gray counting.
If you don't have such a machine instruction, another good choice is to unroll the increment loop for some small 2 K , and use some smart iterative approach (using lookup tables) to handle the updates which are not hard-coded.
lemondedeninaug

lemondedeninaug

Beginner2022-09-19Added 2 answers

Set a 0 = 0. To get a n + 1 from a n , just change bit r n , where r n is the number of trailing 1-bits in the binary representation of n. So we get:
( r n ) = { 0 , 1 , 0 , 2 , 0 , 1 , 0 , 3 , 0 , 1 , 0 , 2 , 0 , 1 , 0 , 4 , 0 , 1 , 0 , 2 , 0 , 1 , 0 , 3 , 0 , 1 , 0 , 2 , 0 , 1 , 0 , 5 , }
( a n ) = { 0 , 1 , 3 , 2 , 6 , 7 , 5 , 4 , 12 , 13 , 15 , 14 , 10 , 11 , 9 , 8 , 24 , 25 , 27 , 26 , 30 , 31 , 29 , 28 , 20 , }
This construction gives the standard Gray code.

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?