Gray codes
I spent a while messing around with Gray codes last night. Does this guy know how to party or what?
A Gray code, named after Bell Labs physicist Frank Gray, is a way of encoding numbers in binary such that each time you add one to a number, only one bit changes. This might sound like a mathematical obscurity, but it’s used all over the place, by motor encoders, genetic algorithms, and all kinds of things that bring joy to the people.
But more importantly, they look cool.
Here’s a shaft encoder with a Gray code (the code is in the concentric rings around the shaft in the top half of the picture).
And here’s a Gray code clock:
This is a linear representation of a 10-bit Gray code.
That encoder always knows which of 2048 (2¹¹, since there are 11 rings) possible angles its shaft is at. This is a resolution of 0.27 degrees. Pretty nifty! The reason to use a Gray code here, and not just a normal binary ordering of the numbers, is that in a normal binary representation, multiple bits can change from one number to the next. For the encoder, that would mean that we’d have to deal with multiple sensors changing their values simultaneously, whereas with a Gray code only one sensor at a time will ever change. For an 11 bit code, an encoder using Gray codes only needs 1/11th the computational power compared to an encoder using straight binary.
To illustrate, this is a Gray code for two bit numbers (0 to 3):
Gray 00 01 11 10
Decimal 0 1 2 3
Binary 00 01 10 11
In the Gray code, when you go up by one, only one bit changes.
But in the binary code, there are two transitions where both bits change, if you include going from 3 back to 0, which happens when the shaft does a full revolution.
Mathematically, the number of bits that differ from one number to another is called the Hamming distance, named after the guy who basically invented error correction. The Hamming distance from one number to another is defined as the number of bits that differ between the numbers. So:
110011 and
111001
have a Hamming distance of 2.
This is a useful concept when thinking about error correction, since the number of bits in a message that got flipped by cosmic rays is equal to the Hamming distance between the intact message and the one with errors (assuming no bits are lost, although there are ways of modeling that, too).
So a Gray code is a binary representation of numbers such that the Hamming distance between successive numbers is always 1.
Remember the discussion of Manhattan distances that I sent out a year ago? Of course you do. The Hamming distance is a type of Manhattan distance in many dimensions, where each dimension can only be 0 or 1. A Gray code with n bits is a Hamiltonian cycle through that n-dimensional hypercube!
There are some special kinds of Gray codes, too (there’s generally more than one n-bit Gray code for any n). One that I think is cool is the Balanced Gray Code, which is a Gray code with the extra property that all bits have the same number of flips after going through the entire sequence. This is desirable if you want, say, all of your sensors to wear out at the same rate. Balanced Gray codes are also used in genetic algorithms. Here is a visualization of an unbalanced 8-bit Gray code:
And now an 8-bit balanced Gray code:
And here are the transitions for the balanced one:
Each X represents a transition from 0 to 1 or from 1 to 0. There are exactly 32 X’s in each row.
Here’s some of the code used to generate these:
https://gist.github.com/belisarius222/47ffa1d3100c6757f9c8
Cheers,
Ted
