Content deleted Content added
m Use svg version of arcs image |
Citation bot (talk | contribs) Add: bibcode, article-number. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox | #UCB_webform_linked 72/990 |
||
| (45 intermediate revisions by 22 users not shown) | |||
Line 5:
The '''reflected binary code''' ('''RBC'''), also known as '''reflected binary''' ('''RB''') or '''Gray code''' after [[Frank Gray (researcher)|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 "{{mono|001}}", and "2" would be "{{mono|010}}". In Gray code, these values are represented as "{{mono|001}}" and "{{mono|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]] [[switch]]es and to facilitate [[error correction]] in digital communications such as [[digital terrestrial television]] and some [[DOCSIS|cable TV]] systems. The use of Gray code in these devices helps simplify logic operations and reduce errors in practice.<ref>{{Cite web |last=Gray |first=Joel |date=March 2020 |title=Understanding Gray Code: A Reliable Encoding System |url=https://graycode.ie/blog/graycode/ |access-date=2023-06-30 |website=graycode.ie |at=Section: Conclusion |language=en}}</ref>
== Function ==
Many devices indicate position by closing and opening switches. If that device uses [[natural binary code]]s, positions 3 and 4 are next to each other but all three bits of the binary representation differ:
▲:{| class="wikitable" style="text-align:center;"
|-
! Decimal !! Binary
Line 30 ⟶ 29:
{{anchor|Monostrophic|Unit-distance|Single-distance|Single-step|Syncopic}}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 [[integer]]s, 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'',<ref name="Tompkins_1956"/><ref name="Kautz_1958"/><ref name="Susskind_1958"/><ref name="Chinal_1973"/><ref name="MIL_1991"/> ''single-distance'', ''single-step'', ''monostrophic''<ref name="Spaulding_1954"/><ref name="Russell_1964"/><ref name="Chinal_1973"/><ref name="MIL_1991"/> or ''syncopic codes'',<ref name="Spaulding_1954"/> in reference to the [[Hamming distance]] of 1 between adjacent codes.
== Invention ==
[[File:Reflected binary Gray 2632058.png|thumb|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 numeral system|binary]] code for non-negative integers, the ''binary-reflected Gray code'', or '''BRGC'''. [[Bell Labs]] researcher
[[George R.
In the standard encoding the least significant bit follows a repetitive pattern of 2 on, 2 off {{nowrap|( … {{mono|11001100}} … );}} the next digit a pattern of 4 on, 4 off; the ''i''th least significant bit a pattern of 2<sup>''i''</sup> on 2<sup>''i''</sup> off. The most significant digit is an exception to this; for an ''n''-bit Gray code, the most significant digit follows 2<sup>''n-1''</sup> on 2<sup>''n-1''</sup> 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:▼
[[File:Gray_code_tesseract.svg|thumb|Visualized as a traversal of [[Vertex (graph theory)|vertices]] of a [[tesseract]]]]
[[File:Gray code number line arcs.svg|thumb|Gray code along the number line]]
▲In the standard encoding of the Gray code the least significant bit follows a repetitive pattern of 2
|-
▲! Decimal !! Binary !! Gray !! Decimal<br />of Gray
|-
|
|-
|
|-
|
|-
|
|-
|
|-
|
|-
|
|-
|
|-
|
|-
|
|-
|
|-
|
|-
|
|-
|
|-
|
▲| 15 || {{mono|1111}} || {{mono|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.<ref name="Goldberg_1989"/>
In modern [[digital communications]], Gray codes play an important role in [[error correction]]. For example, in a [[digital modulation]] scheme such as [[quadrature amplitude modulation|QAM]] where data is typically transmitted in [[symbol rate|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]].
Line 94 ⟶ 91:
It can serve as a solution guide for the [[Towers of Hanoi]] problem, based on a game by the French [[Édouard Lucas]] in 1883.<ref name="Lucas_1883"/><ref name="Parville_1883"/><ref name="Allardice-Fraser_1883"/><ref name="Lucas_1892"/> Similarly, the so-called Towers of Bucharest and Towers of Klagenfurt game configurations yield [[#n-ary|ternary and pentary]] Gray codes.<ref name="Herter-Rote_2016"/>
[[Martin Gardner]] wrote a popular account of the Gray code in his August 1972 [[List of Martin Gardner Mathematical Games columns|"Mathematical Games" column]] in ''[[Scientific American]]''.<ref name="Gardner_1972"/>
The code also forms a [[Hamiltonian cycle]] on a [[hypercube]], where each bit is seen as one dimension.
Line 100 ⟶ 97:
=== Telegraphy codes ===
{{anchor|Baudot|Excess-1 Gray}}When the French engineer [[Émile Baudot]] changed from using a 6-unit (6-bit) code to 5-unit code for his [[printing telegraph]] system,
{{anchor|Schäffler telegraph|Schäffler code}}About the same time, the German-Austrian {{ill|Otto Schäffler|de|Theodor Heinrich Otto Schäffler}}<ref name="Zemanek_1979"/> demonstrated another printing telegraph in Vienna using a 5-bit reflected binary code for the same purpose, in 1874.<ref name="Zemanek_1976"/><ref name="Knuth_2014"/>
Line 107 ⟶ 104:
[[Frank Gray (researcher)|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,<ref name="Gray_1947"/> and the name of Gray stuck to the codes. The "[[Pulse-code modulation#History|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.<ref name="Goodall_1951"/>
[[File:US02632058 Gray.png|thumb|
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.
Line 134 ⟶ 132:
=== Error correction ===
In modern [[digital communications]], 1D- and 2D-Gray codes play an important role in error prevention before applying an [[error correction]]. For example, in a [[digital modulation]] scheme such as [[quadrature amplitude modulation|QAM]] where data is typically transmitted in [[symbol rate|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
<gallery heights="120" mode="packed" style="text-align:left">
QPSK Gray Coded.svg|Codes 4-PSK
Line 148 ⟶ 146:
=== Cycling through states with minimal effort ===
If a system has to cycle sequentially 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,<ref name="Bhat-Savage_1996"/> that flips every bit equally often. Since bit-flips are evenly distributed, this is optimal in the following way: balanced Gray codes minimize the maximal count of bit-flips for each digit.
==== Gray code counters and arithmetic ====
[[George R. Stibitz]] utilized a reflected binary code in a binary pulse counting device in 1941 already.<ref name="Stibitz_1941"/><ref name="Winder_1959"/><ref name="Knuth_2014"/>
A typical use of Gray code counters is building a [[FIFO (computing and electronics)|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.<ref name="Donohue_2003"/> 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,<ref group="nb" name="NB_Arithmetic_conversion"/> 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.<ref name="Hulst_1957"/>
Line 162 ⟶ 159:
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,<ref name="Powell_1968"/> add one to it with a standard binary adder, and then convert the result back to Gray code.<ref name="Mehta-Owens-Irwin_1996"/> 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.<ref name="Doran_2007"/>
====
As the execution of [[program code]] typically causes an instruction memory access pattern of locally consecutive addresses, [[bus encoding]]s 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.<ref name="Su-Tsui-Despain_1994"/><ref name="Guo-Parameswaran_2010"/>
== Constructing an ''n''-bit Gray code ==
[[File:Binary-reflected Gray code construction.svg|frame|right|The first few steps of the reflect-and-prefix method.]]
Line 197 ⟶ 194:
The one-bit Gray code is ''G''<sub>1</sub> = ({{mono|0,1}}). This can be thought of as built recursively as above from a zero-bit Gray code ''G''<sub>0</sub> = ( [[Empty string|Λ]] ) consisting of a single entry of zero length. This iterative process of generating ''G''<sub>''n''+1</sub> from ''G''<sub>''n''</sub> makes the following properties of the standard reflecting code clear:
* ''G''<sub>''n''</sub> is a [[permutation]] of the numbers 0, ..., 2<sup>''n''</sup> − 1. (Each number appears exactly once in the list.)
* ''G''<sub>''n''</sub> is embedded as the first half of ''G''<sub>''n''+1</sub>.
Line 206 ⟶ 202:
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 ''n''th Gray code is obtained by computing <math>n \oplus \left\lfloor \tfrac{n}{2} \right\rfloor</math>. Prepending a {{mono|0}} bit leaves the order of the code words unchanged, prepending a {{mono|1}} bit reverses the order of the code words. If the bits at position <math>i</math> of codewords are inverted, the order of neighbouring blocks of <math>2^i</math> 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:
▲:{{{mono|000,001,010,011,100,101,110,111}}} → {{{mono|010,011,000,001,110,111,100,101}}} {{pad|2em}}(invert bit 1)
If bit 2 is inverted, blocks of 4 codewords reverse order:
▲:{{{mono|000,001,010,011,100,101,110,111}}} → {{{mono|100,101,110,111,000,001,010,011}}} {{pad|2em}}(invert bit 2)
Thus, performing an [[exclusive or]] on a bit <math>b_i</math> at position <math>i</math> with the bit <math>b_{i+1}</math> at position <math>i+1</math> leaves the order of codewords intact if <math>b_{i+1} = \mathtt{0}</math>, and reverses the order of blocks of <math>2^{i+1}</math> codewords if <math>b_{i+1} = \mathtt{1}</math>. Now, this is exactly the same operation as the reflect-and-prefix method to generate the Gray code.
Line 220 ⟶ 214:
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 <math>g_i</math> is the <math>i</math>th Gray-coded bit (<math>g_0</math> being the most significant bit), and <math>b_i</math> is the <math>i</math>th binary-coded bit (<math>b_0</math> being the most-significant bit), the reverse translation can be given recursively: <math>b_0 = g_0</math>, and <math>b_i=g_i \oplus b_{i-1}</math>. 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 <math>\mathrm{code}_0 = \mathtt{0}</math>, and at step <math>i > 0</math> find the bit position of the least significant {{mono|1}} in the binary representation of <math>i</math> and flip the bit at that position in the previous code <math>\mathrm{code}_{i-1}</math> to get the next code <math>\mathrm{code}_i</math>. The bit positions start 0, 1, 0, 2, 0, 1, 0, 3,
== Converting to and from Gray code ==
Line 266 ⟶ 260:
== Special types of Gray codes ==
In practice, "Gray code" almost always refers to a binary-reflected Gray code (BRGC). However, mathematicians have discovered other kinds of Gray codes. Like BRGCs, each consists of a list of words, where each word differs from the next in only one digit (each word has a [[Hamming distance]] of 1 from the next word).
=== Gray codes with ''n'' bits and of length less than
It is possible to construct binary Gray codes with ''n'' bits with a length of less than {{math|
=== ''n''-ary Gray code <span class="anchor" id="n-ary"></span><span class="anchor" id="ternary"></span><span class="anchor" id="pentary"></span> ===
{| border="0" cellpadding="10" align="right"
Line 351 ⟶ 343:
</syntaxhighlight>
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,<ref name="Guan_1998"/> 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.
Line 357 ⟶ 349:
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 (arithmetic)|carry]] operation.
=== Balanced Gray code ===
Although the binary reflected Gray code is useful in many scenarios, it is not optimal in certain cases because of a lack of "uniformity".<ref name="Bhat-Savage_1996"/> 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 <math>(\delta_k)</math>; 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 <math>\lambda_k = \tfrac{R^n}{n}</math> for all ''k''. Clearly, when <math>R = 2</math>, such codes exist only if ''n'' is a power of 2.<ref>{{cite journal |
▲for all ''k''. Clearly, when <math>R = 2</math>, such codes exist only if ''n'' is a power of 2.<ref>{{cite journal |author=D. G. Wagner, J. West |title=Construction of Uniform Gray Codes |journal=Congressus Numerantium |volume=80 |year=1991 |pages=217–223}}</ref> 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 <math>2\left\lfloor \tfrac{2^n}{2n} \right\rfloor</math> or <math>2\left\lceil \tfrac{2^n}{2n} \right\rceil</math>.<ref name="Bhat-Savage_1996"/> 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.<ref name="Suparta_2005"/>
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:<ref name="Bhat-Savage_1996"/>
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:<ref name="Bhat-Savage_1996"/>
We will now show a construction<ref name="Flahive-Bose_2007"/> and implementation<ref name="Strackx-Piessens_2016"/> 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 <math>G'</math> given an ''n''-digit Gray code ''G'' in such a way that the balanced property is preserved. To do this, we consider partitions of <math>G = g_0, \ldots, g_{2^n-1}</math> into an even number ''L'' of non-empty blocks of the form
where <math>k_1 = 0</math>, <math>k_{L-1} = -2</math>, and <math>k_{L} \equiv -1 \pmod{2^n}</math>). This partition induces an <math>(n+2)</math>-digit Gray code given by
{{block indent|1=<math display="block">\begin{align}
:<math>\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}, </math>▼
▲
\end{align}</math>}}
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 <math>\lambda'_i</math> is
\lambda'_i = \begin{cases}
4 \lambda_i - 2 m_i, & \text{if } 0 \leq i < n \\
Line 414 ⟶ 408:
We can formalize the concept of monotone Gray codes as follows: consider the partition of the hypercube <math>Q_n = (V_n, E_n)</math> into ''levels'' of vertices that have equal weight, i.e.
for <math>0 \leq i \leq n</math>. These levels satisfy <math>|V_n(i)| = \textstyle\binom{n}{i}</math>. Let <math>Q_n(i)</math> be the subgraph of <math>Q_n</math> induced by <math>V_n(i) \cup V_n(i+1)</math>, and let <math>E_n(i)</math> be the edges in <math>Q_n(i)</math>. A monotonic Gray code is then a Hamiltonian path in <math>Q_n</math> such that whenever <math>\delta_1 \in E_n(i)</math> comes before <math>\delta_2 \in E_n(j)</math> in the path, then <math>i \leq j</math>.
Line 420 ⟶ 414:
An elegant construction of monotonic ''n''-digit Gray codes for any ''n'' is based on the idea of recursively building subpaths <math>P_{n,j}</math> of length <math>2 \textstyle\binom{n}{j}</math> having edges in <math>E_n(j)</math>.<ref name="Savage-Winkler_1995"/> We define <math>P_{1,0} = (\mathtt{0}, \mathtt{1})</math>, <math>P_{n,j} = \emptyset</math> whenever <math>j < 0</math> or <math>j \geq n</math>, and
P_{n+1,j} = \mathtt{1}P^{\pi_n}_{n,j-1}, \mathtt{0}P_{n,j}
</math>
Line 426 ⟶ 420:
otherwise. Here, <math>\pi_n</math> is a suitably defined permutation and <math>P^{\pi}</math> refers to the path ''P'' with its coordinates permuted by <math>\pi</math>. These paths give rise to two monotonic ''n''-digit Gray codes <math>G_n^{(1)}</math> and <math>G_n^{(2)}</math> 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
</math>
The choice of <math>\pi_n</math> which ensures that these codes are indeed Gray codes turns out to be <math>\pi_n = E^{-1}\left(\pi_{n-1}^2\right)</math>. The first few values of <math>P_{n,j}</math> are shown in the table below.
{| class="wikitable floatright" style="text-align: center;"
|+ Subpaths in the Savage–Winkler algorithm
Line 456 ⟶ 449:
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 [[coroutine]]s.
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 <math>Q_{2n+1}(n)</math> is [[vertex-transitive graph|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 <math>n \leq 15</math>, and the preceding construction for monotonic codes ensures a Hamiltonian path of length at least 0.839{{px2}}''N'', where ''N'' is the number of vertices in the middle-level subgraph.<ref name="Savage_1997"/>
=== Beckett–Gray code ===
Another type of Gray code, the '''Beckett–Gray code''', is named for Irish playwright [[Samuel Beckett]], who was interested in [[symmetry]]. His play "[[Quad (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.<ref name="Goddyn_1999"/> 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 (computing and electronics)|first in, first out]] [[Queue (data structure)|queue]], so that (of the actors onstage) the actor being dequeued is always the one who was enqueued first.<ref name="Goddyn_1999"/> 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''.<ref name="Knuth_2014"/> According to Sawada and Wong, the search space for ''n'' = 6 can be explored in 15 hours, and more than {{val|9,500}} solutions for the case ''n'' = 7 have been found.<ref name="Sawada-Wong_2007"/>
===
{{snakes_and_coils_in_the_box.svg}}
[[Snake-in-the-box]] codes, or ''snakes'', are the sequences of nodes of [[induced path]]s in an ''n''-dimensional [[hypercube graph]], and coil-in-the-box codes,<ref name="Richards_1971"/> or ''coils'', are the sequences of nodes of induced [[cycle (graph theory)|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;<ref name="Kautz_1958"/> since then, there has been much research on finding the code with the largest possible number of codewords for a given hypercube dimension.
===
Yet another kind of Gray code is the '''single-track Gray code''' (STGC) developed by Norman B. Spedding<ref name="Spedding_1994_1"/><ref name="Spedding_1994_2"/> and refined by Hiltgen, Paterson and Brandestini in
[[File:Animated Graycode.gif|thumb|Animated and color-coded version of the STGC rotor.]]
Line 482 ⟶ 475:
An STGC for ''P'' = 30 and ''n'' = 5 is reproduced here:
|+ Single-track Gray code for 30 positions
! Angle || Code
Line 505 ⟶ 498:
|-
| 60° || {{mono|11000}} || 132° || {{mono|01100}} || 204° || {{mono|00110}} || 276° || {{mono|00011}} || 348° || {{mono|10001}}
|}<!--
But even better would be an actual illustration of the single track, on a rotary encoder, with the 5 pick-up sensors.
This is done – does that mean that the 1s and 0s can go now? They take up a whole lot of visual space.
Line 515 ⟶ 507:
The Gray code nature is useful (compared to [[chain code]]s, also called [[De Bruijn sequence]]s), 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.<ref name="Alciatore-Histand_1999"/>
[[File:9-bit, Single-Track Gray Code.gif|thumb|9-bit,
Since this 30 degree example was added, there has been a lot of interest in examples with higher angular resolution. In 2008, Gary Williams,<ref name="Experts_Exchange_Williams_2008">{{cite web |last1=Williams |first1=Gary |title='single track gray code' sought for encoding 360 degrees with 9 sensors |url=https://www.experts-exchange.com/questions/23594359/'single-track-gray-code'-sought-for-encoding-360-degrees-with-9-sensors.html#a22127642 |website=Experts Exchange|date=25 July 2008 }}</ref>{{ugc|date=January 2025}} based on previous work,<ref name="Etzion-Paterson_1996"/> 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<ref name="Thingiverse_9-Bit_Singletrack_Gray_Code_Rotorary_Encoder">{{cite web |last1=Bauer |first1=Florian |title=9-Bit Absolute Singletrack Gray Code Rotary Encoder |url=https://www.thingiverse.com/thing:4590077 |website=Thingiverse}}</ref> 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
Line 942 ⟶ 933:
| 359° || {{mono||100000000}}
|}
|+ Starting and ending angles for the 20 tracks for a
▲:{|class="wikitable" style="text-align:center; background:#FFFFFF; border-width:0;"
▲|+ 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
|rowspan="21" style="text-align:center; background:#FFFFFF; border-width:0;"|
|-
Line 989 ⟶ 979:
|}
=== Two-dimensional Gray code ===
[[File:16QAM Gray Coded.svg|200px|thumb|right|A Gray-coded constellation diagram for rectangular 16-[[Quadrature amplitude modulation|QAM]]]]
Line 997 ⟶ 987:
Two-dimensional Gray codes also have uses in [[___location identification]]s 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.<ref name="Strang-Dammann-Roeckl-Plass_2009"/>
=== Excess
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.▼
▲If a subsection of a specific codevalue is extracted from that value, for example the last 3 bits of a 4-bit
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.▼
▲Example: The highest 3-bit
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.▼
▲When working with sensors that output multiple,
== Gray isometry ==
Line 1,013 ⟶ 1,004:
There are a number of binary codes similar to Gray codes, including:
* {{anchor|Datex}}Datex codes or Giannini codes (1954), as described by Carl P. Spaulding,<ref name="Spaulding_1954"/><ref name="Spaulding_1965"/><ref name="Wheeler_1969"/><ref name="Dokter-Steinhauer_1973"/><ref name="Dokter-Steinhauer_1975"/><ref name="MIL_1991"/> use a variant of [[#O'Brien II|O'Brien code II]].
* {{anchor|
* {{anchor|Lucal|MRB}}Lucal code (1959)<ref name="Lucal_1959"/><ref name="Sellers-Hsiao-Bearnson_1968"/><ref name="Doran_2007"/> aka modified reflected binary code (MRB)<ref name="Lucal_1959"/><ref name="Sellers-Hsiao-Bearnson_1968"/><ref group="nb" name="NB_Modified"/>
* {{anchor|Gillham}}[[Gillham code]] (1961/1962),<ref name="Wheeler_1969"/><ref name="Wightman_1972"/><ref name="MIL_1991"/><ref name="Phillips_1998"/><ref name="Stewart_2010"/> uses a variant of [[#Datex|Datex]] code and [[#O'Brien II|O'Brien code II]].
Line 1,023 ⟶ 1,013:
The following [[binary-coded decimal]] (BCD) codes are Gray code variants as well:
* {{anchor|Petherick|RAE}}Petherick code (1953),<ref name="Petherick_1953"/><ref name="Petherick-Hopkins_1958"/><ref name="Baumgartner_1963"/><ref name="Charnley-Bidgood-Boardman_1965"/><ref name="Powell_1968"/><ref name="Hoklas_2005_1"/><ref group="nb" name="NB_Petherick_OBrien-II"/> also known as [[Royal Aircraft Establishment]] (RAE) code.<ref name="Hollingdale_1958"/>
* {{anchor|Foss|O'Brien|O'Brien I|Watts|O'Brien II}}O'Brien codes I and II (1955)<ref name="O'Brien_1955"/><ref name="Steinbuch_1962"/><ref name="Steinbuch-Weber-Heinemann_1974"/><ref name="Dokter-Steinhauer_1973"/><ref name="Dokter-Steinhauer_1975"/><ref name="Hoklas_2005_1"/> (An O'Brien type-I code<ref group="nb" name="NB_OBrien-I_Glixon"/> was already described by Frederic A. Foss of [[IBM]]<ref name="Foss_1954_1"/><ref name="Foss_1954_2"/> and used by [[#Varec|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<!-- see Savard_2018 -->.<ref name="Evans_1958"/><ref name="Evans_1960"/><ref name="Evans_1961"/><ref name="Benjamin-Nicholls_1963"/><ref name="Klinkowski_1964"/><ref name="Klinkowski_1966"/><ref name="EDN_1967"/><ref name="Toth-Zentai_1979"/><ref name="Savard_2018"/><ref group="nb" name="NB_Arithmetic_conversion"/><ref group="nb" name="NB_Modified"/> An O'Brien type-II code was already used by [[#Datex|Datex]] in 1954.<ref group="nb" name="NB_Petherick_OBrien-II"/>)
Line 1,037 ⟶ 1,026:
| colspan="18"|
|-
| rowspan="4"| {{anchor|Gray BCD}}'''Gray BCD''' || style="background:lightgray"|'''4''' || {{mono|0}} || {{mono|0}} || {{mono|0}} || {{mono|0}} || {{mono|0}} || {{mono|0}} || {{mono|0}} || {{mono|0}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || rowspan="4"|
|-
| style="background:lightgray"|'''3''' || {{mono|0}} || {{mono|0}} || {{mono|0}} || {{mono|0}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}}
Line 1,047 ⟶ 1,036:
| colspan="18"|
|-
| rowspan="4"| {{anchor|Paul}}'''Paul''' || style="background:lightgray"|'''4''' || style="background:#0FF"|{{mono|1}} || {{mono|0}} || {{mono|0}} || {{mono|0}} || {{mono|0}} || {{mono|0}} || {{mono|0}} || {{mono|0}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || rowspan="4"|
|-
| style="background:lightgray"|'''3''' || {{mono|0}} || {{mono|0}} || {{mono|0}} || {{mono|0}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}}
Line 1,057 ⟶ 1,046:
| colspan="18"|
|-
| rowspan="4"|'''Glixon''' || style="background:lightgray"|'''4''' || {{mono|0}} || {{mono|0}} || {{mono|0}} || {{mono|0}} || {{mono|0}} || {{mono|0}} || {{mono|0}} || {{mono|0}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || rowspan="4"|
|-
| style="background:lightgray"|'''3''' || {{mono|0}} || {{mono|0}} || {{mono|0}} || {{mono|0}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || {{mono|0}}
Line 1,067 ⟶ 1,056:
| colspan="18"|
|-
| rowspan="4"|'''Tompkins I''' || style="background:lightgray"|'''4''' || {{mono|0}} || {{mono|0}} || {{mono|0}} || {{mono|0}} || {{mono|0}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || rowspan="4"|
|-
| style="background:lightgray"|'''3''' || {{mono|0}} || {{mono|0}} || {{mono|0}} || {{mono|0}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || {{mono|0}}
Line 1,077 ⟶ 1,066:
| colspan="18"|
|-
| rowspan="4"|'''O'Brien I''' '''(Watts)''' || style="background:lightgray"|'''4''' || {{mono|0}} || {{mono|0}} || {{mono|0}} || {{mono|0}} || {{mono|0}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || rowspan="4"|
|-
| style="background:lightgray"|'''3''' || {{mono|0}} || {{mono|0}} || {{mono|0}} || {{mono|0}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || {{mono|0}} || {{mono|0}} || {{mono|0}} || {{mono|0}}
Line 1,087 ⟶ 1,076:
| colspan="18"|
|-
| rowspan="4"|'''Petherick''' '''(RAE)''' || style="background:lightgray"|'''4''' || {{mono|0}} || {{mono|0}} || {{mono|0}} || {{mono|0}} || {{mono|0}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || rowspan="4"|
|-
| style="background:lightgray"|'''3''' || style="background:#0FF"|{{mono|1}} || {{mono|0}} || {{mono|0}} || {{mono|0}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || {{mono|0}} || {{mono|0}} || {{mono|0}} || style="background:#0FF"|{{mono|1}}
Line 1,097 ⟶ 1,086:
| colspan="18"|
|-
| rowspan="4"|'''O'Brien II''' || style="background:lightgray"|'''4''' || {{mono|0}} || {{mono|0}} || {{mono|0}} || {{mono|0}} || {{mono|0}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || rowspan="4"|
|-
| style="background:lightgray"|'''3''' || {{mono|0}} || {{mono|0}} || {{mono|0}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || {{mono|0}} || {{mono|0}} || {{mono|0}}
Line 1,107 ⟶ 1,096:
| colspan="18"|
|-
| rowspan="4"|{{anchor|Susskind}}'''Susskind<!-- I-->''' || style="background:lightgray"|'''4''' || {{mono|0}} || {{mono|0}} || {{mono|0}} || {{mono|0}} || {{mono|0}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || rowspan="4"|
|-
| style="background:lightgray"|'''3''' || {{mono|0}} || {{mono|0}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || {{mono|0}} || {{mono|0}}
Line 1,117 ⟶ 1,106:
| colspan="18"|
|-
| rowspan="4"|{{anchor|Klar}}'''Klar''' || style="background:lightgray"|'''4''' || {{mono|0}} || {{mono|0}} || {{mono|0}} || {{mono|0}} || {{mono|0}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || rowspan="4"|
|-
| style="background:lightgray"|'''3''' || {{mono|0}} || {{mono|0}} || {{mono|0}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || {{mono|0}} || {{mono|0}} || {{mono|0}}
Line 1,127 ⟶ 1,116:
| colspan="18"|
|-
| rowspan="4"|'''Tompkins II''' || style="background:lightgray"|'''4''' || {{mono|0}} || {{mono|0}} || {{mono|0}} || {{mono|0}} || {{mono|0}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || rowspan="4"|
|-
| style="background:lightgray"|'''3''' || {{mono|0}} || {{mono|0}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || {{mono|0}} || {{mono|0}} || {{mono|0}}
Line 1,137 ⟶ 1,126:
| colspan="18"|
|-
| rowspan="4"|{{nowrap|'''Excess-3 Gray'''}} || style="background:lightgray"|'''4''' || {{mono|0}} || {{mono|0}} || {{mono|0}} || {{mono|0}} || {{mono|0}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || rowspan="4"|
|-
| style="background:lightgray"|'''3''' || {{mono|0}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || style="background:#0FF"|{{mono|1}} || {{mono|0}}
Line 1,146 ⟶ 1,135:
|}
== See also ==
* [[Linear-feedback shift register]]
Line 1,156 ⟶ 1,145:
* [[Hilbert curve]]
== Notes ==
{{reflist|group="nb"|refs=
Line 1,171 ⟶ 1,160:
}}
== References ==
{{reflist|refs=
Line 1,203 ⟶ 1,192:
<ref name="Richards_1971">{{cite book |author-first=Richard Kohler |author-last=Richards |title=Digital Design |chapter=Snake-in-the-Box Codes |publisher=[[Wiley-Interscience]], [[John Wiley & Sons, Inc.]] |___location=Ames, Iowa, USA |publication-place=New York, USA |date=January 1971 |isbn=0-471-71945-5 |lccn=73-147235 |pages=206–207}} (12+577+1 pages)</ref>
<ref name="Sellers-Hsiao-Bearnson_1968">{{cite book |author-first1=Frederick F. |author-last1=Sellers, Jr.<!-- to be sync'ed with corresponding citeref --> |author-first2=Mu-Yue |author-last2=Hsiao |author-first3=Leroy W. |author-last3=Bearnson |title=Error Detecting Logic for Digital Computers |publisher=[[McGraw-Hill Book Company]] |___location=New York, USA |edition=1st |oclc=439460 |lccn=68-16491 |pages=152–164 |date=November 1968}}</ref>
<ref name="Lucal_1959">{{cite journal |author-first=Harold M. |author-last=Lucal |title=Arithmetic Operations for Digital Computers Using a Modified Reflected Binary |journal=[[IRE Transactions on Electronic Computers]] |volume=EC-8 |number=4 |pages=449–458 |date=December 1959 |issn=0367-9950 |doi=10.1109/TEC.1959.5222057 |s2cid=206673385
<ref name="Spaulding_1954">{{cite web |title=Digital coding and translating system |author-first=Carl P. |author-last=Spaulding |publisher=Datex Corporation |___location=Monrovia, California, USA |year=1965a<!-- necessary for proper citeref linking --> |date=1965-01-12<!-- gdate --> |orig-date=1954-03-09<!-- fdate --> |id={{US patent|3165731A}}. Serial No. 415058 |url=https://patentimages.storage.googleapis.com/7f/1d/09/6a9b1fa3e67cb8/US3165731.pdf |access-date=2018-01-21 |url-status=live |archive-url=https://web.archive.org/web/20200805101618/https://patentimages.storage.googleapis.com/7f/1d/09/6a9b1fa3e67cb8/US3165731.pdf |archive-date=2020-08-05}} (28 pages)</ref>
<ref name="Spaulding_1965">{{cite book |title=How to Use Shaft Encoders |author-first=Carl P. |author-last=Spaulding |year=1965b<!-- necessary for proper citeref linking --> |date=1965-07-12 |publisher=Datex Corporation<!-- Datex Div, of Conrac Corp. / a subsidiary of Giannini Control Corp. --> |___location=Monrovia, California, USA}} (85 pages)</ref>
<ref name="Foss_1954_1">{{cite web |title=Control Systems |author-first=Frederic A. |author-last=Foss |date=1960-12-27<!-- gdate --> |orig-date=1954-12-17<!-- fdate --> |id={{US patent|2966670A}}. Serial No. 475945 |publisher=[[International Business Machines Corp]] |pages=Fig. 7, Fig. 8, Fig. 11 |no-pp=yes |url=https://patentimages.storage.googleapis.com/3d/a8/16/1dc616c432ca95/US2966670.pdf |access-date=2020-08-05 |url-status=live |archive-url=https://web.archive.org/web/20200621145238/https://patentimages.storage.googleapis.com/3d/a8/16/1dc616c432ca95/US2966670.pdf |archive-date=2020-06-21}} (14 pages) (NB. The author called his code 2*-4-2-1 (+9-±7-±3-±1) reflected<!-- -coded --> decimal code.)</ref>
<ref name="Foss_1954_2">{{cite journal |title=The Use of a Reflected Code in Digital Control Systems |author-first=Frederic A. |author-last=Foss |date=December 1954 |journal=[[IRE Transactions on Electronic Computers]] |volume=EC-3 |issue=4 |issn=2168-1740 |doi=10.1109/IREPGELC.1954.6499244 |pages=1–6}} (6 pages)</ref>
<ref name="O'Brien_1955">{{cite journal |author-first=Joseph A. |author-last=O'Brien |title=Cyclic Decimal Codes for Analogue to Digital Converters |journal=[[Transactions of the American Institute of Electrical Engineers, Part I: Communication and Electronics]] |___location=Bell Telephone Laboratories, Whippany, New Jersey, USA |volume=75 |issue=2 |date=May 1956 |orig-date=1955-11-15, 1955-06-23 |issn=0097-2452 |doi=10.1109/TCE.1956.6372498 |id=Paper 56-21 |s2cid=51657314 |pages=120–122 |url=https://pdfslide.net/documents/cyclic-decimal-codes-for-analogue-to-digital-converters.html |access-date=2020-05-18 |archive-date=2020-05-18 |archive-url=https://web.archive.org/web/20200518075301/https://pdfslide.net/documents/cyclic-decimal-codes-for-analogue-to-digital-converters.html |url-status=dead }} (3 pages) (NB. This paper was prepared for presentation at the AIEE Winter General Meeting, New York, USA, 1956-01-30 to 1956-02-03.)</ref>
<ref name="Tompkins_1956">{{cite journal |author-first=Howard E. |author-last=Tompkins |title=Unit-Distance Binary-Decimal Codes for Two-Track Commutation |date=September 1956 |orig-date=1956-07-16 |journal=[[IRE Transactions on Electronic Computers]] |issn=0367-9950 |volume=EC-5 |issue=3 |doi=10.1109/TEC.1956.5219934 |series=Correspondence |___location=[[Moore School of Electrical Engineering]], [[University of Pennsylvania]], Philadelphia, Pennsylvania, USA |page=139 |url=https://dokumen.tips/documents/unit-distance-binary-decimal-codes-for-two-track-commutation.html |access-date=2020-05-18 |archive-date=2020-05-18 |archive-url=https://web.archive.org/web/20200518083051/https://dokumen.tips/documents/unit-distance-binary-decimal-codes-for-two-track-commutation.html |url-status=dead }} (1 page)</ref>
<ref name="Glixon_1957">{{cite journal |date=March 1957 |title=Can You Take Advantage of the Cyclic Binary-Decimal Code? |author-first=Harry Robert |author-last=Glixon |journal=[[Control Engineering (magazine)|Control Engineering]] |issn=0010-8049 |publisher=[[Technical Publishing Company]], a division of Dun-Donnelley Publishing Corporation, [[Dun & Bradstreet Corp.]] |volume=4 |number=3 |pages=<!-- 3, -->87–91 |url=https://books.google.com/books?id=-_5IAQAAIAAJ}}<!-- https://web.archive.org/web/20180115014809/https://donmooreswartales.com/2010/05/12/harry-glixon/ https://books.google.com/books?id=-_5IAQAAIAAJ&q=cyclic+binary+code --> (5 pages)</ref>
<ref name="Steinbuch_1962">{{cite book |title=Taschenbuch der Nachrichtenverarbeitung |language=de |editor-first=Karl W. |editor-last=Steinbuch |editor-link=Karl W. Steinbuch |date=1962 |edition=1 |publisher=[[Springer-Verlag OHG]] |___location=Karlsruhe, Germany |publication-place=Berlin / Göttingen / New York |lccn=62-14511 |pages=71–74, 97, 761–764, 770, 1080–1081}}</ref>
<ref name="Steinbuch-Weber-Heinemann_1974">{{cite book |title=Taschenbuch der Informatik – Band II – Struktur und Programmierung von EDV-Systemen |language=de |editor-first1=Karl W. |editor-last1=Steinbuch |editor-link1=Karl W. Steinbuch |editor-first2=Wolfgang |editor-last2=Weber <!-- |editor-link2=:de:Wolfgang Weber (Ingenieur)? --> |editor-first3=Traute |editor-last3=Heinemann |date=1974 |orig-date=1967 |edition=3 |volume=2 |series=Taschenbuch der Nachrichtenverarbeitung |publisher=[[Springer Verlag]] |___location=Berlin, Germany |isbn=3-540-06241-6 |lccn=73-80607 |pages=98–100}}</ref>
<ref name="Dokter-Steinhauer_1973">{{cite book |title=Digital Electronics |author-first1=Folkert |author-last1=Dokter |author-first2=Jürgen |author-last2=Steinhauer |chapter=2.4. Coding numbers in the binary system |date=1973-06-18 |series=Philips Technical Library (PTL) / Macmillan Education |publisher=[[The Macmillan Press Ltd.]] / [[N. V. Philips' Gloeilampenfabrieken]] |edition=Reprint of 1st English |___location=Eindhoven, Netherlands |sbn=333-13360-9 |isbn=978-1-349-01419-4 |doi=10.1007/978-1-349-01417-0 |pages=32, 39, 50–53
<ref name="Dokter-Steinhauer_1975">{{cite book |author-first1=Folkert |author-last1=Dokter |author-first2=Jürgen |author-last2=Steinhauer |title=Digitale Elektronik in der Meßtechnik und Datenverarbeitung: Theoretische Grundlagen und Schaltungstechnik |chapter=2.4.4.6. Einschrittige Kodes |language=de |series=Philips Fachbücher |publisher=[[Deutsche Philips GmbH]] |publication-place=Hamburg, Germany |volume=I |date=1975 |orig-date=1969 |edition=improved and extended 5th |isbn=3-87145-272-6 |pages=41, 48, 51, 58, 60–61}} (xii+327+3 pages)</ref>
<ref name="Petherick_1953">{{cite book |author-first=Edward John |author-last=Petherick |title=A Cyclic Progressive Binary-coded-decimal System of Representing Numbers |date=October 1953 |type=Technical Note MS15 |publisher=[[Royal Aircraft Establishment]] (RAE) |___location=Farnborough, UK}} (4 pages) (NB. Sometimes referred to as ''A Cyclic-Coded Binary-Coded-Decimal System of Representing Numbers''.)</ref>
<ref name="Petherick-Hopkins_1958">{{cite book |author-first1=Edward John |author-last1=Petherick |author-first2=A. J. |author-last2=Hopkins |title=Some Recently Developed Digital Devices for Encoding the Rotations of Shafts |date=1958 |type=Technical Note MS21 |publisher=[[Royal Aircraft Establishment]] (RAE) |___location=Farnborough, UK}}</ref>
<ref name="Baumgartner_1963">{{cite periodical |title=Digitizer als Analog-Digital-Wandler in der Steuer-, Meß- und Regeltechnik |periodical=Technische Mitteilungen |series=Relais, elektronische Geräte, Steuerungen |language=de |date=May 1963 |issue=13 |publisher=Franz Baumgartner (FraBa) |___location=Cologne-Niehl, Germany |pages=1–2 |url=https://www.posital.com/media/posital_media/documents/TechnischeMitteilung_May1963.pdf |access-date=2020-05-21 |archive-url=https://web.archive.org/web/20200521211656/https://www.posital.com/media/posital_media/documents/TechnischeMitteilung_May1963.pdf |archive-date=2020-05-21 |quote-pages=1–2 |quote=[…] Die Firma Harrison Reproduction Equipment, Farnborough/England […] hat in jahrelanger Entwicklung in Zusammenarbeit mit der Britischen Luftwaffe und britischen Industriebetrieben den mechanischen Digitizer […] zu einer technischen Reife gebracht, die fast allen Anforderungen […] genügt. […] Um bei der dezimalen Entschlüsselung des verwendeten Binärcodes zu eindeutigen und bei der Übergabe von einer Dezimalstelle zur anderen in der Reihenfolge immer richtigen Ergebnissen zu kommen, wurde ein spezieller Code entwickelt, der jede Möglichkeit einer Fehlaussage durch sein Prinzip ausschließt und der außerdem durch seinen Aufbau eine relativ einfache Entschlüsselung erlaubt. Der Code basiert auf dem [[#Petherick|Petherick-Code]]. […]}} (4 pages)</ref>
<ref name="Charnley-Bidgood-Boardman_1965">{{cite journal |title=The Design of a Pneumatic Position Encoder |author-first1=C. J. |author-last1=Charnley |author-first2=R. E. |author-last2=Bidgood |author-first3=G. E. T. |author-last3=Boardman |journal=IFAC Proceedings Volumes |publisher=The College of Aeronautics, Cranfield, Bedford, England |volume=2 |issue=3 |date=October 1965 |pages=75–88 |id=Chapter 1.5. |doi=10.1016/S1474-6670(17)68955-9
<ref name="Wheeler_1969">{{cite book |title=Analog to digital encoder |author-first=Edwin L. |author-last=Wheeler |publisher=Conrac Corporation |___location=New York, USA |date=1969-12-30<!-- gdate --> |orig-date=1968-04-05<!-- fdate --> |id={{US patent|3487460A}}. Serial No. 719026 (397812<!-- 1964-09-21 -->) |url=https://patentimages.storage.googleapis.com/f0/c0/60/9c3231f7e8ed44/US3487460.pdf |access-date=2018-01-21 |url-status=live |archive-url=https://web.archive.org/web/20200805102804/https://patentimages.storage.googleapis.com/f0/c0/60/9c3231f7e8ed44/US3487460.pdf |archive-date=2020-08-05 |quote-page=5<!-- of text, p. 8 in total -->, left column 9, rows 15–22 |quote=[…] The [[MOA-Gillham code|MOA-GILLHAM code]] is essentially the combination of the Gray code discussed thereinabove and the well known [[#Datex|Datex code]]; the Datex code is disclosed in U.S. Patent {{citeref|Spaulding|1965a|3,165,731|style=plain}}. The arrangement is such that the Datex code defines the bits for the units count of the encoder and the Gray code defines the bits for each of the higher order decades, the tens, hundreds, etc. […]}} (11 pages)</ref>
<ref name="Bishup-Repeta-Giarrizzo_1963">{{cite web |title=Telemetering and supervisory control system having normally continuous telemetering signals |id=US3397386A |author-first1=Bernard W. |author-last1=Bishup |author-first2=Anthony A. |author-last2=Repeta |author-first3=Frank C. |author-last3=Giarrizzo |publisher=[[Leeds & Northrup|Leeds and Northrup Co.]] |date=1968-08-13 |orig-date=1963-04-03 |url=https://patents.google.com/patent/US3397386A/en}} [https://patentimages.storage.googleapis.com/c8/f3/cc/936fef75655a2c/US3397386.pdf]</ref>
<ref name="Savage_1997">{{cite journal |author-first=Carla Diane |author-last=Savage |author-link=Carla Diane Savage |title=Long cycles in the middle two levels of the Boolean lattice |journal=[[Ars Combinatoria (journal)|Ars Combinatoria]] |issn=0381-7032 |volume=35 |issue=A |date=1997-01-16 |___location=North Carolina State University, Raleigh, North Carolina, USA |s2cid=15975960 |citeseerx=10.1.1.39.2249 |pages=97–108 |url=http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=DACA73A3D791549CE05443B7948527EC?doi=10.1.1.39.2249&rep=rep1&type=pdf |access-date=2020-05-13 |url-status=live |archive-url=https://web.archive.org/web/20200513191647/http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=DACA73A3D791549CE05443B7948527EC?doi=10.1.1.39.2249&rep=rep1&type=pdf |archive-date=2020-05-13}} (15 pages)</ref>
<ref name="Phillips_1998">{{cite web |title=Altitude – MODEC ASCII |author-first=Darryl |author-last=Phillips |date=2012-07-26 |orig-date=1998 |publisher=AirSport Avionics |url=http://www.airsport-corp.com/modecascii.txt |url-status=usurped |archive-url=https://web.archive.org/web/20120726003224/http://www.airsport-corp.com/modecascii.txt |archive-date=2012-07-26}}</ref>
<ref name="Stewart_2010">{{cite web |title=Aviation Gray Code: Gillham Code Explained |date=2010-12-03 |author-first=K. |author-last=Stewart |publisher=Custom Computer Services (CCS) |url=
<ref name="Leslie-Russell_1964">{{cite book |title=A cyclic progressive decimal code for simple translation to decimal and analogue outputs |author-first1=William "Bill" H. P. |author-last1=Leslie |author-first2=A. |author-last2=Russell |publisher=[[National Engineering Laboratory]] |___location=East Kilbride, Glasgow, UK |date=1964 |type=Report |id=NEL Report 129}} (17 pages)</ref>
<ref name="Russell_1964">{{cite journal |title=Some Binary Codes and a Novel Five-Channel Code |author-first=A. |author-last=Russell |date=August 1964 |journal=Control (Systems, Instrumentation, Data Processing, Automation, Management, incorporating Automation Progress)<!-- "Control" (London) is a predecessor of "Control and Instrumentation" (C&I), ISSN 0010-8022, formed in April 1969 by merger with "Measurement and Instrument Review" (M&I). --> |volume=8 |number=74 |series=Special Features |publisher=Morgan-Grampain (Publishers) Limited |publication-place=London, UK |pages=399–404 |url=https://books.google.com/books?id=jf4eAAAAMAAJ |access-date=2020-06-22}} (6 pages)</ref>
Line 1,236 ⟶ 1,225:
<ref name="Klinkowski_1964">{{cite web |title=Electronic Diode Matrix Decoder Circuits |author-first=James J. |author-last=Klinkowski |id={{US patent|3309695A}}. Serial No. 353845 |publisher=[[Burroughs Corporation]] |___location=Detroit, Michigan, USA |date=1967-03-14 |orig-date=1964-03-23 |url=https://patentimages.storage.googleapis.com/71/6a/f4/044b43b93097e7/US3309695.pdf |access-date=2020-05-23 |url-status=live |archive-url=https://web.archive.org/web/20200523144819/https://patentimages.storage.googleapis.com/71/6a/f4/044b43b93097e7/US3309695.pdf |archive-date=2020-05-23}} (5 pages) [https://web.archive.org/web/20200805103732/https://patentimages.storage.googleapis.com/97/33/74/aec52610026e59/USRE26780.pdf<!-- https://patentimages.storage.googleapis.com/97/33/74/aec52610026e59/USRE26780.pdf -->]</ref>
<ref name="Klinkowski_1966">{{cite web |title=Binary-coded decimal signal converter |author-first=James J. |author-last=Klinkowski |id={{US patent|3504363A}}. Serial No. 603926 |publisher=[[Burroughs Corporation]] |___location=Detroit, Michigan, USA |date=1970-03-31 |orig-date=1966-12-22 |url=https://patentimages.storage.googleapis.com/65/d6/45/f7837c143fa3da/US3504363.pdf |access-date=2020-05-23 |url-status=live |archive-url=https://web.archive.org/web/20200523145655/https://patentimages.storage.googleapis.com/65/d6/45/f7837c143fa3da/US3504363.pdf |archive-date=2020-05-23}} (7 pages)</ref>
<ref name="EDN_1967">{{cite journal |title=(([title unknown])) |journal=[[Electrical Design News]] |issn=0012-7515 |publisher=[[Rogers Publishing Company]] |date=1967 |volume=12 |pages=<!-- 44, 448? -->}} [https://books.google.com/books?id=MThAAQAAIAAJ&q=%22Watts+code%22+%22Excess-3+Gray+Code%22][https://books.google.com/books?id=MThAAQAAIAAJ&q=%22Watts+code%22+%22Excess-3+Gray+Code%22]</ref>
<ref name="Toth-Zentai_1979">{{cite journal |title=Some Problems Of Angular Rotational Digital Converters |author-first=Györgyi |author-last=Tóth-Zentai |volume=23 |number=3–4 |journal=Periodica Polytechnica Electrical Engineering |date=1979-10-05 |pages=265–270 [266] |___location=Department of Electronics Technology, Technical University, Budapest, Hungary |url=https://pp.bme.hu/ee/article/view/4838 |access-date=2020-05-23}} [https://pp.bme.hu/ee/article/download/4838/3943/] (6 pages) (NB. Shows a 6-digit Watts code.<!-- also mentions a scheme named V-logic -->)</ref>
<ref name="Knuth_2014">{{cite book |author-last=Knuth |author-first=Donald Ervin |author-link=Donald Ervin Knuth |chapter=Enumeration and Backtracking / Generating all ''n''-tuples |title=The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1 |volume=4A |edition=1 |title-link=The Art of Computer Programming |date=2014-09-12 |publisher=[[Addison-Wesley Professional]] |isbn=978-0-13348885-2 |pages=442–443<!-- list of pages incomplete --> |chapter-url=https://books.google.com/books?id=IkuEBAAAQBAJ}} (912 pages)</ref>
<ref name="Heath_1961">{{cite journal |title=Pioneers Of Binary Coding |author-first=F.<!-- Fred? --> G. |author-last=Heath |journal=[[Journal of the Institution of Electrical Engineers]] |publisher=[[Institution of Engineering and Technology]] (IET) |___location=[[Manchester College of Science and Technology]], Faculty of Technology of the [[University of Manchester]], Manchester, UK |volume=7 |issue=81 |date=September 1961 |doi=10.1049/jiee-3.1961.0300 |pages=539–541 |url=https://ieeexplore.ieee.org/document/5324416 |archive-url=https://web.archive.org/web/20200328084237/https://ieeexplore.ieee.org/document/5324416/ |url-status=dead |archive-date=28 March 2020 |access-date=2020-06-22}} (3 pages)</ref>
<ref name="Cattermole_1969">{{cite book |author-first=Kenneth W. |author-last=Cattermole |title=Principles of pulse code modulation |edition=1 |publisher=[[Iliffe Books Ltd.]] / [[American Elsevier Publishing Company, Inc.]] |date=1969 |publication-place=London, UK / New York, USA |___location=Harlow, Essex, UK |sbn=444-19747-8 |isbn=978-0-444-19747-4 |lccn=78-80432 |pages=245, 434 |quote-page=245 |quote=[…] <!-- This was devised by Elisha Gray at some time before 1878, for telegraph usage; in recent times it has been used in electron-beam coding tubes […], and is generally applicable to parallel coders in which all the digits are produced simultaneously. […] -->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 {{citeref|Heath|1961|Heath|style=plain}} testifies to his usage of it. Many people take it as referring to [[Frank Gray (researcher)|Frank Gray]] of [[Bell Telephone Laboratories]], who in 1947 first proposed its use in [[coding tube]]s: his patent is listed in the bibliography. <!-- This is a particular interesting example of [[multiple invention]]. Two British engineers, C. W. Earp and M. F. Wintle, rediscovered it independently within a few month of F. Gray, some seventy years after E. Gray. -->[…]}} (2+448+2 pages)<!-- (NB. At least Charles William Earp's and Malcolm Frank Wintle's patent US2568724 describes a different code used for PCM.) --></ref>
<ref name="Edwards_2004">{{cite book |title=Cogwheels of the Mind: The Story of Venn Diagrams |author-first=Anthony William Fairbank |author-last=Edwards |author-link=Anthony William Fairbank Edwards |publisher=[[Johns Hopkins University Press]] |date=2004 |isbn=0-8018-7434-3 |___location=Baltimore, Maryland, USA |pages=48, 50 |url=https://books.google.com/books?id=7_0Thy4V3JIC&pg=PA65}}</ref>
<ref name="Goodall_1951">{{cite journal |author-first=William M. |author-last=Goodall |title=Television by Pulse Code Modulation |journal=[[Bell System Technical Journal]] |volume=30 |issue=1 |pages=33–49 |date=January 1951 |doi=10.1002/j.1538-7305.1951.tb01365.x}} (NB. Presented orally before the I.R.E. National Convention, New York City, March 1949.)</ref>
<ref name="Bhat-Savage_1996">{{cite journal |author-first1=Girish S. |author-last1=Bhat |author-first2=Carla Diane |author-last2=Savage |author-link2=Carla Diane Savage |title=Balanced Gray Codes |journal=[[Electronic Journal of Combinatorics]] |date=1996 |volume=3 |url=https://www.combinatorics.org/ojs/index.php/eljc/article/view/v3i1r25/ |issue=1 |article-number=R25 |doi=10.37236/1249 |doi-access=free}}</ref>
<ref name="Donohue_2003">{{cite web |author-first=Ryan |author-last=Donohue |title=Synchronization in Digital Logic Circuits |date=2003 |url=
<ref name="Mehta-Owens-Irwin_1996">{{cite book |author-last1=Mehta |author-first1=Huzefa |author-last2=Owens |author-first2=Robert Michael |author-last3=Irwin |author-first3=Mary Jane "Janie" |chapter=Some issues in gray code addressing |title=Proceedings of the Sixth Great Lakes Symposium on VLSI |date=1996-03-22 |issn=1066-1395 |doi=10.1109/GLSV.1996.
<ref name="Su-Tsui-Despain_1994">{{cite report |title=Low Power Architecture Design and Compilation Techniques for High-Performance Processors |author-first1=Ching-Long |author-last1=Su |author-first2=Chi-Ying |author-last2=Tsui |author-first3=Alvin M. |author-last3=Despain |date=1994 |publisher=Advanced Computer Architecture Laboratory |id=ACAL-TR-94-01 |url=http://www.scarpaz.com/2100-papers/Power%20Estimation/su94-low%20power%20architecture%20and%20compilation.pdf |access-date=2020-12-17 |url-status=live |archive-url=https://web.archive.org/web/20200726170626/http://www.scarpaz.com/2100-papers/Power%20Estimation/su94-low%20power%20architecture%20and%20compilation.pdf |archive-date=2020-07-26}}</ref>
<ref name="Guo-Parameswaran_2010">{{cite journal |author-first1=Hui |author-last1=Guo |author-first2=Sri |author-last2=Parameswaran |doi=10.1016/j.sysarc.2010.03.003 |volume=56 |issue=4–6 |date=April–June 2010 |title=Shifted Gray encoding to reduce instruction memory address bus switching for low-power embedded systems |journal=Journal of Systems Architecture |pages=180–190}}</ref>
<ref name="Dietz_2002">{{cite web |author-first=Henry Gordon "Hank" |author-last=Dietz |title=The Aggregate Magic Algorithms: Gray Code Conversion |work=The Aggregate |publisher=Electrical and Computer Engineering Department, College of Engineering, [[University of Kentucky]] |date=2002 |url=
<ref name="Guan_1998">{{cite journal |title=Generalized Gray Codes with Applications |author-last=Guan |author-first=Dah-Jyh |journal=Proceedings of the National Scientific Council, Republic of China, Part A |volume=22 |date=1998 |pages=841–848 |citeseerx=10.1.1.119.1344}}</ref>
<ref name="Suparta_2005">{{cite journal |author-first=I. Nengah |author-last=Suparta |title=A simple proof for the existence of exponentially balanced Gray codes |journal=[[Electronic Journal of Combinatorics]] |date=2005 |volume=12 |article-number=N19 |doi-access=free |doi=10.37236/1986}}</ref>
<ref name="Flahive-Bose_2007">{{cite journal |author-first1=Mary Elizabeth |author-last1=Flahive |author-link1=Mary Elizabeth Flahive |author-first2=Bella |author-last2=Bose |title=Balancing cyclic ''R''-ary Gray codes |journal=[[Electronic Journal of Combinatorics]] |date=2007 |volume=14 |article-number=R31 |doi-access=free |doi=10.37236/949}}</ref>
<ref name="Strackx-Piessens_2016">{{cite journal |author-first1=Raoul |author-last1=Strackx |author-first2=Frank |author-last2=Piessens |title=Ariadne: A Minimal Approach to State Continuity |journal=Usenix Security |date=2016 |volume=25 |url=https://distrinet.cs.kuleuven.be/software/sce/ariadne.html}}</ref>
<ref name="Savage-Winkler_1995">{{cite journal |author-first1=Carla Diane |author-last1=Savage |author-link1=Carla Diane Savage |author-first2=Peter |author-last2=Winkler |author-link2=Peter Winkler |title=Monotone Gray codes and the middle levels problem |journal=[[Journal of Combinatorial Theory]] | series=Series A |date=1995 |volume=70 |issn=0097-3165 |pages=230–248 |issue=2 |doi=10.1016/0097-3165(95)90091-8|doi-access=free}}</ref>
<ref name="Goddyn_1999">{{cite web |title=MATH 343 Applied Discrete Math Supplementary Materials |author-last=Goddyn |author-first=Luis |date=1999 |publisher=Department of Mathematics, [[Simon Fraser University]] |url=
<ref name="Sawada-Wong_2007">{{cite journal |author-first1=Joseph "Joe" |author-last1=Sawada |author-first2=Dennis Chi-Him |author-last2=Wong |title=A Fast Algorithm to generate Beckett–Gray codes |journal=Electronic Notes in Discrete Mathematics |volume=29 |pages=571–577 |date=2007 |doi=10.1016/j.endm.2007.07.091}}</ref>
<ref name="Spedding_1994_1">{{cite patent |inventor-last=Spedding |inventor-first=Norman Bruce<!-- Industrial Research Limited --> |pubdate=1994-10-28 |title=A position encoder |country=NZ |number=264738}}{{failed verification|date=July 2015}}</ref>
<ref name="Spedding_1994_2">{{cite web <!-- descriptive title: -->|title=The following is a copy of the provisional patent filed on behalf of Industrial Research Limited on 1994-10-28 – NZ Patent 264738 |author-first=Norman Bruce |author-last=Spedding |publisher=Industrial Research Limited |date=1994-10-28 |id=NZ Patent 264738 |url=http://www.winzurf.co.nz/Single_Track_Grey_Code_Patent/Single_track_Grey_code_encoder_patent.pdf |access-date=2018-01-14 |url-status=live |archive-url=https://web.archive.org/web/20171029205005/http://www.winzurf.co.nz/Single_Track_Grey_Code_Patent/Single_track_Grey_code_encoder_patent.pdf |archive-date=2017-10-29}}</ref>
<ref name="Hiltgen-Paterson-Brandestini_1996">{{cite journal |title=Single-Track Gray Codes |author-last1=Hiltgen |author-first1=Alain P. |author-first2=Kenneth G. |author-last2=Paterson |author-first3=Marco |author-last3=Brandestini |journal=[[IEEE Transactions on Information Theory]] |volume=42 |issue=5 |date=September 1996 |pages=1555–1561 |doi=10.1109/18.532900 |zbl=857.94007
<ref name="Hiltgen-Paterson_2001">{{cite journal |title=Single-Track Circuit Codes |author-last1=Hiltgen |author-first1=Alain P. |author-first2=Kenneth G. |author-last2=Paterson |journal=[[IEEE Transactions on Information Theory]] |volume=47 |issue=6 |date=September 2001 |pages=2587–2595 |doi=10.1109/18.945274 |bibcode=2001ITIT...47.2587H |citeseerx=10.1.1.10.8218 |url=http://www.hpl.hp.com/techreports/2000/HPL-2000-81.pdf |access-date=2018-01-15 |url-status=live |archive-url=https://web.archive.org/web/20180115013155/http://www.hpl.hp.com/techreports/2000/HPL-2000-81.pdf |archive-date=2018-01-15}}</ref>
<ref name="Etzion-Schwartz_1999">{{cite journal |title=The Structure of Single-Track Gray Codes |author-last1=Etzion |author-first1=Tuvi |author-first2=Moshe |author-last2=Schwartz |journal=[[IEEE Transactions on Information Theory]] |volume=IT-45 |issue=7 |date=November 1999 |orig-date=1998-05-17 |pages=2383–2396 |doi=10.1109/18.796379 |citeseerx=10.1.1.14.8333 |url=http://etzion.net.technion.ac.il/files/2016/02/P54.pdf |access-date=2018-01-15 |url-status=live |archive-url=https://web.archive.org/web/20180115022531/http://etzion.net.technion.ac.il/files/2016/02/P54.pdf |archive-date=2018-01-15 }} [https://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi?1998/CS/CS0937 Technical Report CS0937 <!-- https://web.archive.org/web/20180115023816/https://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi?1998/CS/CS0937 -->] {{Webarchive|url=https://web.archive.org/web/20181215171438/http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi?1998/CS/CS0937 |date=2018-12-15 }}</ref>
<ref name="Sillke_1997">{{cite web |author-first=Torsten |author-last=Sillke |date=1997 |orig-date=1993-03-01 |title=Gray-Codes with few tracks (a question of Marco Brandestini) |url=http://www.mathematik.uni-bielefeld.de/~sillke/PROBLEMS/gray |access-date=2017-10-29 |url-status=live |archive-url=https://web.archive.org/web/20171029202303/https://www.math.uni-bielefeld.de/~sillke/PROBLEMS/gray |archive-date=2017-10-29}}</ref>
<ref name="Etzion-Paterson_1996">{{cite journal |title=Near Optimal Single-Track Gray Codes |author-first1=Tuvi |author-last1=Etzion |author-first2=Kenneth G. |author-last2=Paterson |journal=[[IEEE Transactions on Information Theory]] |volume=IT-42 |issue=3 |pages=779–789 |date=May 1996 |doi=10.1109/18.490544 |citeseerx=10.1.1.14.1527 |url=http://etzion.net.technion.ac.il/files/2016/02/P36.pdf |access-date=2018-04-08 |url-status=live |archive-url=https://web.archive.org/web/20161030214251/http://etzion.net.technion.ac.il/files/2016/02/P36.pdf |archive-date=2016-10-30}}</ref>
<ref name="Ruskey_2005">{{cite journal |title=A Survey of Venn Diagrams: Symmetric Diagrams |url=
<ref name="Alciatore-Histand_1999">{{cite book |author-last1=Alciatore |author-first1=David G. |author-first2=Michael B. |author-last2=Histand |title=Mechatronics |date=1999 |publisher=[[McGraw–Hill Education]] – Europe |isbn=978-0-07-131444-2 |url=
<ref name="Krishna_2008">{{cite web |author=Krishna |title=Gray code for QAM |date=2008-05-11 |url=
<ref name="Greferath_2009">{{cite book |editor-first1=Massimiliano |editor-last1=Sala |editor-first2=Teo |editor-last2=Mora |editor-first3=Ludovic |editor-last3=Perret |editor-first4=Shojiro |editor-last4=Sakata |editor-first5=Carlo |editor-last5=Traverso |title=Gröbner Bases, Coding, and Cryptography |url=https://archive.org/details/grbnerbasescodin00sala |url-access=limited |date=2009 |publisher=[[Springer Science & Business Media]] |isbn=978-3-540-93806-4 |chapter=An Introduction to Ring-Linear Coding Theory |author-first=Marcus |author-last=Greferath |page=[https://archive.org/details/grbnerbasescodin00sala/page/n226 220]}}</ref>
<ref name="Hazewinkel-Sole_2016">{{cite book |chapter=Kerdock and Preparata codes |author-first=Patrick |author-last=Solé |title=[[Encyclopedia of Mathematics]] |editor-first=Michiel |editor-last=Hazewinkel |editor-link=Michiel Hazewinkel |publisher=[[Springer Science+Business Media]] |date=2016 |isbn=978-1-4020-0609-8 |chapter-url=https://www.encyclopediaofmath.org/index.php/Kerdock_and_Preparata_codes |url-status=live |archive-url=https://web.archive.org/web/20171029191032/https://www.encyclopediaofmath.org/index.php/Kerdock_and_Preparata_codes |archive-date=2017-10-29}}</ref>
<ref name="Evans_1958">{{cite journal |title=(([title unknown])) |author-first=David Silvester |author-last=Evans |volume=10–12 |page=87 |journal=Transactions |publisher=Institute of Measurement and Control |date=1958 |url=https://books.google.com/books?id=mwJvieqKGFsC&q=%22Watts+code%22}} (NB. The Watts code was called W.R.D. code or Watts Reflected Decimal to distinguish it from other codes used at [[Hilger & Watts Ltd.]])</ref>
<ref name="Evans_1960">{{cite book |title=Fundamentals of Digital Instrumentation |author-first=David Silvester |author-last=Evans |publisher=[[Hilger & Watts Ltd]] |___location=London, UK |edition=1 |date=1960 |url=https://books.google.com/books?id=gpVNAAAAYAAJ |access-date=2020-05-24}} (39 pages)</ref>
<ref name="Evans_1961">{{cite book |title=Digital Data: Their derivation and reduction for analysis and process control |chapter=Chapter Three: Direct Reading from Coded Scales |author-first=David Silvester |author-last=Evans<!-- M.I.E.E. --> |edition=1<!-- printed by J. W. Arrowsmith Ltd, Bristol, UK --> |publisher=[[Hilger & Watts Ltd]] / [[Interscience Publishers]] |___location=London, UK |date=March 1961 |pages=18–23 |url=https://books.google.com/books?id=WOIJAAAAMAAJ |access-date=2020-05-24 |quote-page=20–23 |quote=[…] Decoding. […] To decode C.P.B. or [[#Watts|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 code|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 [[Aiken code|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".)</ref>
Line 1,291 ⟶ 1,280:
<ref name="Fischer_2000">{{cite web |title=The Evolution of Character Codes, 1874–1968 |author-first=Eric N. |author-last=Fischer |date=2000-06-20 |id=ark:/13960/t07x23w8s |url=https://archive.org/details/enf-ascii |access-date=2020-12-20 |quote=[…] 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 [[Edward Davy|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 [[David Edward Hughes|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. […]}} [https://web.archive.org/web/20180919020435/http://index-of.es/Varios-2/ASCII%20The%20Evolution%20of%20Character%20Codes.pdf][https://archive.org/details/enf-ascii]</ref>
<ref name="MacMillan_2010">{{cite web |title=Codes that Don't Count - Some Printing Telegraph Codes as Products of their Technologies (With Particular Attention to the Teletypesetter) |author-first=David M. |author-last=MacMillan |work=lemur.com |___location=Mineral Point, Wisconsin, USA |version=Revision 3 |date=2010-04-27 |orig-date=2010-04-25, 2010-04-23 |url=http://www.circuitousroot.com/artifice/telegraphy/tty/codes/index.html |access-date=2020-12-20 |url-status=live |archive-url=https://web.archive.org/web/20201218233813/http://www.circuitousroot.com/artifice/telegraphy/tty/codes/index.html |archive-date=2020-12-18}}</ref>
<ref name="ITU_1909">{{cite book |title=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 |language=fr |date=1909 |orig-date=1908 |___location=Lisbon,
<ref name="ITU_1933_FR">{{cite book |title=Règlement télégraphique annexé à la convention internationale des télécommunications - protocol finale audit règlement - Madrid, 1932 |language=fr |chapter=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 |___location=Madrid, Spain |publication-place=Berne, Switzerland |publisher=[[Bureau Internationale de L'Union Télégraphique]] |date=1933 |orig-date=1932 |pages=31–40 [33] |url=http://search.itu.int/history/HistoryDigitalCollectionDocLibrary/4.5.43.fr.201.pdf |access-date=2020-12-21 |url-status=live |archive-url=https://web.archive.org/web/20201221011133/http://search.itu.int/history/HistoryDigitalCollectionDocLibrary/4.5.43.fr.201.pdf |archive-date=2020-12-21}} (1+188 pages) [https://web.archive.org/web/20201221012741/https://www.itu.int/en/history/Pages/PlenipotentiaryConferences.aspx?conf=4.5]</ref>
<ref name="ITU_1933_EN">{{cite book |title=Telegraph Regulations Annexed To The International Telecommunication Convention - Final Protocol To The Telegraph Regulations - Madrid 1932 |chapter=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. |language=en, fr |date=1933 |orig-date=1932 |id=43-152-2 / 18693 |pages=32–40 [34] |publisher=General Post Office / [[His Majesty's Stationery Office]] |___location=London, UK |url=http://search.itu.int/history/HistoryDigitalCollectionDocLibrary/4.5.43.en.101.pdf |access-date=2020-12-21 |url-status=live |archive-url=https://web.archive.org/web/20201221011748/http://search.itu.int/history/HistoryDigitalCollectionDocLibrary/4.5.43.en.101.pdf |archive-date=2020-12-21}} (1+2*120+26 pages) [https://web.archive.org/web/20201221012741/https://www.itu.int/en/history/Pages/PlenipotentiaryConferences.aspx?conf=4.5]</ref>
Line 1,297 ⟶ 1,286:
}}
== Further reading ==
{{refbegin|30em}}
* {{cite book |author-first=Richard Kohler |author-last=Richards |title=Arithmetic Operations in Digital Computers |publisher=[[D. Van Nostrand Co., Inc.]] |___location=New York, USA |edition=5 |date=1955 |url=https://books.google.com/books?id=BI5QAAAAMAAJ}}
* {{cite book |author-first=Richard Kohler |author-last=Richards |title=Electronic Digital Components and Circuits |publisher=[[D. Van Nostrand Co., Inc.]] |date=1967 |pages=490, 500–504, 510–511}}
Line 1,308 ⟶ 1,298:
* {{cite web |title=Gray Code Fundamentals |work=Design How-To |at=Part 1 |author-first=Clive "Max" |author-last=Maxfield |date=2012-10-01 |orig-date=2011-05-28 |publisher=[[EETimes]] |url=https://www.eetimes.com/document.asp?doc_id=1278809 |access-date=2017-10-30 |url-status=live |archive-url=https://web.archive.org/web/20171030135842/https://www.eetimes.com/document.asp?doc_id=1278809 |archive-date=2017-10-30}} [https://www.eetimes.com/document.asp?doc_id=1278827<!-- https://web.archive.org/web/20171030140209/https://www.eetimes.com/document.asp?doc_id=1278827 --> Part 2] [https://www.eetimes.com/document.asp?doc_id=1278853<!-- https://web.archive.org/web/20171030140323/https://www.eetimes.com/document.asp?doc_id=1278853 --> Part 3]
* {{cite book |title=Hacker's Delight |title-link=Hacker's Delight |chapter=Chapter 13: Gray Code |author-first=Henry S. |author-last=Warren, Jr. |date=2013 |edition=2 |publisher=[[Addison Wesley]] – [[Pearson Education, Inc.]] |isbn=978-0-321-84268-8 |pages=311–317<!-- page 318 is blank -->}} (7 pages)
* {{cite journal |title=Computing Binary Combinatorial Gray Codes Via Exhaustive Search With SAT Solvers |author-last1=Zinovik |author-first1=Igor |author-last2=Kroening |author-first2=Daniel |author-last3=Chebiryak |author-first3=Yury |journal=[[IEEE Transactions on Information Theory]] |publisher=[[IEEE]] |volume=54 |issue=4 |date=2008-03-21 |pages=1819–1823 |doi=10.1109/TIT.2008.917695 |
* {{cite journal |author-first=Joseph A. |author-last=O'Brien |title=Unit-Distance Binary-Decimal Code Translators |journal=[[IRE Transactions on Electronic Computers]] |volume=EC-6 |issue=2 |date=June 1957 |issn=0367-9950 |doi=10.1109/TEC.1957.5221585 |pages=122–123 |url=https://www.researchgate.net/publication/250929745 |access-date=2020-05-25}} (2 pages)
* {{cite magazine |title=A decimal Gray code – Easily converted for shaft position coding |author-first=K. G. |author-last=Barr |___location=Faculty of Natural Sciences, [[University of the West Indies]] |date=March 1981 |magazine=[[Wireless World]] |volume=87 |number=1542 |pages=86–87 |url=https://worldradiohistory.com/hd2/IDX-Site-Early-Radio/Archive-Wireless-World-IDX/80s/Wireless-World-1981-03-OCR-Page-0046.pdf |access-date=2020-07-28 |url-status=live |archive-url=https://web.archive.org/web/20200728093447/https://worldradiohistory.com/hd2/IDX-Site-Early-Radio/Archive-Wireless-World-IDX/80s/Wireless-World-1981-03-OCR-Page-0046.pdf |archive-date=2020-07-28}}
{{refend}}
== External links ==▼
{{refbegin|30em}}
▲==External links==
* [http://demonstrations.wolfram.com/BinaryGrayCode/ "Gray Code" demonstration] by Michael Schreiber, [[Wolfram Demonstrations Project]] (with Mathematica implementation). 2007.
* [https://xlinux.nist.gov/dads/HTML/graycode.html NIST Dictionary of Algorithms and Data Structures: Gray code].
Line 1,321 ⟶ 1,314:
* [http://www.bushytails.net/~randyg/encoder/encoderwheel.html Optical Encoder Wheel Generator]
* [https://web.archive.org/web/20110724021700/http://prototalk.net/forums/showthread.php?t=78 ProtoTalk.net – Understanding Quadrature Encoding] – Covers quadrature encoding in more detail with a focus on robotic applications
{{refend}}
{{DEFAULTSORT:Gray Code}}
| |||