Gray Code

Written by: maffelu , 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

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:

Decimal	Binary	Gray code
0	0000	0000
1	0001	0001
2	0010	0011
3	0011	0010
4	0100	0110
5	0101	0111
6	0110	0101
7	0111	0100
8	1000	1100
9	1001	1101
10	1010	1111
11	1011	1110
12	1100	1010
13	1101	1011
14	1110	1001
15	1111	1000

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

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

. 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 1	Value 2	Answer
True	False	True
True	True	False
False	True	True
False	False	False

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

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

There are 43 comments on this article.

satya

2010-08-21 00:37:23

nice one

raj

2010-09-01 11:39:57

it was nice explanation but try to give some examples so that learners can try them to understand better

noel

2010-09-12 20:22:06

thanks

piya

2010-10-06 23:01:42

tell me how we can understnd properly how to know the sequence of digits in gr code

Samuel

2010-10-07 09:08:45

I beg that i be assisted how i can convert binary to Gray code

Maffelu

2010-10-07 13:22:00

Samuel: The article actually explains how you convert binaries to Gray Code. The example is written in C# but is extremly general.
Is there something in the code that is unclear?

rajesh

2010-10-25 09:42:14

thanks.........

2010-11-07 01:17:14

plz tell me the method of decimal to gray code conversion

jkarretero

2010-11-10 00:04:29

In case that could be useful for someone, this is a function to convert binary to Gray code.

/*
The purpose of this function is to convert an unsigned
binary number to reflected binary Gray code.
*/
unsigned short binaryToGray(unsigned short num)
{
return (num>>1) ^ num;
}

Khan

2010-11-29 10:23:31

Few more examples could have served the purpose more usefully.Nice though!

2011-01-23 07:52:51

some how detailed explanation is needed

2011-02-10 21:19:15

where do i xor the number what value

Banahene A. Dic

2011-02-12 08:15:33

Infant for man and God I have really admire you guys site

Hop

2011-03-08 13:52:05

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

------------
two things :
1) regular binary string 0011 != 2 but == 3
2) where did the 0001 came from in the boolean xor table, i assume the 0011 comes for the graycode 2, and the 0010 for the binary 2. But where do this 0001 come from ? thx !

Rachi

2011-03-29 00:31:30

You are perfect...!

Adetoun

2011-04-05 01:55:49

Great work

dinesh kumar

2011-04-10 01:06:24

I'M CAN UNDERSTAND IN GRAY CODE NICE EXAMPLE THAT..

Junias

2011-04-12 01:19:43

convert 10101011 to gray code pls

gaurav salvi

2011-04-24 01:13:37

what is the use of gray code in any field???
(general, electronics, etc uses)

Maffelu

2011-04-24 05:51:57

gaurav salvi: The use of gray code in computers lies in the development of hard discs. Using gray code reduces errors when there is a misread on the hard disc.

You can read some more about it here actually:
http://www.duxcw.com/digest/guides/hd/hd6.htm

asem mohamed

2011-05-20 08:15:49

thx
like to learn more

albert

2011-06-14 07:22:45

i like this artical

priya

2011-07-06 23:49:40

easy to larn

priyanka

2011-07-07 00:00:27

Thaks...................

ashutosh

2011-07-22 09:50:44

most understandable

Mohammed

2011-09-03 03:59:49

understandable

Vasanth

2011-09-06 07:13:29

nice one..pls give more eg.

hari

2011-09-07 00:27:10

Interesting, the hard disk example is nice.

parth

2011-09-12 10:18:53

good...

2011-10-07 02:03:05

why we use gray code

kedir

2011-10-07 08:24:20

i like it it's easy and clear thanks!!!!

sid bloodsaw

2011-10-12 16:24:44

only thing i have to say is that the decimal number for the conversion to gray code was 3 not 2 ^.^ other than that thanks for this! i understood it now :D

younes

2011-10-16 15:08:01

thanks very good ......

azhar

2011-10-27 11:50:10

hi
this lesson is very good to understand

Albert

2011-11-15 07:04:06

hallo,
wollte eigentlich fragen, wie kann man sich einen Algorithmus Ã¼berlegen damit eine zahl kodiert in gray-code ins dezimalzahl Ã¼bertragen kann ?!!
mfg, Albert

Manal