Talk:Gray code

Edit request

After being informed by MrOllie about a potential conflict of interest, I am now formally requesting to make the following additions to the page. The Combinatorial Object Server is a collection of open source software tools I frequently use to create this kind of illustrations illustrations, and to which I am a frequent contributor. Two of the papers cited in the following paragraphs were (co)-authored by me.

A: Add the following paragraph to the Section "Constructing an n-bit Gray code":

---

There is an equivalent and conceptually much simpler definition of the binary reflected Gray code via the following greedy algorithm: We initialize the algorithm with the all-0 string of length $n$. Now we repeatedly flip the rightmost (least significant) bit, such that in each step, a new binary string is created that has not been encountered in the list of strings before. For example, in the case $n=3$ we start with 000, then we flip the rightmost bit and get 001. We then flip the middle bit, as flipping the rightmost bit would yield again 000, which we have seen before, yielding 011, etc. Unlike the previous descriptions, the greedy rule does not directly translate into an efficient algorithm, as it requires storing an exponentially long list of strings and therefore potentially expensive lookup operations.

---

B: Add the following section entitled "Restricting the weight range" before the Section "Special types of Gray codes":

---

Restricting the BRGC of length $n=5$ to four different weight intervals, indicated at the top. 0-bits are drawn as white squares, 1-bits as black squares.

We define the weight of a binary string as the number of 1s in the string. The $n$-bit BRGC has the surprising property that if we consider the subsequence of strings whose weight is in any fixed interval $[k,l]$, where $0\leq k\leq l\leq n$, then any two consecutive strings in this subsequence differ in either 1 bit or 2 bits (in the case of distance 2, the difference is an exchange of a 0 with a 1) . This distance property even holds for the difference between the first and last string in the subsequence. In particular, by restricting the weight range to a single number, i.e., by choosing $k=l$, we get a cyclic distance-2 Gray code for $k$-combinations of an $n$-element set. This is illustrated in the figure on the right for the case $n=5$ and four different weight intervals $[k,l]$.

---

C: Revise the following paragraph in the section on "Monotonic Gray codes":

---

Wheel representation of a middle-levels Gray code for $n=3$ (binary strings of length 7 with weight 3 or 4).

Monotonic codes have an interesting connection to a conjecture of Lovász, which asserts 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 preceding construction for monotonic codes ensures a Hamiltonian path of length at least $0.839N$ where $\textstyle N=2{\binom {2n+1}{n}}$ is the number of vertices in the middle-level subgraph (see also ). This construction was later improved by Johnson to cycles of length $(1-o(1))N,$ and solved full in full generality by constructing cycles of length $N$ for all $n\geq 1$ by Mütze. The figure on the right shows a solution for $n=3$.

---

D: Add the following section entitled "Generalizations" at the very end:

---

The term combinatorial Gray code refers more generally to any listing of combinatorial objects with the property that any two consecutive objects differ in a specified, usually small, way. For instance, the classical reflected binary code described before is a listing of binary strings of a certain length such that any two consecutive strings differ only in a single bit. The Steinhaus-Johnson-Trotter algorithm generates a listing of all permutations of a certain length such that any two consecutive permutations differ only in an adjacent transposition. Another classical combinatorial Gray code is a listing of all binary trees on a certain number of nodes such that any two consecutive trees differ only in a tree rotation. As a last example, it is possible to list of spanning trees of a graph such that any two consecutive trees differ only in exchanging a single edge. All of these algorithms are described in Knuth's book.

Any such combinatorial Gray code problem can be rephrased as a Hamiltonian path problem in a suitably defined graph, by taking the combinatorial objects as vertices, and connecting any two that differ in the specified way by an edge. The resulting graph is called a flip graph. Clearly, the question for a Gray code listing of the objects is equivalent to asking for a Hamiltonian path in the flip graph. For the first three combinatorial Gray codes mentioned before, these graphs are the hypercube (binary strings), the permutohedron (permutations), and the associahedron (binary trees).

---

E: Add the following external link:

---

• Generation algorithms for the binary reflected Gray code on the Combinatorial Object Server

---

Torsten Mütze (talk) 16:18, 29 May 2019 (UTC)

References

I've made enquiries regarding this request at Wikipedia:WikiProject Mathematics and Wikipedia:WikiProject Computing for help.  Spintendo  01:05, 30 May 2019 (UTC)

Hi, thank you very much for the request. Without commenting on the suggested content, I object to the addition of the external link (part "E"), and have removed your remaining three additions of it on the German Wikipedia. An administrator had already undone the fourth (de:Special:Diff/186098511). Unless Combinatorial Object Server has an article, the external link does not appear to be a relevant addition; due to the number of links added, it rather looks like advertising. ~ ToBeFree (talk) 23:31, 30 May 2019 (UTC)

See also: Bottom of Talk:Permutation (Special:PermanentLink/899577378#tbf-objection-2019). ~ ToBeFree (talk) 23:55, 30 May 2019 (UTC)

The extlink looks ok to me in principle. It's certainly not the case that extlinks have to come from organizations that are article subjects. I don't see the connection to combinatorial Gray codes though. Is there code on that site for generating them? 173.228.123.207 (talk) 08:42, 8 June 2019 (UTC)

Yes, in particular for restricting the weight range, and for generating the diagrams and wheels. Torsten Mütze (talk) 17:07, 11 June 2019 (UTC)

Reply 25-JUN-2019

  Request closed for inactivity  

• The above edit request has not received any non-COI editor responses in the past 2+1⁄2 weeks (17 days total).
• The Gray code article is highly technical in nature. Articles such as this may be adversely affected by changes which do not carry the benefit of local editor input and expertise. To that end, a request for input was listed approximately 27 days ago at the talk pages of the WikiProjects which govern this article. No replies were received.
• Without this additional input, as a safeguard the request has been declined as needing discussion.
• The COI editor is urged to revive stalled communications by making contact with local editors through their own talk pages, then by moving the discussion to this talk page.
• Unless being assisted by another review editor, the COI editor is asked to allow for a reasonable amount of time to pass before reactivating a subsequent {{request edit}} template covering the same request.

Regards,  Spintendo  19:25, 25 June 2019 (UTC)

@Spintendo: It looks like these requests were fulfilled by Torsten Mütze in late May 2019 - a month before you wrote this reply. ~Kvng (talk) 13:40, 2 July 2019 (UTC)

Thanks for pointing out that the COI requestor added his own stuff; I reverted it, since it lack supports where. It was an awful lot of text on an obscure offshoot not discussed in secondary sources. Any editor is free to put back portions of this material as they see fit. Dicklyon (talk) 13:57, 2 July 2019 (UTC)

Gray code and incremental encoders

Re [1] This keeps adding "Gray codes are used in linear and rotary position encoders (absolute encoders and incremental encoders) in preference to natural binary encoding.", i.e. adding "incremental encoders". (I've no idea what "natural binary" is either, or "unnatural binary").

Gray code is used for absolute encoders. That is its purpose. I have never heard of it ever being applied to incremental encoders.

Now presumably the implication here is that quadrature encoders are using a 2-bit Gray code, also that quadrature encoders are incremental encoders. These are two statements that are true enough (they can't be disproven), but neither of them are useful here. The point is that Gray codes are specifically used for the absolute case and that incremental encoders (which are predominantly 1 bit, and that's the usual implication of the term) don't need to, or benefit from, using them. Quadrature is a separate case, and again, I've never heard "Gray code" applied to them as a term (for merely 2 bits, this is a pretty degenerate case).

We should not have such a prominent statement which implies, to any extent, that incremental encoders need or use Gray code. If there's an exception to this, such as quadrature, then that should be covered later, and without using such broad terms. Andy Dingley (talk) 21:05, 8 March 2020 (UTC)

I agree with your concern about "natural binary" and changed it to "binary". I also agree that Gray codes are "specifically used" for parallel absolute encoders. However, Gray codes are also specifically used for K maps, state machine sequencers, clock-crossing FIFOs, digital communications, incremental encoders, etc. Clearly, the use of Gray codes in absolute encoders is not its exclusive purpose.

The term "incremental encoder" is widely used for devices with quadrature outputs; this is in no way an "exception" or a "degenerate" or edge case, and I can find no evidence that 1-bit encoders are the predominant meaning of this term. Having said that, the notion that incremental encoders don't need to use Gray code is mistaken. Errors can occur at binary-encoded code boundaries for any word size of two bits or more -- an issue that obviously applies to incremental encoders. And although the Gray code employed by quadrature encoders is commonly referred to as quadrature encoding, its use here is not "inferred" or "implicated"; incremental encoders absolutely must and do use Gray code, for the very same reasons as absolute encoders. Lambtron talk 16:16, 9 March 2020 (UTC)

• Gray codes are used for lots of things: but we're just talking encoders here. I would dispute that " "incremental encoder" is widely used for devices with quadrature outputs; " – they're called quadrature encoders. This is the COMMONNAME term used. Incremental encoders, and that term, are used for the single rotation direction encoders with a single bit, or a single bit and a zero pulse. We might describe or even define quadrature encoders as "a form of incremental encoder", but the terms are kept distinct if they're being used as an ordinal, identifying term. Nor have I described them as "degenerate".

It's clearly true that "Errors can occur at binary-encoded code boundaries for any word size of two bits or more", which is one reason why incremental encoders don't do that. Nor do quadrature encoders. "incremental encoders absolutely must and do use Gray code" is simply false (the counter examples are myriad) and unless we regard a 2 bit quadrature signal as a form of Gray code (a degenerate example), they don't use Gray code, let alone must do.

The current wording is poor and unencyclopedic. It's not wrong, but it is misleading, and it's misleading when it could easily avoid that. Andy Dingley (talk) 23:58, 9 March 2020 (UTC)

In my professional experience and in literature, "incremental encoder" is by far the most widely used term for incremental encoders with quadrature outputs. To get a sense of just how widespread this is, one can simply google "incremental encoder" and survey the results. This isn't "misleading" or "unencyclopedic"; it's just a reality.

Yes, the quadrature-encoded signals from an incremental encoder (or for that matter, the signals from any absolute encoder) can be -- and are -- regarded as binary numbers, and these numbers fully conform to the definition of Gray code: a numerical code in which consecutive integers are represented by binary numbers differing in only one digit. Furthermore, incremental and absolute encoders use Gray code for exactly the same reasons. The definition doesn't make exceptions for or treat 2-bit Gray codes any differently than others, and there's no evidence that word size is relevant to the usefulness of Gray code, so I see no reason to classify this as a "degenerate example" that is somehow unworthy of inclusion or equal treatment.

To understand why incremental encoders use Gray code -- and why they absolutely must do so -- consider what could happen if binary encoding were used instead. This is easily done with a simple case study: Suppose that the encoder is moving in the "forward" direction and the AB signal pair is sampled while the code is transitioning from 01 to 10, and that AB is sampled as 00 (due to metastability or input signals not changing simultaneously). As a result, the reader will incorrectly assume that the encoder has moved in the "reverse" direction and, in the process, lose track of the actual position. This is almost always a problem and in many applications (e.g., motion control) it's a catastrophic event; hence the requirement for Gray code. Lambtron talk 15:27, 10 March 2020 (UTC)

• I've no wish to get into a professional experience pissing match. And I've understood the need for Gray codes for decades. There are some disagreements here which are minor matters of terminology, and a more relevant question of how to word the article.

In my experience, quadrature encoders are called that. They're kept separate, at least in name, from single bit incremental encoders. A name which is thus kept for that type, not quadrature. Maybe that's a local thing, but that's how we roll.

Single bit incremental encoders are widespread. They do not use Gray code. It is thus clear that we cannot claim "all encoders must use Gray code" (and in fact, simple binary absolute encoders are still available, and usable, at least for low speeds).

We should state that Gray code is important to absolute encoders, for the reasons you point out, and could clarify that the problem is that of the simultaneous change of multiple bits. But should not say that incremental encoders need to use it: single bits certainly don't, and if we wanted to mention quadrature (we can clarify what they use as a waveform without needing to categorise that as either Gray or non-Gray (I still don't see that as a Gray code, other than in this very restricted 2-bit manner)) we should call them quadratures, as the simplest and clearest name (because calling them "incremental" confuses them with others, when we don't need to). There are solutions as to how to word this which offend neither of our definitions, and without falling into cofusable terms when we don't need to. We're not here to score point, we're supposed to be being accurate, clear and unconfusable. Andy Dingley (talk) 00:35, 11 March 2020 (UTC)

I also have no desire for a pissing contest and sincerely hope my comments aren't perceived as such.

I agree that the terminology could cause confusion. Aside from popular usage, as a technical matter, "incremental encoder" is a general term for two different device types, which sometimes are referred to as "quadrature encoders" and "tachometer encoders" (2- and 1-bit encoders, respectively). So to resolve this, I propose that we consistently refer to incremental encoders as "quadrature encoders" to make it clear that we're specifically talking about incremental encoders with quadrature outputs.

On the other hand, IMO it should be stated unequivocally that quadrature encoders output Gray code, and that this is essential for proper operation, and that Gray code serves exactly the same purpose in quadrature and absolute encoders. A 2-bit Gray code is, in fact, still a Gray code regardless of how it's produced or used or, in the case of quadrature encoders, its "quadrature" nom de guerre. A rose is still a rose by any other name. And the use of "only" 2 bits does not diminish the importance or utility of Gray code in any way. As one of the most widely used position sensors in the world, quadrature encoders should not be relegated to a passing mention here, nor should their use of Gray code be portrayed as trivial or restricted. Lambtron talk 16:45, 11 March 2020 (UTC)

• I seem to have got through life thinking of quadrature encoders as being two phase-shifted signals, rather than Gray codes, but I've no objection to describing them that way (I also remember synchros).

I'm less keen on turning incremental encoders into tachometers. That's one use, but there's plenty of low-cost stuff counting pulses from such an encoder and a zero point.

I think emphasising "Gray code is used when a multi-bit signal would be prone to errors around multi-bit transitions" would be a good thing. That's the core of all of this. Andy Dingley (talk) 17:11, 11 March 2020 (UTC)

Yes, that's the core of it, and the reason Gray invented it for the "PCM tube" A/D converter. But the observation that a two-bit "quadrature" signal is also a Gray code is also pretty old. I don't think I was the first to notice it when I wrote about the mouse interface, in 1980, "The counters needed for X and Y simply count through four states, in either direction (up or down), changing only one bit at a time (i.e., 00, 01, 11, 10). This is a simple case of either a Gray code counter or a Johnson counter (Moebius counter)." The property of only one bit changing at a time was key; still is. Dicklyon (talk) 04:49, 12 March 2020 (UTC)

Here it is in 1977: "The rotor position encoder utilizes two LED, two phototransistors, and an encoder wheel to generate a two bit Gray code which defines one of four quadrature area positions of the rotor." and "The output of the optical commutator is a 2 bit Gray code (reflected binary) which changes one bit only for every 90° of rotation. The Gray code was selected because only one bit changes at a time, so that there is never an uncertainty in output." Dicklyon (talk) 05:14, 12 March 2020 (UTC)

Emphasising the core concept is a worthy goal, but it may not be possible to explain in a single sentence. There are a number of key issues behind the concept that probably should be mentioned. My apologies for the excessive verbosity; just trying to cover all the bases:

• Gray code is used to convey state information to asynchronous receivers.
• Each unique Gray code value represents a particular state.
• The represented entity must have exactly 2^N states (int N > 1) and the state sequence must be purely linear.
• The Gray code associated with the current state is transmitted as multiple signals (a "signal bus").
• Each bus signal conveys one bit of the Gray code.
• Since the bus receiver is asynchronous, sampling errors are unavoidable -- even with Gray code.
• The root cause of sampling errors is receiver metastability.
• Metastability is possible whenever a signal is sampled in close time proximity to a signal state transition.
• With Gray code, only one bus signal is subject to sampling error because the representations of consecutive states differ in only one bit.
• With other encoding, multiple bus signals may be subject to sampling errors because the representations of consecutive states may differ in multiple bits.
• A sampling error manifests as a sampled state which differs from the actual state.
• When only single-bit sampling errors are possible, the sampled state will be either the actual current state or the actual previous state. The latter is technically an error, but one that is tolerable. This is what Gray code offers.
• When multi-bit sampling errors are possible, the sampled state will be either the actual current state or a code-dependent state which has no relationship to the actual state. The latter is a critical error, and the reason why Gray code is used here.

Lambtron talk 15:53, 12 March 2020 (UTC)

I'd say I don't quite agree with some of those points. Metastability is one possible mechanism, but not the only one that Gray codes ameliorate. For example, with encoders that use separate mechanical or optical tracks to switch code bits, the asynchronous nature of the receiver and metastability are not the issue; it's just that different bits can switch at slightly different values of the analog signal (angle or whatever). Look at the original PCM tube patent drawing for example. Dicklyon (talk) 06:54, 14 March 2020 (UTC)

I see your point. I think the issue has been confused because of the wording. There are a couple of fundamental concepts here which seem a bit blended:

1. Mechanical code generators cannot reliably generate a non-Gray code because tracks and detectors cannot be perfectly aligned. In the vicinity of every intentional code boundary in which the codes differ in multiple bits, the inevitable mechanical misalignment creates a region -- which lies between the valid codes -- of invalid codes. The problem here isn't a temporal one of some bits changing before others (the current wording); it's the generation of invalid codes when the device is positioned in one of these "nether regions". In fact, the device may be parked in such a position and, as a result, continuously output an invalid code.
2. Electronic code receivers cannot reliably receive a non-Gray code due to metastability. Receivers are necessarily asynchronous because the received code isn't accompanied by a clock, and asynchronous receivers are inherently affected by metastability. This problem could be described as some receiver output bits changing before others, but it's an issue even if all input code bits change simultaneously. It has nothing to do with receiving static codes; it's about sampling near code transitions while the device is moving. Lambtron talk 17:07, 16 March 2020 (UTC)

Why are you denying the existence of synchronous code receivers, with clocks? They're everywhere. Need to rescope your statement. Dicklyon (talk) 00:46, 17 March 2020 (UTC)

No denial! The receiver is necessarily asynchronous with respect to incoming code edges, which are effectively in their own private clock domain. The receiver has its own clock and is indeed a fully synchronous FSM, but has no idea when code edges will arrive. Like a UART, but with parallel inputs. Lambtron talk 02:37, 17 March 2020 (UTC)

Sounds like a denial. Some encoders send clock with data, so that the receiver isn't asynchronous. And some receivers don't have clocks, but are triggered by incoming code edges. There are lots of possibilities, and Gray codes help in some of them, but not all. Dicklyon (talk) 04:27, 17 March 2020 (UTC)

Accusations of "denial" aren't helpful. Or sensible, since there has been no discussion of synchronous receivers until now. Also, not to put too fine a point on it, but collaboration is a two-way street. Instead of simply criticising my attempts to improve this article, how about proactively presenting your own ideas about how to "rescope" statements? Lambtron talk 13:31, 17 March 2020 (UTC)

I'm just trying to help you see that in "fundamental concepts", your statement "Receivers are necessarily asynchronous" might not be right. Sorry if I came across harshly. I remain unclear on exactly what you're trying to improve, just don't want it to be undertaken with shaky premises. Dicklyon (talk) 00:20, 19 March 2020 (UTC)

Varec codes?

The recently added references in support of "Varec code" as a variant of Gray code are not convincing. The refs are all by or about the company Varec who say they used a "reflected binary Gray code", but in base-10, base-12, and base-16 variants and few twists, but there's nothing to indicate that these were ever recognized as different codes, or called "Varec codes" or "Varec pulse codes" by anybody. The quoted line "The complete dispatching operation, gauging, and remote control is integrated into one single unitized system when a 'Varec' Pulse Code Telemetering System is installed" is about a Varec brand "Pulse Code Telemeterig System", not about a "Varec Pulse Code". They used an O'Brien variant for base 10, and other trivial variations. Is there any reason to not just delete this one manufacturer's obscure system with no independent mentions? Dicklyon (talk) 04:08, 22 May 2020 (UTC)

@Matthiaspaul: are you still thinking there is a code called Varec code? Dicklyon (talk) 22:45, 22 May 2020 (UTC)

The Varec code is as much mentionable as are the Datex and Gillham codes. They all have been (or still are) widely used in their corresponding industries. None of these "industry codes" were discussed in academic papers, but this does not make them non-notable, in particular as the Varec and Datex codes seem to have existed in 1954 already, that is, even before O'Brien wrote his article in 1955 (and published in 1956).

As many of these codes, they were referred to under different names. I added one ref actually naming it "Varec code" (minus the typo), unfortunately this one doesn't have a code chart. Some years back I also saw some scanned PDFs with code charts from IIRC the 1960s, but I can't find them now.

--Matthiaspaul (talk) 23:20, 22 May 2020 (UTC)

What makes them non-notable (or not worth mention even) is the lack of sources that mention them. Even the Varec literature never says "Varec code"; they say they use a Gray code. Could be similar for Datex and Gillham, which I haven't looked into yet. If you want to mention that Varec used Gray codes, that could be OK, but to call them Varec codes is not OK. Dicklyon (talk) 01:19, 23 May 2020 (UTC)

Excess-3 or Stibitz sources

On a different note, I am searching for the earliest references defining Gray excess-3 codes in order to nail down when they were introduced and by whom. Does someone have a "really old"(tm) ref for them? --Matthiaspaul (talk) 23:29, 22 May 2020 (UTC)

There's a 1958 patent (or [2]) mentioning Gray excess-3. Dicklyon (talk) 06:12, 23 May 2020 (UTC)

The Swiss version of the same patent calls it a Stibitz-Gray code, so maybe that's the thing to look more for. Dicklyon (talk) 17:04, 23 May 2020 (UTC)

1954 Bell Laboratories Record has Stibitz Gray code, but not decimal or excess-3 as far as I can find. Dicklyon (talk) 17:10, 23 May 2020 (UTC)

The 1957 book by Stibitz has Gray codes, and excess-3 (shifted) binary, and bi-quinary, but I don't see excess-3 Gray there. Dicklyon (talk) 17:18, 23 May 2020 (UTC)

The 1957 book by Maurice Wilkes has "Stibitz's excess-three code". Glaser 1981 says that Edmund Berkeley says that Stibitz came up with it in 1939. Aspray 1990 also talks about it in Stibitz's relay-based "Complex Computer". Sounds like it predates Gray? Dicklyon (talk) 17:28, 23 May 2020 (UTC)