4
$\begingroup$

I recently solved the basic problem of generating a n-bit Gray Code. The solution I used involved building larger-bit Gray Codes from smaller ones recursively (the solution I've seen on most websites).

However, I then had an idea for a Greedy Gray Code Algorithm: Start the Gray Code at 0 and at every step, find and change the single smallest bit such that we get a new, not-visited-before number. Keep on repeating this until we have exhausted all the 2^N possible numbers with N bits.

I was sure that this approach wouldn't work for some values of N, but so far, it has worked for all N from 1 to 30. This was quite surprising for me, especially as I haven't seen this Greedy approach mentioned anywhere as a solution to the Gray Code Problem.

So, my question is, does this Greedy algorithm for generating N-bit Gray Codes always work? Is there a proof of its correctness? Otherwise, what value of N causes this algorithm to not be able to generate a correct Gray Code?

$\endgroup$
2
$\begingroup$

Your construction results in the standard binary-reflected Gray code, a recursive construction of which is described on Wikipedia, for example. We can also describe it in a different way: to generate the $m$'th codeword from the $(m-1)$'th, flip the least significant 1 bit of $m$. For example, when $n=3$, we have: $$ \begin{array}{c|c} 000 & 000 \\ 00\textbf{1} & 00\textbf{1} \\ 0\textbf{1}1 & 0\textbf{1}0 \\ 01\textbf{0} & 01\textbf{1} \\ \textbf{1}10 & \textbf{1}00 \\ 11\textbf{1} & 10\textbf{1} \\ 1\textbf{0}1 & 1\textbf{1}0 \\ 10\textbf{0} & 11\textbf{1} \end{array} $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.