fbpx
Wikipedia

Gray code

August 28, 2023

Lucal code[1][2]
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.[3]

Function Edit

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 011 — 001 — 101 — 100. 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,[4][5][6][7][8] single-distance, single-step, monostrophic[9][10][7][8] or syncopic codes,[9] in reference to the Hamming distance of 1 between adjacent codes.

Invention Edit

 
Gray's patent introduces the term "reflected binary code"

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.[11][12][13] Frank Gray introduced the term reflected binary code in his 1947 patent application, remarking that the code had "as yet no recognized name".[14] 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:

 
Visualized as a traversal of vertices of a tesseract
 
Gray code along the number line
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.[15]

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[11][12][13] 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";[16][17] one of those also lists "minimum error code" and "cyclic permutation code" among the names.[17] A 1954 patent application refers to "the Bell Telephone Gray code".[18] Other names include "cyclic binary code",[12] "cyclic progression code",[19][12] "cyclic permuting binary"[20] or "cyclic permuted binary" (CPB).[21][22]

The Gray code is sometimes misattributed to 19th century electrical device inventor Elisha Gray.[13][23][24][25]

History and practical application Edit

Mathematical puzzles Edit

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.[26][13]

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

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

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

Telegraphy codes Edit

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[33] or 1876,[34][35] 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,[36][37][38] and other symbols appropriately placed, the 5-bit character code has been recognized as a reflected binary code.[13] This code became known as Baudot code[39] and, with minor changes, was eventually adopted as International Telegraph Alphabet No. 1 (ITA1, CCITT-1) in 1932.[40][41][38]

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

Analog-to-digital signal conversion Edit

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,[14] 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.[44]

 
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 Edit

 
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 Edit

Due to the Hamming distance properties of Gray codes, they are sometimes used in genetic algorithms.[15] 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 Edit

Gray codes are also used in labelling the axes of Karnaugh maps since 1953[45][46][47] as well as in Händler circle graphs since 1958,[48][49][50][51] both graphical methods for logic circuit minimization.

Error correction Edit

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 Edit

Main article: Clock domain crossing

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 Edit

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,[52] 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 Edit

George R. Stibitz utilized a reflected binary code in a binary pulse counting device in 1941 already.[11][12][13]

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.[53] 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.[54]

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,[55] add one to it with a standard binary adder, and then convert the result back to Gray code.[56] 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.[57]

Gray code addressing Edit

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.[58][59]

Constructing an n-bit Gray code Edit

 
The first few steps of the reflect-and-prefix method.
 
4-bit Gray code permutation

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.[13] 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  . 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   of codewords are inverted, the order of neighbouring blocks of   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   at position   with the bit   at position   leaves the order of codewords intact if  , and reverses the order of blocks of   codewords if  . 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   is the  th Gray-coded bit (  being the most significant bit), and   is the  th binary-coded bit (  being the most-significant bit), the reverse translation can be given recursively:  , and  . 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  , and at step   find the bit position of the least significant 1 in the binary representation of   and flip the bit at that position in the previous code   to get the next code  . 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 Edit

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.[60][55][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) {  uint mask = num;  while (mask) { // Each Gray code bit is exclusive-ored with all more significant bits.  mask >>= 1;  num ^= mask;  }  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 Edit

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 Edit

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.[61] OEIS sequence A290772 [62] 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 Edit

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.[31] The (n, k)-Gray code is the n-ary Gray code with k digits.[63] The sequence of elements in the (3, 2)-Gray code is: 00,01,02,12,11,10,20,21,22. The (n, k)-Gray code may be constructed recursively, as the BRGC, or may be constructed iteratively. An algorithm to iteratively generate the (N, k)-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,[63] 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 Edit

Although the binary reflected Gray code is useful in many scenarios, it is not optimal in certain cases because of a lack of "uniformity".[52] 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  ; the transition counts (spectrum) of G are the collection of integers defined by

 

A Gray code is uniform or uniformly balanced if its transition counts are all equal, in which case we have   for all k. Clearly, when  , such codes exist only if n is a power of 2.[64] 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   or  .[52] 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.[65]

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:[52]

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:[52]

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[66] and implementation[67] 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   given an n-digit Gray code G in such a way that the balanced property is preserved. To do this, we consider partitions of   into an even number L of non-empty blocks of the form

 

where  ,  , and  ). This partition induces an  -digit Gray code given by

 
 
 
 

If we define the transition multiplicities

 

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   is

 

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   transition and splitting another block at another digit   transition produces a different Gray code with exactly the same transition spectrum  , so one may for example[65] designate the first   transitions at digit   as those that fall between two blocks. Uniform codes can be found when   and  , and this construction can be extended to the R-ary case as well.[66]

Long run Gray codes Edit

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.[68]

Monotonic Gray codes Edit

Monotonic codes are useful in the theory of interconnection networks, especially for minimizing dilation for linear arrays of processors.[69] 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   into levels of vertices that have equal weight, i.e.

 

for  . These levels satisfy  . Let   be the subgraph of   induced by  , and let   be the edges in  . A monotonic Gray code is then a Hamiltonian path in   such that whenever   comes before   in the path, then  .

An elegant construction of monotonic n-digit Gray codes for any n is based on the idea of recursively building subpaths   of length   having edges in  .[69] We define  ,   whenever   or  , and

 

otherwise. Here,   is a suitably defined permutation and   refers to the path P with its coordinates permuted by  . These paths give rise to two monotonic n-digit Gray codes   and   given by

 

The choice of   which ensures that these codes are indeed Gray codes turns out to be  . The first few values of   are shown in the table below.

Subpaths in the Savage–Winkler algorithm
  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   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  , 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.[70]

Beckett–Gray code Edit

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.[71] 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.[71] 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.[13] 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.[72]

Snake-in-the-box codes Edit

 
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,[73] 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;[5] 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 Edit

Yet another kind of Gray code is the single-track Gray code (STGC) developed by Norman B. Spedding[74][75] and refined by Hiltgen, Paterson and Brandestini in "Single-track Gray codes" (1996).[76][77] 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.[78]

 
Animated and color-coded version of the STGC rotor.

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[79] 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.[74] 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.[80] 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:

Single-track Gray code for 30 positions
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.[81] 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.[82]

 
9-bit, Single-Track Gray Code, displaying one degree angular resolution.

Since this 30 degree example was added, there has been a lot of interest in examples with higher angular resolution. In 2008, Gary Williams,[83] based on previous work [80] 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[84] was designed by etzenseep (Florian Bauer) in September, 2022.

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

Single-track Gray code for 360 positions
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
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 and ending angles for the 20 tracks for a Single-track Gray Code with 9 sensors separated by 40°
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 23
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 Edit

 
A Gray-coded constellation diagram for rectangular 16-QAM

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.[85]

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.[86]

Excess-Gray-Code Edit

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 Edit

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

Related codes Edit

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:

4-bit unit-distance BCD codes[nb 6]
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 [110][111]
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 [125]
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) [122][110][111][123][124][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 [4][110][111]
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[103][104][nb 9] 2, 4, 10 Yes [109][110][111][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[103][104][nb 9] 2, 10 Yes [19][107][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[91][103][104][nb 9] 2, 10 Yes [109][110][111][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 [6]
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 [126][127]
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 [4][110][111]
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[103][104][nb 9] 2, 10 Yes [8][103]
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

See also Edit

Notes Edit

  1. ^ a b c By applying a simple inversion rule, the Gray code and the O'Brien code I can be translated into the 8421 pure binary code and the 2421 Aiken code, respectively, to ease arithmetic operations.[C]
  2. ^ Sequence 0, 1, 0, 2, 0, 1, 0, 3, … (sequence A007814 in the OEIS).
  3. ^ a b c There are several Gray code variants which are called "modified" of some sort: The Glixon code is sometimes called modified Gray code.[D] The Lucal code is also called modified reflected binary code (MRB).[E] The O'Brien code I or Watts code is sometimes referred to as reflected binary modified Gray code.[F]
  4. ^ a b c d By interchanging and inverting three bit rows, the O'Brien code II and the Petherick code can be transferred into each other.
  5. ^ a b c d By swapping two pairs of bit rows, individually shifting four bit rows and inverting one of them, the Glixon code and the O'Brien code I can be transferred into each other.
  6. ^ Other unit-distance BCD codes include the non-Gray code related 5-bit Libaw–Craig and the 1-2-1 code.
  7. ^ Depending on a code's target application, the Hamming weights of a code can be important properties beyond coding-theoretical considerations also for physical reasons. Under some circumstances the all-cleared and/or all-set states must be omitted (f.e. to avoid non-conductive or short-circuit conditions), it may be desirable to keep the highest used weight as low as possible (f.e. to reduce power consumption of the reader circuit) or to keep the variance of used weights small (f.e. to reduce acoustic noise or current fluctuations).
  8. ^ a b c For Gray BCD, Paul and Klar codes, the number of necessary reading tracks can be reduced from 4 to 3 if inversion of one of the middle tracks is acceptable.
  9. ^ a b c d e f For O'Brien codes I and II and Petherick, Susskind, Klar as well as Excess-3 Gray codes, a 9s complement can be derived by inverting the most-significant (fourth) binary digit.
  10. ^ For Tompkins code II, a 9s complement can be derived by inverting the first three digits and swapping the two middle binary digits.

References Edit

  1. ^ a b c Lucal, Harold M. (December 1959). "Arithmetic Operations for Digital Computers Using a Modified Reflected Binary". IRE Transactions on Electronic Computers. EC-8 (4): 449–458. doi:10.1109/TEC.1959.5222057. ISSN 0367-9950. S2CID 206673385. (10 pages)
  2. ^ a b c Sellers, Jr., Frederick F.; Hsiao, Mu-Yue; Bearnson, Leroy W. (November 1968). Error Detecting Logic for Digital Computers (1st ed.). New York, USA: McGraw-Hill Book Company. pp. 152–164. LCCN 68-16491. OCLC 439460.
  3. ^ Gray, Joel (March 2020). "Understanding Gray Code: A Reliable Encoding System". graycode.ie. Section: Conclusion. Retrieved 2023-06-30.
  4. ^ a b c d Tompkins, Howard E. (September 1956) [1956-07-16]. "Unit-Distance Binary-Decimal Codes for Two-Track Commutation". IRE Transactions on Electronic Computers. Correspondence. Moore School of Electrical Engineering, University of Pennsylvania, Philadelphia, Pennsylvania, USA. EC-5 (3): 139. doi:10.1109/TEC.1956.5219934. ISSN 0367-9950. Retrieved 2020-05-18. (1 page)
  5. ^ a b Kautz, William H. (June 1958). "Unit-Distance Error-Checking Codes". IRE Transactions on Electronic Computers. EC-7 (2): 179–180. doi:10.1109/TEC.1958.5222529. ISSN 0367-9950. S2CID 26649532. (2 pages)
  6. ^ a b Susskind, Alfred Kriss; Ward, John Erwin (1958-03-28) [1957, 1956]. "III.F. Unit-Distance Codes / VI.E.2. Reflected Binary Codes". Written at Cambridge, Massachusetts, USA. In Susskind, Alfred Kriss (ed.). Notes on Analog-Digital Conversion Techniques. Technology Books in Science and Engineering. Vol. 1 (3 ed.). New York, USA: Technology Press of the Massachusetts Institute of Technology / John Wiley & Sons, Inc. / Chapman & Hall, Ltd. pp. 3-10–3-16 [3-13–3-16], 6-65–6-60 [6-60]. (x+416+2 pages) (NB. The contents of the book was originally prepared by staff members of the Servomechanisms Laboraratory, Department of Electrical Engineering, MIT, for Special Summer Programs held in 1956 and 1957. Susskind's "reading-type code" is actually a minor variant of the code shown here with the two most significant bit rows swapped to better illustrate symmetries. Also, by swapping two bit rows and inverting one of them, the code can be transferred into the Petherick code, whereas by swapping and inverting two bit rows, the code can be transferred into the O'Brien code II.)
  7. ^ a b Chinal, Jean P. (January 1973). "3.3. Unit Distance Codes". Written at Paris, France. Design Methods for Digital Systems. Translated by Preston, Alan; Summer, Arthur (1st English ed.). Berlin, Germany: Akademie-Verlag / Springer-Verlag. p. 50. doi:10.1007/978-3-642-86187-1. ISBN 978-0-387-05871-9. S2CID 60362404. License No. 202-100/542/73. Order No. 7617470(6047) ES 19 B 1 / 20 K 3. Retrieved 2020-06-21. (xviii+506 pages) (NB. The French 1967 original book was named "Techniques Booléennes et Calculateurs Arithmétiques", published by Éditions Dunod [fr].)
  8. ^ a b c d e f Military Handbook: Encoders – Shaft Angle To Digital (PDF). United States Department of Defense. 1991-09-30. MIL-HDBK-231A. (PDF) from the original on 2020-07-25. Retrieved 2020-07-25. (NB. Supersedes MIL-HDBK-231(AS) (1970-07-01).)
  9. ^ a b c Spaulding, Carl P. (1965-01-12) [1954-03-09]. "Digital coding and translating system" (PDF). Monrovia, California, USA: Datex Corporation. U.S. Patent 3165731A. Serial No. 415058. (PDF) from the original on 2020-08-05. Retrieved 2018-01-21. (28 pages)
  10. ^ a b Russell, A. (August 1964). "Some Binary Codes and a Novel Five-Channel Code". Control (Systems, Instrumentation, Data Processing, Automation, Management, incorporating Automation Progress). Special Features. London, UK: Morgan-Grampain (Publishers) Limited. 8 (74): 399–404. Retrieved 2020-06-22. (6 pages)
  11. ^ a b c Stibitz, George Robert (1943-01-12) [1941-11-26]. "Binary counter". New York, USA: Bell Telephone Laboratories, Incorporated. U.S. Patent 2,307,868. Serial No. 420537. Retrieved 2020-05-24. p. 2, right column, rows 43–73: […] A clearer idea of the position of the balls after each pulse will be obtained if the set of balls is represented by a number having a similar number of digits, each of which may have one of two arbitrary values, for example 0 and 1. If the upper position is called 0 and the lower position […] 1, then the setting of the counter […] may be read from left to right as 0,100,000. […] Following is a translation of the number of pulses received into this form of binary notation for the first sixteen pulses as received on the first five balls […] Pulse number […] Binary notation […] (4 pages)
  12. ^ a b c d e Winder, C. Farrell (October 1959). (PDF). Electronic Industries. Chilton Company. 18 (10): 76–80. Archived from the original (PDF) on 2020-09-28. Retrieved 2018-01-14. p. 78: […] The type of code wheel most popular in optical encoders contains a cyclic binary code pattern designed to give a cyclic sequence of "on-off" outputs. The cyclic binary code is also known as the cyclic progression code, the reflected binary code, and the Gray code. This code was originated by G. R. Stibitz, of Bell Telephone Laboratories, and was first proposed for pulse-code modulation systems by Frank Gray, also of BTL. Thus the name Gray code. The Gray or cyclic code is used mainly to eliminate the possibility of errors at code transition which could result in gross ambiguities. […]
  13. ^ a b c d e f g h i Knuth, Donald Ervin (2014-09-12). "Enumeration and Backtracking / Generating all n-tuples". The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1. Vol. 4A (1 ed.). Addison-Wesley Professional. pp. 442–443. ISBN 978-0-13348885-2. (912 pages)
  14. ^ a b Gray, Frank (1953-03-17) [1947-11-13]. Pulse Code Communication (PDF). New York, USA: Bell Telephone Laboratories, Incorporated. U.S. Patent 2,632,058. Serial No. 785697. (PDF) from the original on 2020-08-05. Retrieved 2020-08-05. (13 pages)
  15. ^ a b Goldberg, David Edward (1989). Genetic Algorithms in Search, Optimization, and Machine Learning (1 ed.). Reading, Massachusetts, USA: Addison-Wesley. Bibcode:1989gaso.book.....G.
  16. ^ Breckman, Jack (1956-01-31) [1953-12-31]. Encoding Circuit (PDF). Long Branch, New Jersey, USA: US Secretary of the Army. U.S. Patent 2,733,432. Serial No. 401738. (PDF) from the original on 2020-08-05. Retrieved 2020-08-05. (8 pages)
  17. ^ a b Ragland, Earl Albert; Schultheis, Jr., Harry B. (1958-02-11) [1953-10-16]. Direction-Sensitive Binary Code Position Control System (PDF). North Hollywood, California, USA: Bendix Aviation Corporation. U.S. Patent 2,823,345. Serial No. 386524. (PDF) from the original on 2020-08-05. Retrieved 2020-08-05. (10 pages)
  18. ^ Domeshek, Sol; Reiner, Stewart (1958-06-24) [1954-01-08]. Automatic Rectification System (PDF). US Secretary of the Navy. U.S. Patent 2,839,974. Serial No. 403085. (PDF) from the original on 2020-08-05. Retrieved 2020-08-05. (8 pages)
  19. ^ a b c Petherick, Edward John (October 1953). A Cyclic Progressive Binary-coded-decimal System of Representing Numbers (Technical Note MS15). Farnborough, UK: Royal Aircraft Establishment (RAE). (4 pages) (NB. Sometimes referred to as A Cyclic-Coded Binary-Coded-Decimal System of Representing Numbers.)
  20. ^ a b Evans, David Silvester (1960). Fundamentals of Digital Instrumentation (1 ed.). London, UK: Hilger & Watts Ltd. Retrieved 2020-05-24. (39 pages)
  21. ^ a b Evans, David Silvester (March 1961). "Chapter Three: Direct Reading from Coded Scales". Digital Data: Their derivation and reduction for analysis and process control (1 ed.). London, UK: Hilger & Watts Ltd / Interscience Publishers. pp. 18–23. Retrieved 2020-05-24. p. 20–23: […] Decoding. […] To decode C.P.B. or W.R.D. codes, a simple inversion rule can be applied. The readings of the higher tracks determine the way in which the lower tracks are translated. The inversion rule is applied line by line for the C.P.B. and for the W.R.D. it is applied decade by decade or line by line. Starting therefore with the top or slowest changing track of the C.P.B., if the result is odd (1) the next track value has to be inverted, i.e. 0 for 1 and 1 for 0. If, however, the first track is even (0), the second track is left as read, i.e. 0 for 0 and 1 for 1. Again, if the resultant reading of the second track is odd, the third track reading is inverted and so on. When an odd is changed to an even the line below is not inverted and when an even is changed to an odd the line below is inverted. The result of applying this rule to the pattern […] is the pure binary (P.B.) pattern […] where each track or digit can be given a definite numerical value (in this instance 1, 2, 4, 8, etc.). […] Using the line-by-line inversion rule on the W.R.D. code produces [a] pattern [of 1, 2, 4, 2 code] where again the digits can be given numerical values and summed decade by decade. The summing of the digits can be very useful, for example, in a high-speed scanning system; but in a parallel decoding system […], it is usual to treat each binary quartet or decade as an entity. In other words, if the first or more significant decade is odd, the second decade is rectified or complemented by inverting the D track and so on, the result being the repeating pattern of [rectified W.R.D. code]. This is an extremely easy thing to achieve since the only change required is the inversion of the meaning of the D track or complementing digit. […] (8+82 pages) (NB. The author does not mention Gray at all and calls the standard Gray code "Cyclic Permuted Binary Code" (C.P.B.), the book index erroneously lists it as "cyclic pure binary code".)
  22. ^ Newson, P. A. (1965). Tables for the Binary Encoding of Angles (1 ed.). United Kingdom Atomic Energy Authority, Research Group, Atomic Energy Research Establishment, Harwell, UK: H. M. Stationery Office. Retrieved 2020-05-24. (12 pages)
  23. ^ Heath, F. G. (September 1961). "Pioneers Of Binary Coding". Journal of the Institution of Electrical Engineers. Manchester College of Science and Technology, Faculty of Technology of the University of Manchester, Manchester, UK: Institution of Engineering and Technology (IET). 7 (81): 539–541. doi:10.1049/jiee-3.1961.0300. Retrieved 2020-06-22. (3 pages)
  24. ^ Cattermole, Kenneth W. (1969). Written at Harlow, Essex, UK. Principles of pulse code modulation (1 ed.). London, UK / New York, USA: Iliffe Books Ltd. / American Elsevier Publishing Company, Inc. pp. 245, 434. ISBN 978-0-444-19747-4. LCCN 78-80432. SBN 444-19747-8. p. 245: […] There seems to be some confusion about the attributation of this code, because two inventors named Gray have been associated with it. When I first heard the name I took it as referring to Elisha Gray, and Heath testifies to his usage of it. Many people take it as referring to Frank Gray of Bell Telephone Laboratories, who in 1947 first proposed its use in coding tubes: his patent is listed in the bibliography. […] (2+448+2 pages)
  25. ^ Edwards, Anthony William Fairbank (2004). Cogwheels of the Mind: The Story of Venn Diagrams. Baltimore, Maryland, USA: Johns Hopkins University Press. pp. 48, 50. ISBN 0-8018-7434-3.
  26. ^ Gros, Luc-Agathon-Louis (1872). Théorie du baguenodier par un clerc de notaire lyonnais (in French) (1 ed.). Lyon, France: Aimé Vingtrinier. Archived from the original on 2017-04-03. Retrieved 2020-12-17. (2+16+4 pages and 4 pages foldout) (NB. This booklet was published anonymously, but is known to have been authored by Louis Gros.)
  27. ^ Lucas, Édouard (November 1883). La tour d'Hanoï: Véritable casse tête annamite - Jeu rapporté du Tonkin par le Professeur N. Claus (de Siam) Mandarin du Collège Li Sou Stian! (in French). Imprimerie Paul Bousrez, Tours. (NB. N. Claus de Siam is an anagram of Lucas d'Amiens, pseudonym of the author Édouard Lucas.)
  28. ^ de Parville, Henri [in French], ed. (1883-12-27). "La tour d'Hanoï, véritable casse-tête annamite, jeu rapporté du Tonkin par le professeur N. Claus (de Siam), mandarin du collège Li-Sou-Stian. Un vrai casse-tête, en effet, mais intéressant. Nous ne saurions mieux remercier le mandarin de son aimable intention à l'égard d'un profane qu'en signalant la Tour d'Hanoï aux personnes patientes possédées par le démon du jeu". Journal des Débats Politiques et Littéraires (Review). Revue des science (in French) (Matin ed.). Paris, France: 1–2 [2]. ark:/12148/bpt6k462461g. from the original on 2020-12-18. Retrieved 2020-12-18. (1 page)
  29. ^ Allardice, R. E.; Fraser, A. Y. (February 1883). Allardice, Robert Edgar; Fraser, Alexander Yule (eds.). "La Tour d'Hanoï". Proceedings of the Edinburgh Mathematical Society (in English and French). Edinburgh Mathematical Society. 2 (5): 50–53. doi:10.1017/S0013091500037147. eISSN 1464-3839. ISSN 0013-0915. S2CID 122159381. (4 pages)
  30. ^ Lucas, Édouard (1979) [1892]. Récréations mathématiques (in French). Vol. 3 (Librairie Albert Blanchard reissue ed.). p. 58. (The first edition of this book was published post-humously.)
  31. ^ a b Herter, Felix; Rote, Günter (2018-11-14) [2018-08-09, 2017-12, 2017-08-09, 2016-04-22]. "Loopless Gray Code Enumeration and the Tower of Bucharest" (PDF). Theoretical Computer Science. Berlin, Germany. 748: 40–54. arXiv:1604.06707. doi:10.1016/j.tcs.2017.11.017. ISSN 0304-3975. S2CID 4014870. (PDF) from the original on 2020-12-16. Retrieved 2020-12-16. (15/18/19/24 pages)
  32. ^ Gardner, Martin (August 1972). "The curious properties of the Gray code and how it can be used to solve puzzles". Scientific American. Mathematical Games. Vol. 227, no. 2. p. 106. (1 page)
  33. ^ Zeman, Johann; Fischer, Ferdinand, eds. (1877). "Einige neuere Vorschläge zur mehrfachen Telegraphie: A. Absatzweise vielfache Telegraphie". Dingler's Polytechnisches Journal (in German). Augsburg, Germany: J. G. Cotta'sche Buchhandlung. 226: 499–507. from the original on 2020-12-21. Retrieved 2020-12-21. p. 499: […] Der um die Mitte des J[ahres] 1874 patenti[e]rte, ebenfalls dem Highton'schen verwandte Typendrucker des französischen Telegraphen-Verwaltungsbeamten Baudot wurde bei seiner 1875 patenti[e]rten Weiterentwicklung in einen fünffachen umgewandelt […]
  34. ^ Butrica, Andrew J. (1991-06-21). "Baudot, Jean Maurice Emile". In Froehlich, Fritz E.; Kent, Allen; Hall, Carolyn M. (eds.). The Froehlich/Kent Encyclopedia of Telecommunications: Volume 2 - Batteries to Codes-Telecommunications. Vol. 2. Marcel Dekker Inc. / CRC Press. pp. 31–34. ISBN 0-8247-2901-3. LCCN 90-3966. Retrieved 2020-12-20. p. 31: […] A Baudot prototype (4 years in the making) was built in 1876. The transmitter had 5 keys similar to those of a piano. Messages were sent in a special 5-element code devised by Baudot […]
  35. ^ Fischer, Eric N. (2000-06-20). "The Evolution of Character Codes, 1874–1968". ark:/13960/t07x23w8s. Retrieved 2020-12-20. […] In 1872, [Baudot] started research toward a telegraph system that would allow multiple operators to transmit simultaneously over a single wire and, as the transmissions were received, would print them in ordinary alphabetic characters on a strip of paper. He received a patent for such a system on June 17, 1874. […] Instead of a variable delay followed by a single-unit pulse, Baudot's system used a uniform six time units to transmit each character. […] his early telegraph probably used the six-unit code […] that he attributes to Davy in an 1877 article. […] in 1876 Baudot redesigned his equipment to use a five-unit code. Punctuation and digits were still sometimes needed, though, so he adopted from Hughes the use of two special letter space and figure space characters that would cause the printer to shift between cases at the same time as it advanced the paper without printing. The five-unit code he began using at this time […] was structured to suit his keyboard […], which controlled two units of each character with switches operated by the left hand and the other three units with the right hand. […] [6]
  36. ^ Rothen, Timotheus (1884-12-25). "Le télégraphe imprimeur Baudot". Journal Télégraphique (in French). Berne, Switzerland: Le Bureau International des Administrations Télégraphiques. VIII / #16 (12): 241–253 [249]. eISSN 2725-738X. ISSN 2223-1420. ark:/12148/bpt6k5725454q. from the original on 2020-12-21. Retrieved 2020-12-20.
  37. ^ Pendry, Henry Walter (1920) [October 1919]. Written at London, UK. The Baudôt Printing Telegraph System (2 ed.). London, Bath, Melbourne, New York: Sir Isaac Pitman and Sons, Ltd. pp. 43–44. LCCN 21005277. OCLC 778309351. OL 6633244M. Retrieved 2020-12-20. (vii+184 pages) (NB. A first edition was published in 1913.)
  38. ^ a b MacMillan, David M. (2010-04-27) [2010-04-25, 2010-04-23]. "Codes that Don't Count - Some Printing Telegraph Codes as Products of their Technologies (With Particular Attention to the Teletypesetter)". lemur.com. Revision 3. Mineral Point, Wisconsin, USA. from the original on 2020-12-18. Retrieved 2020-12-20.
  39. ^ Written at Lisbon, Portugual. Convention télégraphique internationale de Saint-Pétersbourg et Règlement et tarifs y annexés, Revision de Lisbonne, 1908 / Extraits de la publication: Documents de la Conférence télégraphique internationale de Lisbonne (in French). Berne, Switzerland: Bureau Internationale de L'Union Télégraphique. 1909 [1908].
  40. ^ "Chapter IX. Signaux de transmission, Article 35. Signaux de transmission des alphabets télegraphiques internationaux 'nos 1 et 2, signaux d.u code Morse, de l'appareil Hughes et de l'appareil Siemens". Written at Madrid, Spain. Règlement télégraphique annexé à la convention internationale des télécommunications - protocol finale audit règlement - Madrid, 1932 (PDF) (in French). Berne, Switzerland: Bureau Internationale de L'Union Télégraphique. 1933 [1932]. pp. 31–40 [33]. (PDF) from the original on 2020-12-21. Retrieved 2020-12-21. (1+188 pages)
  41. ^ "Chapter IX. Transmission Signals. Article 35. Transmission Signals of the International Telegraph Alphabets Nos. 1 and 2, Morse Code Signals and Signals of the Hughes and Siemens Instruments.". Telegraph Regulations Annexed To The International Telecommunication Convention - Final Protocol To The Telegraph Regulations - Madrid 1932 (PDF) (in English and French). London, UK: General Post Office / His Majesty's Stationery Office. 1933 [1932]. pp. 32–40 [34]. 43-152-2 / 18693. (PDF) from the original on 2020-12-21. Retrieved 2020-12-21. (1+2*120+26 pages)
  42. ^ Zemanek, Heinrich "Heinz" Josef (1983-12-01). Otto Schäffler (1838-1928). Pionier des Telephons, der Telegraphie und der Lochkarte sowie Erbauer der ersten Wiener Telephonzentrale. Blätter für Technikgeschichte (in German and English). Vol. 41–43 (1979–1981) (1 ed.). Vienna, Austria: Technisches Museum für Industrie und Gewerbe, Forschungsinstitut für Technikgeschichte / Springer-Verlag. pp. 81–118. ISBN 3-21181779-4. ISSN 0067-9127. OCLC 952698275.
  43. ^ Zemanek, Heinrich "Heinz" Josef (1976-06-07). "Computer prehistory and history in central Europe". Written at Vienna, Austria. International Workshop on Managing Requirements Knowledge. AFIPS '76: Proceedings of the June 7–10, 1976, national computer conference and exposition June 1976. Vol. 1. New York, USA: American Federation of Information Processing Societies, Association for Computing Machinery. pp. 15–20. doi:10.1145/1499799.1499803. ISBN 978-1-4503-7917-5. S2CID 14114959. from the original on 2020-12-17. Retrieved 2020-12-17. p. 17: […] In 1874, Schaeffler [de] invented another printing telegraph, a quadruple system like the Baudot, but mechanically more sophisticated. The Hughes telegraph had two synchronously rotating fingers, one in the sender and one in the receiver. By a piano-like keyboard the operator selected a letter and thereby made contact with the rotating finger in the corresponding direction. Since the receiving finger was in the same direction at this moment, the receiver could print the correct letter. The Baudot and the Schaeffler printing telegraphs use a five-bit binary code. ... Schaeffler's code is a reflected binary code! What F. Gray patented in 1953 for PCM, Schaeffler had applied in his telegraph in 1874, and for a similar reason: reliability. He had contact fingers sensing on five cams consecutively all combinations; the right one triggers printing. If the fingers are to make a minimal number of movements, the solution is the reflected binary code. For Schaeffler, this idea was a minor one. More exactly, the code is described in a letter by the Austrian Post employee, J[ohann] N[epomuk] Teufelhart, inserted there as a footnote and telling that Schaeffler found the code by combining wooden bars with the different combinations until he had the best solution. Another Post employee, Alexander Wilhelm Lambert of Linz, claims to have shown this code to Schaeffler as early as 1872, but this claim is not clear and cannot be checked. […] (6 pages)
  44. ^ Goodall, William M. (January 1951). "Television by Pulse Code Modulation". Bell System Technical Journal. 30 (1): 33–49. doi:10.1002/j.1538-7305.1951.tb01365.x. (NB. Presented orally before the I.R.E. National Convention, New York City, March 1949.)
  45. ^ Karnaugh, Maurice (November 1953) [1953-04-23, 1953-03-17]. (PDF). Transactions of the American Institute of Electrical Engineers, Part I: Communication and Electronics. 72 (5): 593–599. doi:10.1109/TCE.1953.6371932. S2CID 51636736. Paper 53-217. Archived from the original (PDF) on 2017-04-16. Retrieved 2017-04-16. (NB. Also contains a short review by Samuel H. Caldwell.)
  46. ^ Wakerly, John F. (1994). Digital Design: Principles & Practices. New Jersey, USA: Prentice Hall. pp. 48–49, 222. ISBN 0-13-211459-3. (NB. The two page sections taken together say that K-maps are labeled with Gray code. The first section says that they are labeled with a code that changes only one bit between entries and the second section says that such a code is called Gray code.)
  47. ^ Brown, Frank Markham (2012) [2003, 1990]. "3.9.2 Maps". Boolean Reasoning – The Logic of Boolean Equations (reissue of 2nd ed.). Mineola, New York, USA: Dover Publications, Inc. p. 49. ISBN 978-0-486-42785-0. p. 49: […] Karnaugh's map orders the arguments of the discriminants according to the reflected binary code, also called the Gray code. […] (xii+291+3 pages)
  48. ^ Händler, Wolfgang (1958). Ein Minimisierungsverfahren zur Synthese von Schaltkreisen (Minimisierungsgraphen) (Dissertation) (in German). Potsdam, Germany: Technische Hochschule Darmstadt. D 17. (73 pages+app.) [9]
  49. ^ Berger, Erich R.; Händler, Wolfgang (1967) [1962]. Steinbuch, Karl W.; Wagner, Siegfried W. (eds.). Taschenbuch der Nachrichtenverarbeitung (in German) (2 ed.). Berlin, Germany: Springer-Verlag OHG. pp. 64, 1034–1035, 1036, 1038. LCCN 67-21079. Title No. 1036. p. 64: […] Übersichtlich ist die Darstellung nach Händler, die sämtliche Punkte, numeriert nach dem Gray-Code […], auf dem Umfeld eines Kreises anordnet. Sie erfordert allerdings sehr viel Platz. […] [Händler's diagram, where all points, numbered according to the Gray code, are arranged on the circumference of a circle, is easily comprehensible. It needs, however, a lot of space.]
  50. ^ (in German). Erlangen, Germany: Friedrich-Alexander Universität. 2012-03-13. Archived from the original on 2017-05-16. Retrieved 2017-04-12.
  51. ^ "Informatik Sammlung Erlangen (ISER) – Impressum" (in German). Erlangen, Germany: Friedrich-Alexander Universität. 2012-03-13. from the original on 2012-02-26. Retrieved 2017-04-15.
  52. ^ a b c d e Bhat, Girish S.; Savage, Carla Diane (1996). "Balanced Gray Codes". Electronic Journal of Combinatorics. 3 (1). doi:10.37236/1249.
  53. ^ Donohue, Ryan (2003). "Synchronization in Digital Logic Circuits" (PDF). (PDF) from the original on 2018-01-15. Retrieved 2018-01-15.
  54. ^ Hulst, George D. (1962-02-06) [1957-11-15]. Reflected binary code counter (PDF). Nutley, New Jersey, USA: International Telephone and Telegraph Corporation (ITT). U.S. Patent 3,020,481. Serial No. 696793. (PDF) from the original on 2020-08-06. Retrieved 2020-08-06. (5 pages)
  55. ^ a b c d Powell, E. Alexander (June 1968). "Codes particularly useful for analogue to digital conversions". A short note on useful codes for Fluidic Control Circuits (PDF). Cranfield, UK: The College of Aeronautics, Department of Production Engineering. pp. 7, 9. S2CID 215864694. CoA Memo 156. (PDF) from the original on 2020-12-15. Retrieved 2020-12-15. (18 pages) (NB. The paper names the Glixon code modified Gray code and misspells Richard W. Hamming's name.)
  56. ^ Mehta, Huzefa; Owens, Robert Michael; Irwin, Mary Jane "Janie" (1996-03-22). "Some issues in gray code addressing". Proceedings of the Sixth Great Lakes Symposium on VLSI. IEEE Computer Society. pp. 178–181. doi:10.1109/GLSV.1996.497616. ISBN 978-0-8186-7502-7. ISSN 1066-1395. S2CID 52837310.
  57. ^ a b Doran, Robert "Bob" William (March 2007). The Gray Code (PDF). CDMTCS Research Report Series. Centre for Discrete Mathematics and Theoretical Computer Science, University of Auckland, New Zealand. CDMTCS-304. (PDF) from the original on 2020-05-22. Retrieved 2020-05-23. (25 pages)
  58. ^ Su, Ching-Long; Tsui, Chi-Ying; Despain, Alvin M. (1994). Low Power Architecture Design and Compilation Techniques for High-Performance Processors (PDF) (Report). Advanced Computer Architecture Laboratory. ACAL-TR-94-01. (PDF) from the original on 2020-07-26. Retrieved 2020-12-17.
  59. ^ Guo, Hui; Parameswaran, Sri (April–June 2010). "Shifted Gray encoding to reduce instruction memory address bus switching for low-power embedded systems". Journal of Systems Architecture. 56 (4–6): 180–190. doi:10.1016/j.sysarc.2010.03.003.
  60. ^ Dietz, Henry Gordon "Hank" (2002). "The Aggregate Magic Algorithms: Gray Code Conversion". The Aggregate. Electrical and Computer Engineering Department, College of Engineering, University of Kentucky. from the original on 2020-12-16. Retrieved 2020-12-16.
  61. ^ Maxfield, Max (2007-06-29). . Archived from the original on 2022-01-29. Retrieved 2022-01-29.
  62. ^ (sequence A290772 in the OEIS)
  63. ^ a b Guan, Dah-Jyh (1998). "Generalized Gray Codes with Applications". Proceedings of the National Scientific Council, Republic of China, Part A. 22: 841–848. CiteSeerX 10.1.1.119.1344.
  64. ^ D. G. Wagner, J. West (1991). "Construction of Uniform Gray Codes". Congressus Numerantium. 80: 217–223.
  65. ^ a b Suparta, I. Nengah (2005). "A simple proof for the existence of exponentially balanced Gray codes". Electronic Journal of Combinatorics. 12. doi:10.37236/1986.
  66. ^ a b Flahive, Mary Elizabeth; Bose, Bella (2007). "Balancing cyclic R-ary Gray codes". Electronic Journal of Combinatorics. 14. doi:10.37236/949.
  67. ^ Strackx, Raoul; Piessens, Frank (2016). "Ariadne: A Minimal Approach to State Continuity". Usenix Security. 25.
  68. ^ Savage, Carla Diane (1997). "A Survey of Combinatorial Gray Codes". SIAM Review. Society for Industrial and Applied Mathematics (SIAM). 39 (4): 605–629. Bibcode:1997SIAMR..39..605S. CiteSeerX 10.1.1.39.1924. doi:10.1137/S0036144595295272. JSTOR 2132693. S2CID 6375360.
  69. ^ a b Savage, Carla Diane; Winkler, Peter (1995). "Monotone Gray codes and the middle levels problem". Journal of Combinatorial Theory. Series A. 70 (2): 230–248. doi:10.1016/0097-3165(95)90091-8. ISSN 0097-3165.
  70. ^ Savage, Carla Diane (1997-01-16). "Long cycles in the middle two levels of the Boolean lattice". Ars Combinatoria. North Carolina State University, Raleigh, North Carolina, USA. 35 (A): 97–108. CiteSeerX 10.1.1.39.2249. ISSN 0381-7032. S2CID 15975960. from the original on 2020-05-13. Retrieved 2020-05-13. (15 pages)
  71. ^ a b Goddyn, Luis (1999). (PDF). Department of Mathematics, Simon Fraser University. Archived from the original (PDF) on 2015-02-17.
  72. ^ Sawada, Joseph "Joe"; Wong, Dennis Chi-Him (2007). "A Fast Algorithm to generate Beckett–Gray codes". Electronic Notes in Discrete Mathematics. 29: 571–577. doi:10.1016/j.endm.2007.07.091.
  73. ^ Richards, Richard Kohler (January 1971). "Snake-in-the-Box Codes". Written at Ames, Iowa, USA. Digital Design. New York, USA: Wiley-Interscience, John Wiley & Sons, Inc. pp. 206–207. ISBN 0-471-71945-5. LCCN 73-147235. (12+577+1 pages)
  74. ^ a b NZ 264738, Spedding, Norman Bruce, "A position encoder", published 1994-10-28 [failed verification]
  75. ^ Spedding, Norman Bruce (1994-10-28). "The following is a copy of the provisional patent filed on behalf of Industrial Research Limited on 1994-10-28 – NZ Patent 264738" (PDF). Industrial Research Limited. NZ Patent 264738. (PDF) from the original on 2017-10-29. Retrieved 2018-01-14.
  76. ^ Hiltgen, Alain P.; Paterson, Kenneth G.; Brandestini, Marco (September 1996). "Single-Track Gray Codes" (PDF). IEEE Transactions on Information Theory. 42 (5): 1555–1561. doi:10.1109/18.532900. Zbl 857.94007.
  77. ^ Hiltgen, Alain P.; Paterson, Kennet

August 28, 2023
gray, code, lucal, code, 1the, reflected, binary, code, also, known, reflected, binary, after, frank, gray, ordering, binary, numeral, system, such, that, successive, values, differ, only, binary, digit, example, representation, decimal, value, binary, would, . Lucal code 1 2 5 4 3 2 1Gray code4 3 2 10 0 0 0 0 01 0 0 0 1 12 0 0 1 1 03 0 0 1 0 14 0 1 1 0 05 0 1 1 1 16 0 1 0 1 07 0 1 0 0 18 1 1 0 0 09 1 1 0 1 110 1 1 1 1 011 1 1 1 0 112 1 0 1 0 013 1 0 1 1 114 1 0 0 1 015 1 0 0 0 1The 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 3 Contents 1 Function 2 Invention 3 History and practical application 3 1 Mathematical puzzles 3 2 Telegraphy codes 3 3 Analog to digital signal conversion 3 4 Position encoders 3 5 Genetic algorithms 3 6 Boolean circuit minimization 3 7 Error correction 3 8 Communication between clock domains 3 9 Cycling through states with minimal effort 3 9 1 Gray code counters and arithmetic 3 9 2 Gray code addressing 4 Constructing an n bit Gray code 5 Converting to and from Gray code 6 Special types of Gray codes 6 1 Gray codes with n bits and of length less than 2n 6 2 n ary Gray code 6 3 Balanced Gray code 6 4 Long run Gray codes 6 5 Monotonic Gray codes 6 6 Beckett Gray code 6 7 Snake in the box codes 6 8 Single track Gray code 6 9 Two dimensional Gray code 6 10 Excess Gray Code 7 Gray isometry 8 Related codes 9 See also 10 Notes 11 References 12 Further reading 13 External linksFunction EditMany 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 0114 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 011 001 101 100 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 4 5 6 7 8 single distance single step monostrophic 9 10 7 8 or syncopic codes 9 in reference to the Hamming distance of 1 between adjacent codes Invention Edit Gray s patent introduces the term reflected binary code 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 11 12 13 Frank Gray introduced the term reflected binary code in his 1947 patent application remarking that the code had as yet no recognized name 14 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 Visualized as a traversal of vertices of a tesseract Gray code along the number lineDecimal Binary Gray Decimalof Gray0 0000 0000 01 0001 0001 12 0010 0011 33 0011 0010 24 0100 0110 65 0101 0111 76 0110 0101 57 0111 0100 48 1000 1100 129 1001 1101 1310 1010 1111 1511 1011 1110 1412 1100 1010 1013 1101 1011 1114 1110 1001 915 1111 1000 8For 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 15 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 11 12 13 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 16 17 one of those also lists minimum error code and cyclic permutation code among the names 17 A 1954 patent application refers to the Bell Telephone Gray code 18 Other names include cyclic binary code 12 cyclic progression code 19 12 cyclic permuting binary 20 or cyclic permuted binary CPB 21 22 The Gray code is sometimes misattributed to 19th century electrical device inventor Elisha Gray 13 23 24 25 History and practical application EditMathematical puzzles Edit 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 26 13 It can serve as a solution guide for the Towers of Hanoi problem based on a game by the French Edouard Lucas in 1883 27 28 29 30 Similarly the so called Towers of Bucharest and Towers of Klagenfurt game configurations yield ternary and pentary Gray codes 31 Martin Gardner wrote a popular account of the Gray code in his August 1972 Mathematical Games column in Scientific American 32 The code also forms a Hamiltonian cycle on a hypercube where each bit is seen as one dimension Telegraphy codes Edit When the French engineer Emile Baudot changed from using a 6 unit 6 bit code to 5 unit code for his printing telegraph system in 1875 33 or 1876 34 35 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 36 37 38 and other symbols appropriately placed the 5 bit character code has been recognized as a reflected binary code 13 This code became known as Baudot code 39 and with minor changes was eventually adopted as International Telegraph Alphabet No 1 ITA1 CCITT 1 in 1932 40 41 38 About the same time the German Austrian Otto Schaffler de 42 demonstrated another printing telegraph in Vienna using a 5 bit reflected binary code for the same purpose in 1874 43 13 Analog to digital signal conversion Edit 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 14 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 44 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 Edit 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 Edit Due to the Hamming distance properties of Gray codes they are sometimes used in genetic algorithms 15 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 Edit Gray codes are also used in labelling the axes of Karnaugh maps since 1953 45 46 47 as well as in Handler circle graphs since 1958 48 49 50 51 both graphical methods for logic circuit minimization Error correction Edit 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 Edit Main article Clock domain crossing 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 Edit 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 52 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 Edit George R Stibitz utilized a reflected binary code in a binary pulse counting device in 1941 already 11 12 13 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 53 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 54 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 55 add one to it with a standard binary adder and then convert the result back to Gray code 56 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 57 Gray code addressing Edit 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 58 59 Constructing an n bit Gray code Edit The first few steps of the reflect and prefix method 4 bit Gray code permutationThe 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 13 For example generating the n 3 list from the n 2 list 2 bit list 00 01 11 10 Reflected 10 11 01 00Prefix old entries with 0 000 001 011 010 Prefix new entries with 1 110 111 101 100Concatenated 000 001 011 010 110 111 101 100The 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 L 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 n 2 displaystyle 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 displaystyle i of codewords are inverted the order of neighbouring blocks of 2 i displaystyle 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 displaystyle b i at position i displaystyle i with the bit b i 1 displaystyle b i 1 at position i 1 displaystyle i 1 leaves the order of codewords intact if b i 1 0 displaystyle b i 1 mathtt 0 and reverses the order of blocks of 2 i 1 displaystyle 2 i 1 codewords if b i 1 1 displaystyle 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 displaystyle g i is the i displaystyle i th Gray coded bit g 0 displaystyle g 0 being the most significant bit and b i displaystyle b i is the i displaystyle i th binary coded bit b 0 displaystyle b 0 being the most significant bit the reverse translation can be given recursively b 0 g 0 displaystyle b 0 g 0 and b i g i b i 1 displaystyle 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 c o d e 0 0 displaystyle mathrm code 0 mathtt 0 and at step i gt 0 displaystyle i gt 0 find the bit position of the least significant 1 in the binary representation of i displaystyle i and flip the bit at that position in the previous code c o d e i 1 displaystyle mathrm code i 1 to get the next code c o d e i displaystyle 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 EditThe 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 60 55 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 gt gt 1 The operator gt gt 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 uint mask num while mask Each Gray code bit is exclusive ored with all more significant bits mask gt gt 1 num mask 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 gt gt 16 num num gt gt 8 num num gt gt 4 num num gt gt 2 num num gt gt 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 EditIn 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 Edit 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 61 OEIS sequence A290772 62 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 Edit Ternary number ternary Gray code0 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 222There 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 31 The n k Gray code is the n ary Gray code with k digits 63 The sequence of elements in the 3 2 Gray code is 00 01 02 12 11 10 20 21 22 The n k Gray code may be constructed recursively as the BRGC or may be constructed iteratively An algorithm to iteratively generate the N k 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 lt 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 63 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 Edit Although the binary reflected Gray code is useful in many scenarios it is not optimal in certain cases because of a lack of uniformity 52 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 d k displaystyle delta k the transition counts spectrum of G are the collection of integers defined by l k j Z R n d j k for k Z n displaystyle 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 l k R n n displaystyle lambda k tfrac R n n for all k Clearly when R 2 displaystyle R 2 such codes exist only if n is a power of 2 64 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 2 n 2 n displaystyle 2 left lfloor tfrac 2 n 2n right rfloor or 2 2 n 2 n displaystyle 2 left lceil tfrac 2 n 2n right rceil 52 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 65 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 52 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 1whereas 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 52 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 1We will now show a construction 66 and implementation 67 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 displaystyle 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 g 2 n 1 displaystyle G g 0 ldots g 2 n 1 into an even number L of non empty blocks of the form g 0 g 1 g k 2 g k 2 1 g k 3 g k L 2 1 g 2 g 1 displaystyle 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 displaystyle k 1 0 k L 1 2 displaystyle k L 1 2 and k L 1 mod 2 n displaystyle k L equiv 1 pmod 2 n This partition induces an n 2 displaystyle n 2 digit Gray code given by 00 g 0 displaystyle mathtt 00 g 0 00 g 1 00 g k 2 01 g k 2 01 g 1 11 g 1 11 g k 2 displaystyle 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 11 g k 2 1 11 g k 3 01 g k 3 01 g k 2 1 00 g k 2 1 00 g k 3 displaystyle 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 00 g 2 00 g 1 10 g 1 10 g 2 10 g 0 11 g 0 11 g 1 01 g 1 01 g 0 displaystyle 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 j d k j i 1 j L displaystyle 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 l i displaystyle lambda i is l i 4 l i 2 m i if 0 i lt n L otherwise displaystyle lambda i begin cases 4 lambda i 2m i amp text if 0 leq i lt n L amp text otherwise end cases 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 displaystyle i transition and splitting another block at another digit i displaystyle i transition produces a different Gray code with exactly the same transition spectrum l i displaystyle lambda i so one may for example 65 designate the first m i displaystyle m i transitions at digit i displaystyle i as those that fall between two blocks Uniform codes can be found when R 0 mod 4 displaystyle R equiv 0 pmod 4 and R n 0 mod n displaystyle R n equiv 0 pmod n and this construction can be extended to the R ary case as well 66 Long run Gray codes Edit 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 68 Monotonic Gray codes Edit Monotonic codes are useful in the theory of interconnection networks especially for minimizing dilation for linear arrays of processors 69 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 displaystyle Q n V n E n into levels of vertices that have equal weight i e V n i v V n v has weight i displaystyle V n i v in V n v text has weight i for 0 i n displaystyle 0 leq i leq n These levels satisfy V n i n i displaystyle V n i textstyle binom n i Let Q n i displaystyle Q n i be the subgraph of Q n displaystyle Q n induced by V n i V n i 1 displaystyle V n i cup V n i 1 and let E n i displaystyle E n i be the edges in Q n i displaystyle Q n i A monotonic Gray code is then a Hamiltonian path in Q n displaystyle Q n such that whenever d 1 E n i displaystyle delta 1 in E n i comes before d 2 E n j displaystyle delta 2 in E n j in the path then i j displaystyle 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 displaystyle P n j of length 2 n j displaystyle 2 textstyle binom n j having edges in E n j displaystyle E n j 69 We define P 1 0 0 1 displaystyle P 1 0 mathtt 0 mathtt 1 P n j displaystyle P n j emptyset whenever j lt 0 displaystyle j lt 0 or j n displaystyle j geq n and P n 1 j 1 P n j 1 p n 0 P n j displaystyle P n 1 j mathtt 1 P n j 1 pi n mathtt 0 P n j otherwise Here p n displaystyle pi n is a suitably defined permutation and P p displaystyle P pi refers to the path P with its coordinates permuted by p displaystyle pi These paths give rise to two monotonic n digit Gray codes G n 1 displaystyle G n 1 and G n 2 displaystyle G n 2 given by G n 1 P n 0 P n 1 R P n 2 P n 3 R and G n 2 P n 0 R P n 1 P n 2 R P n 3 displaystyle 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 p n displaystyle pi n which ensures that these codes are indeed Gray codes turns out to be p n E 1 p n 1 2 displaystyle pi n E 1 left pi n 1 2 right The first few values of P n j displaystyle P n j are shown in the table below Subpaths in the Savage Winkler algorithm P n j displaystyle P n j j 0 j 1 j 2 j 3n 1 0 1n 2 00 01 10 11n 3 000 001 100 110 010 011 101 111n 4 0000 0001 1000 1100 0100 0110 0010 0011 1010 1011 1001 1101 0101 0111 1110 1111These 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 Lovasz conjecture which states that every connected vertex transitive graph contains a Hamiltonian path The middle level subgraph Q 2 n 1 n displaystyle 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 15 displaystyle 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 70 Beckett Gray code Edit 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 71 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 71 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 13 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 72 Snake in the box codes Edit Maximum lengths of snakes Ls and coils Lc in the snakes in the box problem for dimensions n from 1 to 4Snake 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 73 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 5 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 Edit Yet another kind of Gray code is the single track Gray code STGC developed by Norman B Spedding 74 75 and refined by Hiltgen Paterson and Brandestini in Single track Gray codes 1996 76 77 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 78 Animated and color coded version of the STGC rotor 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 79 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 74 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 80 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 Single track Gray code for 30 positions Angle Code Angle Code Angle Code Angle Code Angle Code0 10000 72 01000 144 00100 216 00010 288 0000112 10100 84 01010 156 00101 228 10010 300 0100124 11100 96 01110 168 00111 240 10011 312 1100136 11110 108 01111 180 10111 252 11011 324 1110148 11010 120 01101 192 10110 264 01011 336 1010160 11000 132 01100 204 00110 276 00011 348 10001Each column is a cyclic shift of the first column and from any row to the next row only one bit changes 81 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 82 9 bit Single Track Gray Code displaying one degree angular resolution Since this 30 degree example was added there has been a lot of interest in examples with higher angular resolution In 2008 Gary Williams 83 based on previous work 80 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 84 was designed by etzenseep Florian Bauer in September 2022 An STGC for P 360 and n 9 is reproduced here Single track Gray code for 360 positions Angle Code Angle Code Angle Code Angle Code Angle Code Angle Code Angle Code Angle Code Angle Code0 100000001 1 110000001 2 111000001 3 111000011 4 111000111 5 111001111 6 111011111 7 111011011 8 1010110119 101011111 10 101011101 11 101010101 12 101010111 13 101110111 14 001110111 15 001010111 16 001011111 17 00101101118 001011001 19 001111001 20 001111101 21 000111101 22 000110101 23 000100101 24 000101101 25 000101001 26 00011100127 000110001 28 000010001 29 000011001 30 000001001 31 100001001 32 100001101 33 100000101 34 110000101 35 01000010136 010000111 37 010000011 38 010000001 39 000000001 40 000000011 41 100000011 42 110000011 43 110000111 44 11000111145 110011111 46 110111111 47 110110111 48 010110111 49 010111111 50 010111011 51 010101011 52 010101111 53 01110111154 011101110 55 010101110 56 010111110 57 010110110 58 010110010 59 011110010 60 011111010 61 001111010 62 00110101063 001001010 64 001011010 65 001010010 66 001110010 67 001100010 68 000100010 69 000110010 70 000010010 71 00001001172 000011011 73 000001011 74 100001011 75 100001010 76 100001110 77 100000110 78 100000010 79 000000010 80 00000011081 000000111 82 100000111 83 100001111 84 100011111 85 100111111 86 101111111 87 101101111 88 101101110 89 10111111090 101110110 91 101010110 92 101011110 93 111011110 94 111011100 95 101011100 96 101111100 97 101101100 98 10110010099 111100100 100 111110100 101 011110100 102 011010100 103 010010100 104 010110100 105 010100100 106 011100100 107 01100010099 111100100 100 111110100 101 011110100 102 011010100 103 010010100 104 010110100 105 010100100 106 011100100 107 011000100108 001000100 109 001100100 110 000100100 111 000100110 112 000110110 113 000010110 114 000010111 115 000010101 116 000011101117 000001101 118 000000101 119 000000100 120 000001100 121 000001110 122 000001111 123 000011111 124 000111111 125 001111111126 011111111 127 011011111 128 011011101 129 011111101 130 011101101 131 010101101 132 010111101 133 110111101 134 110111001135 010111001 136 011111001 137 011011001 138 011001001 139 111001001 140 111101001 141 111101000 142 110101000 143 100101000144 101101000 145 101001000 146 111001000 147 110001000 148 010001000 149 011001000 150 001001000 151 001001100 152 001101100153 000101100 154 000101110 155 000101010 156 000111010 157 000011010 158 000001010 159 000001000 160 000011000 161 000011100162 000011110 163 000111110 164 001111110 165 011111110 166 111111110 167 110111110 168 110111010 169 111111010 170 111011010171 101011010 172 101111010 173 101111011 174 101110011 175 101110010 176 111110010 177 110110010 178 110010010 179 110010011180 111010011 181 111010001 182 101010001 183 001010001 184 011010001 185 010010001 186 110010001 187 100010001 188 100010000189 110010000 190 010010000 191 010011000 192 011011000 193 001011000 194 001011100 195 001010100 196 001110100 197 000110100198 000010100 199 000010000 200 000110000 201 000111000 202 000111100 203 001111100 204 011111100 205 111111100 206 111111101207 101111101 208 101110101 209 111110101 210 110110101 211 010110101 212 011110101 213 011110111 214 011100111 215 011100101216 111100101 217 101100101 218 100100101 219 100100111 220 110100111 221 110100011 222 010100011 223 010100010 224 110100010225 100100010 226 100100011 227 000100011 228 000100001 229 100100001 230 100100000 231 100110000 232 110110000 233 010110000234 010111000 235 010101000 236 011101000 237 001101000 238 000101000 239 000100000 240 001100000 241 001110000 242 001111000243 011111000 244 111111000 245 111111001 246 111111011 247 011111011 248 011101011 249 111101011 250 101101011 251 101101010252 111101010 253 111101110 254 111001110 255 111001010 256 111001011 257 011001011 258 001001011 259 001001111 260 101001111261 101000111 262 101000110 263 101000100 264 101000101 265 001000101 266 001000111 267 001000110 268 001000010 269 001000011270 001000001 271 001100001 272 101100001 273 101100000 274 101110000 275 101010000 276 111010000 277 011010000 278 001010000279 001000000 280 011000000 281 011100000 282 011110000 283 111110000 284 111110001 285 111110011 286 111110111 287 111110110288 111010110 289 111010111 290 011010111 291 011010101 292 111010101 293 111011101 294 110011101 295 110010101 296 110010111297 110010110 298 010010110 299 010011110 300 010011111 301 010001111 302 010001101 303 010001001 304 010001011 305 010001010306 010001110 307 010001100 308 010000100 309 010000110 310 010000010 311 011000010 312 011000011 313 011000001 314 011100001315 010100001 316 110100001 317 110100000 318 010100000 319 010000000 320 110000000 321 111000000 322 111100000 323 111100001324 111100011 325 111100111 326 111101111 327 111101101 328 110101101 329 110101111 330 110101110 331 110101010 332 110101011333 110111011 334 100111011 335 100101011 336 100101111 337 100101101 338 100101100 339 100111100 340 100111110 341 100011110342 100011010 343 100010010 344 100010110 345 100010100 346 100011100 347 100011000 348 100001000 349 100001100 350 100000100351 110000100 352 110000110 353 110000010 354 111000010 355 101000010 356 101000011 357 101000001 358 101000000 359 100000000Starting and ending angles for the 20 tracks for a Single track Gray Code with 9 sensors separated by 40 Starting Angle Ending Angle Length3 4 223 28 631 37 744 48 556 60 564 71 874 76 388 91 494 96 399 104 6110 115 6131 134 4138 154 23173 181 9186 187 2220 238 19242 246 5273 279 7286 289 4307 360 54Two dimensional Gray code Edit A Gray coded constellation diagram for rectangular 16 QAMTwo 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 85 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 86 Excess Gray Code Edit 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 EditThe bijective mapping 0 00 1 01 2 11 3 10 establishes an isometry between the metric space over the finite field Z 2 2 displaystyle mathbb Z 2 2 with the metric given by the Hamming distance and the metric space over the finite ring Z 4 displaystyle 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 Z 2 2 m displaystyle mathbb Z 2 2m and Z 4 m displaystyle mathbb Z 4 m Its importance lies in establishing a correspondence between various good but not necessarily linear codes as Gray map images in Z 2 2 displaystyle mathbb Z 2 2 of ring linear codes from Z 4 displaystyle mathbb Z 4 87 88 Related codes EditThis section may contain an excessive number of citations The details given are Too many references makes the text hard to read Please consider removing references to unnecessary or disreputable sources merging citations where possible or if necessary flagging the content for deletion March 2021 Learn how and when to remove this template message There are a number of binary codes similar to Gray codes including Datex codes aka Giannini codes 1954 as described by Carl P Spaulding 9 89 90 91 92 8 use a variant of O Brien code II Codes used by Varec ca 1954 93 94 95 96 use a variant of O Brien code I as well as base 12 and base 16 Gray code variants Lucal code 1959 1 2 57 aka modified reflected binary code MRB 1 2 nb 3 Gillham code 1961 1962 90 97 8 98 99 uses a variant of Datex code and O Brien code II Leslie and Russell code 1964 100 10 101 97 Royal Radar Establishment code 97 Hoklas code 1988 102 103 104 The following binary coded decimal BCD codes are Gray code variants as well Petherick code 1953 19 105 106 107 55 103 nb 4 also known as Royal Aircraft Establishment RAE code 108 O Brien codes I and II 1955 109 110 111 91 92 103 An O Brien type I code nb 5 was already described by Frederic A Foss of IBM 112 113 and used by Varec in 1954 Later it was also known as Watts code or Watts reflected decimal WRD code and is sometimes ambiguously referred to as reflected binary modified Gray code 114 20 21 115 116 117 118 119 120 nb 1 nb 3 An O Brien type II code was already used by Datex in 1954 nb 4 Excess 3 Gray code 1956 121 aka Gray excess 3 code 91 92 8 Gray 3 excess code reflex excess 3 code excess Gray code 103 Gray excess code 10 excess 3 Gray code or Gray Stibitz code described by Frank P Turvey Jr of ITT 121 Tompkins codes I and II 1956 4 110 111 91 92 103 Glixon code 1957 sometimes ambiguously also called modified Gray code 122 55 123 124 110 111 91 92 103 nb 3 nb 5 4 bit unit distance BCD codes nb 6 Name Bit 0 1 2 3 4 5 6 7 8 9 Weights nb 7 Tracks Compl Cyclic 5s CommentGray BCD 4 0 0 0 0 0 0 0 0 1 1 0 3 4 3 nb 8 No 2 4 8 16 No 110 111 3 0 0 0 0 1 1 1 1 1 12 0 0 1 1 1 1 0 0 0 01 0 1 1 0 0 1 1 0 0 1Paul 4 1 0 0 0 0 0 0 0 1 1 1 3 4 3 nb 8 No 2 10 No 125 3 0 0 0 0 1 1 1 1 1 12 0 0 1 1 1 1 0 0 0 01 1 1 1 0 0 1 1 0 0 1Glixon 4 0 0 0 0 0 0 0 0 1 1 0 3 4 No 2 4 8 10 shifted 1 122 110 111 123 124 nb 5 3 0 0 0 0 1 1 1 1 1 02 0 0 1 1 1 1 0 0 0 01 0 1 1 0 0 1 1 0 0 0Tompkins I 4 0 0 0 0 0 1 1 1 1 1 0 4 2 No 2 4 10 Yes 4 110 111 3 0 0 0 0 1 1 1 1 1 02 0 0 1 1 1 1 1 0 0 01 0 1 1 0 0 0 1 1 0 0O Brien I Watts 4 0 0 0 0 0 1 1 1 1 1 0 3 4 9 103 104 nb 9 2 4 10 Yes 109 110 111 nb 5 3 0 0 0 0 1 1 0 0 0 02 0 0 1 1 1 1 1 1 0 01 0 1 1 0 0 0 0 1 1 0Petherick RAE 4 0 0 0 0 0 1 1 1 1 1 1 3 3 9 103 104 nb 9 2 10 Yes 19 107 nb 4 3 1 0 0 0 1 1 0 0 0 12 0 0 1 1 1 1 1 1 0 01 1 1 1 0 0 0 0 1 1 1O Brien II 4 0 0 0 0 0 1 1 1 1 1 1 3 3 9 91 103 104 nb 9 2 10 Yes 109 110 111 nb 4 3 0 0 0 1 1 1 1 0 0 02 0 1 1 1 0 0 1 1 1 01 1 1 0 0 0 0 0 0 1 1Susskind 4 0 0 0 0 0 1 1 1 1 1 1 4 3 9 nb 9 2 10 Yes 6 3 0 0 1 1 1 1 1 1 0 02 0 1 1 1 0 0 1 1 1 01 1 1 1 0 0 0 0 1 1 1Klar 4 0 0 0 0 0 1 1 1 1 1 0 4 4 3 nb 8 9 nb 9 2 10 Yes 126 127 3 0 0 0 1 1 1 1 0 0 02 0 0 1 1 1 1 1 1 0 01 0 1 1 1 0 0 1 1 1 0Tompkins II 4 0 0 0 0 0 1 1 1 1 1 1 3 2 9 nb 10 2 10 Yes 4 110 111 3 0 0 1 1 1 1 1 0 0 02 1 1 1 0 0 0 0 0 1 11 0 1 1 1 0 0 1 1 1 0Excess 3 Gray 4 0 0 0 0 0 1 1 1 1 1 1 4 4 9 103 104 nb 9 2 10 Yes 8 103 3 0 1 1 1 1 1 1 1 1 02 1 1 1 0 0 0 0 1 1 11 0 0 1 1 0 0 1 1 0 0See also EditLinear feedback shift register De Bruijn sequence Steinhaus Johnson Trotter algorithm an algorithm that generates Gray codes for the factorial number system Minimum distance code Prouhet Thue Morse sequence related to inverse Gray code Ryser formula Hilbert curveNotes Edit a b c By applying a simple inversion rule the Gray code and the O Brien code I can be translated into the 8421 pure binary code and the 2421 Aiken code respectively to ease arithmetic operations C Sequence 0 1 0 2 0 1 0 3 sequence A007814 in the OEIS a b c There are several Gray code variants which are called modified of some sort The Glixon code is sometimes called modified Gray code D The Lucal code is also called modified reflected binary code MRB E The O Brien code I or Watts code is sometimes referred to as reflected binary modified Gray code F a b c d By interchanging and inverting three bit rows the O Brien code II and the Petherick code can be transferred into each other a b c d By swapping two pairs of bit rows individually shifting four bit rows and inverting one of them the Glixon code and the O Brien code I can be transferred into each other Other unit distance BCD codes include the non Gray code related 5 bit Libaw Craig and the 1 2 1 code Depending on a code s target application the Hamming weights of a code can be important properties beyond coding theoretical considerations also for physical reasons Under some circumstances the all cleared and or all set states must be omitted f e to avoid non conductive or short circuit conditions it may be desirable to keep the highest used weight as low as possible f e to reduce power consumption of the reader circuit or to keep the variance of used weights small f e to reduce acoustic noise or current fluctuations a b c For Gray BCD Paul and Klar codes the number of necessary reading tracks can be reduced from 4 to 3 if inversion of one of the middle tracks is acceptable a b c d e f For O Brien codes I and II and Petherick Susskind Klar as well as Excess 3 Gray codes a 9s complement can be derived by inverting the most significant fourth binary digit For Tompkins code II a 9s complement can be derived by inverting the first three digits and swapping the two middle binary digits References Edit a b c Lucal Harold M December 1959 Arithmetic Operations for Digital Computers Using a Modified Reflected Binary IRE Transactions on Electronic Computers EC 8 4 449 458 doi 10 1109 TEC 1959 5222057 ISSN 0367 9950 S2CID 206673385 10 pages a b c Sellers Jr Frederick F Hsiao Mu Yue Bearnson Leroy W November 1968 Error Detecting Logic for Digital Computers 1st ed New York USA McGraw Hill Book Company pp 152 164 LCCN 68 16491 OCLC 439460 Gray Joel March 2020 Understanding Gray Code A Reliable Encoding System graycode ie Section Conclusion Retrieved 2023 06 30 a b c d Tompkins Howard E September 1956 1956 07 16 Unit Distance Binary Decimal Codes for Two Track Commutation IRE Transactions on Electronic Computers Correspondence Moore School of Electrical Engineering University of Pennsylvania Philadelphia Pennsylvania USA EC 5 3 139 doi 10 1109 TEC 1956 5219934 ISSN 0367 9950 Retrieved 2020 05 18 1 page a b Kautz William H June 1958 Unit Distance Error Checking Codes IRE Transactions on Electronic Computers EC 7 2 179 180 doi 10 1109 TEC 1958 5222529 ISSN 0367 9950 S2CID 26649532 2 pages a b Susskind Alfred Kriss Ward John Erwin 1958 03 28 1957 1956 III F Unit Distance Codes VI E 2 Reflected Binary Codes Written at Cambridge Massachusetts USA In Susskind Alfred Kriss ed Notes on Analog Digital Conversion Techniques Technology Books in Science and Engineering Vol 1 3 ed New York USA Technology Press of the Massachusetts Institute of Technology John Wiley amp Sons Inc Chapman amp Hall Ltd pp 3 10 3 16 3 13 3 16 6 65 6 60 6 60 x 416 2 pages NB The contents of the book was originally prepared by staff members of the Servomechanisms Laboraratory Department of Electrical Engineering MIT for Special Summer Programs held in 1956 and 1957 Susskind s reading type code is actually a minor variant of the code shown here with the two most significant bit rows swapped to better illustrate symmetries Also by swapping two bit rows and inverting one of them the code can be transferred into the Petherick code whereas by swapping and inverting two bit rows the code can be transferred into the O Brien code II a b Chinal Jean P January 1973 3 3 Unit Distance Codes Written at Paris France Design Methods for Digital Systems Translated by Preston Alan Summer Arthur 1st English ed Berlin Germany Akademie Verlag Springer Verlag p 50 doi 10 1007 978 3 642 86187 1 ISBN 978 0 387 05871 9 S2CID 60362404 License No 202 100 542 73 Order No 7617470 6047 ES 19 B 1 20 K 3 Retrieved 2020 06 21 xviii 506 pages NB The French 1967 original book was named Techniques Booleennes et Calculateurs Arithmetiques published by Editions Dunod fr a b c d e f Military Handbook Encoders Shaft Angle To Digital PDF United States Department of Defense 1991 09 30 MIL HDBK 231A Archived PDF from the original on 2020 07 25 Retrieved 2020 07 25 NB Supersedes MIL HDBK 231 AS 1970 07 01 a b c Spaulding Carl P 1965 01 12 1954 03 09 Digital coding and translating system PDF Monrovia California USA Datex Corporation U S Patent 3165731A Serial No 415058 Archived PDF from the original on 2020 08 05 Retrieved 2018 01 21 28 pages a b Russell A August 1964 Some Binary Codes and a Novel Five Channel Code Control Systems Instrumentation Data Processing Automation Management incorporating Automation Progress Special Features London UK Morgan Grampain Publishers Limited 8 74 399 404 Retrieved 2020 06 22 6 pages a b c Stibitz George Robert 1943 01 12 1941 11 26 Binary counter New York USA Bell Telephone Laboratories Incorporated U S Patent 2 307 868 Serial No 420537 Retrieved 2020 05 24 p 2 right column rows 43 73 A clearer idea of the position of the balls after each pulse will be obtained if the set of balls is represented by a number having a similar number of digits each of which may have one of two arbitrary values for example 0 and 1 If the upper position is called 0 and the lower position 1 then the setting of the counter may be read from left to right as 0 100 000 Following is a translation of the number of pulses received into this form of binary notation for the first sixteen pulses as received on the first five balls Pulse number Binary notation 1 4 pages a b c d e Winder C Farrell October 1959 Shaft Angle Encoders Afford High Accuracy PDF Electronic Industries Chilton Company 18 10 76 80 Archived from the original PDF on 2020 09 28 Retrieved 2018 01 14 p 78 The type of code wheel most popular in optical encoders contains a cyclic binary code pattern designed to give a cyclic sequence of on off outputs The cyclic binary code is also known as the cyclic progression code the reflected binary code and the Gray code This code was originated by G R Stibitz of Bell Telephone Laboratories and was first proposed for pulse code modulation systems by Frank Gray also of BTL Thus the name Gray code The Gray or cyclic code is used mainly to eliminate the possibility of errors at code transition which could result in gross ambiguities a b c d e f g h i Knuth Donald Ervin 2014 09 12 Enumeration and Backtracking Generating all n tuples The Art of Computer Programming Volume 4A Combinatorial Algorithms Part 1 Vol 4A 1 ed Addison Wesley Professional pp 442 443 ISBN 978 0 13348885 2 912 pages a b Gray Frank 1953 03 17 1947 11 13 Pulse Code Communication PDF New York USA Bell Telephone Laboratories Incorporated U S Patent 2 632 058 Serial No 785697 Archived PDF from the original on 2020 08 05 Retrieved 2020 08 05 13 pages a b Goldberg David Edward 1989 Genetic Algorithms in Search Optimization and Machine Learning 1 ed Reading Massachusetts USA Addison Wesley Bibcode 1989gaso book G Breckman Jack 1956 01 31 1953 12 31 Encoding Circuit PDF Long Branch New Jersey USA US Secretary of the Army U S Patent 2 733 432 Serial No 401738 Archived PDF from the original on 2020 08 05 Retrieved 2020 08 05 8 pages a b Ragland Earl Albert Schultheis Jr Harry B 1958 02 11 1953 10 16 Direction Sensitive Binary Code Position Control System PDF North Hollywood California USA Bendix Aviation Corporation U S Patent 2 823 345 Serial No 386524 Archived PDF from the original on 2020 08 05 Retrieved 2020 08 05 10 pages Domeshek Sol Reiner Stewart 1958 06 24 1954 01 08 Automatic Rectification System PDF US Secretary of the Navy U S Patent 2 839 974 Serial No 403085 Archived PDF from the original on 2020 08 05 Retrieved 2020 08 05 8 pages a b c Petherick Edward John October 1953 A Cyclic Progressive Binary coded decimal System of Representing Numbers Technical Note MS15 Farnborough UK Royal Aircraft Establishment RAE 4 pages NB Sometimes referred to as A Cyclic Coded Binary Coded Decimal System of Representing Numbers a b Evans David Silvester 1960 Fundamentals of Digital Instrumentation 1 ed London UK Hilger amp Watts Ltd Retrieved 2020 05 24 39 pages a b Evans David Silvester March 1961 Chapter Three Direct Reading from Coded Scales Digital Data Their derivation and reduction for analysis and process control 1 ed London UK Hilger amp Watts Ltd Interscience Publishers pp 18 23 Retrieved 2020 05 24 p 20 23 Decoding To decode C P B or W R D codes a simple inversion rule can be applied The readings of the higher tracks determine the way in which the lower tracks are translated The inversion rule is applied line by line for the C P B and for the W R D it is applied decade by decade or line by line Starting therefore with the top or slowest changing track of the C P B if the result is odd 1 the next track value has to be inverted i e 0 for 1 and 1 for 0 If however the first track is even 0 the second track is left as read i e 0 for 0 and 1 for 1 Again if the resultant reading of the second track is odd the third track reading is inverted and so on When an odd is changed to an even the line below is not inverted and when an even is changed to an odd the line below is inverted The result of applying this rule to the pattern is the pure binary P B pattern where each track or digit can be given a definite numerical value in this instance 1 2 4 8 etc Using the line by line inversion rule on the W R D code produces a pattern of 1 2 4 2 code where again the digits can be given numerical values and summed decade by decade The summing of the digits can be very useful for example in a high speed scanning system but in a parallel decoding system it is usual to treat each binary quartet or decade as an entity In other words if the first or more significant decade is odd the second decade is rectified or complemented by inverting the D track and so on the result being the repeating pattern of rectified W R D code This is an extremely easy thing to achieve since the only change required is the inversion of the meaning of the D track or complementing digit 8 82 pages NB The author does not mention Gray at all and calls the standard Gray code Cyclic Permuted Binary Code C P B the book index erroneously lists it as cyclic pure binary code Newson P A 1965 Tables for the Binary Encoding of Angles 1 ed United Kingdom Atomic Energy Authority Research Group Atomic Energy Research Establishment Harwell UK H M Stationery Office Retrieved 2020 05 24 12 pages Heath F G September 1961 Pioneers Of Binary Coding Journal of the Institution of Electrical Engineers Manchester College of Science and Technology Faculty of Technology of the University of Manchester Manchester UK Institution of Engineering and Technology IET 7 81 539 541 doi 10 1049 jiee 3 1961 0300 Retrieved 2020 06 22 3 pages Cattermole Kenneth W 1969 Written at Harlow Essex UK Principles of pulse code modulation 1 ed London UK New York USA Iliffe Books Ltd American Elsevier Publishing Company Inc pp 245 434 ISBN 978 0 444 19747 4 LCCN 78 80432 SBN 444 19747 8 p 245 There seems to be some confusion about the attributation of this code because two inventors named Gray have been associated with it When I first heard the name I took it as referring to Elisha Gray and Heath testifies to his usage of it Many people take it as referring to Frank Gray of Bell Telephone Laboratories who in 1947 first proposed its use in coding tubes his patent is listed in the bibliography 2 448 2 pages Edwards Anthony William Fairbank 2004 Cogwheels of the Mind The Story of Venn Diagrams Baltimore Maryland USA Johns Hopkins University Press pp 48 50 ISBN 0 8018 7434 3 Gros Luc Agathon Louis 1872 Theorie du baguenodier par un clerc de notaire lyonnais in French 1 ed Lyon France Aime Vingtrinier Archived from the original on 2017 04 03 Retrieved 2020 12 17 2 2 16 4 pages and 4 pages foldout NB This booklet was published anonymously but is known to have been authored by Louis Gros Lucas Edouard November 1883 La tour d Hanoi Veritable casse tete annamite Jeu rapporte du Tonkin par le Professeur N Claus de Siam Mandarin du College Li Sou Stian in French Imprimerie Paul Bousrez Tours NB N Claus de Siam is an anagram of Lucas d Amiens pseudonym of the author Edouard Lucas de Parville Henri in French ed 1883 12 27 La tour d Hanoi veritable casse tete annamite jeu rapporte du Tonkin par le professeur N Claus de Siam mandarin du college Li Sou Stian Un vrai casse tete en effet mais interessant Nous ne saurions mieux remercier le mandarin de son aimable intention a l egard d un profane qu en signalant la Tour d Hanoi aux personnes patientes possedees par le demon du jeu Journal des Debats Politiques et Litteraires Review Revue des science in French Matin ed Paris France 1 2 2 ark 12148 bpt6k462461g Archived from the original on 2020 12 18 Retrieved 2020 12 18 1 page Allardice R E Fraser A Y February 1883 Allardice Robert Edgar Fraser Alexander Yule eds La Tour d Hanoi Proceedings of the Edinburgh Mathematical Society in English and French Edinburgh Mathematical Society 2 5 50 53 doi 10 1017 S0013091500037147 eISSN 1464 3839 ISSN 0013 0915 S2CID 122159381 3 4 pages Lucas Edouard 1979 1892 Recreations mathematiques in French Vol 3 Librairie Albert Blanchard reissue ed p 58 The first edition of this book was published post humously a b Herter Felix Rote Gunter 2018 11 14 2018 08 09 2017 12 2017 08 09 2016 04 22 Loopless Gray Code Enumeration and the Tower of Bucharest PDF Theoretical Computer Science Berlin Germany 748 40 54 arXiv 1604 06707 doi 10 1016 j tcs 2017 11 017 ISSN 0304 3975 S2CID 4014870 Archived PDF from the original on 2020 12 16 Retrieved 2020 12 16 4 15 18 19 24 pages Gardner Martin August 1972 The curious properties of the Gray code and how it can be used to solve puzzles Scientific American Mathematical Games Vol 227 no 2 p 106 1 page Zeman Johann Fischer Ferdinand eds 1877 Einige neuere Vorschlage zur mehrfachen Telegraphie A Absatzweise vielfache Telegraphie Dingler s Polytechnisches Journal in German Augsburg Germany J G Cotta sche Buchhandlung 226 499 507 Archived from the original on 2020 12 21 Retrieved 2020 12 21 p 499 Der um die Mitte des J ahres 1874 patenti e rte ebenfalls dem Highton schen verwandte Typendrucker des franzosischen Telegraphen Verwaltungsbeamten Baudot wurde bei seiner 1875 patenti e rten Weiterentwicklung in einen funffachen umgewandelt Butrica Andrew J 1991 06 21 Baudot Jean Maurice Emile In Froehlich Fritz E Kent Allen Hall Carolyn M eds The Froehlich Kent Encyclopedia of Telecommunications Volume 2 Batteries to Codes Telecommunications Vol 2 Marcel Dekker Inc CRC Press pp 31 34 ISBN 0 8247 2901 3 LCCN 90 3966 Retrieved 2020 12 20 p 31 A Baudot prototype 4 years in the making was built in 1876 The transmitter had 5 keys similar to those of a piano Messages were sent in a special 5 element code devised by Baudot Fischer Eric N 2000 06 20 The Evolution of Character Codes 1874 1968 ark 13960 t07x23w8s Retrieved 2020 12 20 In 1872 Baudot started research toward a telegraph system that would allow multiple operators to transmit simultaneously over a single wire and as the transmissions were received would print them in ordinary alphabetic characters on a strip of paper He received a patent for such a system on June 17 1874 Instead of a variable delay followed by a single unit pulse Baudot s system used a uniform six time units to transmit each character his early telegraph probably used the six unit code that he attributes to Davy in an 1877 article in 1876 Baudot redesigned his equipment to use a five unit code Punctuation and digits were still sometimes needed though so he adopted from Hughes the use of two special letter space and figure space characters that would cause the printer to shift between cases at the same time as it advanced the paper without printing The five unit code he began using at this time was structured to suit his keyboard which controlled two units of each character with switches operated by the left hand and the other three units with the right hand 5 6 Rothen Timotheus 1884 12 25 Le telegraphe imprimeur Baudot Journal Telegraphique in French Berne Switzerland Le Bureau International des Administrations Telegraphiques VIII 16 12 241 253 249 eISSN 2725 738X ISSN 2223 1420 ark 12148 bpt6k5725454q Archived from the original on 2020 12 21 Retrieved 2020 12 20 Pendry Henry Walter 1920 October 1919 Written at London UK The Baudot Printing Telegraph System 2 ed London Bath Melbourne New York Sir Isaac Pitman and Sons Ltd pp 43 44 LCCN 21005277 OCLC 778309351 OL 6633244M Retrieved 2020 12 20 vii 184 pages NB A first edition was published in 1913 a b MacMillan David M 2010 04 27 2010 04 25 2010 04 23 Codes that Don t Count Some Printing Telegraph Codes as Products of their Technologies With Particular Attention to the Teletypesetter lemur com Revision 3 Mineral Point Wisconsin USA Archived from the original on 2020 12 18 Retrieved 2020 12 20 Written at Lisbon Portugual Convention telegraphique internationale de Saint Petersbourg et Reglement et tarifs y annexes Revision de Lisbonne 1908 Extraits de la publication Documents de la Conference telegraphique internationale de Lisbonne in French Berne Switzerland Bureau Internationale de L Union Telegraphique 1909 1908 Chapter IX Signaux de transmission Article 35 Signaux de transmission des alphabets telegraphiques internationaux nos 1 et 2 signaux d u code Morse de l appareil Hughes et de l appareil Siemens Written at Madrid Spain Reglement telegraphique annexe a la convention internationale des telecommunications protocol finale audit reglement Madrid 1932 PDF in French Berne Switzerland Bureau Internationale de L Union Telegraphique 1933 1932 pp 31 40 33 Archived PDF from the original on 2020 12 21 Retrieved 2020 12 21 1 188 pages 7 Chapter IX Transmission Signals Article 35 Transmission Signals of the International Telegraph Alphabets Nos 1 and 2 Morse Code Signals and Signals of the Hughes and Siemens Instruments Telegraph Regulations Annexed To The International Telecommunication Convention Final Protocol To The Telegraph Regulations Madrid 1932 PDF in English and French London UK General Post Office His Majesty s Stationery Office 1933 1932 pp 32 40 34 43 152 2 18693 Archived PDF from the original on 2020 12 21 Retrieved 2020 12 21 1 2 120 26 pages 8 Zemanek Heinrich Heinz Josef 1983 12 01 Otto Schaffler 1838 1928 Pionier des Telephons der Telegraphie und der Lochkarte sowie Erbauer der ersten Wiener Telephonzentrale Blatter fur Technikgeschichte in German and English Vol 41 43 1979 1981 1 ed Vienna Austria Technisches Museum fur Industrie und Gewerbe Forschungsinstitut fur Technikgeschichte Springer Verlag pp 81 118 ISBN 3 21181779 4 ISSN 0067 9127 OCLC 952698275 Zemanek Heinrich Heinz Josef 1976 06 07 Computer prehistory and history in central Europe Written at Vienna Austria International Workshop on Managing Requirements Knowledge AFIPS 76 Proceedings of the June 7 10 1976 national computer conference and exposition June 1976 Vol 1 New York USA American Federation of Information Processing Societies Association for Computing Machinery pp 15 20 doi 10 1145 1499799 1499803 ISBN 978 1 4503 7917 5 S2CID 14114959 Archived from the original on 2020 12 17 Retrieved 2020 12 17 p 17 In 1874 Schaeffler de invented another printing telegraph a quadruple system like the Baudot but mechanically more sophisticated The Hughes telegraph had two synchronously rotating fingers one in the sender and one in the receiver By a piano like keyboard the operator selected a letter and thereby made contact with the rotating finger in the corresponding direction Since the receiving finger was in the same direction at this moment the receiver could print the correct letter The Baudot and the Schaeffler printing telegraphs use a five bit binary code Schaeffler s code is a reflected binary code What F Gray patented in 1953 for PCM Schaeffler had applied in his telegraph in 1874 and for a similar reason reliability He had contact fingers sensing on five cams consecutively all combinations the right one triggers printing If the fingers are to make a minimal number of movements the solution is the reflected binary code For Schaeffler this idea was a minor one More exactly the code is described in a letter by the Austrian Post employee J ohann N epomuk Teufelhart inserted there as a footnote and telling that Schaeffler found the code by combining wooden bars with the different combinations until he had the best solution Another Post employee Alexander Wilhelm Lambert of Linz claims to have shown this code to Schaeffler as early as 1872 but this claim is not clear and cannot be checked 6 pages Goodall William M January 1951 Television by Pulse Code Modulation Bell System Technical Journal 30 1 33 49 doi 10 1002 j 1538 7305 1951 tb01365 x NB Presented orally before the I R E National Convention New York City March 1949 Karnaugh Maurice November 1953 1953 04 23 1953 03 17 The Map Method for Synthesis of Combinational Logic Circuits PDF Transactions of the American Institute of Electrical Engineers Part I Communication and Electronics 72 5 593 599 doi 10 1109 TCE 1953 6371932 S2CID 51636736 Paper 53 217 Archived from the original PDF on 2017 04 16 Retrieved 2017 04 16 NB Also contains a short review by Samuel H Caldwell Wakerly John F 1994 Digital Design Principles amp Practices New Jersey USA Prentice Hall pp 48 49 222 ISBN 0 13 211459 3 NB The two page sections taken together say that K maps are labeled with Gray code The first section says that they are labeled with a code that changes only one bit between entries and the second section says that such a code is called Gray code Brown Frank Markham 2012 2003 1990 3 9 2 Maps Boolean Reasoning The Logic of Boolean Equations reissue of 2nd ed Mineola New York USA Dover Publications Inc p 49 ISBN 978 0 486 42785 0 p 49 Karnaugh s map orders the arguments of the discriminants according to the reflected binary code also called the Gray code xii 291 3 pages 1st edition Handler Wolfgang 1958 Ein Minimisierungsverfahren zur Synthese von Schaltkreisen Minimisierungsgraphen Dissertation in German Potsdam Germany Technische Hochschule Darmstadt D 17 73 pages app 9 Berger Erich R Handler Wolfgang 1967 1962 Steinbuch Karl W Wagner Siegfried W eds Taschenbuch der Nachrichtenverarbeitung in German 2 ed Berlin Germany Springer Verlag OHG pp 64 1034 1035 1036 1038 LCCN 67 21079 Title No 1036 p 64 Ubersichtlich ist die Darstellung nach Handler die samtliche Punkte numeriert nach dem Gray Code auf dem Umfeld eines Kreises anordnet Sie erfordert allerdings sehr viel Platz Handler s diagram where all points numbered according to the Gray code are arranged on the circumference of a circle is easily comprehensible It needs however a lot of space Informatik Sammlung Erlangen ISER in German Erlangen Germany Friedrich Alexander Universitat 2012 03 13 Archived from the original on 2017 05 16 Retrieved 2017 04 12 Informatik Sammlung Erlangen ISER Impressum in German Erlangen Germany Friedrich Alexander Universitat 2012 03 13 Archived from the original on 2012 02 26 Retrieved 2017 04 15 a b c d e Bhat Girish S Savage Carla Diane 1996 Balanced Gray Codes Electronic Journal of Combinatorics 3 1 doi 10 37236 1249 Donohue Ryan 2003 Synchronization in Digital Logic Circuits PDF Archived PDF from the original on 2018 01 15 Retrieved 2018 01 15 Hulst George D 1962 02 06 1957 11 15 Reflected binary code counter PDF Nutley New Jersey USA International Telephone and Telegraph Corporation ITT U S Patent 3 020 481 Serial No 696793 Archived PDF from the original on 2020 08 06 Retrieved 2020 08 06 5 pages a b c d Powell E Alexander June 1968 Codes particularly useful for analogue to digital conversions A short note on useful codes for Fluidic Control Circuits PDF Cranfield UK The College of Aeronautics Department of Production Engineering pp 7 9 S2CID 215864694 CoA Memo 156 Archived PDF from the original on 2020 12 15 Retrieved 2020 12 15 18 pages NB The paper names the Glixon code modified Gray code and misspells Richard W Hamming s name Mehta Huzefa Owens Robert Michael Irwin Mary Jane Janie 1996 03 22 Some issues in gray code addressing Proceedings of the Sixth Great Lakes Symposium on VLSI IEEE Computer Society pp 178 181 doi 10 1109 GLSV 1996 497616 ISBN 978 0 8186 7502 7 ISSN 1066 1395 S2CID 52837310 a b Doran Robert Bob William March 2007 The Gray Code PDF CDMTCS Research Report Series Centre for Discrete Mathematics and Theoretical Computer Science University of Auckland New Zealand CDMTCS 304 Archived PDF from the original on 2020 05 22 Retrieved 2020 05 23 25 pages Su Ching Long Tsui Chi Ying Despain Alvin M 1994 Low Power Architecture Design and Compilation Techniques for High Performance Processors PDF Report Advanced Computer Architecture Laboratory ACAL TR 94 01 Archived PDF from the original on 2020 07 26 Retrieved 2020 12 17 Guo Hui Parameswaran Sri April June 2010 Shifted Gray encoding to reduce instruction memory address bus switching for low power embedded systems Journal of Systems Architecture 56 4 6 180 190 doi 10 1016 j sysarc 2010 03 003 Dietz Henry Gordon Hank 2002 The Aggregate Magic Algorithms Gray Code Conversion The Aggregate Electrical and Computer Engineering Department College of Engineering University of Kentucky Archived from the original on 2020 12 16 Retrieved 2020 12 16 Maxfield Max 2007 06 29 How to generate Gray Codes for non power of 2 sequences Archived from the original on 2022 01 29 Retrieved 2022 01 29 sequence A290772 in the OEIS a b Guan Dah Jyh 1998 Generalized Gray Codes with Applications Proceedings of the National Scientific Council Republic of China Part A 22 841 848 CiteSeerX 10 1 1 119 1344 D G Wagner J West 1991 Construction of Uniform Gray Codes Congressus Numerantium 80 217 223 a b Suparta I Nengah 2005 A simple proof for the existence of exponentially balanced Gray codes Electronic Journal of Combinatorics 12 doi 10 37236 1986 a b Flahive Mary Elizabeth Bose Bella 2007 Balancing cyclic R ary Gray codes Electronic Journal of Combinatorics 14 doi 10 37236 949 Strackx Raoul Piessens Frank 2016 Ariadne A Minimal Approach to State Continuity Usenix Security 25 Savage Carla Diane 1997 A Survey of Combinatorial Gray Codes SIAM Review Society for Industrial and Applied Mathematics SIAM 39 4 605 629 Bibcode 1997SIAMR 39 605S CiteSeerX 10 1 1 39 1924 doi 10 1137 S0036144595295272 JSTOR 2132693 S2CID 6375360 a b Savage Carla Diane Winkler Peter 1995 Monotone Gray codes and the middle levels problem Journal of Combinatorial Theory Series A 70 2 230 248 doi 10 1016 0097 3165 95 90091 8 ISSN 0097 3165 Savage Carla Diane 1997 01 16 Long cycles in the middle two levels of the Boolean lattice Ars Combinatoria North Carolina State University Raleigh North Carolina USA 35 A 97 108 CiteSeerX 10 1 1 39 2249 ISSN 0381 7032 S2CID 15975960 Archived from the original on 2020 05 13 Retrieved 2020 05 13 15 pages a b Goddyn Luis 1999 MATH 343 Applied Discrete Math Supplementary Materials PDF Department of Mathematics Simon Fraser University Archived from the original PDF on 2015 02 17 Sawada Joseph Joe Wong Dennis Chi Him 2007 A Fast Algorithm to generate Beckett Gray codes Electronic Notes in Discrete Mathematics 29 571 577 doi 10 1016 j endm 2007 07 091 Richards Richard Kohler January 1971 Snake in the Box Codes Written at Ames Iowa USA Digital Design New York USA Wiley Interscience John Wiley amp Sons Inc pp 206 207 ISBN 0 471 71945 5 LCCN 73 147235 12 577 1 pages a b NZ 264738 Spedding Norman Bruce A position encoder published 1994 10 28 failed verification Spedding Norman Bruce 1994 10 28 The following is a copy of the provisional patent filed on behalf of Industrial Research Limited on 1994 10 28 NZ Patent 264738 PDF Industrial Research Limited NZ Patent 264738 Archived PDF from the original on 2017 10 29 Retrieved 2018 01 14 Hiltgen Alain P Paterson Kenneth G Brandestini Marco September 1996 Single Track Gray Codes PDF IEEE Transactions on Information Theory 42 5 1555 1561 doi 10 1109 18 532900 Zbl 857 94007 Hiltgen Alain P Paterson Kennet, wikipedia, wiki, book, books, library,

article

, read, download, free, free download, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, picture, music, song, movie, book, game, games.