2
$\begingroup$

When I was fairly young, I taught myself to count in binary. I thought it would be a fun party trick to impress people. I soon found out that it was not.

Over the years I've come to appreciate Gray code/reflected binary code for its property of only flipping one bit for each increment/decrement of the underlying count. But I've always been bothered by the fact that, if I wanted to mentally take any arbitrary Gray code and add or subtract 1 from it, I'd have to either convert it to and then back from its numeric value, or construct a table to work out what the next code should be.

It seems to me that there should be some trick that a person with "average" short term memory and addition skills should be able to do to take any arbitrary value in Gray code and figure out which bit to flip to get the next value... But I've never found it.

Does such a thing exist?

$\endgroup$
  • $\begingroup$ What research have you done? We expect you to do a significant amount of research before asking, including checking standard references (like Wikipedia, a textbook), and to show us in the question what you've found. If your question is answered in the obvious place on Wikipedia, you probably haven't done enough research before asking. There's little point in us repeating material already widely available in standard references. $\endgroup$ – D.W. Aug 25 '16 at 23:08
2
$\begingroup$

Wikipedia describes a very simple algorithm for this task:

To construct the binary-reflected Gray code iteratively, at step 0 start with the $\text{code}_0 = 0$, and at step $i > 0 $ find the bit position of the least significant 1 in the binary representation of $i$ and flip the bit at that position in the previous code $\text{code}_{i-1}$ to get the next code $\text{code}_i$.

Source: https://en.wikipedia.org/wiki/Gray_code#Constructing_an_n-bit_Gray_code

This is certainly simple enough to do in your head.

$\endgroup$
1
$\begingroup$

Gray codes are hamilton cycles in hypercube graphs $Q_n$, which can be recursively constructed using Hamilton cycles in $Q_{n-1}$. Perhaps you can do these computations by hand for small n and see if that helps.

$\endgroup$
0
$\begingroup$

The title of my masters thesis was Efficient Hardware Implementations of Gray Code Arithmetic. The goal was to find a way to, at the digital hardware level, perform arithmetic on Gray code directly without first converting to binary. Spoiler alert: I never did find a way to do that. What I did find was a way to convert from Gray code to binary more quickly (in logarithmic rather than linear time). If I'm remembering correctly, converting from binary back to Gray code is already fast.

Now I did come up with a fast Gray code numeric comparitor, i.e. a circuit that could compare the value of two numbers expressed in Gray code, that did not require initial conversion to binary.

$\endgroup$
  • $\begingroup$ Could you summarize the part relevant to the question here? $\endgroup$ – Evil Jun 8 at 1:38

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.