Gray code

Uses your system voice; voice and rate in settings.

Snapshot

≈ 20 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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 " ", and "2" would be " ". In Gray code, these values are represented as " " and " ". 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.

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 " ", and "2" would be " ". In Gray code, these values are represented as " " and " ". 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. QPSK Gray Coded.svg|Codes 4-PSK 8PSK Gray Coded.svg|Codes 8-PSK 16QAM Gray Coded.svg|Codes 16-QAM

Gray code addressing

As the execution of executable 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. 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 , prefixing the entries in the reflected list with a binary  , and then concatenating the original list with the reversed list. For example, generating the n = 3 list from the n = 2 list: The one-bit Gray code is G 1  = ( ). This can be thought of as built recursively as above from a zero-bit Gray code G 0  = ( Λ ) consisting of a single entry of zero length. This iterative process of generating G n+1 from G n makes the following properties of the standard reflecting code clear: G n is a permutation of the numbers 0, ..., 2 n  − 1. (Each number appears exactly once in the list.) G n is embedded as the first half of G n+1 . Therefore, the coding is stable, in the sense that once a binary number appears in G n 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 G n differs by only one bit from the previous entry. (The Hamming distance is 1.) The last entry in G n differs by only one bit from the first entry. (The code is cyclic.) These characteristics suggest a simple and fast method of translating a binary value into the corresponding Gray code. Each bit is inverted if the next higher bit of the input value is set to one. This can be performed in parallel by a bit-shift and exclusive-or operation if they are available: the nth Gray code is obtained by computing n \oplus \left\lfloor \tfrac{n}{2} \right\rfloor . Prepending a bit leaves the order of the code words unchanged, prepending a bit reverses the order of the code words. If the bits at position i of codewords are inverted, the order of neighbouring blocks of 2^i codewords is reversed. For example, if bit 0 is inverted in a 3 bit codeword sequence, the order of two neighbouring codewords is reversed If bit 1 is inverted, blocks of 2 codewords change order: If bit 2 is inverted, blocks of 4 codewords reverse order: Thus, performing an exclusive or on a bit b_i at position i with the bit b_{i+1} at position i+1 leaves the order of codewords intact if b_{i+1} = \mathtt{0} , and reverses the order of blocks of 2^{i+1} codewords if b_{i+1} = \mathtt{1} . Now, this is exactly the same operation as the reflect-and-prefix method to generate the Gray code. A similar method can be used to perform the reverse translation, but the computation of each bit depends on the computed value of the next higher bit so it cannot be performed in parallel. Assuming g_i is the i th Gray-coded bit ( g_0 being the most significant bit), and b_i is the i th binary-coded bit ( b_0 being the most-significant bit), the reverse translation can be given recursively: b_0 = g_0 , and b_i=g_i \oplus b_{i-1} . Alternatively, decoding a Gray code into a binary number can be described as a prefix sum of the bits in the Gray code, where each individual summation operation in the prefix sum is performed modulo two. To construct the binary-reflected Gray code iteratively, at step 0 start with the \mathrm{code}_0 = \mathtt{0} , and at step i > 0 find the bit position of the least significant in the binary representation of i and flip the bit at that position in the previous code \mathrm{code}_{i-1} to get the next code \mathrm{code}_i . The bit positions start 0, 1, 0, 2, 0, 1, 0, 3, ... See find first set for efficient algorithms to compute these values. 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 Gray encoding of x will always give either x or its bitwise negation.

n-ary Gray code

|} 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 . The (n, k)-Gray code is the n-ary Gray code with k digits. The sequence of elements in the (3, 2)-Gray code is: . 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 There are other Gray code algorithms for (n, k)-Gray codes. The (n, k)-Gray code produced by the above algorithm is always cyclical; some algorithms, such as that by Guan, lack this property when k is odd. On the other hand, while only one digit at a time changes with this method, it can change by wrapping (looping from n − 1 to 0). In Guan's algorithm, the count alternately rises and falls, so that the numeric difference between two Gray code digits is always one. Gray codes are not uniquely defined, because a permutation of the columns of such a code is a Gray code too. The above procedure produces a code in which the lower the significance of a digit, the more often it changes, making it similar to normal counting methods. See also Skew binary number system, a variant ternary number system where at most two digits change on each increment, as each increment can be done with at most one digit carry operation. \lambda_k = |\{ j \in \mathbb{Z}_{R^n} : \delta_j = k \}| \, , \text { for } k \in \mathbb{Z}_n A Gray code is uniform or uniformly balanced if its transition counts are all equal, in which case we have \lambda_k = \tfrac{R^n}{n} for all k. Clearly, when R = 2 , such codes exist only if n is a power of 2. If n is not a power of 2, it is possible to construct well-balanced binary codes where the difference between two transition counts is at most 2; so that (combining both cases) every transition count is either 2\left\lfloor \tfrac{2^n}{2n} \right\rfloor or 2\left\lceil \tfrac{2^n}{2n} \right\rceil . Gray codes can also be exponentially balanced if all of their transition counts are adjacent powers of two, and such codes exist for every power of two. For example, a balanced 4-bit Gray code has 16 transitions, which can be evenly distributed among all four positions (four transitions per position), making it uniformly balanced: 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: We will now show a construction and implementation for well-balanced binary Gray codes which allows us to generate an n-digit balanced Gray code for every n. The main principle is to inductively construct an (n + 2)-digit Gray code G' given an n-digit Gray code G in such a way that the balanced property is preserved. To do this, we consider partitions of G = g_0, \ldots, g_{2^n-1} into an even number L of non-empty blocks of the form \left\{g_0\right\}, \left\{g_1, \ldots, g_{k_2}\right\}, \left\{g_{k_2+1}, \ldots, g_{k_3}\right\}, \ldots, \left\{g_{k_{L-2}+1}, \ldots, g_{-2}\right\}, \left\{g_{-1}\right\} where k_1 = 0 , k_{L-1} = -2 , and k_{L} \equiv -1 \pmod{2^n} ). This partition induces an (n+2) -digit Gray code given by If we define the transition multiplicities m_i = \left|\left\{ j : \delta_{k_j} = i, 1 \leq j \leq L \right\}\right| to be the number of times the digit in position i changes between consecutive blocks in a partition, then for the (n + 2)-digit Gray code induced by this partition the transition spectrum \lambda'_i is \lambda'_i = \begin{cases} 4 \lambda_i - 2 m_i, & \text{if } 0 \leq i The delicate part of this construction is to find an adequate partitioning of a balanced n-digit Gray code such that the code induced by it remains balanced, but for this only the transition multiplicities matter; joining two consecutive blocks over a digit i transition and splitting another block at another digit i transition produces a different Gray code with exactly the same transition spectrum \lambda'_i , so one may for example designate the first m_i transitions at digit i as those that fall between two blocks. Uniform codes can be found when R \equiv 0 \pmod 4 and R^n \equiv 0 \pmod n , and this construction can be extended to the R-ary case as well. We can formalize the concept of monotone Gray codes as follows: consider the partition of the hypercube Q_n = (V_n, E_n) into levels of vertices that have equal weight, i.e. V_n(i) = \{ v \in V_n : v \text{ has weight } i \} for 0 \leq i \leq n . These levels satisfy |V_n(i)| = \textstyle\binom{n}{i} . Let Q_n(i) be the subgraph of Q_n induced by V_n(i) \cup V_n(i+1) , and let E_n(i) be the edges in Q_n(i) . A monotonic Gray code is then a Hamiltonian path in Q_n such that whenever \delta_1 \in E_n(i) comes before \delta_2 \in E_n(j) in the path, then i \leq j . An elegant construction of monotonic n-digit Gray codes for any n is based on the idea of recursively building subpaths P_{n,j} of length 2 \textstyle\binom{n}{j} having edges in E_n(j) . We define P_{1,0} = (\mathtt{0}, \mathtt{1}) , P_{n,j} = \emptyset whenever j or j \geq n , and P_{n+1,j} = \mathtt{1}P^{\pi_n}_{n,j-1}, \mathtt{0}P_{n,j} otherwise. Here, \pi_n is a suitably defined permutation and P^{\pi} refers to the path P with its coordinates permuted by \pi . These paths give rise to two monotonic n-digit Gray codes G_n^{(1)} and G_n^{(2)} given by G_n^{(1)} = P_{n,0} P_{n,1}^R P_{n,2} P_{n,3}^R \cdots \text{ and } G_n^{(2)} = P_{n,0}^R P_{n,1} P_{n,2}^R P_{n,3} \cdots The choice of \pi_n which ensures that these codes are indeed Gray codes turns out to be \pi_n = E^{-1}\left(\pi_{n-1}^2\right) . The first few values of P_{n,j} are shown in the table below. These monotonic Gray codes can be efficiently implemented in such a way that each subsequent element can be generated in O(n) time. The algorithm is most easily described using coroutines. Monotonic codes have an interesting connection to the Lovász conjecture, which states that every connected vertex-transitive graph contains a Hamiltonian path. The "middle-level" subgraph Q_{2n+1}(n) is vertex-transitive (that is, its automorphism group is transitive, so that each vertex has the same "local environment" and cannot be differentiated from the others, since we can relabel the coordinates as well as the binary digits to obtain an automorphism) and the problem of finding a Hamiltonian path in this subgraph is called the "middle-levels problem", which can provide insights into the more general conjecture. The question has been answered affirmatively for n \leq 15 , and the preceding construction for monotonic codes ensures a Hamiltonian path of length at least 0.839 N, where N is the number of vertices in the middle-level subgraph. Another type of Gray code, the Beckett–Gray code, is named for Irish playwright Samuel Beckett, who was interested in symmetry. His play "Quad" features four actors and is divided into sixteen time periods. Each period ends with one of the four actors entering or leaving the stage. The play begins and ends with an empty stage, and Beckett wanted each subset of actors to appear on stage exactly once. Clearly the set of actors currently on stage can be represented by a 4-bit binary Gray code. Beckett, however, placed an additional restriction on the script: he wished the actors to enter and exit so that the actor who had been on stage the longest would always be the one to exit. The actors could then be represented by a FIFO queue, so that (of the actors onstage) the actor being dequeued is always the one who was enqueued first. Beckett was unable to find a Beckett–Gray code for his play, and indeed, an exhaustive listing of all possible sequences reveals that no such code exists for n = 4. It is known today that such codes do exist for n = 2, 5, 6, 7, and 8, and do not exist for n = 3 or 4. An example of an 8-bit Beckett–Gray code can be found in Donald Knuth's Art of Computer Programming. According to Sawada and Wong, the search space for n = 6 can be explored in 15 hours, and more than solutions for the case n = 7 have been found.

Snake-in-the-box codes

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

Single-track Gray code

Yet another kind of Gray code is the single-track Gray code (STGC) developed by Norman B. Spedding and refined by Hiltgen, Paterson and Brandestini in Single-track Gray Codes (1996). The STGC is a cyclical list of P unique binary encodings of length n such that two consecutive words differ in exactly one position, and when the list is examined as a P × n matrix, each column is a cyclic shift of the first column. The name comes from their use with rotary encoders, where a number of tracks are being sensed by contacts, resulting for each in an output of or . To reduce noise due to different contacts not switching at exactly the same moment in time, one preferably sets up the tracks so that the data output by the contacts are in Gray code. To get high angular accuracy, one needs lots of contacts; in order to achieve at least 1° accuracy, one needs at least 360 distinct positions per revolution, which requires a minimum of 9 bits of data, and thus the same number of contacts. If all contacts are placed at the same angular position, then 9 tracks are needed to get a standard BRGC with at least 1° accuracy. However, if the manufacturer moves a contact to a different angular position (but at the same distance from the center shaft), then the corresponding "ring pattern" needs to be rotated the same angle to give the same output. If the most significant bit (the inner ring in Figure 1) is rotated enough, it exactly matches the next ring out. Since both rings are then identical, the inner ring can be cut out, and the sensor for that ring moved to the remaining, identical ring (but offset at that angle from the other sensor on that ring). Those two sensors on a single ring make a quadrature encoder. That reduces the number of tracks for a "1° resolution" angular encoder to 8 tracks. Reducing the number of tracks still further cannot be done with BRGC. For many years, Torsten Sillke and other mathematicians believed that it was impossible to encode position on a single track such that consecutive positions differed at only a single sensor, except for the 2-sensor, 1-track quadrature encoder. So for applications where 8 tracks were too bulky, people used single-track incremental encoders (quadrature encoders) or 2-track "quadrature encoder + reference notch" encoders. Norman B. Spedding, however, registered a patent in 1994 with several examples showing that it was possible. Although it is not possible to distinguish 2 n 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 2 n  − 2n positions and that for prime n the limit is 2 n  − 2 positions. The authors went on to generate a 504-position single track code of length 9 which they believe is optimal. Since this number is larger than 2 8  = 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: Each column is a cyclic shift of the first column, and from any row to the next row only one bit changes. The single-track nature (like a code chain) is useful in the fabrication of these wheels (compared to BRGC), as only one track is needed, thus reducing their cost and size. The Gray code nature is useful (compared to chain codes, also called De Bruijn sequences), as only one sensor will change at any one time, so the uncertainty during a transition between two discrete states will only be plus or minus one unit of angular measurement the device is capable of resolving. Since this 30 degree example was added, there has been a lot of interest in examples with higher angular resolution. In 2008, Gary Williams, based on previous work, discovered a 9-bit single track Gray code that gives a 1 degree resolution. This Gray code was used to design an actual device which was published on the site Thingiverse. This device was designed by etzenseep (Florian Bauer) in September 2022. An STGC for P = 360 and n = 9 is reproduced here: Part 2 Part 3 (7 pages) (5 pages) (2 pages) ProtoTalk.net – Understanding Quadrature Encoding – Covers quadrature encoding in more detail with a focus on robotic applications

Text derived from https://en.wikipedia.org/w/index.php?oldid=1374164130 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

24 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.