The motivation for encoding bits in Gray code was to count in binary but to have only one bit change with every +1 count. Let's consider binary to Gray.
The motivation for encoding bits in Gray code was to count in binary but to have only one bit change with every +1 count. This is helpful in mechanical switches where we don’t want intermediate states to be present at the output while switching, something that can happen due to imperfections. Gray codes are also useful for basic error correction: two bits changed in a single state change? Something must be wrong.
Some Gray codes, those that are ‘cyclic’, have the added benefit that when they ‘roll’ — go from the ‘terminal count’ to the initial state — there is also only one bit change (that is, the first and last number are different by a single bit change). The Wikipedia page for Gray code is fascinating and worth a read. In this page, I found code for converting binary code to Gray. Something like this:
num_gray = num_bin ^ (num_bin >> 1)
Where ^ is XOR and >> is ‘shift right by one.’ Pretty neat, and easy to remember for the next time you’re asked at a party for the Gray of 10010110. You could quickly answer 11011101 after consulting a napkin scribble. Huge applause to you!
I’ve wondered what the logic circuit may look like. I wasn’t clever enough to directly convert the code above to gates so I looked at the bits.
We see that in the case of a single bit — in yellow — the binary and Gray are the same. In hardware, that’s just a wire. For two bits — in blue — we see that the most significant bit (MSB) is G1 = B1, and the least significant bit (LSB) is G0 = NOT B0. Looking at three bits — in purple — G2 = B2 as before, but the negation rule no longer works. We need a new strategy. Looking for more elaborate patterns we may notice that Gn = Bn XOR Bn+1 for GN-1 to G0 and GN = BN!
The equivalent circuit of the software implementation. Gate D can be removed by a wire for G3 = B3.
If we look back to the pseudo-code, we can see that the operation is the same: we’re XORing Bn and Bn+1 by shifting the input first and inserting a 0 at the MSB position. (That’s shown as the additional superfluous XOR gate with a 0 input.) As a designer, it’s always nice when the solution is a single logic level!
I may have taken the naive approach to solving this problem. How would you do it better or differently?
Elektor Magazine has been one of the leading sources of information on electronics for engineers, designers, start-ups and companies for 65 years. Our magazine is powered by an active community of electronics engineers – from students to professionals – who are passionate about designing and sharing innovative ideas.
For them, we publish hundreds of items a year, in formats such as articles, videos, webinars, and other learning formats. Our mission is to share knowledge in every possible way and inspire readers with the latest developments within the electrical engineering sector.
Thank you for your vote!
Leave further comments in the fields below.
Thank you for your vote!
If you wish to leave a comment with your rating, please first use the login below. If not, just close this window.
Discussion (4 comments)