Fundamentals of Data Representation: Gray coding

From Wikibooks, open books for an open world
Jump to: navigation, search

UNIT 1 - ⇑ Fundamentals of Data Representation ⇑

← Hamming code Gray coding Images →

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 a 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 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
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