Gray Code

Count so that only one bit changes per step. Build Gray code by reflection, and convert to it and back with XOR gates.

You Will Be Able To

  • Explain why a count that changes one bit per step is safe to read while it changes.
  • Build the Gray code of any width by reflection.
  • Convert binary to Gray with b ^ (b >> 1) and Gray to binary with a running XOR.
Lesson
G1.7
Time
20 min
Runs on
Your browser
Check
5 questions

A count goes from 7 to 8 on a bus whose four wires arrive at different times. In binary all four bits change. A reader that samples mid-change sees 6, 4 or 0: values that were never sent.

Seven to Eight on a Skewed BusBit k of the bus arrives k + 1 ns after the source changes at 10 ns. One column per nanosecond.
01234time (ns)10.511.512.513.514.5binary bus01110110010000001000binary value76408gray bus01001100never sentsettled
Scroll horizontally ↔
  1. Cycle 1

    Bit 0 has arrived and the others have not. The binary bus reads 0110, which is 6.

  2. Cycle 3

    Three bits have changed and the top one has not. The binary bus reads 0, far from both 7 and 8.

  3. Cycle 4

    The Gray bus changed only its top bit. Before that moment it read 7, after it 8, and never anything else.

Measured on the simulator. A Gray reader can be one step late, but never wrong.

One Bit Changes per Step

In Gray code, neighbouring numbers differ in exactly one bit. That includes the wrap from the largest value back to 0.

Bits That Flip per StepEach column is one step of a 4-bit counter. The last column is the wrap from 15 to 0.
0123456789101112131415n1234567891011121314150binary0001001000110100010101100111100010011010101111001101111011110000gray0001001100100110011101010100110011011111111010101011100110000000binary flips1213121412131214gray flips7 to 8wrap
Scroll horizontally ↔
  1. Cycle 3

    3 to 4 flips three binary bits. The Gray code flips one.

  2. Cycle 7

    7 to 8 flips all four binary bits. The Gray code flips only its top bit.

  3. Cycle 15

    The wrap from 15 to 0 flips four binary bits and one Gray bit.

Measured on the simulator: at most 4 binary flips and exactly 1 Gray flip per step.

Two places need this. A position encoder reads a disk while it turns. A FIFO passes its pointers between two clocks. In both, a value is read while it changes. With one changing bit, the reader gets the old value or the new one.

Binary Beside Gray
23
22
21
20

Weights show bit magnitudes. For signed values, the leftmost bit has a negative weight.

Unsigned
7

Binary-reflected Gray: 0100

  1. 7. Binary 0111, Gray 0100.
  2. 8. Binary 1000, Gray 1100. Four binary bits changed and one Gray bit.

Click the bits of the binary value. The panel shows its Gray code.

Building Gray Code by Reflection

Gray code of n + 1 bits is built from the code of n bits. Write the list, then write it again in reverse order below it. Put 0 in front of the first half and 1 in front of the second.

Reflect and PrefixArrows show how each list is built from the one before.
  • Neutral
  • Step
  • Data
Reflect and prefixArrows show how each list is built from the one before. neutral 1 bit 0, 1 step Reflect 0, 1 | 1, 0 neutral 2 bits 00, 01, 11, 10 step Reflect 00, 01, 11, 10 | 10,11, 01, 00 neutral 3 bits 000, 001, 011, 010,110, 111, 101, 100 copy, then reverseprefix 0 | 1copy, then reverseprefix 0 | 1
  1. neutral 1 bit0, 1
    • copy, then reverse → Reflect
  2. step Reflect0, 1 | 1, 0
    • prefix 0 | 1 → 2 bits
  3. neutral 2 bits00, 01, 11, 10
    • copy, then reverse → Reflect
  4. step Reflect00, 01, 11, 10 | 10, 11, 01, 00
    • prefix 0 | 1 → 3 bits
  5. neutral 3 bits000, 001, 011, 010, 110, 111, 101, 100
  1. Reflect

    Copy the 1-bit list 0, 1 and add it again backwards: 0, 1, 1, 0.

  2. Prefix

    A 0 in front of the first half and a 1 in front of the second: 00, 01, 11, 10.

  3. Once more

    The same two moves give the 3-bit code. At the seam the two halves meet on the same word, so only the new top bit changes.

Read the diagram as text
  • 1 bit: 0, 1
  • Reflect: 0, 1 | 1, 0
  • 2 bits: 00, 01, 11, 10
  • Reflect: 00, 01, 11, 10 | 10, 11, 01, 00
  • 3 bits: 000, 001, 011, 010, 110, 111, 101, 100
  • 1 bit → Reflect: copy, then reverse
  • Reflect → 2 bits: prefix 0 | 1
  • 2 bits → Reflect: copy, then reverse
  • Reflect → 3 bits: prefix 0 | 1

This is the binary-reflected Gray code, the one used almost everywhere.

The reflection explains the one-bit rule. Inside each half the old code already changes one bit per step. At the seam and at the wrap only the new top bit changes.

Binary to Gray and Back

Encoding needs one XOR per bit. Each Gray bit is the binary bit XOR the binary bit above it: g = b ^ (b >> 1). The top bit stays as it is.

Decoding goes the other way. The top binary bit is the top Gray bit. Each lower binary bit is the binary bit above it XOR its own Gray bit. The XOR runs down the whole word.

Single XOR

b = g ^ (g >> 1);

Measured: 12 of 16 wrong.

Running XOR

b[3] = g[3];
for (int i = 2; i >= 0; i--)
  b[i] = b[i + 1] ^ g[i];

Measured: 0 of 16 wrong.

The running XOR is a chain: an n-bit decoder has n - 1 XOR gates in a row. Each binary bit is also the XOR of all Gray bits from the top down to its own position.

Asked in interviews
  1. Why are FIFO pointers passed between clocks in Gray code?

    A pointer is sampled while it may be changing. In Gray code only one bit changes per step. The sample is the old value or the new one, never a third value.

  2. How do you convert binary to Gray and back?

    Encode with g = b ^ (b >> 1). Decode with a running XOR from the top. The top bit copies across. Each lower bit is the binary bit above it XOR its own Gray bit.

  3. Does Gray code work for a counter that wraps at 10?

    Not at the wrap. The Gray code of 9 is 1101, so going back to 0 changes three bits. The one-bit rule holds for a power-of-two length.

Try It

Each line is one step. Binary changes up to four bits at once: at 7 to 8 and at the wrap to 0. Gray changes exactly one bit every time.

The XOR of the old and the new value has a 1 for every changed bit, and $countones counts them.

Change the encoder to g = b ^ (b << 1); and run again. The Gray column is no longer one flip per step.

RUNIcarus Verilog · in your browser
Edit the code, then run it
Expected: 1 binary 0001 gray 0001 flips: binary 1, gray 1 2 binary 0010 gray 0011 flips: binary 2, gray 1 3 binary 0011 gray 0010 flips: binary 1, gray 1 4 binary 0100 gray 0110 flips: binary 3, gray 1 5 binary 0101 gray 0111 flips: binary 1, gray 1 6 binary 0110 gray 0101 flips: binary 2, gray 1 7 binary 0111 gray 0100 flips: binary 1, gray 1 8 binary 1000 gray 1100 flips: binary 4, gray 1 9 binary 1001 gray 1101 flips: binary 1, gray 1 10 binary 1010 gray 1111 flips: binary 2, gray 1 11 binary 1011 gray 1110 flips: binary 1, gray 1 12 binary 1100 gray 1010 flips: binary 3, gray 1 13 binary 1101 gray 1011 flips: binary 1, gray 1 14 binary 1110 gray 1001 flips: binary 2, gray 1 15 binary 1111 gray 1000 flips: binary 1, gray 1 0 binary 0000 gray 0000 flips: binary 4, gray 1 most flips in one step: binary 4, gray 1

Check Yourself

Predict the outputThe program decodes the Gray code 1011 with a running XOR. What exact line does it print?
module tb;
  logic [3:0] g, b;
  initial begin
    g = 4'b1011;
    b[3] = g[3];
    for (int i = 2; i >= 0; i--) b[i] = b[i + 1] ^ g[i];
    $display("%0d", b);
  end
endmodule
Spot the bugEach option converts the 4-bit binary value b to Gray code g. The bench checks one flip per step over all 16 steps and decodes every code back. Which option fails?
ConceptThe 2-bit Gray code is 00, 01, 11, 10. What is the 3-bit code built from it by reflection?
ConceptA 4-bit binary count passes 7 to 8 on a bus whose wires arrive at different times. Which values can a reader see?
ConceptHow many XOR gates does a 4-bit binary-to-Gray encoder need?

Common Mistakes

Wrong Shift left in the binary-to-Gray conversion.

Each Gray bit is a binary bit XOR the bit above it, which a right shift brings down.

Fix Shift right by one.

Before
g = b ^ (b << 1);
After
g = b ^ (b >> 1);

Wrong Decode Gray with the same single XOR as the encoder.

Each binary bit depends on every Gray bit above it. Measured: one XOR decodes 12 of the 16 codes wrongly.

Fix Use a running XOR from the top bit down.

Before
b = g ^ (g >> 1);
After
b[3] = g[3];
for (int i = 2; i >= 0; i--)
  b[i] = b[i + 1] ^ g[i];

Wrong Count from 0 to 9 in Gray code and expect one bit to change at the wrap.

The Gray code of 9 is 1101, so 9 back to 0 changes three bits.

Fix Wrap only at a power of two, or use a code made for that length.

Wrong Expect Gray code to make arithmetic easier.

Gray code has no simple adder. Its value is the running XOR of its bits.

Fix Count in binary inside a block; convert to Gray only where the value must cross a boundary.

Remember

  • Gray code changes exactly one bit per step, including the wrap at a power of two.
  • A value read while it changes is then either the old one or the new one.
  • Build n + 1 bits from n bits: reflect the list and prefix 0 and 1.
  • Encode with g = b ^ (b >> 1); decode with a running XOR from the top bit.

Practice

Report a problem with this page