Gray code
Counting with one bit changing at a time
Gray code is a binary numbering in which consecutive values differ in exactly one bit, which removes the transient glitches ordinary binary counting causes when several bits flip at the same time.
Builds onBinary numbers
Binary counts by the carry rule, and that rule sometimes flips a lot of bits in a single step: going from
7 to 8 the pattern jumps 0111 to 1000, and all four bits change at once. On paper that is fine. In hardware it is a problem, because no two wires ever switch at the exact same instant. Gray code is a different way to order the same patterns so that every step changes just one bit, and that one change is what makes it safe to read a value while it is still moving. Convert any number to Gray code and watch the single-bit steps in the Gray code converter.Picture a mechanical counter wheel reading out a position in binary. As it rolls from
7 (0111) to 8 (1000), the four bits do not all flip together: for a brief moment the wheels might show 1111 (15) or 0000 (0), a value that was never meant to appear. If something samples the counter at that instant, it reads garbage. Gray code relabels the count so only one wheel ever moves per step, so there is no in-between pattern to misread.Why several bits flipping is a problem
Real signals have slightly different delays, so when a counter advances and four bits are supposed to change together, they actually change one shortly after another. During that tiny window the output passes through invalid intermediate codes. Feed that output into a decoder and those spurious codes become spurious select pulses: the wrong line briefly fires. Gray code sidesteps the whole issue. Because consecutive values differ in only one bit, the worst a mistimed read can do is return the old value or the new value, never a wrong third value in between.
The single-bit-change property
Here is the standard 3-bit (reflected) Gray code beside plain binary. Read down the Gray column and check each step against the one above it: exactly one bit flips every time, and that includes the wrap from the last row back to the first (
100 to 000 flips only the top bit), so a wheel that keeps turning never sees a multi-bit jump.| decimal | binary | gray |
|---|---|---|
| 0 | 000 | 000 |
| 1 | 001 | 001 |
| 2 | 010 | 011 |
| 3 | 011 | 010 |
| 4 | 100 | 110 |
| 5 | 101 | 111 |
| 6 | 110 | 101 |
| 7 | 111 | 100 |
011 to 100 flips all three bits; in Gray the same step (010 to 110) flips only one. Every Gray step, including the cyclic wrap 100 back to 000, changes a single bit.Building it: reflect and prefix
Gray code is also called reflected binary code because of how you build it. Start with the 1-bit code, then grow it one bit at a time by mirroring:
- Start with the 1-bit list:
0,1. - Reflect it: write the list, then write it again reversed below itself, giving
0, 1, 1, 0. - Prefix: put a
0in front of every entry in the top (original) half and a1in front of every entry in the bottom (reflected) half. - Repeat to add another bit.
1-bit: 0 1 2-bit: 00 01 11 10 3-bit: 000 001 011 010 110 111 101 100
The reflection is exactly why only one bit ever changes: the mirror line sits between two entries that are identical except for the new prefix bit, and inside each half the property already held by construction.
Converting binary to Gray and back
You rarely build Gray code by hand; you convert. Going from binary to Gray, each Gray bit is the XOR of two neighbouring binary bits (the bit and the one just above it), and the top bit is copied unchanged:
g_i = b_i ⊕ b_(i+1) (the most significant bit has no neighbour above, so g_MSB = b_MSB)
For example, binary
0110 (decimal 6): the top bit 0 copies to g3 = 0; then g2 = b2 XOR b3 = 1 XOR 0 = 1, g1 = b1 XOR b2 = 1 XOR 1 = 0, g0 = b0 XOR b1 = 0 XOR 1 = 1. So 0110 becomes Gray 0101.Going from Gray back to binary is *not* the same formula. The top bit still copies (
b_MSB = g_MSB), but each lower binary bit is the XOR of the Gray bit with the binary bit you just computed above it, a running XOR from the top down:b_MSB = g_MSB b_i = g_i ⊕ b_(i+1) (working downward from the top bit)
Decoding Gray
0101 back: b3 = g3 = 0; b2 = g2 XOR b3 = 1 XOR 0 = 1; b1 = g1 XOR b2 = 0 XOR 1 = 1; b0 = g0 XOR b1 = 1 XOR 1 = 0. That recovers binary 0110 (decimal 6), exactly where we started.The binary-to-Gray direction is the easy one to wire: it is just one XOR gate per bit on adjacent inputs, with the top bit passing straight through. The figure below is that converter for three bits.
B2 passes straight to G2; G1 = B2 XOR B1 and G0 = B1 XOR B0. Open it in the lab, dial the binary inputs through 000 to 111, and confirm the probes spell the Gray column from the table above.Where Gray code is used
The classic use is a rotary or optical shaft encoder: a disc with concentric tracks read by sensors to report an angle. With binary tracks, a sensor straddling a boundary at the multi-bit transition could report a wildly wrong angle; with Gray-coded tracks only one track changes at a boundary, so the worst error is off by one step. Two more places it shows up: the axes of a Karnaugh map are ordered in Gray code so that physically adjacent cells differ in exactly one variable (that is what makes a K-map's groupings valid), and a counter value that must cross between two unrelated clock domains is Gray-coded so a mistimed sample can be wrong by at most one count instead of by an arbitrary garbage value.
Common mistakes. Gray code is an *ordering*, not a place-value system: you cannot read its value by adding column weights the way you do in binary, you must convert it to binary first. Three more traps: the most significant bit is copied straight across (there is no XOR on it); the two conversion directions use different rules (binary to Gray is an independent XOR of each pair of neighbours, Gray to binary is a cumulative running XOR from the top down, so do not reuse one formula for both); and remember the code is cyclic, so the step from the last value back to the first also changes only one bit, which is the whole point for a wheel that keeps turning.
Try it
Convert the binary number
1011 to Gray code using g_i = b_i XOR b_(i+1), then convert your Gray answer back to binary with the running-XOR rule to check it.Answer
Build it in the lab ↗Binary
1011 is b3 b2 b1 b0 = 1 0 1 1. To Gray: g3 = b3 = 1; g2 = b2 XOR b3 = 0 XOR 1 = 1; g1 = b1 XOR b2 = 1 XOR 0 = 1; g0 = b0 XOR b1 = 1 XOR 1 = 0. So the Gray code is 1110. Back to binary: b3 = g3 = 1; b2 = g2 XOR b3 = 1 XOR 1 = 0; b1 = g1 XOR b2 = 1 XOR 0 = 1; b0 = g0 XOR b1 = 0 XOR 1 = 1, recovering 1011.Gray code is the first time you reorder bits for a *physical* reason rather than a numeric one: it trades a tidy place-value reading for a guarantee that nothing glitches mid-change. You will meet that guarantee again on a Karnaugh map's axes and wherever a counter is read by something on a different clock. Next, another way of coding numbers chosen for human convenience: binary-coded decimal, which keeps each decimal digit in its own group of bits.
Frequently asked
What is Gray code?
Gray code is a binary numbering in which consecutive values differ in exactly one bit. It reorders the same bit patterns as ordinary binary so that advancing by one step never flips more than a single bit, which avoids the transient wrong readings caused when several bits switch at slightly different times.
Why does only one bit change in Gray code?
By construction. Gray code is built by reflecting the list and prefixing a new bit, so neighbouring entries are always identical except for one position. That single-bit-change property means a value read while it is changing can only be the old or the new value, never an invalid pattern in between.
How do you convert binary to Gray code?
Copy the most significant bit unchanged, then make every other Gray bit the XOR of the binary bit and the binary bit just above it:
g_i = b_i XOR b_(i+1). For example binary 0110 becomes Gray 0101. It is one XOR gate per bit on adjacent inputs.How do you convert Gray code back to binary?
Use a running XOR from the top down: the most significant binary bit equals the most significant Gray bit, and each lower bit is
b_i = g_i XOR b_(i+1), XORing the Gray bit with the binary bit you just computed above it. This is a different rule from the binary-to-Gray direction, which XORs neighbouring input bits independently.Where is Gray code used?
In rotary and optical shaft encoders (so a sensor at a boundary is at worst off by one step), in the axis ordering of a Karnaugh map (so adjacent cells differ in one variable), and in clock-domain crossing, where a counter is Gray-coded so a mistimed sample can be wrong by at most one count rather than by an arbitrary value.
Every lesson here builds toward one thing: a working CPU, from the transistor up.
Open the free lab →