Gray code
A way of counting where only one bit changes at a time, and why that avoids a nasty glitch.
A counter that changes one bit at a time
Plain binary counting has a habit you may not have noticed. Going from 3 to 4 is 011 to 100, and all three bits change at once. From 7 to 8 is 0111 to 1000: four bits change. In a real circuit nothing changes at exactly the same instant, so for a moment during that step the wires can show a pattern that is neither the old value nor the new one.
Gray code is a different order for the same patterns, chosen so that every step changes exactly one bit. Its formal name is reflected binary code, and it is not a different way of writing numbers: the patterns are the same 0s and 1s, just listed in a different sequence. Step through the widget and compare the two columns.
In the binary column the number of lit digits varies; in the Gray column it is always exactly one, even on the wrap from the last value back to 0.
Why?: what is wrong with a few bits changing at once?
Picture a rotary encoder, the disc inside a volume knob or a robot's wheel that reports how far it has turned. Each bit is a track on the disc read by its own sensor. As the disc turns from position 3 (011) to position 4 (100), the three sensors do not flip at precisely the same moment, so between the two readings you might see 111 or 000: position 7 or position 0, both badly wrong. With Gray code only one track changes between neighbouring positions, so the worst a mistimed read can do is show the old value or the new one, and both are within one step of the truth. The same problem appears whenever a value is read while it is changing, such as a count crossing from one clock to another.
Building the sequence
Gray code is built by reflecting. Start with one bit: 0, 1. Write the list out, then write it again backwards underneath, like a reflection in a mirror: 0, 1, 1, 0. Now put a 0 in front of the original half and a 1 in front of the reflected half: 00, 01, 11, 10. That is the 2 bit sequence, and every step changes one bit. Do it again, reflect and prefix, and you get the 3 bit sequence:
000, 001, 011, 010, 110, 111, 101, 100
Why does it work? The two halves are mirror images, so where they meet, the two middle entries are identical apart from the new front bit. And within each half the steps are the steps of the shorter code, which already changed one bit each. So the new sequence changes one bit per step too, all the way along.
Converting binary to Gray and back
You do not need to build the whole list to find the Gray code of one number. Write the binary number, write it again shifted one place to the right underneath, and XOR the columns. Remember XOR from stage 2: the output is 1 when the two inputs differ. The top bit has nothing above it and is copied unchanged.
Worked example. What is 6 in Gray code, and how do you get back?
6 in binary is 110. Shifted right by one it is 011. XOR column by column: 1 with 0 is 1, 1 with 1 is 0, 0 with 1 is 1. The Gray code is 101, and it is entry number 6 in the list above, counting the first entry as 0.
Going back runs from the left. Copy the top bit: 1. Each following binary bit is the Gray bit in that position XOR the binary bit you have just written: 0 XOR 1 = 1, then 1 XOR 1 = 0. That gives 110, which is 6 again.
In hardware, binary to Gray is a single row of XOR gates, one per bit below the top, all working at once. Gray to binary is a chain, because each bit needs the one you just worked out, but it is still only XOR gates.
Common mistake: reading a Gray pattern as a binary number
The Gray code for 6 is 101, and 101 read as ordinary binary is 5. Both are true, and neither means 6 equals 5. A pattern only has a value once you say which code it is in. When you read a Gray-coded sensor, convert first and then treat the result as a number, never the other way round.
You have met this before
Look back at the Karnaugh maps in stage 4. The rows and columns were labelled 00, 01, 11, 10, not 00, 01, 10, 11. That is the 2 bit Gray code, and it is the whole reason the map works: neighbouring squares differ in exactly one variable, so a group of squares is a set of inputs where one variable does not matter, and that variable drops out of the term. The map even wraps around at the edges, because 10 and 00 differ in one bit too, just like the last and first entries of the widget.
What to remember
- Gray code is an order for bit patterns in which consecutive values differ in exactly one bit, including the wrap.
- It matters wherever a value is read while it changes: a mistimed read is then off by at most one step.
- Build it by reflecting the list and prefixing 0 to the first half and 1 to the second.
- Binary to Gray is the number XOR itself shifted right by one; Gray to binary runs the XOR from the top bit down.
- The 00, 01, 11, 10 headings of a Karnaugh map are the 2 bit Gray code.
Check yourself
Get 5 right in a row and the lesson is done. A wrong answer costs the run, not the lesson.
Counting in 4 bit Gray code, 0 is 0000 and 1 is 0001. Which bit changes between them?
0000 → 0001
Already know this? and come back to the quiz any time.