Gray Code

Gray code is a binary encoding system where adjacent values differ by only one bit, eliminating the multi-bit transition errors that plague standard binary encoding. From rotary encoders and ADCs to clock domain crossing and finite state machine design, Gray code ensures error-free transitions in applications where timing uncertainties and glitches could cause catastrophic failures.

Learning Objectives

• Understand how Gray code differs from binary code in single-bit-change property
• Convert between binary and Gray code using XOR-based algorithms
• Analyze why Gray code prevents glitches in asynchronous systems and state machines
• Apply Gray code to clock domain crossing, ADCs, and rotary encoder applications

Reading time: 12 minutes | Difficulty: Intermediate | Prerequisites: Binary System, Finite State Machines

What is Gray Code?

Gray code, also known as Gray binary code or reflected binary code, is a binary numeral system where adjacent values differ by only one bit. In other words, Gray code is a binary code where each successive value differs from the previous value by only one bit.

For example, the binary representation of decimal numbers 1 and 2 is 0001 and 0010 respectively. Note that two LSB bits (bit#0 and bit#1) have to change for the transition from 1 to 2. In Gray code, 1 and 2 are represented by 0001 and 0011 respectively, but the same transition now requires only a change of one bit (bit#1 from LSB).

Binary vs. Gray Code Transition Comparison

This code is used in many applications, including digital communications, error correction, and electronic devices. One of the main advantages of Gray code is that it eliminates the possibility of errors that could occur when transitioning between two consecutive binary values.

Gray Code Table (0-15)

Here's the Gray code for binary values from 0 to 15:

Key observation: Every transition from one Gray code value to the next changes exactly one bit. This single-bit-change property is what makes Gray code valuable for error-sensitive applications.

Common Usage

1. Digital-to-Analog and Analog-to-Digital Converters (DACs/ADCs)

Gray code is used in digital-to-analog converters (DACs) and analog-to-digital converters (ADCs) to reduce the likelihood of errors in the conversion process. In these applications, the Gray code is used to represent the output voltage or the input signal in a way that minimizes the error due to small variations in the voltage or signal level.

For example, in a binary-encoded ADC, if the analog input is at the transition point between 7 (0111) and 8 (1000), timing uncertainty could cause the ADC to briefly read any value from 0 to 15 because all four bits change simultaneously. With Gray code (0100 → 1100), only one bit changes, limiting errors to adjacent values.

2. Limiting Transition Errors

Because adjacent values differ in only one bit, a bit that is misread or arrives late during a transition produces an error of at most one step. Gray code does not detect or correct errors by itself; error-detecting and error-correcting codes, such as parity or Hamming codes, are separate techniques.

3. Clock Domain Crossing (CDC)

Gray code is also used to represent a counter value, such as a FIFO pointer, that is transferred between two clock domains. This works because such a value changes by one step at a time. The value is first encoded into Gray code in the source clock domain, and then decoded from Gray code in the destination clock domain.

The advantage of using Gray code in clock domain crossing (CDC) is that it minimizes the probability of errors caused by metastability, which can occur when data is sampled at an uncertain time between two clock edges. With Gray code, even if the data is sampled at the wrong time, the resulting error is limited to a single bit flip, which can be detected and corrected more easily than if multiple bits had changed.

FIFO Pointer Synchronization: Asynchronous FIFOs use Gray-coded read and write pointers when crossing clock domains. Since pointers increment by one each cycle, Gray encoding ensures that even if the receiving clock domain samples the pointer during a transition, it will read either the old value or the new value (differing by only one bit), never a corrupted intermediate value with multiple bits in transition.

Binary to Gray Code Conversion

Converting a binary number to its equivalent Gray code representation involves a simple algorithm that can be applied to each bit in the binary number. Here's the algorithm:

1. Copy the MSB: Start with the most significant bit (MSB) of the binary number and copy it to the corresponding bit in the Gray code.
2. XOR adjacent bits: For each subsequent bit of Gray code, set it to 0 if values in the corresponding bit position in binary and the previous bit position are the same, else 1. (This is an XOR operation.)

Step-by-Step Example

Here's an example to illustrate the algorithm:

Binary number: 101011

1. Copy the most significant bit (MSB) to the corresponding bit in the Gray code.

2. For bit#4 in Gray: bit#5 and bit#4 in binary are different (1 and 0), so result should be 1.

3. For bit#3 in Gray: bit#4 and bit#3 in binary are different (0 and 1), so result should be 1.

4. For bit#2 in Gray: bit#3 and bit#2 in binary are different (1 and 0), so result should be 1.

5. For bit#1 in Gray: bit#2 and bit#1 in binary are different (0 and 1), so result should be 1.

6. For bit#0 in Gray: bit#1 and bit#0 in binary are the same (1 and 1), so result should be 0.

Result: Binary 101011 = Gray 111110

Mathematical Formula

The conversion can be expressed mathematically as:

Gray[n-1] = Binary[n-1]  (MSB, just copy)
Gray[i] = Binary[i+1] ⊕ Binary[i]  (for i = n-2 down to 0)

Where ⊕ represents XOR operation

Common Beginner Mistakes