The Code of Gray
This article is part of a series, access the series index.
Have you ever heard of anything called a gray code? If you aren’t a programmer or a computer enthusiast (or for that matter an electrical engineer), then probably not. It kind of sounds like a movie doesn’t it? Tom Hanks And Audrey Tatou (one of my favorite actresses) investigate the hidden meanings inside the holy testament of binary that is the last page of Alan Turing’s secret journal. They discover that if you start counting up by one in binary and attach the data up to an RGB monitor you will eventually over time see every possible image that you could possibly see on that screen. Every possible image. Imagine in image, it’d eventually show up. Pretty cool huh?
The term gray code is named after Frank Gray who worked Bell Labs. We might explore more about Mr. Gray in another post. For now it’s fine to know that it’s also known as a “reflected binary code”. Gray code still sounds cooler. It has been attempted to be patented four times: once in 1947 by Frank Gray, and then twice in 1953, and another time in 1954. Those eager inventors, even Mr. Gray, were just jumping on a bandwagon that had already been started by Émile Baudot, a French engineer.
There are different types of gray codes, but the concept can be boiled down to something probably a bit simplified. It is in essence a sequence of a sequence of bits (a “binary numeral system”), so imagine a sequence of bytes to keep it simple. Now each byte in the sequence changes by one bit. So one bit in a byte is different than the byte before it. If you make a circular code, then the last byte is one bit different than the first byte.
An example can clear things up very well. Here is a 3 bit wide gray code to illustrate (a byte would be too long):
000 100 110 010 011 111 101 001
So you can see how this might be useful because as you move up and down the code only one bit changes at a time.
Gray codes were ‘invented’ for a particular purpose actually (telephony and communication originally). This is particularly useful in electronics when there are switches and they don’t all necessarily change state at the exact same time. If I change from 101 to 010, I could accidentally ‘read’ in between 110, or 011, or 000, or 111. How do I know I’m reading the actual value and not an in between state? When only one switch changes at a time then I don’t have to worry about it as much.
They are used to facilitate error detection, but they can also be used to determine what location a read-head might be on a circular disk. Error detection, location determination (angles), mapping, and probably a few other things if you’re clever enough.
Funny enough, you know what gray code is actually like? You ever play that Tower of Hanoi game where you have to move the discs from one stick to another stick but you can’t put a larger disc on top of a smaller one? Gray codes can serve as a map towards solving those things. Neat, huh?
So how does one construct a gray code? Well, a binary-reflected Gray code can be generated by reflecting the sequence of bits. You start with 0 and 1, reflect them, and then add 0 to the first part and 1 to the second part. I think a diagram would be most illustrative:
See? I hope that’s clear enough. There is all sorts of properties of these lists and math that can come from them, but that is out of the scope of this introductory article.
There are multiple types of gray codes, some of them easier to explain than others. For beginning programmers it’s best I think to stick to an example of an alternate gray code that’s easy to explain. To me that’s the Beckett-Gray code. Besides I think this one has an interesting story behind it too. There once was this playwright named Samuel Beckett who wanted to write a play called “Quad”. It was divided into sixteen sections. Becket wanted the players to change around each scene (one either entering and exiting), beginning and ending with an empty stage. This could be represented by a four bit gray code. However, he wanted the player who exited in his section to be the player who had been on the stage the longest.
How could this be done? In programming this type of restriction would be implemented by a first-in first-out (FIFO) stack. We’ll learn more about such a construction in a later article, but for the time being basically imagine a line of people. First come first served: the line of people progresses towards the front of the line as each person joined it. You can see how this is analogous to the play’s requirements then I hope. Such codes exist, but unfortunately they cannot exist for four players (bits), nor for 3, so Beckett never truly achieved his goal in that regard.
So that’s a gray code for ya. It kind of is like a secret binary code lost to annals of time… but since it’s still used in modern digital clock like circuits it kind of loses that romanticized charm. I hope you learned something new!
If you appreciate my tutorials please help support me through my Patreon.