Fundamentals of Data Representation: Gray coding

Changing binary numbers from one value to another can involve changing several bits at once. For example changing from 7 to 8, 0111 to 1000 involves 4 digits changing, but why is this an issue?

As you know, computers are very fast and sometimes multiple things happen at once, especially if you are dealing with realtime systems. If program 'A' wanted to read a number stored by program 'B', and read the number mid way through that number changing, program 'A' might read a midstate, an incorrect number.

Hello Penwell, i can see u (;

0111 Program 'B' tells the number 7 to increment by 1 to 8
0101 (midstate 5) digit 2 changes
1101 (midstate 13) digit 4 changes <-Program 'A' fetches this number
1001 (midstate 9) digit 3 changes
1000 (final 8) digit 1 changes

Taking the simple example above, imagine if we were dealing with money where program B was working out the interest on your account, increasing your money from £7 to £8. Program A might be a cash machine telling you how much money you had in your account. If you look at the program above you see that the cash machine would tell you that you had £13, so you take out £13 and then become immediately overdrawn. (Bank databases actually use locking to solve this, but the example is a good one).

This could be particularly catastrophic if this error occurred in the military. Can you imagine an anti-air battery (Program A) deciding where to fire its missiles, and due to reading the direction of enemy planes stored on a remote radar system (Program B), shooting the missile in the wrong direction and shooting down an allied plane!

What is needed is Gray Code, a number system that changes one bit at a time to avoid midstates. Take a look at the examples below and see how only one bit changes for subsequent number:

Binary Number	Gray Code
Rotary encoder for angle-measuring devices marked in 3-bit binary 0 = 000 1 = 001 2 = 010 3 = 011 4 = 100 5 = 101 6 = 110 7 = 111	Rotary encoder for angle-measuring devices marked in 3-bit binary-reflected Gray code (BRGC) 0 = 000 1 = 001 2 = 011 3 = 010 4 = 110 5 = 111 6 = 101 7 = 100

Usually in the exam you wouldn't be asked to convert anything more that 3 or 4 bits. But in case you do here is an easy method for converting binary to gray code.

Converting binary to gray code

1. Take the first bit as it is.
2. For the next bit, add the previous bit to the current bit.
3. If you have a carry ignore it. E.g. 1+1=10. Take it as 0 rather than 10.
4. Repeat for the rest of the bits.

Exercise: Gray Code Explain how Gray Code works: Answer: Gray code works by only one bit changing between subsequent numbers. This is to avoid midstates Explain why we might want to use Gray Code Answer: We need to use gray code in situations where we are worried about midstates. That means in situations where we might accidentally read a value before it has completely changed from one state to another, giving us an incorrect value. Complete the following sequence of Gray Code states: 0 = 000 1 = 001 2 = ... 3 = ... 4 = ... 5 = 111 6 = 101 7 = 100 Answer: 0 = 000 1 = 001 2 = 011 3 = 010 4 = 110 5 = 111 6 = 101 7 = 100