A Gray code is an ordered set of binary numbers such that only one bit changes from one element to the next. Any n-bit Gray code will have 2<sup>n</sup> elements. {000, 001, 011, 010, 110, 111, 101, 100} and {000, 010, 011, 001, 101, 100, 110, 111} are both examples of 3-bit Gray codes. Note that only one bit changes between each element and each set has 8 (2<sup>3</sup>) elements.

A binary reflected Gray code (BRGC) is a particular encoding for non-negative integers. To find a BRGC of n bits, take the BRGC of ( n - 1 ) bits, writing it forward and then backward. Prefix the first half of the binary numbers with 0, and prefix the second half of the binary numbers with 1. The binary reflected Gray code of 1 bit (integer values 0 and 1) is:

<pre> Integer BRGC ======= ==== 0 0 1 1 </pre>

To find the BRCG up through 2-bit integers (0, 1, 2, 3), write the BRCG of 1 bit going forward (0, 1), then backwards (1, 0), to get (0, 1, 1, 0). Prefix the first half of those numbers with 0 and the second half with 1, giving us:

Looking at the above chart we came up with, we can see that the BRCG encoding for the integer 2 is 11.

Let's try it one more time, finding the BRCG for integers up to 3-bits (0, 1, 2, 3, 4, 5, 6, 7). First we write the 2 bit BRGC forward then backwards (00, 01, 11, 10, 10, 11, 01, 00). Finally we prefix the first half of those numbers with 0, and the second half with 1:

Looking that the chart above tells us that the BRGC encoding for the integer 7 is 100.

<h4>The Challenge</h4>

Write a class BRGC containing three static methods. The first method displays a table of long integers and their BRGC encoded values up to n-bits. It should have the following signature:

public static void displayBRCG(long n)

Calling the method...

BRGC.displayBRGC(3);

...should produce something similar to the following output:

I believe that method encode() requires a second parameter; namely, the number of bits in the Gray code. Of course, encode(5) will always match the pattern "0*111", but we need to figure out the number of zeroes somehow.

Jason Menard
Sheriff

Joined: Nov 09, 2000
Posts: 6450

posted

0

Originally posted by Roy Tock: I believe that method encode() requires a second parameter; namely, the number of bits in the Gray code. Of course, encode(5) will always match the pattern "0*111", but we need to figure out the number of zeroes somehow.

No, not really. You aren't required to display leading zeroes. The answer for encode(5) will always be "111" for example, as opposed to "0111", "00111" or the like. But if it helps to think about it like this, keep in mind that the standard binary representation of 5 requires three bits, so the BRGC encoded representatin of 5 also requires three bits. [ August 03, 2003: Message edited by: Jason Menard ]

You can write the Gray codes for n bits into a grid so that when you move from one cell to another in NSEW directions only one bit changes - wrap around from one edge to the opposite edge. I wonder if that's at all tricky to automate.

A good question is never answered. It is not a bolt to be tightened into place but a seed to be planted and to bear more seed toward the hope of greening the landscape of the idea. John Ciardi

Getting late...here's my early entry. There's no recursion. encode() relies on a pattern, which I got by staring at the problem statement for a little while. decode() is the inverse of encode().

Here's a quick solution. I didn't do a real implementation of decode() since it seems to be a bit trickier than encode() and my brain has retired for the night, but I stuck in a decode method that doesn't run in linear time (alas, quadratic).

There is a very neat property of Gray Codes You can translate from Gray Code to Binary by realizing that a '1' in Gray code means that the corresponding digit in binary code is different from the one immediately to the left. A '0' in Gray code means the corresponding binary digit is the same.

Hi All, This code works by using the number of bits to run a recursive method. In using the previous values to create the current values it stores the previous value in 2 places adding the "0" in front of one, and "1" in front of another. The resulting BRGC is stored in an array and printed; solving problem (a). (b) To find the BRGC of a particular number it calculates the number of bits by converting the number to a Binary String (Long.toBinaryString(y) ) and creates the array using the solution to (a). It then looks up the BRGC corresponding to the correct index. (c) To find the number corresponding to the BRGC, we already have the number of bits, create the array and search it (Arrays.binarySearch) to give the right index.

Here's my solution... No arrays were explicitly used. I used an algorithm for my encode that is simple enough I could have done the whole method in one line. Simply take the unencoded decimal value, use integer division to divide it by 2, and XOR that value with the unencoded decimal value. Then just convert the resulting decimal to binary to get your BRGC encoding. For my display() method, I simply called encode() and padded the result with the appropriate number of zeroes prefixed. Since there's a simple equation to encode a number into BRGC, I would think there might also be an equation to decode as well. Anyone have any idea on this? Not knowing an easy way to decode, I used the algorithm Michael Zalewski mentioned but implemented it quite differently than he did, prefering mathematical bit manipulation to character manipulation.