Gray Code

Knowledge Summary

Definition of Gray Code

Gray code is a binary encoding method in which adjacent codes differ in exactly one bit.

Gray Code vs Natural Binary Code

Conversion Formulas

Binary -> Gray code:

$G_i = B_i \oplus B_{i+1}$

The highest bit stays the same. Each remaining bit is the XOR of the current bit and the previous bit of the original binary number.

int binaryToGray(int n) {
    return n ^ (n >> 1);
}

Gray code -> Binary:

The highest bit stays the same. Each remaining binary bit is the XOR of the current Gray-code bit and the already determined previous binary bit.

1int grayToBinary(int g) {
2    int b = 0;
3    for (; g; g >>= 1)
4        b ^= g;
5    return b;
6}

Applications of Gray Code

1. Reducing errors: in digital signal transmission, adjacent values differ by only one bit, reducing glitches
2. Rotary encoders: used for mechanical position encoding
3. Karnaugh maps: Gray code ordering is used in logic circuit simplification

Frequently Tested Points

• Given a binary code, find its Gray code
• Given a Gray code, find its binary code
• The generation pattern of n-bit Gray codes