So what is behind the theory of binary gray code? It was named after Frank Gray and is a numerical system where each successive value differs from the one before it by one bit value. It is like counting in binary, but in binary counting a step may require changing two bits. For instance going from 1 (01) to 2 (10) would involve changing the most significant value 1 to a zero and then changing the next bit to a 1. This would be a two step process. In gray code you would go from 01 to 11 and then to 10. Notice on each of these steps we only change one bit. Gray code is currently being used in the digital communications industry to clean up and error correct signals for things like your digital TV. So if your tv signals are getting smashed during an episode of the Teletubbies, it could be Frank Gray who comes to your (or Tinkie Winkie’s) rescue! The theory behind it is not that hard once you understand you can only change one bit at a time. We will cover how to do produce gray code using the reflective method using our good old friend Ruby right here on the Programming underground!
Before we start, I have to admit that Ruby makes this whole process ridiculously easy. I don’t think anyone can doubt the expressive power of the language. Implementing this reflective method in another language would be a bit more drawn out. My only beef with Ruby is that it is too expressive. Ruby enthusiasts often spend their time on boards arguing which of their methods are the “most compact and elegant” even though they all work equally well. You often can solve the same problems a hundred different ways.
Back to our gray code, there are many ways to do it but by far the most common is what is called “Reflected binary code” in which we use binary values only (even though you can us other base values) and follow a process of taking each bit, reversing it, prepending a 0 to the first unreflected array elements and prepending a 1 to the reflected array elements and simply concatenating them together. Below we demonstrate how this works…
// Original bits 0, 1 // Get a reverse version 1, 0 // Prepend 0 to the original bits 00, 01 // Prepend 1 to the reverse version 11, 10 // Add reverse onto new original 00, 01, 11, 10
Pretty straight forward right? As long as we follow these steps on each iteration we will be golden. The trick here is that you can do this iteratively or of course recursively. In my example below I create a recursive version which is typically the most sought after solution and the solution most asked for from any classes that may deal with an example in gray code. First thing is first and we will create a function called “graycode” and pass to it an array and the number of iterations we want to go through. Like all recursive functions, the first thing we should think about is hitting our “base case” which is the case where we need to signal to the process when we have hit the end of the road. Our end of the road is when our value passed into the function is less than 1. On each successive recursive call, we are going to decrement “n” by one so that eventually we will hit our base case of n being less than 1 and return.
For our first iteration we are going to check that our array is empty. If it is, then we are going to put in our starting bits of 0 and 1. If it is not empty we are going to go through our steps where we prepend the 0 or 1 onto each element, reverse the array (that is the reflective part) and smash it onto the end of the original array. Let’s take a look at how we can accomplish this in Ruby…
# graycode takes an array and the number of iterations "n" to proceed with.
# It assumes that we have a binary array only.
def graycode(list, n)
# base case
if n < 1
return
else
# First iteration, fill with binary values 0 and 1.
# Then print the two elements
if list.empty?
list.push("0")
puts 0
list.push("1")
puts 1, "\n"
else
# Reflective method
# 1) Take incoming array and reverse it
reverse = list.reverse
#2) Append 0 onto each element for original list elements and print it
list.each_index { |i| puts list[i] = "0" + list[i] }
#3) Append 1 onto each element of new reverse list and print it
reverse.each_index { |i| puts reverse[i] = "1" + reverse[i] }
#4) Concatenate arrays
list += reverse
# Add a break to see each successive iteration
puts
end
# Subtract 1 from n and recursively call itself until we hit base case
graycode(list, n - 1)
end
end
# Create array
list = Array.new
# Call our function with 3 iterations
graycode(list, 3)
This Ruby code can of course be crunched down much smaller by simply taking out several of the narrative comments and maybe even joining a few of the lines up. I wanted to stick with a very explicit setup to show you the steps we talked about before and how we are implementing them in the language.
To kick off the function we test for our base case and once reached, we simply return out of the function. If we are not at the base case yet, we go about checking if we have an empty array. If so, we fill it with our starting values and print them to the display. If we are not at the base case and we don’t have an empty array, we go about getting a reflective copy of the array by reversing it. We then loop through each element of the original array and add our 0 onto the front of them. We then do the same with the reversed version but instead adding a 1. At each iteration we print out the new element to the screen. Lastly, we add the two arrays together and pass that on to the next recursive call. Of course as we do that we will have to decrement “n” so that again it will reach the base case setup at the beginning of the function.
The result should be a list of gray code values for binary…
// This is our n = 1 0 1 // This is our n = 2 00 01 11 10 // This is our n = 3 000 001 011 010 110 111 101 100
Again, not too complicated once you know the steps and work it out through the code. Ruby does a great job at creating the solution for this without having to rely on loops for reversing and concatenating like you would do in a language like C/C++. It also doesn’t require you to define some new dimensions as the array grows. You could mimic this in Java or .NET however by using an expanding collection like Arraylist. So you could give that a try if you are interested in porting it over to another one of your favorite languages. Keep in mind that our implementation is also dealing with strings here and if you want to actually work on each of the values, you will need to make sure you take the appropriate action to make sure you are using the correct types.
I hope you enjoyed this little algorithm. It is nice to play around with something like this while you sip your tea or orange juice on a Saturday morning. Thanks again for reading! 🙂
