# Gray code

Lucal code
5 4 3 2 1
Gray code
4 3 2 1
0 0 0 0 0 0
1 0 0 0 1 1
2 0 0 1 1 0
3 0 0 1 0 1
4 0 1 1 0 0
5 0 1 1 1 1
6 0 1 0 1 0
7 0 1 0 0 1
8 1 1 0 0 0
9 1 1 0 1 1
10 1 1 1 1 0
11 1 1 1 0 1
12 1 0 1 0 0
13 1 0 1 1 1
14 1 0 0 1 0
15 1 0 0 0 1

The reflected binary code (RBC), also known as reflected binary (RB) or Gray code after Frank Gray, is an ordering of the binary numeral system such that two successive values differ in only one bit (binary digit).

For example, the representation of the decimal value "1" in binary would normally be "001" and "2" would be "010". In Gray code, these values are represented as "001" and "011". That way, incrementing a value from 1 to 2 requires only one bit to change, instead of two.

Gray codes are widely used to prevent spurious output from electromechanical switches and to facilitate error correction in digital communications such as digital terrestrial television and some cable TV systems. The use of Gray code in these devices helps simplify logic operations and reduce errors in practice.

## Function

Many devices indicate position by closing and opening switches. If that device uses natural binary codes, positions 3 and 4 are next to each other but all three bits of the binary representation differ:

Decimal Binary
... ...
3 011
4 100
... ...

The problem with natural binary codes is that physical switches are not ideal: it is very unlikely that physical switches will change states exactly in synchrony. In the transition between the two states shown above, all three switches change state. In the brief period while all are changing, the switches will read some spurious position. Even without keybounce, the transition might look like 011001101100. When the switches appear to be in position 001, the observer cannot tell if that is the "real" position 1, or a transitional state between two other positions. If the output feeds into a sequential system, possibly via combinational logic, then the sequential system may store a false value.

This problem can be solved by changing only one switch at a time, so there is never any ambiguity of position, resulting in codes assigning to each of a contiguous set of integers, or to each member of a circular list, a word of symbols such that no two code words are identical and each two adjacent code words differ by exactly one symbol. These codes are also known as unit-distance, single-distance, single-step, monostrophic or syncopic codes, in reference to the Hamming distance of 1 between adjacent codes.

## Invention

In principle, there can be more than one such code for a given word length, but the term Gray code was first applied to a particular binary code for non-negative integers, the binary-reflected Gray code, or BRGC. Bell Labs researcher George R. Stibitz described such a code in a 1941 patent application, granted in 1943. Frank Gray introduced the term reflected binary code in his 1947 patent application, remarking that the code had "as yet no recognized name". He derived the name from the fact that it "may be built up from the conventional binary code by a sort of reflection process".

In the standard encoding the least significant bit follows a repetitive pattern of 2 on, 2 off ( … 11001100 … ); the next digit a pattern of 4 on, 4 off; the ith least significant bit a pattern of 2i on 2i off. The most significant digit is an exception to this; for an n-bit Gray code, the most significant digit follows 2n-1 on 2n-1 off, the same as for the second-most significant digit, but starting at a different point in the sequence. The four-bit version of this is shown below:

Decimal Binary Gray Decimal
of Gray
0 0000 0000 0
1 0001 0001 1
2 0010 0011 3
3 0011 0010 2
4 0100 0110 6
5 0101 0111 7
6 0110 0101 5
7 0111 0100 4
8 1000 1100 12
9 1001 1101 13
10 1010 1111 15
11 1011 1110 14
12 1100 1010 10
13 1101 1011 11
14 1110 1001 9
15 1111 1000 8

For decimal 15 the code rolls over to decimal 0 with only one switch change. This is called the cyclic or adjacency property of the code.

In modern digital communications, Gray codes play an important role in error correction. For example, in a digital modulation scheme such as QAM where data is typically transmitted in symbols of 4 bits or more, the signal's constellation diagram is arranged so that the bit patterns conveyed by adjacent constellation points differ by only one bit. By combining this with forward error correction capable of correcting single-bit errors, it is possible for a receiver to correct any transmission errors that cause a constellation point to deviate into the area of an adjacent point. This makes the transmission system less susceptible to noise.

Despite the fact that Stibitz described this code before Gray, the reflected binary code was later named after Gray by others who used it. Two different 1953 patent applications use "Gray code" as an alternative name for the "reflected binary code"; one of those also lists "minimum error code" and "cyclic permutation code" among the names. A 1954 patent application refers to "the Bell Telephone Gray code". Other names include "cyclic binary code", "cyclic progression code", "cyclic permuting binary" or "cyclic permuted binary" (CPB).

The Gray code is sometimes misattributed to 19th century electrical device inventor Elisha Gray.

## History and practical application

### Mathematical puzzles

Reflected binary codes were applied to mathematical puzzles before they became known to engineers.

The binary-reflected Gray code represents the underlying scheme of the classical Chinese rings puzzle, a sequential mechanical puzzle mechanism described by the French Louis Gros in 1872.

It can serve as a solution guide for the Towers of Hanoi problem, based on a game by the French Édouard Lucas in 1883. Similarly, the so-called Towers of Bucharest and Towers of Klagenfurt game configurations yield ternary and pentary Gray codes.

Martin Gardner wrote a popular account of the Gray code in his August 1972 Mathematical Games column in Scientific American.

The code also forms a Hamiltonian cycle on a hypercube, where each bit is seen as one dimension.

### Telegraphy codes

When the French engineer Émile Baudot changed from using a 6-unit (6-bit) code to 5-unit code for his printing telegraph system, in 1875 or 1876, he ordered the alphabetic characters on his print wheel using a reflected binary code, and assigned the codes using only three of the bits to vowels. With vowels and consonants sorted in their alphabetical order, and other symbols appropriately placed, the 5-bit character code has been recognized as a reflected binary code. This code became known as Baudot code and, with minor changes, was eventually adopted as International Telegraph Alphabet No. 1 (ITA1, CCITT-1) in 1932.

About the same time, the German-Austrian Otto Schäffler [de] demonstrated another printing telegraph in Vienna using a 5-bit reflected binary code for the same purpose, in 1874.

### Analog-to-digital signal conversion

Frank Gray, who became famous for inventing the signaling method that came to be used for compatible color television, invented a method to convert analog signals to reflected binary code groups using vacuum tube-based apparatus. Filed in 1947, the method and apparatus were granted a patent in 1953, and the name of Gray stuck to the codes. The "PCM tube" apparatus that Gray patented was made by Raymond W. Sears of Bell Labs, working with Gray and William M. Goodall, who credited Gray for the idea of the reflected binary code. Part of front page of Gray's patent, showing PCM tube (10) with reflected binary code in plate (15)

Gray was most interested in using the codes to minimize errors in converting analog signals to digital; his codes are still used today for this purpose.

### Position encoders Rotary encoder for angle-measuring devices marked in 3-bit binary-reflected Gray code (BRGC) A Gray code absolute rotary encoder with 13 tracks. Housing, interrupter disk, and light source are in the top; sensing element and support components are in the bottom.

Gray codes are used in linear and rotary position encoders (absolute encoders and quadrature encoders) in preference to weighted binary encoding. This avoids the possibility that, when multiple bits change in the binary representation of a position, a misread will result from some of the bits changing before others.

For example, some rotary encoders provide a disk which has an electrically conductive Gray code pattern on concentric rings (tracks). Each track has a stationary metal spring contact that provides electrical contact to the conductive code pattern. Together, these contacts produce output signals in the form of a Gray code. Other encoders employ non-contact mechanisms based on optical or magnetic sensors to produce the Gray code output signals.

Regardless of the mechanism or precision of a moving encoder, position measurement error can occur at specific positions (at code boundaries) because the code may be changing at the exact moment it is read (sampled). A binary output code could cause significant position measurement errors because it is impossible to make all bits change at exactly the same time. If, at the moment the position is sampled, some bits have changed and others have not, the sampled position will be incorrect. In the case of absolute encoders, the indicated position may be far away from the actual position and, in the case of incremental encoders, this can corrupt position tracking.

In contrast, the Gray code used by position encoders ensures that the codes for any two consecutive positions will differ by only one bit and, consequently, only one bit can change at a time. In this case, the maximum position error will be small, indicating a position adjacent to the actual position.

### Genetic algorithms

Due to the Hamming distance properties of Gray codes, they are sometimes used in genetic algorithms. They are very useful in this field, since mutations in the code allow for mostly incremental changes, but occasionally a single bit-change can cause a big leap and lead to new properties.

### Boolean circuit minimization

Gray codes are also used in labelling the axes of Karnaugh maps since 1953 as well as in Händler circle graphs since 1958, both graphical methods for logic circuit minimization.

### Error correction

In modern digital communications, Gray codes play an important role in error correction. For example, in a digital modulation scheme such as QAM where data is typically transmitted in symbols of 4 bits or more, the signal's constellation diagram is arranged so that the bit patterns conveyed by adjacent constellation points differ by only one bit. By combining this with forward error correction capable of correcting single-bit errors, it is possible for a receiver to correct any transmission errors that cause a constellation point to deviate into the area of an adjacent point. This makes the transmission system less susceptible to noise.

### Communication between clock domains

Digital logic designers use Gray codes extensively for passing multi-bit count information between synchronous logic that operates at different clock frequencies. The logic is considered operating in different "clock domains". It is fundamental to the design of large chips that operate with many different clocking frequencies.

### Cycling through states with minimal effort

If a system has to cycle through all possible combinations of on-off states of some set of controls, and the changes of the controls require non-trivial expense (e.g. time, wear, human work), a Gray code minimizes the number of setting changes to just one change for each combination of states. An example would be testing a piping system for all combinations of settings of its manually operated valves.

A balanced Gray code can be constructed, that flips every bit equally often. Since bit-flips are evenly distributed, this is optimal in the following way: balanced Gray codes minimize the maximal count of bit-flips for each digit.

#### Gray code counters and arithmetic

George R. Stibitz utilized a reflected binary code in a binary pulse counting device in 1941 already.

A typical use of Gray code counters is building a FIFO (first-in, first-out) data buffer that has read and write ports that exist in different clock domains. The input and output counters inside such a dual-port FIFO are often stored using Gray code to prevent invalid transient states from being captured when the count crosses clock domains. The updated read and write pointers need to be passed between clock domains when they change, to be able to track FIFO empty and full status in each domain. Each bit of the pointers is sampled non-deterministically for this clock domain transfer. So for each bit, either the old value or the new value is propagated. Therefore, if more than one bit in the multi-bit pointer is changing at the sampling point, a "wrong" binary value (neither new nor old) can be propagated. By guaranteeing only one bit can be changing, Gray codes guarantee that the only possible sampled values are the new or old multi-bit value. Typically Gray codes of power-of-two length are used.

Sometimes digital buses in electronic systems are used to convey quantities that can only increase or decrease by one at a time, for example the output of an event counter which is being passed between clock domains or to a digital-to-analog converter. The advantage of Gray codes in these applications is that differences in the propagation delays of the many wires that represent the bits of the code cannot cause the received value to go through states that are out of the Gray code sequence. This is similar to the advantage of Gray codes in the construction of mechanical encoders, however the source of the Gray code is an electronic counter in this case. The counter itself must count in Gray code, or if the counter runs in binary then the output value from the counter must be reclocked after it has been converted to Gray code, because when a value is converted from binary to Gray code,[nb 1] it is possible that differences in the arrival times of the binary data bits into the binary-to-Gray conversion circuit will mean that the code could go briefly through states that are wildly out of sequence. Adding a clocked register after the circuit that converts the count value to Gray code may introduce a clock cycle of latency, so counting directly in Gray code may be advantageous.

To produce the next count value in a Gray-code counter, it is necessary to have some combinational logic that will increment the current count value that is stored. One way to increment a Gray code number is to convert it into ordinary binary code, add one to it with a standard binary adder, and then convert the result back to Gray code. Other methods of counting in Gray code are discussed in a report by Robert W. Doran, including taking the output from the first latches of the master-slave flip flops in a binary ripple counter.

As the execution of program code typically causes an instruction memory access pattern of locally consecutive addresses, bus encodings using Gray code addressing instead of binary addressing can reduce the number of state changes of the address bits significantly, thereby reducing the CPU power consumption in some low-power designs.

## Constructing an n-bit Gray code

The binary-reflected Gray code list for n bits can be generated recursively from the list for n − 1 bits by reflecting the list (i.e. listing the entries in reverse order), prefixing the entries in the original list with a binary 0, prefixing the entries in the reflected list with a binary 1, and then concatenating the original list with the reversed list. For example, generating the n = 3 list from the n = 2 list:

 2-bit list: 00, 01, 11, 10 Reflected: 10, 11, 01, 00 Prefix old entries with 0: 000, 001, 011, 010, Prefix new entries with 1: 110, 111, 101, 100 Concatenated: 000, 001, 011, 010, 110, 111, 101, 100

The one-bit Gray code is G1 = (0,1). This can be thought of as built recursively as above from a zero-bit Gray code G0 = ( Λ ) consisting of a single entry of zero length. This iterative process of generating Gn+1 from Gn makes the following properties of the standard reflecting code clear:

• Gn is a permutation of the numbers 0, ..., 2n − 1. (Each number appears exactly once in the list.)
• Gn is embedded as the first half of Gn+1.
• Therefore, the coding is stable, in the sense that once a binary number appears in Gn it appears in the same position in all longer lists; so it makes sense to talk about the reflective Gray code value of a number: G(m) = the mth reflecting Gray code, counting from 0.
• Each entry in Gn differs by only one bit from the previous entry. (The Hamming distance is 1.)
• The last entry in Gn differs by only one bit from the first entry. (The code is cyclic.)

These characteristics suggest a simple and fast method of translating a binary value into the corresponding Gray code. Each bit is inverted if the next higher bit of the input value is set to one. This can be performed in parallel by a bit-shift and exclusive-or operation if they are available: the nth Gray code is obtained by computing $n\oplus \left\lfloor {\tfrac {n}{2}}\right\rfloor$ . Prepending a 0 bit leaves the order of the code words unchanged, prepending a 1 bit reverses the order of the code words. If the bits at position $i$ of codewords are inverted, the order of neighbouring blocks of $2^{i}$ codewords is reversed. For example, if bit 0 is inverted in a 3 bit codeword sequence, the order of two neighbouring codewords is reversed

000,001,010,011,100,101,110,111 → 001,000,011,010,101,100,111,110  (invert bit 0)

If bit 1 is inverted, blocks of 2 codewords change order:

000,001,010,011,100,101,110,111 → 010,011,000,001,110,111,100,101  (invert bit 1)

If bit 2 is inverted, blocks of 4 codewords reverse order:

000,001,010,011,100,101,110,111 → 100,101,110,111,000,001,010,011  (invert bit 2)

Thus, performing an exclusive or on a bit $b_{i}$ at position $i$ with the bit $b_{i+1}$ at position $i+1$ leaves the order of codewords intact if $b_{i+1}={\mathtt {0}}$ , and reverses the order of blocks of $2^{i+1}$ codewords if $b_{i+1}={\mathtt {1}}$ . Now, this is exactly the same operation as the reflect-and-prefix method to generate the Gray code.

A similar method can be used to perform the reverse translation, but the computation of each bit depends on the computed value of the next higher bit so it cannot be performed in parallel. Assuming $g_{i}$ is the $i$ th Gray-coded bit ($g_{0}$ being the most significant bit), and $b_{i}$ is the $i$ th binary-coded bit ($b_{0}$ being the most-significant bit), the reverse translation can be given recursively: $b_{0}=g_{0}$ , and $b_{i}=g_{i}\oplus b_{i-1}$ . Alternatively, decoding a Gray code into a binary number can be described as a prefix sum of the bits in the Gray code, where each individual summation operation in the prefix sum is performed modulo two.

To construct the binary-reflected Gray code iteratively, at step 0 start with the $\mathrm {code} _{0}={\mathtt {0}}$ , and at step $i>0$ find the bit position of the least significant 1 in the binary representation of $i$ and flip the bit at that position in the previous code $\mathrm {code} _{i-1}$ to get the next code $\mathrm {code} _{i}$ . The bit positions start 0, 1, 0, 2, 0, 1, 0, 3, ....[nb 2] See find first set for efficient algorithms to compute these values.

## Converting to and from Gray code

The following functions in C convert between binary numbers and their associated Gray codes. While it may seem that Gray-to-binary conversion requires each bit to be handled one at a time, faster algorithms exist.[nb 1]

typedef unsigned int uint;

// This function converts an unsigned binary number to reflected binary Gray code.
uint BinaryToGray(uint num)
{
return num ^ (num >> 1); // The operator >> is shift right. The operator ^ is exclusive or.
}

// This function converts a reflected binary Gray code number to a binary number.
uint GrayToBinary(uint num)
{
while (mask) {           // Each Gray code bit is exclusive-ored with all more significant bits.
}
return num;
}

// A more efficient version for Gray codes 32 bits or fewer through the use of SWAR (SIMD within a register) techniques.
// It implements a parallel prefix XOR function. The assignment statements can be in any order.
//
// This function can be adapted for longer Gray codes by adding steps.

uint GrayToBinary32(uint num)
{
num ^= num >> 16;
num ^= num >>  8;
num ^= num >>  4;
num ^= num >>  2;
num ^= num >>  1;
return num;
}
// A Four-bit-at-once variant changes a binary number (abcd)2 to (abcd)2 ^ (00ab)2, then to (abcd)2 ^ (00ab)2 ^ (0abc)2 ^ (000a)2.


On newer processors, the number of ALU instructions in the decoding step can be reduced by taking advantage of the CLMUL instruction set. If MASK is the constant binary string of ones ended with a single zero digit, then carryless multiplication of MASK with the grey encoding of x will always give either x or its bitwise negation.

## Special types of Gray codes

In practice, "Gray code" almost always refers to a binary-reflected Gray code (BRGC). However, mathematicians have discovered other kinds of Gray codes. Like BRGCs, each consists of a list of words, where each word differs from the next in only one digit (each word has a Hamming distance of 1 from the next word).

### Gray codes with n bits and of length less than 2n

It is possible to construct binary Gray codes with n bits with a length of less than 2n, if the length is even. One possibility is to start with a balanced Gray code and remove pairs of values at either the beginning and the end, or in the middle. OEIS sequence A290772  gives the number of possible Gray sequences of length 2 n which include zero and use the minimum number of bits.

### n-ary Gray code

 Ternary number → ternary Gray code 0 → 000 1 → 001 2 → 002 10 → 012 11 → 011 12 → 010 20 → 020 21 → 021 22 → 022 100 → 122 101 → 121 102 → 120 110 → 110 111 → 111 112 → 112 120 → 102 121 → 101 122 → 100 200 → 200 201 → 201 202 → 202 210 → 212 211 → 211 212 → 210 220 → 220 221 → 221 222 → 222

There are many specialized types of Gray codes other than the binary-reflected Gray code. One such type of Gray code is the n-ary Gray code, also known as a non-Boolean Gray code. As the name implies, this type of Gray code uses non-Boolean values in its encodings.

For example, a 3-ary (ternary) Gray code would use the values 0,1,2. The (nk)-Gray code is the n-ary Gray code with k digits. The sequence of elements in the (3, 2)-Gray code is: 00,01,02,12,11,10,20,21,22. The (nk)-Gray code may be constructed recursively, as the BRGC, or may be constructed iteratively. An algorithm to iteratively generate the (Nk)-Gray code is presented (in C):

// inputs: base, digits, value
// output: Gray
// Convert a value to a Gray code with the given base and digits.
// Iterating through a sequence of values would result in a sequence
// of Gray codes in which only one digit changes at a time.
void toGray(unsigned base, unsigned digits, unsigned value, unsigned gray[digits])
{
unsigned baseN[digits];	// Stores the ordinary base-N number, one digit per entry
unsigned i;		// The loop variable

// Put the normal baseN number into the baseN array. For base 10, 109
// would be stored as [9,0,1]
for (i = 0; i < digits; i++) {
baseN[i] = value % base;
value    = value / base;
}

// Convert the normal baseN number into the Gray code equivalent. Note that
// the loop starts at the most significant digit and goes down.
unsigned shift = 0;
while (i--) {
// The Gray digit gets shifted down by the sum of the higher
// digits.
gray[i] = (baseN[i] + shift) % base;
shift = shift + base - gray[i];	// Subtract from base so shift is positive
}
}
// EXAMPLES
// input: value = 1899, base = 10, digits = 4
// output: baseN[] = [9,9,8,1], gray[] = [0,1,7,1]
// input: value = 1900, base = 10, digits = 4
// output: baseN[] = [0,0,9,1], gray[] = [0,1,8,1]


There are other Gray code algorithms for (n,k)-Gray codes. The (n,k)-Gray code produced by the above algorithm is always cyclical; some algorithms, such as that by Guan, lack this property when k is odd. On the other hand, while only one digit at a time changes with this method, it can change by wrapping (looping from n − 1 to 0). In Guan's algorithm, the count alternately rises and falls, so that the numeric difference between two Gray code digits is always one.

Gray codes are not uniquely defined, because a permutation of the columns of such a code is a Gray code too. The above procedure produces a code in which the lower the significance of a digit, the more often it changes, making it similar to normal counting methods.

See also Skew binary number system, a variant ternary number system where at most two digits change on each increment, as each increment can be done with at most one digit carry operation.

### Balanced Gray code

Although the binary reflected Gray code is useful in many scenarios, it is not optimal in certain cases because of a lack of "uniformity". In balanced Gray codes, the number of changes in different coordinate positions are as close as possible. To make this more precise, let G be an R-ary complete Gray cycle having transition sequence $(\delta _{k})$ ; the transition counts (spectrum) of G are the collection of integers defined by

$\lambda _{k}=|\{j\in \mathbb {Z} _{R^{n}}:\delta _{j}=k\}|\,,{\text{ for }}k\in \mathbb {Z} _{n}$ A Gray code is uniform or uniformly balanced if its transition counts are all equal, in which case we have $\lambda _{k}={\tfrac {R^{n}}{n}}$ for all k. Clearly, when $R=2$ , such codes exist only if n is a power of 2. If n is not a power of 2, it is possible to construct well-balanced binary codes where the difference between two transition counts is at most 2; so that (combining both cases) every transition count is either $2\left\lfloor {\tfrac {2^{n}}{2n}}\right\rfloor$ or $2\left\lceil {\tfrac {2^{n}}{2n}}\right\rceil$ . Gray codes can also be exponentially balanced if all of their transition counts are adjacent powers of two, and such codes exist for every power of two.

For example, a balanced 4-bit Gray code has 16 transitions, which can be evenly distributed among all four positions (four transitions per position), making it uniformly balanced:

0 1 1 1 1 1 1 0 0 0 0 0 0 1 1 0
0 0 1 1 1 1 0 0 1 1 1 1 0 0 0 0
0 0 0 0 1 1 1 1 1 0 0 1 1 1 0 0
0 0 0 1 1 0 0 0 0 0 1 1 1 1 1 1

whereas a balanced 5-bit Gray code has a total of 32 transitions, which cannot be evenly distributed among the positions. In this example, four positions have six transitions each, and one has eight:

1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 1 1 0 0 0
1 1 0 0 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 0 0 1 1
1 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 1
1 1 1 1 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 1 1 1 1

We will now show a construction and implementation for well-balanced binary Gray codes which allows us to generate an n-digit balanced Gray code for every n. The main principle is to inductively construct an (n + 2)-digit Gray code $G'$ given an n-digit Gray code G in such a way that the balanced property is preserved. To do this, we consider partitions of $G=g_{0},\ldots ,g_{2^{n}-1}$ into an even number L of non-empty blocks of the form

$\left\{g_{0}\right\},\left\{g_{1},\ldots ,g_{k_{2}}\right\},\left\{g_{k_{2}+1},\ldots ,g_{k_{3}}\right\},\ldots ,\left\{g_{k_{L-2}+1},\ldots ,g_{-2}\right\},\left\{g_{-1}\right\}$ where $k_{1}=0$ , $k_{L-1}=-2$ , and $k_{L}\equiv -1{\pmod {2^{n}}}$ ). This partition induces an $(n+2)$ -digit Gray code given by

${\mathtt {00}}g_{0},$ ${\mathtt {00}}g_{1},\ldots ,{\mathtt {00}}g_{k_{2}},{\mathtt {01}}g_{k_{2}},\ldots ,{\mathtt {01}}g_{1},{\mathtt {11}}g_{1},\ldots ,{\mathtt {11}}g_{k_{2}},$ ${\mathtt {11}}g_{k_{2}+1},\ldots ,{\mathtt {11}}g_{k_{3}},{\mathtt {01}}g_{k_{3}},\ldots ,{\mathtt {01}}g_{k_{2}+1},{\mathtt {00}}g_{k_{2}+1},\ldots ,{\mathtt {00}}g_{k_{3}},\ldots ,$ ${\mathtt {00}}g_{-2},{\mathtt {00}}g_{-1},{\mathtt {10}}g_{-1},{\mathtt {10}}g_{-2},\ldots ,{\mathtt {10}}g_{0},{\mathtt {11}}g_{0},{\mathtt {11}}g_{-1},{\mathtt {01}}g_{-1},{\mathtt {01}}g_{0}$ If we define the transition multiplicities

$m_{i}=\left|\left\{j:\delta _{k_{j}}=i,1\leq j\leq L\right\}\right|$ to be the number of times the digit in position i changes between consecutive blocks in a partition, then for the (n + 2)-digit Gray code induced by this partition the transition spectrum $\lambda '_{i}$ is

$\lambda '_{i}={\begin{cases}4\lambda _{i}-2m_{i},&{\text{if }}0\leq i The delicate part of this construction is to find an adequate partitioning of a balanced n-digit Gray code such that the code induced by it remains balanced, but for this only the transition multiplicities matter; joining two consecutive blocks over a digit $i$ transition and splitting another block at another digit $i$ transition produces a different Gray code with exactly the same transition spectrum $\lambda '_{i}$ , so one may for example designate the first $m_{i}$ transitions at digit $i$ as those that fall between two blocks. Uniform codes can be found when $R\equiv 0{\pmod {4}}$ and $R^{n}\equiv 0{\pmod {n}}$ , and this construction can be extended to the R-ary case as well.

### Long run Gray codes

Long run (or maximum gap) Gray codes maximize the distance between consecutive changes of digits in the same position. That is, the minimum run-length of any bit remains unchanged for as long as possible.

### Monotonic Gray codes

Monotonic codes are useful in the theory of interconnection networks, especially for minimizing dilation for linear arrays of processors. If we define the weight of a binary string to be the number of 1s in the string, then although we clearly cannot have a Gray code with strictly increasing weight, we may want to approximate this by having the code run through two adjacent weights before reaching the next one.

We can formalize the concept of monotone Gray codes as follows: consider the partition of the hypercube $Q_{n}=(V_{n},E_{n})$ into levels of vertices that have equal weight, i.e.

$V_{n}(i)=\{v\in V_{n}:v{\text{ has weight }}i\}$ for $0\leq i\leq n$ . These levels satisfy $|V_{n}(i)|=\textstyle {\binom {n}{i}}$ . Let $Q_{n}(i)$ be the subgraph of $Q_{n}$ induced by $V_{n}(i)\cup V_{n}(i+1)$ , and let $E_{n}(i)$ be the edges in $Q_{n}(i)$ . A monotonic Gray code is then a Hamiltonian path in $Q_{n}$ such that whenever $\delta _{1}\in E_{n}(i)$ comes before $\delta _{2}\in E_{n}(j)$ in the path, then $i\leq j$ .

An elegant construction of monotonic n-digit Gray codes for any n is based on the idea of recursively building subpaths $P_{n,j}$ of length $2\textstyle {\binom {n}{j}}$ having edges in $E_{n}(j)$ . We define $P_{1,0}=({\mathtt {0}},{\mathtt {1}})$ , $P_{n,j}=\emptyset$ whenever $j<0$ or $j\geq n$ , and

$P_{n+1,j}={\mathtt {1}}P_{n,j-1}^{\pi _{n}},{\mathtt {0}}P_{n,j}$ otherwise. Here, $\pi _{n}$ is a suitably defined permutation and $P^{\pi }$ refers to the path P with its coordinates permuted by $\pi$ . These paths give rise to two monotonic n-digit Gray codes $G_{n}^{(1)}$ and $G_{n}^{(2)}$ given by

$G_{n}^{(1)}=P_{n,0}P_{n,1}^{R}P_{n,2}P_{n,3}^{R}\cdots {\text{ and }}G_{n}^{(2)}=P_{n,0}^{R}P_{n,1}P_{n,2}^{R}P_{n,3}\cdots$ The choice of $\pi _{n}$ which ensures that these codes are indeed Gray codes turns out to be $\pi _{n}=E^{-1}\left(\pi _{n-1}^{2}\right)$ . The first few values of $P_{n,j}$ are shown in the table below.

Subpaths in the Savage–Winkler algorithm
$P_{n,j}$ j = 0 j = 1 j = 2 j = 3
n = 1 0, 1
n = 2 00, 01 10, 11
n = 3 000, 001 100, 110, 010, 011 101, 111
n = 4 0000, 0001 1000, 1100, 0100, 0110, 0010, 0011 1010, 1011, 1001, 1101, 0101, 0111 1110, 1111

These monotonic Gray codes can be efficiently implemented in such a way that each subsequent element can be generated in O(n) time. The algorithm is most easily described using coroutines.

Monotonic codes have an interesting connection to the Lovász conjecture, which states that every connected vertex-transitive graph contains a Hamiltonian path. The "middle-level" subgraph $Q_{2n+1}(n)$ is vertex-transitive (that is, its automorphism group is transitive, so that each vertex has the same "local environment" and cannot be differentiated from the others, since we can relabel the coordinates as well as the binary digits to obtain an automorphism) and the problem of finding a Hamiltonian path in this subgraph is called the "middle-levels problem", which can provide insights into the more general conjecture. The question has been answered affirmatively for $n\leq 15$ , and the preceding construction for monotonic codes ensures a Hamiltonian path of length at least 0.839N where N is the number of vertices in the middle-level subgraph.

### Beckett–Gray code

Another type of Gray code, the Beckett–Gray code, is named for Irish playwright Samuel Beckett, who was interested in symmetry. His play "Quad" features four actors and is divided into sixteen time periods. Each period ends with one of the four actors entering or leaving the stage. The play begins and ends with an empty stage, and Beckett wanted each subset of actors to appear on stage exactly once. Clearly the set of actors currently on stage can be represented by a 4-bit binary Gray code. Beckett, however, placed an additional restriction on the script: he wished the actors to enter and exit so that the actor who had been on stage the longest would always be the one to exit. The actors could then be represented by a first in, first out queue, so that (of the actors onstage) the actor being dequeued is always the one who was enqueued first. Beckett was unable to find a Beckett–Gray code for his play, and indeed, an exhaustive listing of all possible sequences reveals that no such code exists for n = 4. It is known today that such codes do exist for n = 2, 5, 6, 7, and 8, and do not exist for n = 3 or 4. An example of an 8-bit Beckett–Gray code can be found in Donald Knuth's Art of Computer Programming. According to Sawada and Wong, the search space for n = 6 can be explored in 15 hours, and more than 9,500 solutions for the case n = 7 have been found.

### Snake-in-the-box codes Maximum lengths of snakes (Ls) and coils (Lc) in the snakes-in-the-box problem for dimensions n from 1 to 4

Snake-in-the-box codes, or snakes, are the sequences of nodes of induced paths in an n-dimensional hypercube graph, and coil-in-the-box codes, or coils, are the sequences of nodes of induced cycles in a hypercube. Viewed as Gray codes, these sequences have the property of being able to detect any single-bit coding error. Codes of this type were first described by William H. Kautz in the late 1950s; since then, there has been much research on finding the code with the largest possible number of codewords for a given hypercube dimension.

### Single-track Gray code

Yet another kind of Gray code is the single-track Gray code (STGC) developed by Norman B. Spedding and refined by Hiltgen, Paterson and Brandestini in "Single-track Gray codes" (1996). The STGC is a cyclical list of P unique binary encodings of length n such that two consecutive words differ in exactly one position, and when the list is examined as a P × n matrix, each column is a cyclic shift of the first column.

The name comes from their use with rotary encoders, where a number of tracks are being sensed by contacts, resulting for each in an output of 0 or 1. To reduce noise due to different contacts not switching at exactly the same moment in time, one preferably sets up the tracks so that the data output by the contacts are in Gray code. To get high angular accuracy, one needs lots of contacts; in order to achieve at least 1° accuracy, one needs at least 360 distinct positions per revolution, which requires a minimum of 9 bits of data, and thus the same number of contacts.

If all contacts are placed at the same angular position, then 9 tracks are needed to get a standard BRGC with at least 1° accuracy. However, if the manufacturer moves a contact to a different angular position (but at the same distance from the center shaft), then the corresponding "ring pattern" needs to be rotated the same angle to give the same output. If the most significant bit (the inner ring in Figure 1) is rotated enough, it exactly matches the next ring out. Since both rings are then identical, the inner ring can be cut out, and the sensor for that ring moved to the remaining, identical ring (but offset at that angle from the other sensor on that ring). Those two sensors on a single ring make a quadrature encoder. That reduces the number of tracks for a "1° resolution" angular encoder to 8 tracks. Reducing the number of tracks still further cannot be done with BRGC.

For many years, Torsten Sillke and other mathematicians believed that it was impossible to encode position on a single track such that consecutive positions differed at only a single sensor, except for the 2-sensor, 1-track quadrature encoder. So for applications where 8 tracks were too bulky, people used single-track incremental encoders (quadrature encoders) or 2-track "quadrature encoder + reference notch" encoders.

Norman B. Spedding, however, registered a patent in 1994 with several examples showing that it was possible. Although it is not possible to distinguish 2n positions with n sensors on a single track, it is possible to distinguish close to that many. Etzion and Paterson conjecture that when n is itself a power of 2, n sensors can distinguish at most 2n − 2n positions and that for prime n the limit is 2n − 2 positions. The authors went on to generate a 504-position single track code of length 9 which they believe is optimal. Since this number is larger than 28 = 256, more than 8 sensors are required by any code, although a BRGC could distinguish 512 positions with 9 sensors.

An STGC for P = 30 and n = 5 is reproduced here:

Angle Code Angle Code Angle Code Angle Code Angle Code 0° 10000 72° 01000 144° 00100 216° 00010 288° 00001 12° 10100 84° 01010 156° 00101 228° 10010 300° 01001 24° 11100 96° 01110 168° 00111 240° 10011 312° 11001 36° 11110 108° 01111 180° 10111 252° 11011 324° 11101 48° 11010 120° 01101 192° 10110 264° 01011 336° 10101 60° 11000 132° 01100 204° 00110 276° 00011 348° 10001

Each column is a cyclic shift of the first column, and from any row to the next row only one bit changes. The single-track nature (like a code chain) is useful in the fabrication of these wheels (compared to BRGC), as only one track is needed, thus reducing their cost and size. The Gray code nature is useful (compared to chain codes, also called De Bruijn sequences), as only one sensor will change at any one time, so the uncertainty during a transition between two discrete states will only be plus or minus one unit of angular measurement the device is capable of resolving.

Since this 30 degree example was added, there has been a lot of interest in examples with higher angular resolution. In 2008, Gary Williams, based on previous work  discovered a 9-bit Single Track Gray Code that gives a 1 degree resolution. This gray code was used to design an actual device which was published on the site Thingiverse. This device was designed by etzenseep (Florian Bauer) in September, 2022.

An STGC for P = 360 and n = 9 is reproduced here:

Angle Code Angle Code Angle Code Angle Code Angle Code Angle Code Angle Code Angle Code Angle Code 0° 100000001 1° 110000001 2° 111000001 3° 111000011 4° 111000111 5° 111001111 6° 111011111 7° 111011011 8° 101011011 9° 101011111 10° 101011101 11° 101010101 12° 101010111 13° 101110111 14° 001110111 15° 001010111 16° 001011111 17° 001011011 18° 001011001 19° 001111001 20° 001111101 21° 000111101 22° 000110101 23° 000100101 24° 000101101 25° 000101001 26° 000111001 27° 000110001 28° 000010001 29° 000011001 30° 000001001 31° 100001001 32° 100001101 33° 100000101 34° 110000101 35° 010000101 36° 010000111 37° 010000011 38° 010000001 39° 000000001 40° 000000011 41° 100000011 42° 110000011 43° 110000111 44° 110001111 45° 110011111 46° 110111111 47° 110110111 48° 010110111 49° 010111111 50° 010111011 51° 010101011 52° 010101111 53° 011101111 54° 011101110 55° 010101110 56° 010111110 57° 010110110 58° 010110010 59° 011110010 60° 011111010 61° 001111010 62° 001101010 63° 001001010 64° 001011010 65° 001010010 66° 001110010 67° 001100010 68° 000100010 69° 000110010 70° 000010010 71° 000010011 72° 000011011 73° 000001011 74° 100001011 75° 100001010 76° 100001110 77° 100000110 78° 100000010 79° 000000010 80° 000000110 81° 000000111 82° 100000111 83° 100001111 84° 100011111 85° 100111111 86° 101111111 87° 101101111 88° 101101110 89° 101111110 90° 101110110 91° 101010110 92° 101011110 93° 111011110 94° 111011100 95° 101011100 96° 101111100 97° 101101100 98° 101100100 99° 111100100 100° 111110100 101° 011110100 102° 011010100 103° 010010100 104° 010110100 105° 010100100 106° 011100100 107° 011000100 108° 001000100 109° 001100100 110° 000100100 111° 000100110 112° 000110110 113° 000010110 114° 000010111 115° 000010101 116° 000011101 117° 000001101 118° 000000101 119° 000000100 120° 000001100 121° 000001110 122° 000001111 123° 000011111 124° 000111111 125° 001111111 126° 011111111 127° 011011111 128° 011011101 129° 011111101 130° 011101101 131° 010101101 132° 010111101 133° 110111101 134° 110111001 135° 010111001 136° 011111001 137° 011011001 138° 011001001 139° 111001001 140° 111101001 141° 111101000 142° 110101000 143° 100101000 144° 101101000 145° 101001000 146° 111001000 147° 110001000 148° 010001000 149° 011001000 150° 001001000 151° 001001100 152° 001101100 153° 000101100 154° 000101110 155° 000101010 156° 000111010 157° 000011010 158° 000001010 159° 000001000 160° 000011000 161° 000011100 162° 000011110 163° 000111110 164° 001111110 165° 011111110 166° 111111110 167° 110111110 168° 110111010 169° 111111010 170° 111011010 171° 101011010 172° 101111010 173° 101111011 174° 101110011 175° 101110010 176° 111110010 177° 110110010 178° 110010010 179° 110010011 180° 111010011 181° 111010001 182° 101010001 183° 001010001 184° 011010001 185° 010010001 186° 110010001 187° 100010001 188° 100010000 189° 110010000 190° 010010000 191° 010011000 192° 011011000 193° 001011000 194° 001011100 195° 001010100 196° 001110100 197° 000110100 198° 000010100 199° 000010000 200° 000110000 201° 000111000 202° 000111100 203° 001111100 204° 011111100 205° 111111100 206° 111111101 207° 101111101 208° 101110101 209° 111110101 210° 110110101 211° 010110101 212° 011110101 213° 011110111 214° 011100111 215° 011100101 216° 111100101 217° 101100101 218° 100100101 219° 100100111 220° 110100111 221° 110100011 222° 010100011 223° 010100010 224° 110100010 225° 100100010 226° 100100011 227° 000100011 228° 000100001 229° 100100001 230° 100100000 231° 100110000 232° 110110000 233° 010110000 234° 010111000 235° 010101000 236° 011101000 237° 001101000 238° 000101000 239° 000100000 240° 001100000 241° 001110000 242° 001111000 243° 011111000 244° 111111000 245° 111111001 246° 111111011 247° 011111011 248° 011101011 249° 111101011 250° 101101011 251° 101101010 252° 111101010 253° 111101110 254° 111001110 255° 111001010 256° 111001011 257° 011001011 258° 001001011 259° 001001111 260° 101001111 261° 101000111 262° 101000110 263° 101000100 264° 101000101 265° 001000101 266° 001000111 267° 001000110 268° 001000010 269° 001000011 270° 001000001 271° 001100001 272° 101100001 273° 101100000 274° 101110000 275° 101010000 276° 111010000 277° 011010000 278° 001010000 279° 001000000 280° 011000000 281° 011100000 282° 011110000 283° 111110000 284° 111110001 285° 111110011 286° 111110111 287° 111110110 288° 111010110 289° 111010111 290° 011010111 291° 011010101 292° 111010101 293° 111011101 294° 110011101 295° 110010101 296° 110010111 297° 110010110 298° 010010110 299° 010011110 300° 010011111 301° 010001111 302° 010001101 303° 010001001 304° 010001011 305° 010001010 306° 010001110 307° 010001100 308° 010000100 309° 010000110 310° 010000010 311° 011000010 312° 011000011 313° 011000001 314° 011100001 315° 010100001 316° 110100001 317° 110100000 318° 010100000 319° 010000000 320° 110000000 321° 111000000 322° 111100000 323° 111100001 324° 111100011 325° 111100111 326° 111101111 327° 111101101 328° 110101101 329° 110101111 330° 110101110 331° 110101010 332° 110101011 333° 110111011 334° 100111011 335° 100101011 336° 100101111 337° 100101101 338° 100101100 339° 100111100 340° 100111110 341° 100011110 342° 100011010 343° 100010010 344° 100010110 345° 100010100 346° 100011100 347° 100011000 348° 100001000 349° 100001100 350° 100000100 351° 110000100 352° 110000110 353° 110000010 354° 111000010 355° 101000010 356° 101000011 357° 101000001 358° 101000000 359° 100000000
Starting Angle Ending Angle Length 3 4 2 23 28 6 31 37 7 44 48 5 56 60 5 64 71 8 74 76 3 88 91 4 94 96 3 99 104 6 110 115 6 131 134 4 138 154 17 173 181 9 186 187 2 220 238 19 242 246 5 273 279 7 286 289 4 307 360 54

### Two-dimensional Gray code

Two-dimensional Gray codes are used in communication to minimize the number of bit errors in quadrature amplitude modulation (QAM) adjacent points in the constellation. In a typical encoding the horizontal and vertical adjacent constellation points differ by a single bit, and diagonal adjacent points differ by 2 bits.

Two-dimensional Gray codes also have uses in location identifications schemes, where the code would be applied to area maps such as a Mercator projection of the earth's surface and an appropriate cyclic two-dimensional distance function such as the Mannheim metric be used to calculate the distance between two encoded locations, thereby combining the characteristics of the Hamming distance with the cyclic continuation of a Mercator projection.

### Excess-Gray-Code

If a subsection of a specific codevalue is extracted from that value, for example the last 3 bits of a 4-bit gray-code, the resulting code will be an "excess gray code". This code shows the property of counting backwards in those extracted bits if the original value is further increased. Reason for this is that gray-encoded values do not show the behaviour of overflow, known from classic binary encoding, when increasing past the "highest" value.

Example: The highest 3-bit gray code, 7, is encoded as (0)100. Adding 1 results in number 8, encoded in gray as 1100. The last 3 bits do not overflow and count backwards if you further increase the original 4 bit code.

When working with sensors that output multiple, gray-encoded values in a serial fashion, one should therefore pay attention whether the sensor produces those multiple values encoded in 1 single gray-code or as separate ones, as otherwise the values might appear to be counting backwards when an "overflow" is expected.

## Gray isometry

The bijective mapping { 0 ↔ 00, 1 ↔ 01, 2 ↔ 11, 3 ↔ 10 } establishes an isometry between the metric space over the finite field $\mathbb {Z} _{2}^{2}$ with the metric given by the Hamming distance and the metric space over the finite ring $\mathbb {Z} _{4}$ (the usual modular arithmetic) with the metric given by the Lee distance. The mapping is suitably extended to an isometry of the Hamming spaces $\mathbb {Z} _{2}^{2m}$ and $\mathbb {Z} _{4}^{m}$ . Its importance lies in establishing a correspondence between various "good" but not necessarily linear codes as Gray-map images in $\mathbb {Z} _{2}^{2}$ of ring-linear codes from $\mathbb {Z} _{4}$ .

## Related codes

There are a number of binary codes similar to Gray codes, including:

The following binary-coded decimal (BCD) codes are Gray code variants as well:

 Name Bit 0 1 2 3 4 5 6 7 8 9 Weights[nb 7] Tracks Compl. Cyclic 5s Comment Gray BCD 4 0 0 0 0 0 0 0 0 1 1 0—3 4 (3[nb 8]) No (2, 4, 8, 16) No  3 0 0 0 0 1 1 1 1 1 1 2 0 0 1 1 1 1 0 0 0 0 1 0 1 1 0 0 1 1 0 0 1 Paul 4 1 0 0 0 0 0 0 0 1 1 1—3 4 (3[nb 8]) No 2, 10 No  3 0 0 0 0 1 1 1 1 1 1 2 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 Glixon 4 0 0 0 0 0 0 0 0 1 1 0—3 4 No 2, 4, 8, 10 (shifted +1) [nb 5] 3 0 0 0 0 1 1 1 1 1 0 2 0 0 1 1 1 1 0 0 0 0 1 0 1 1 0 0 1 1 0 0 0 Tompkins I 4 0 0 0 0 0 1 1 1 1 1 0—4 2 No 2, 4, 10 Yes  3 0 0 0 0 1 1 1 1 1 0 2 0 0 1 1 1 1 1 0 0 0 1 0 1 1 0 0 0 1 1 0 0 O'Brien I (Watts) 4 0 0 0 0 0 1 1 1 1 1 0—3 4 9[nb 9] 2, 4, 10 Yes [nb 5] 3 0 0 0 0 1 1 0 0 0 0 2 0 0 1 1 1 1 1 1 0 0 1 0 1 1 0 0 0 0 1 1 0 Petherick (RAE) 4 0 0 0 0 0 1 1 1 1 1 1—3 3 9[nb 9] 2, 10 Yes [nb 4] 3 1 0 0 0 1 1 0 0 0 1 2 0 0 1 1 1 1 1 1 0 0 1 1 1 1 0 0 0 0 1 1 1 O'Brien II 4 0 0 0 0 0 1 1 1 1 1 1—3 3 9[nb 9] 2, 10 Yes [nb 4] 3 0 0 0 1 1 1 1 0 0 0 2 0 1 1 1 0 0 1 1 1 0 1 1 1 0 0 0 0 0 0 1 1 Susskind 4 0 0 0 0 0 1 1 1 1 1 1—4 3 9[nb 9] 2, 10 Yes  3 0 0 1 1 1 1 1 1 0 0 2 0 1 1 1 0 0 1 1 1 0 1 1 1 1 0 0 0 0 1 1 1 Klar 4 0 0 0 0 0 1 1 1 1 1 0—4 4 (3[nb 8]) 9[nb 9] 2, 10 Yes  3 0 0 0 1 1 1 1 0 0 0 2 0 0 1 1 1 1 1 1 0 0 1 0 1 1 1 0 0 1 1 1 0 Tompkins II 4 0 0 0 0 0 1 1 1 1 1 1—3 2 9[nb 10] 2, 10 Yes  3 0 0 1 1 1 1 1 0 0 0 2 1 1 1 0 0 0 0 0 1 1 1 0 1 1 1 0 0 1 1 1 0 Excess-3 Gray 4 0 0 0 0 0 1 1 1 1 1 1—4 4 9[nb 9] 2, 10 Yes  3 0 1 1 1 1 1 1 1 1 0 2 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0