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.
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|
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.
- Take the first bit as it is.
- For the next bit, add the previous bit to the current bit.
- If you have a carry ignore it. E.g. 1+1=10. Take it as 0 rather than 10.
- Repeat for the rest of the bits.
Gray code works by only one bit changing between subsequent numbers. This is to avoid midstates
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.
0 = 000 1 = 001 2 = 011 3 = 010 4 = 110 5 = 111 6 = 101 7 = 100