# 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. Group: Number & logic URL: https://digiwleea.wleeaf.dev/learn/gray-code/ [Binary](https://digiwleea.wleeaf.dev/learn/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](https://digiwleea.wleeaf.dev/tools/gray-code-converter/). > **TIP:** 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](https://digiwleea.wleeaf.dev/learn/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](https://digiwleea.wleeaf.dev/learn/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 | _Three-bit binary versus Gray code. In binary, 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: 1. Start with the 1-bit list: `0`, `1`. 2. **Reflect** it: write the list, then write it again **reversed** below itself, giving `0, 1, 1, 0`. 3. **Prefix**: put a `0` in front of every entry in the top (original) half and a `1` in front of every entry in the bottom (reflected) half. 4. 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](https://digiwleea.wleeaf.dev/learn/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 XOR 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 XOR 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. _Circuit diagram: A 3-bit binary-to-Gray converter. The top bit 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](https://digiwleea.wleeaf.dev/learn/karnaugh/) 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. > **WARN:** **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](https://digiwleea.wleeaf.dev/learn/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. **Q (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. **A:** 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`. > **KEY:** 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](https://digiwleea.wleeaf.dev/learn/karnaugh/)'s axes and wherever a [counter](https://digiwleea.wleeaf.dev/learn/counter/) is read by something on a different clock. Next, another way of coding numbers chosen for human convenience: [binary-coded decimal](https://digiwleea.wleeaf.dev/learn/bcd/), which keeps each decimal digit in its own group of bits. ### FAQ **Q:** What is Gray code? **A:** 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. **Q:** Why does only one bit change in Gray code? **A:** 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. **Q:** How do you convert binary to Gray code? **A:** 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. **Q:** How do you convert Gray code back to binary? **A:** 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. **Q:** Where is Gray code used? **A:** 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](https://digiwleea.wleeaf.dev/learn/karnaugh/) (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.