Gray Code

Question 1

What is Gray code? (Definition)

Answer

Gray code, also called reflected binary code, is a binary code with the property that only one bit changes when a number is incremented (or decremented) by one.

Gray code, also known as reflected binary, encodes integers in binary such that two consecutive values differ by only one bit, i.e., their Hamming distance is $ 1 $.

Example:

Number	Binary	Gray
0	0000	0000
1	0001	0001
2	0010	0011
3	0011	0010
4	0100	0110
5	0101	0111
6	0110	0101
7	0111	0100
8	1000	1100

This property is useful to prevent errors during transitions between nearby values.

Question 2

How to convert binary to Gray code?

Answer

To convert a binary number $ B $ into Gray code $ G $, simply apply the following operation: $$ G = B \oplus (B >> 1) $$

Example: $$ \begin{align} 1 0 1 1 & \\ \oplus \rightarrow 1 0 1 & (1) \\ = 1 1 1 0 & \end{align} $$ The binary code 1011 corresponds to 1110 in its reflected Gray code form.

The implementation of the algorithm in a programming language can be done in one line using XOR and shift operators: function bin2gray(n) return n ^ (n >> 1)

Question 3

How to convert a decimal to Gray code?

Answer

An algorithm to convert an integer into Gray code (binary) uses successive divisions by powers of 2 and checks the parity of the rounded quotient.

To convert a decimal integer to Gray code, first convert it to binary, then apply: $$ G = B \oplus (B >> 1) $$

Example: $$ \begin{align} 29_{10} &= 11101_2 \\ 11101 >> 1 &= 01110 \\ G &= 11101 \oplus 01110 = 10011 \end{align} $$

Question 4

How to convert a string?

Answer

Gray code conversion can be done byte by byte.

Example: The character k with ASCII code $ 107 $, i.e. in binary $ 01101011 $, has Gray code: $ 01101011 \oplus 00110101 = 01011110 $, which is $ 94 $, the code of the character ^

Question 5

What are the first values in Gray Code?

Answer

The first Gray code values for 4 bits are: 0000, 0001, 0011, 0010, 0110, 0111, 0101, 0100, 1100, 1101, 1111, 1110, 1010, 1011, 1001, 1000

The corresponding decimal values are: 0, 1, 3, 2, 6, 7, 5, 4, 12, 13, 15, 14, 10, 11, 9, 8, etc. here

Question 6

What are the advantages of Gray Code?

Answer

The main advantage of Gray code is that two consecutive values differ by only one bit.

This helps to: reduce transition errors, avoid inconsistent intermediate states, improve measurement reliability, etc.

It is notably used in position encoders, analog-to-digital converters, and certain combinatorial algorithms.

Question 7

How to recognize Gray Code?

Answer

Gray code is difficult to distinguish from another binary code.

The word “gray” (gray or grey in English) can be a hint.

In a Gray code sequence, the Hamming distance between consecutive values is $ 1 $.

An ASCII message encoded with Gray code results in a simple substitution of the 128 ASCII values.

Question 8

Is there a direct formula for the n-th Gray code?

Answer

The n-th Gray code can be computed directly using: $$ G(n) = n \oplus (n >> 1) $$

This formula allows generating the entire sequence efficiently without building previous values.

Question 9

Can Gray code be used for real numbers?

Answer

Gray code applies only to discrete binary representations.

For a real number encoded in fixed-point format (such as Q4.4), apply Gray code to the underlying integer binary representation.

Question 10

What is the connection with the Tower of Hanoi?

Answer

Gray code is related to solving the Tower of Hanoi.

Each move corresponds to a change of a single bit, which exactly reflects the Gray code property. This enables systematic generation of an optimal solution.

Question 11

When was Gray Code invented?

Answer

Gray code was popularized by a patent filed in 1953 by Frank Gray, a researcher working at Bell Labs.