Gray Code

How to understand and use Gray code

2011-01-25

What is Gray code?




From Wikipedia
The reflected binary code, also known as Gray code after Frank Gray, is a binary numeral system where two successive values differ in only one bit.

The reflected binary code was originally designed to prevent spurious output from electromechanical switches. Today, Gray codes are widely used to facilitate error correction in digital communications such as digital terrestrial television and some cable TV systems.


One good way to explain the use of Gray code is to take a look at how a hard drive work, in extreme simplicity.
A hard drive contains a disc where information is stored. The information on the disc is stored in ones and zero´s, binaries. The disc is divided into sections which each has a binary signature.

Here is a picture to explain:

imagehttp://admin.morkalork.com/uploads/images/binaries/BinaryCircelGray1.png

As we can see here, section 0 for example has the binary signature 0000 and section 15 has the binary signature 1111. When a hard drive is running it reads section by section and if the hard drive for some reason has a failure and the reader jumps from section 15 to section 0 the reading changes from 0000 to 1111 which means that every bit read is faulty.
This could change alot depending on how the information is parsed.

A hard drive could be exposed to a lot of external forces and the reader can jump and missread at any time. This cannot be forseen, but it can be prevented to some extent.
Enter Gray code.

Gray code is a way to sort the binaries so that one binary never differs more than one bit from another. This is good news compared to the drastic differance between 0000 and 1111.
If we look at a 4-bit value in ordinary binary form and in Gray code form we can see some patterns. The changes in each binary string is bolded:

DecimalBinaryGray code
000000000
100010001
200100011
300110010
401000110
501010111
601100101
701110100
810001100
910011101
1010101111
1110111110
1211001010
1311011011
1411101001
1511111000


There is a pattern that emerges here. The digit that changes in the regular binary string is the same that changes in Gray code.

If we look at how a Gray code hard drive would look we can see that this hard drive looks a lot different than the ordinary one:

imagehttp://admin.morkalork.com/uploads/images/binaries/BinaryCircelGray2.png
Note: Gray code is small, red font, ordinary binary code is in black

This doesn't seem to make sense. The ordinary hard drive is ruled by the regular binary pattern where each section has the same binary value as it's section value. The Gray code seems to have no pattern at all.

Let's first look at why it makes sense:
If you look at the difference between each section you can see that there is never more than one bit that differs from the previous and upcomming section. Quite weird, but very effective when it comes to error handling.

Is there a pattern?
Of course there is =D. Anything else would be silly. The pattern however is not as easy to see as the normal binary pattern where you can just look at it's numerical counterpart and do the math.
In the Gray code circle we can look at section 5 for example. The regular binary value is 0101 which we can quickly see is 5. The Gray code value however is 0111 which should be 7 in decimal, how strange.
With gray code we will have to accept a new way to do the math. First, let's understand how we get the Gray coded binaries.
Gray code is decided by bitwise operations with XOR. The XOR operator works like this: if two values are the same the result is false, if the two are different the answer is true. This chart can explain it:

Value 1 XOR Value 2
Value 1Value 2Answer
TrueFalseTrue
TrueTrueFalse
FalseTrueTrue
FalseFalseFalse


Read more about XOR here.

Now that we know how XOR works we can convert regular binary string 0011 (decimal 2):

We check each bit, starting from the right, with the next one:

1 XOR 1 = 0
1 XOR 0 = 1
0 XOR 0 = 0
0 XOR 0 = 0

As we can see, all of a sudden 0011 turns into 0010. Hopefully this somewhat explains what Grey code is and how it works and is used.


C# Gray code generator



If you're interested in C# programming you might find this helpful in order to explain how to calculate Gray code.

We will make a console application that converts regular binaries into Gray code binaries. It will output them next to each other so to visualize the difference, it will look like this:

imagehttp://admin.morkalork.com/uploads/images/binaries/BinaryToGrayConsole.png

Now, there are easy ways to convert decimals to binary and binaries to Gray code and there are hard ways. If you want an easy way out you can read my blog on the subject here.
This program will do it the hard way =()

First, we're gonna need two arrays that can hold 16 values.


string[] binaries = new string[16];
string[] grays = new string[16];


The hard way of converting decimal values to binaries is to use modulus. What we do is that we take the number to convert and divide it by two. If there is a remainder, we add a 1, otherwise a 0.
As an example we can try it out on the number 3, that we know must be 0011 in binaries:

3 % 2 = 1
1 % 2 = 1
0 % 0 = 0
0 % 0 = 0


Funny thing here. We seem to have a remainer after the second step as well, but since we run this integer style we round down. But since there was a remainder we add a 1 to the binary.

The C# code to create binaries thus looks like this:


//=========CREATE BINARY ARRAY===========
binaries[0] = ""; //We need something to index from

for (int i = 0;i <= 15 ;i++ )
{
int currentNumber = i;

//Convert iterator to binary
while (currentNumber != 0)
{
binaries[italic] = (currentNumber % 2).ToString() + binaries[italic];
currentNumber = currentNumber / 2;
}

//Add missing zeroes
while (binaries[italic].Length != 4)
{
binaries[italic] = "0" + binaries[italic];
}
}


We can also note that we have a smaller loop after the converting event where we add zero´s to the binary in order to make it a 4-bit value.

Now we come to the Gray code converting part. Happy days! We will use what we've learned so far:


//==========CREATE GRAY ARRAY=============
for (int i = 0;i <= 15 ;i++ ) //Outer loop, for each binary
{
for (int j = 3;j >= 0 ;j-- ) //Inner loop, for each binary bit
{
//Run the XOR check
if(j != 0)
{
if (binaries[i][j]=='0' && binaries[i][j-1]=='0')
grays[i] = "0" + grays[i];

if (binaries[i][j]=='1' && binaries[i][j-1]=='1')
grays[i] = "0" + grays[i];

if (binaries[i][j]=='0' && binaries[i][j-1]=='1')
grays[i] = 1 + grays[i];

if (binaries[i][j]=='1' && binaries[i][j-1]=='0')
grays[i] = 1 + grays[i];
}
else
{
if (binaries[i][j]=='0')
grays[i] = "0" + grays[i];

if (binaries[i][j]=='1')
grays[i] = 1 + grays[i];
}
}
}


As we can see, we run through every bit of every binary and the bit after it (read from right to left) and make an XOR check. If however we are checking the MSB (Most Significant Bit) we make a check towards 0 since we can add a 0 to a 4-bit (0011 -> 00011) without changing it's value.

After that, it's just a matter of outputting the result:


//===============OUTPUT========================
Console.WriteLine("#    Binary    Gray code   " + Environment.NewLine);
for (int k = 0;k < binaries.Length ;k++ )
Console.WriteLine("{0}:    {1}    {2}   ",k, binaries[k], grays[k]);

Console.Read();


The full source code can be downloaded here:


Hope you enjoyed reading it! Please leave your views and any errors you might (hopefully not) find =D

Article comments

Feel free to comment this article using a facebook profile.

I'm using facebook accounts for identification since even akismet couldn't handle all the spam I receive every day.

How to understand and use Gray code