Talk:Gray code/Archive 1

Archive 1

Untitled

The following was at Gray_coding, and is moved here in case anyone wants to add some of it to the Gray_code article.

---

A gray code is a special coding system designed to prevent spurious output from practical electromechanical switches and is specifically relevant to encoding of position information for a rotating object. For example, if we create a device that indicates position by closing and opening switches, we could use the binary code to represent position:

Binary Code

Input position	Output 3	Output 2	Output 1
0	0	0	0
1	0	0	1
2	0	1	0
3	0	1	1
4	1	0	0
5	1	0	1
6	1	1	0
7	1	1	1

The problem is that, with real (mechanical) switches, it is very unlikely that two switches will change states exactly in synchrony. For example, in the transistion from state 3 to state 4, all three switches change state. In the brief period while all are changing, the switches will read some spurious position.

A gray code solves this problem by changing only one switch at a time, so there is never any ambiguity of position:

Gray Code

Input position	Output 3	Output 2	Output 1
0	0	0	0
1	0	0	1
2	0	1	1
3	0	1	0
4	1	1	0
5	1	1	1
6	1	0	1
7	1	0	0

Notice also that state seven can roll over to state zero with only one switch change.

---

I liked the less-technical introduction, so I copied it to the article.

I wish this article had a photo of an "encoder disk".

-- DavidCary 14:13, 12 Jun 2004 (UTC)

updates

Hi all, my first contribution to Wikipedia, hopefully it will go over well. I changed the example from a 4-bit BRGC to a 3-bit BRGC because it's a little bit simpler at first glance. I also added a lot of info about special types of Gray codes. Since this came from a paper I wrote, I added many of the references at the bottom that I used for the paper. I have some trivial C++ code to recursively generate an n-bit BRGC but I don't know if that would really be appropriate to attach to this. Thoughts? Rob 05:16, 6 Sep 2004 (UTC)

Real numbers?

Isn't it possible to give the real numbers a gray code representation? But the article only mentions integers. A5 18:42, 20 Apr 2005 (UTC)

Maybe....though I had never heard of doing it. I suppose you can define a Gray code sequence for non-binary numbers such that only one digit changes. Following the same method for generating binary Gray codes, for trinary:

(trinary Gray code moved to main article)

You can extend this to decimal if you wish. Hmm, maybe I'll add trinary to the article. Cburnett 19:03, Apr 20, 2005 (UTC)

This doesn't exactly answer the original question. You can have gray codes for other bases, but can you have one for the real numbers? The immediate answer seems to be no, since there's no such thing in the real numbers as two "successive" numbers. Deco 00:25, 21 Apr 2005 (UTC)

You can represent real numbers in Gray code....but to finite precision. The point of the above is that you can easily find a Gray code for base 10 so its just if you care about infinite precision. Cburnett 01:25, Apr 21, 2005 (UTC)

Gray codes are codes where neighbouring elements only differ in one symbol. On the real number line, there is no such thing as a neighbour - between any two numbers, there are infinitely many other numbers--Niels Ø 08:45, Apr 21, 2005 (UTC).

There are times when it is convenient to think of the bits from a sensor (whether it uses natural binary codes or gray codes) as bits of a binary fraction (i.e., a value from 0 to 1), rather than the bits of a binary integer.

Let's think about rotary encoders (like the one in the article) with 2, 3, 4, 5, 6, ... and N rings. (It doesn't matter what order the rings are in, so let's put the coarser rings nearer the center).

If you look carefully, the 7-ring encoder is just like the 8-ring coder with the 8th (outermost) ring filed off. The 6-ring encoder is just like the 7-ring encoder with the 7th (outermost) ring filed off.

If we represent these as fractional bits (rather than trying to make an integer out of them), it makes it easier to write software that can handle any kind of encoder (with any number of rings).

When encoder positions are represented as (fixed-point arithmetic) fractions such as

0.0100100111000000 and
0.0110110111000000

, software can find the angle between encoder position without needing to know exactly how many rings the encoder has. Then it is easy to upgrade to a more-precise encoder (more rings) or reduce cost by substituding a cheaper encoder (fewer rings), without changing any software.

When encoder positions are represented as integers such as

01001001110. and
01101101110.

, software needs to know exactly how many rings the encoder has, and usually needs to be re-compiled whenever the number of rings changes (which can be annoying).

Getting back to the original point: If you can give me a natural binary representation of a "real number", I can give you a (binary) Gray code representation of that number.

Does that answer the original question?

Is this something that should go into the article ?

--DavidCary 18:23, 14 May 2005 (UTC)

n-ary gray codes

Currently, two sections in the article deals with non-binary Gray codes. Both sections may have merit, so I guess they should be merged. --Niels Ø 08:24, Apr 21, 2005 (UTC)

Doh, I missed the n-ary section. Merged. Cburnett 16:28, Apr 21, 2005 (UTC)

Are n-ary gray codes actually *used* for anything, or are they only interesting to mathematicians? --DavidCary 05:37, 6 November 2005 (UTC)

An example: I'm generating a list of colours such that each colour is "nearby" to the next in RGB-space. If each coordinate can take n values, then an (n, 3)-Gray code is what I'm after. --Taejo|대조 13:21, 23 June 2007 (UTC)

Jos.koot 23:24, 23 November 2006 (UTC) : added a real working Scheme implementation of the algorithm together with an algorithm computing one single element of a Gray code and its inverse. In the pseudo algorithm the use of array n[k+1] is not needed and the arrays can be properly sized to k elements by halting when i grows out of range.

other applications of gray codes

Added some explanation on Gray Codes in Genetic Algorithms. -Shiri (a newbie)

am i correct in thinking

that a grey code cannot exist for a circular sequence with an odd number of values? Plugwash 01:43, 26 December 2005 (UTC)

Correct. This is evident because going from one number to the next toggles one bit. An odd number of toggles cannot produce the original value; at least one bit must be different. Non-circular sequences are possible, of course. Deco 02:13, 26 December 2005 (UTC)

What about the sequence (00, 01, 11, 10, 20, 21, 22, 12, 02)? --Pezezin 23:22, 30 June 2006 (UTC)

The argument applies to binary Gray codes only. For larger bases, the situation is different.--Niels Ø 09:31, 24 November 2006 (UTC)

A remark should be added that cyclic ternary gray codes do exists for every k. (I don't know about (n,k) codes with n>3) Examples: (2,3) : (000 200 210 010 110 112 212 012 022 222 122 102 202 002 001 101 201 211 111 011 021 121 221 220 020 120 100)

(2,4): (0000 1000 1200 0200 2200 2210 0210 1210 1010 0010 2010 2110 0110 1110 1112 2112 0112 0212 2212 1212 1012 2012 0012 0022 2022 1022 1222 2222 0222 0122 2122 1122 1102 2102 0102 0202 2202 1202 1002 2002 0002 0001 1001 2001 2101 1101 0101 0201 1201 2201 2211 1211 0211 0111 1111 2111 2011 1011 0011 0021 1021 2021 2121 1121 0121 0221 1221 2221 2220 0220 1220 1020 0020 2020 2120 0120 1120 1100 0100 2100 2000)

These circular ternary gray codes can easily be produced by

(define (circular-ternary-gray-code k)
 (let-values (((f t r) (values 0 1 2))) ; permutations of 0, 1 and 2 generate different gray codes
  (define (long h f t r)
   (if (positive? h)
    (let ((h (sub1 h)))
     (long h f t r)
     (move h f r t)
     (long h t f r)
     (move h r t f)
     (long h f t r))))
  (define (strt h f t r)
   (if (positive? h)
    (let ((h (sub1 h)))
     (strt h f r t)
     (move h f t r)
     (long h r t f))))
  (define (fini h f t r)
   (if (positive? h)
    (let ((h (sub1 h)))
     (long h f r t)
     (move h f t r) 
     (fini h r t f))))
  (define result ())
  (define pattern (make-vector k f))
  (define (move h f t r)
   (vector-set! pattern h t)
   (set! result (cons (vector->list pattern) result)))
  (if (positive? k)
   (let ((h (sub1 k)))
    (strt h f r t) 
    (move h f t r) 
    (long h r f t) 
    (move h t r f) 
    (long h f t r) 
    (move h r f t)
    (fini h t f r)))
  result))

Furthermore a O(k) algorithm exists for computing the i-th element of the gray codes produced by the above algorithm. The inverse exists too, i.e. a function that accepts a gray code and returns the i telling which element it is. In fact the ternary gray codes produced by the above algorithm show how to move a tower of hanoi Tower of hanoi from one peg back onto the same peg while passing every feasible distribution of disks exactly once (circular Hamilton path)

Jos.koot 13:40, 29 November 2006 (UTC)

Single-Track Gray Codes

It's the inner two tracks of Figure 1 that are the same except for an angular offset, and the inner track supplies the most significant bit. I have changed the text to correspond. It seems an unlikely error, though - has the figure been changed?

I made the same changes in the rotary encoder article.

       - Jim Van Zandt

Are those programming examples really necessary?

If you think it would help, I could provide some alternative versions in Javascript, BASIC, FORTRAN and Z80 opcodes. We could even go the whole hog and and merge this page with the list of hello world programs. What do you reckon? -- Sakurambo 22:06, 17 May 2006 (UTC)

Assuming you're being sarcastic, people have a bizarre tendency to add implementations in their favourite language to articles. Just cut out the ones you don't like. Deco 23:28, 30 June 2006 (UTC)

The proposed languages are not bizarre enough for the bizarre tendency! If you can write it for Atanasoff-Berry Computer or at least in assembler for PDP-8/System360, it would be another story :-) Beyond the joke, I would say that all those implementations are subject to WikiBooks and should be moved there (leaving just a link here). -- Goldie (tell me) 20:49, 5 September 2006 (UTC)

Or for my wiki, LiteratePrograms. </plug> :-) Deco 13:01, 20 November 2006 (UTC)

Gray code is not invented by Frank Gray

Frank Gray have not been born when the reflective binary code was invented. I do not know who have invented it either but the code was already in use in the mid-XIX century. In the Gray's patent it is clearly stated that he is claiming only the receiver and the implemented method for translation.

Elisha Gray does have some good chances to be the first who have put the code in an electrical aparatus but anyone's "invention" will have to be proved. I have no enough time to fix the name across the whole article. -- Goldie (tell me) 21:39, 5 September 2006 (UTC)

There is no evidence to connect Elisha Gray to the Gray code, but several gray-code-like patterns and devices do pre-date Frank Gray's patent, according to the study by Don Knuth. Dicklyon 23:30, 23 November 2006 (UTC)

Code Bug

The following code can become an infinite loop:

In the programming language C, a conversion from a Gray code g to an unsigned binary representation b can be achieved efficiently through:

 b = g;
 while (g >>= 1) {b ^= g;}

INTERNATIONAL STANDARD ISO/IEC 9899, Programming languages — C

6.5.7 Bitwise shift operators

4 The result of E1 << E2 is E1 left-shifted E2 bit positions; vacated bits are filled with zeros. If E1 has an unsigned type, the value of the result is E1 ´ 2E2, reduced modulo one more than the maximum value representable in the result type. If E1 has a signed type and nonnegative value, and E1 ´ 2E2 is representable in the result type, then that is the resulting value; otherwise, the behavior is undefined.

5 The result of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an unsigned type or if E1 has a signed type and a nonnegative value, the value of the result is the integral part of the quotient of E1 / 2E2. If E1 has a signed type and a negative value, the resulting value is implementation-defined. —The preceding unsigned comment was added by Crm123 (talk • contribs) 17:24, 7 May 2007 (UTC).

gray code toy worth a mention?

The Brain Puzzler [1] was a mechanical toy produced in the 1970s or early 80s. The solution to the puzzle was a RBGC. Worth a link from the article? 216.220.208.238 16:24, 15 December 2006 (UTC)

The "Tower of hanoi" external link is dead (404).

Single track Gray code image

I've added an image to the section, corresponding with the table, but I'm too lazy to write a caption. Shinobu 11:14, 17 May 2007 (UTC)

Is that the image that the text in that section is calling "Figure 1"? Rather than refer to the figure, the figure needs a caption that calls to the reference.

No, figure 1 refers to the normal rotary encoder. Shinobu 08:39, 11 June 2007 (UTC)

haskell code?

Quoting the article :

(The base case can also be thought of as a single zero-bit Gray code (n=0, G = { " " }) which is made into the one-bit code by the recursive process, as demonstrated in the Haskell example below).

I don't see any haskell code in the article. Anyone does? Stdazi (talk) 09:06, 18 August 2008 (UTC)

• I have added some Haskell code, if someone thinks that this code is in wrong place, cut and paste as is to move it.

I had some problems to format this code, because wiki translated lists to links. The style is very simple, because I take into account that imperative languages programers are not familiar with recursive definitions, much more less with higher order functions. But, I used map, a higher order function, if you think it obscures the program, change transpose to:

transpose :: [ anytype_t ] -> [ anytype_t ]
transpose [] = []
transpose ([]:xss) = []
transpose ((x:xs):xss)=
      (heads ((x:xs):xss)):(transpose (tails ((x:xs):xss)))
  where heads [] = []
        heads (x:xs) = (head x):(heads xs)
        tails [] = [] 
        tails (x:xs) = (tail x):(tails xs)

or let them search more about haskell and map in Wikipedia :) —Preceding unsigned comment added by Elias (talk • contribs) 04:30, 3 January 2009 (UTC)

Algorithm correct?

A test using Java with grayN(21, 3, 3) gives me: {-1,2,2}

Obviously that is not correct!

Using this code:

    static int[] grayN(int value, int base, int digits)
    {
        // parameters: value, base, digits
        // Convert a value to a graycode with the given base and digits. Iterating
        // through a sequence of values would result in a sequence of graycodes in
        // which only one digit changes at a time.

        int baseN[] = new int[digits];  // Stores the ordinary base-N number, one digit per entry
        int gray[] = new int[digits];   // Stores the base-N graycode number

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

        // Convert the normal baseN number into the graycode equivalent. Note that
        // the loop starts at the most significant digit and goes down.
        int shift = 0;
        for (i = digits - 1; i >= 0; i--)
        {
            // The gray digit gets shifted down equal to the sum of the higher
            // digits.
            gray[i] = (baseN[i] + base - shift) % base;  // + base to prevent neg
            shift += gray[i];
        }

        return gray;
    }

Is my code wrong, or is there a bug in the algorithm shown on the article?  —CobraA1 01:15, 13 February 2009 (UTC)

The C code is wrong in some senses. First, the first loop gets the digits in the reverse order to the stated one; the comment is right as is your code, but the C code does it wrong. Second, just adding base does not avoid negatives. Third, it does not declare the loop variable. I'm fixing all these issues, but ultimately I think this fragment should be replaced by pseudocode or a description. --pgimeno (talk) 16:21, 7 August 2009 (UTC)

Code snippets

Why so many code snippets? Most of them are not even particularly intelligible. I bet if we wanted clarity and precision, then matlab code would beat them all. Any opinions? Dicklyon 06:58, 10 December 2006 (UTC)

For example, compare this to the others to convert binary B to Gray G:

 G = bitxor(B, bitshift(B, -1));

The other direction probably requires a loop and more bit twiddling, though. Dicklyon 07:11, 10 December 2006 (UTC)

OK, even though I wasn't kidding, I take it back. Reading the talk above, I took the suggestion and removed the ones I didn't like, which was all of them. Pseudocode is enough, since the details of the others only obscure the point, except for programmers who know the language; and they don't need it. Dicklyon 07:21, 10 December 2006 (UTC)

I am totally in favour of this. Gray codes are generally used in electronic hardware, so personally I don't see the need for any software examples at all. -- Sakurambo 桜ん坊 11:25, 10 December 2006 (UTC)

Well, now that hardware is usually designed by writing Verilog code, code is the lingua-franca of algorithms, so we really out to have something. But showing off programming language features and syntax is not the point. Dicklyon 17:31, 10 December 2006 (UTC)

I would like to add here that LISP is one of those languages famous for being unreadable to someone unfamiliar with it. Pseudocode? Better formatting? I'll leave it to you all, but as it stands I didn't find the snippets very illuminating. Shinobu 11:37, 17 May 2007 (UTC)

Would it be okay to bring back one pseudo-code (or C-like language) example for encoding, and one example for decoding? I actually came back to this page looking for them, since it is useful sometimes for encoding integers in genetic algorithms. I do agree that previously there were too many, and it was messy, but I think a single snippet for each of encoding/decoding would be nice. Fstonedahl (talk) 20:52, 11 January 2009 (UTC)

The useful 'C-like' language for a web page is JavaScript. There could be code snippets which actually demonstrate something in the browser: an edit box to a text output, for example. —Preceding unsigned comment added by 81.108.210.118 (talk) 09:31, 8 October 2009 (UTC)

Iterative construction

I came to this page looking for the information below, and didn't find it, so I added it in the section Constructing an n-bit gray code. I don't think I explained it brilliantly though, so I'd appreciate improvements.

To construct the binary-reflected Gray code iteratively, start with the code 0, and at step i find the bit position of the least significant '1' in the binary representation of i - flip the bit at that position in the previous code to get the next code. The bit positions start 0, 1, 0, 2, 0, 1, 0, 3, ... (sequence A007814 in the OEIS).

Motivation: I'm writing code that needs to traverse all 2^edges possible graphs of n nodes, and easiest is to change one edge at a time from the previous graph. Hv (talk) 12:12, 2 January 2010 (UTC)

another example

http://blog.plover.com/2009/06/21/ (maybe this is worth adding it) —Preceding unsigned comment added by 91.37.9.19 (talk) 23:51, 21 June 2009 (UTC)

The conversion methods in the last couple of lines are interesting, but the small error described in the bulk of the article is chance: the height happened to occur where the least significant bit changed; if it had occurred where the most significant bit changed the reading could be very inacurate! —Preceding unsigned comment added by 81.108.210.118 (talk) 09:43, 8 October 2009 (UTC)

You are completely wrong. The whole point of gray code is that there isn't a "most significant" bit. —Dominus (talk) 12:44, 3 January 2010 (UTC)

Examples please

Snakes and coils - in the Snake-in-the-box codes section - sound interesting - but what do they look like? Not every reader capable of understanding the description has the chops to actually construct something from an abstract definition. If anyone could add an example or two of each of these objects, it would communicate the notions involved much better. Simple folk like me need plenty of concrete examples to wrap my head around. ;-) yoyo (talk) 10:07, 9 June 2010 (UTC)

Iterative construction cleanup.

Some proposed wording: Informally, to construct a Gray code on n bits from one on n - 1 bits, take the previous Gray code and list the elements first in order, then in reverse order. Prepend a 0 to the elements that are listed in order, and a 1 to the elements that are listed in reverse order.

Somewhat more formally, let G_n be the canonical Gray code on n bits, let G_n(k) be the k-th entry in the code, where 0 ≤ k < 2ⁿ, and let #G_n(k) be the k-th entry of the code preceded by # (where # is either 1 or 0). The following constructs the canonical Gray code on n bits:

G₁ = (0, 1).

If n > 1, then:

• If 0 ≤ k ≤ 2^{n - 1} - 1, then G_n(k)=0G_{n - 1}(k).
• If 2^{n - 1} ≤ k ≤ 2ⁿ - 1, then G_n(k)=1G_n-1(2ⁿ - (k + 1)).

So G₂(0) = 0G₁(0) = 00. Similarly, G₂(1) = 0G₁(1) = 01.

How does this sound? --147.26.161.144 (talk) 20:51, 18 July 2010 (UTC)

The first paragraph is OK. The subsequent formalism doesn't contribute much: harder to understand and less helpful than the current text. The [01]G(n) notation feels sort of ad hoc. The example could be more illustrative (e.g., pick one of the values from the reversed sequence). (I am, of course, not exactly a disinterested party!) -- Elphion (talk) 16:53, 19 July 2010 (UTC)

My use of the phrase "iterative construction" was intended to convey the concept of "determining the next value from the previous one". Your proposal however looks to be a rewrite of the presentation of the recursive algorithm at the start of the Constructing an n-bit Gray code section, which already seems to me quite adequate as it stands. What issue are you aiming to address with this? Hv (talk) 09:22, 21 July 2010 (UTC)

Connection to symbolic dynamics

I'd like to hint at a connection with Symbolic dynamics, specifically the Tent map. A sort of Gray code of real numbers $x\in [0,1]$ is constructed as follows. Let $T:[0,1]\rightarrow [0,1]$ be the Tent map with slope 2 and $\Omega =\{0,c,1\}$ be a set of symbols. Define an address map $A:[0,1]\rightarrow \{0,c,1\}$ by letting $A(x)=0$ whenever $x<{\frac {1}{2}}$, $A(x)=c$ only for $x={\frac {1}{2}}$ and $A(x)=1$ otherwise. Then the infinite Gray code of $x$ is given as the sequence $g_{n}(x)=A(T^{n}(x))$. This sequence is an element of the so-called Shift space $\Omega ^{\mathbb {N} }$. Now, for an integer $k$ with $k<2^{m}$ consider the real number $x={\frac {k}{2^{m}-1}}$. Then the m-digit Gray code of $k$ is the first m digits of the sequence $g_{n}(x)$ defined above. 80.1.165.108 (talk) 01:04, 26 March 2011 (UTC) O. Klinke, University of Birmingham, UK

Incorrect link to Chain code?

In Gray code#Single-track Gray code, there is "(compared to chain codes, also called De Bruijn sequences)". But the chain codes described at that article are for compressing monochrome images and seem unrelated to De Bruijn sequences. There's also a reference to “code chains”. Could someone more familiar with this material correct these links or add explanation of how they're related? — Unbitwise (talk) 21:03, 22 June 2011 (UTC)

Vietnamese-rings puzzle?

The binary-reflected Gray code can also be used to serve as a solution guide for the Tower of Hanoi problem, as well a classical Vietnamese-rings puzzle and a sequential mechanical puzzle mechanism. Apart from the unclear syntax ("as well a" = as well as for a?), what is a classical Vietnamese-rings puzzle? Some variant of the Chinese rings puzzle?--85.75.178.41 (talk) 11:27, 23 June 2011 (UTC)

Irrelevant reference?

The reference "Venn Diagram Survey — Symmetric Diagrams" for the sentence "Note that each column is a cyclic shift of the first column, and from any row to the next row only one bit changes." in the Single-track Gray code section makes no sense to me in relation to that sentence. I'm not familiar with Venn Diagrams, but as far as I can tell the reference doesn't relate in any way to the subject. Am I correct? If not, what is the relation? -- Sjock (talk) 20:32, 28 September 2011 (UTC)

Simple conversion to binary

I read this page for a class assignment and noticed that most algorithms were in needlessly complicated code form. I found that the slides on this website did a much better job at explaining how to convert between binary and Gray. Therefore I propose to add an example (sub)section which basically reads something like this: assume you have a Gray code (X3,X2,X1,X0) = 1010 and would like to convert it to binary(Y3,Y2,Y1,Y0), then Y3 = X3 and Y2 = X2 XOR Y3, Y1 = X1 XOR Y2 ... Y[n] = X[n] XOR Y[n+1] ==> Y1,Y2,Y3,Y4 = 1100. Likewise, to go from binary to Gray, X3 = Y3, X2 = Y3 XOR Y2... I admit, I do not know the rules of WP very well and this is the first time editing anything other than typos, but would anyone have any problems with this addition? — Preceding unsigned comment added by 98.249.63.58 (talk) 02:32, 3 October 2011 (UTC)

Looks like a reliable source, and I don't see an equivalently simple method in the article, so it looks like it might be a good addition. Dicklyon (talk) 05:14, 3 October 2011 (UTC)

The last few paragraphs of the construction section already say this. I agree it could be said more clearly. The bit-by-bit formulas already present should be incorporated into any new discussion. It would help to relate the two conversions more clearly to the preceding theoretical construction (which makes clear that Gray codes have the properties they do). -- Elphion (talk) 13:51, 3 October 2011 (UTC)

Ternary Gray Code

The section explains that other gray codes exist but would benefit from at least one example. Since the given algorithm is cyclic, perhaps a reflected version would help make the point. Is this a viable alternative?:

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

81.108.210.118 (talk) 11:06, 9 October 2009 (UTC)

I first had the same idea: on each digit position, alternate 0,1,2,2,1,0 (like the binary sequence 0,1,1,0). But because 3 is not a multiple of 2, the code can NOT be cyclic this way: 22 is too far from 00, 222 is too far from 000, etc. Teuxe (talk) 16:31, 20 January 2012 (UTC)

Anti-Gray Codes?

Is there a code where the bit patterns of successive elements differ from each other by a maximal, rather than minimal, number of bits?

The problem with Gray codes for positional measurements is that you're vulnerable to misreads: if you get some birdshit on one of your black blobs and it goes white, for instance, if it's the bit that differs between that position and one of its neighbours, you can no longer detect that transition. Ditto if your photocell is flaky or something. With an anti-Gray code, you have multiple bits changing at every transition, so you're much more likely to detect it. If you have a shitty photocell or a shitted-on mark, you won't get the pattern you expected, but you will get a transition to an unexpected state - at which point you declare an error condition, call the repairman or cleaner, and either stop or or take a gamble on being where you think you should be, and hope the next transition works out.

Kind of like 8b/10b encoding if you think about it in precisely the wrong way.

-- Tom Anderson 2007-09-19 2330 +0100 —Preceding unsigned comment added by 128.40.81.22 (talk) 22:31, 19 September 2007 (UTC)

If you consider the recursive method for Gray Code construction, one solution to creating "Anti-Gray Codes" is to add 01010101... instead of 00000...11111... to the code at every step. E.g.: (0, 1), (00, 11, 01, 10), (000, 111, 001, 110, 010, 101, 011, 100)... this creates a large distance between adjacent codes, but not necessarily between further codes.72.231.157.16 (talk) 05:27, 18 April 2009 (UTC)

While that does create some distance you'll notice that many of your generated numbers share several bits from the 4th place on. 110,010 is a hamming distance of 1. Optimally anti-gray code for a set of three binary numbers will always alternate between hamming distances of 2 and 3. 000,111,001,110,101,010,100,011 you'll note is better having hamming distances of 3,2,3,2,3,2,3. Tat (talk) 23:17, 17 August 2012 (UTC)

Took me a while to figure it out, I needed one too. Take any gray code. Shift all the bits to the left by 1. Double the list. And alternate XOR flips. Done. You have an anti-gray code.

Take gray code. 0 1

Shift all the bits to the left by 1. 00 10

Double the list. 00 00 10 10

Alternate XOR flips. 00 11 10 01

The reason this works is because gray codes by definition have the minimal amount of distance. Xor flips have the maximum (they flip every bit). If you interweave them you will have maximum, maximum -1, maximum, maximum -1, maximum, maximum -1... which is an optimal anti-gray code. Also note, you don't really *need* to shift the bits to the left. You can introduce a zero *anywhere*, so long as you do it consistently. Watch, I'll do it with the middle digit.

    00,01,11,10

-> 000,001,101,100 -> 000,000,001,001,101,101,100,100 -> 000,111,001,110,101,010,100,011 (perfect anti-grey code).

Fast conversion to binary

This is an implementation of n.log(n) conversion in C designed to be independent of the type width.

unsigned short grayToBinary(unsigned short num)
{
        unsigned short shift, mask;
        for(shift=1; mask=num>>shift-1>>1; shift<<=1)
                num ^= mask;
        return num;
}

Is it worth of replacing the current example? --egg 22:11, 3 November 2011 (UTC)

Am I dense, or is the expression num>>shift-1>>1 nonsensical? And why don't you put some spaces around binary operators, and maybe some courtesy parens, to give us a clue what it means? I expect it means (num >> (shift - 1)) >> 1, but it's unclear to me how that differs from num >> shift; sorry I'm not more familiar with c semantics. And it's not clear when/why this loop terminates; for 16-bit shorts, you'd want shift values of 1, 2, 4, 8, but it goes on through 16, 32, 64, ... 32768, doesn't it? Dicklyon (talk) 05:54, 4 November 2011 (UTC)

Plus I'm dense. I see why I misinterpreted now. Dicklyon (talk) 15:54, 4 November 2011 (UTC)

The expression essentially means num>>shift but the >> operator has undefined behaviour for shifts longer or equal to the width of type, which is the case we need to stop the loop. This might be a more readable version of the same algorithm:

unsigned short grayToBinary(unsigned short num)
{
        unsigned short shift;
        for(shift=1; shift<8*sizeof(num); shift*=2)
                num ^= num>>shift;
        return num;
}

Both versions work well. BTW, why do we use the short type instead of the common unsigned int?.. --egg 13:20, 4 November 2011 (UTC)

The second example is far superior to the first. (The first completely obscures the principle being illustrated.) Applying the principle of self-documenting code, how about:

unsigned short grayToBinary(unsigned short num)
{
        unsigned short shift;
        unsigned short numBits = 8 * sizeof(num);
        for(shift=1; shift<numBits; shift*=2) {
                num ^= num>>shift;
        }
        return num;
}

A final version should include something like the documentation in the example in the article. It's probably worth a comment that the algorithm assumes that the bitwidth of the argument is a power of 2. (I've worked on machines where that's not true.) Why "unsigned short"? That's the likely domain of discourse. ints are probably overkill, though the additional execution cost wouldn't amount to much. In C++ you might accommodate both with templates. -- Elphion (talk) 15:10, 4 November 2011 (UTC)

Yes, much better. I'd style it nicer and use int though: Dicklyon (talk) 15:54, 4 November 2011 (UTC)

unsigned int grayToBinary(unsigned int num)
{
    unsigned int numBits = 8 * sizeof(num);
    unsigned int shift;
    for (shift = 1; shift < numBits; shift *= 2)
    {
        num ^= num >> shift;
    }
    return num;
}

Correction

As user:Mikron30 has pointed out, this version does not work: it converts 12 to 9 rather than to the correct value (8). The problem is that num should be XORed with the shift of its original value, not of its current value, as follows:

unsigned int grayToBinary(unsigned int num)
{
    unsigned int numBits = 8 * sizeof(num);
    unsigned int shift;
    unsigned int mask = num;
    for (shift = 1; shift < numBits; shift *= 2)
    {
        num ^= mask >> shift;
    }
    return num;
}

Since in this case mask will always shift eventually to 0, it suffices to loop while mask is non-zero. Counting the bits is not necessary. I've updated the algorithm in the article accordingly.

-- Elphion (talk) 06:49, 15 April 2013 (UTC)

How many Gray codes are there?

I was asked recently how many distinct binary Gray codes there are are n bits. Given the canonical Gray code on n bits, you can easily create (2^n)*n! Gray codes by choosing any of the 2^n vertices as starting points, and permuting the columns of bitflips. Example, if the bits are numbered from right to left as this: 4 3 2 1, then the Gray code on 4 bits is made by flipping the following positions in order: 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1. Now this can be permuted by anything in S₄, so for any of the 16 starting points, there are 24 Gray codes. Does this hit all possible ones? If so, they are all isomorphic to the canonical one, and the formula is nice. If not, then the problem is more interesting. --147.26.161.144 (talk) 20:23, 18 July 2010 (UTC)

There are many more because the ones you described are “only” those for one specific transition-sequence. The section types of Gray codes describes many more possible sequences. Every single one of those has, again, $2^{n}n!$ different code-representations. — Preceding unsigned comment added by 91.112.63.30 (talk) 12:46, 24 June 2013 (UTC)

Gillham code

I have been searching and searching for hours and did not find any theory behind Gillham code which is another type of Gray code. Gillham code is used in aviation altitude encoders/ transponders. I would really appreciate if someone could post some info on Gillham code, conversion algorithm, etc... —Preceding unsigned comment added by Myval (talk • contribs) 07:29, 25 September 2008 (UTC)

I agree that this "Gray code" article should at least mention Gillham code. But now that we have a Gillham code article, that article would be a better place for details about it. --DavidCary (talk) 17:53, 25 June 2013 (UTC)

I would also like to see a reference to Gillham code and to its application in aviation, as this is IMHO one of the most important applications of a type of Gray code - Sswitcher (talk) 08:21, 16 June 2014 (UTC)

PCM tube?

Should PCM tube reference Pulse Code Modulation or the subsection on that page? — Preceding unsigned comment added by 59.167.182.149 (talk) 03:09, 13 December 2014 (UTC)

Yes; but what subsection do you have in mind? Dicklyon (talk) 03:45, 13 December 2014 (UTC)

Baudot code, one of the first use of Gray code

In article page, Baudot code might be given as historically it was one of the first use of gray code, has shown by next illustration:

Illustration: Baudot code

Let ·Fig. · V · IV·   · I · II·III·
----+-----+---+---+---+---+---+---+
 A  · 1   ·   ·   ·   · ● ·   ·   ·    
É / · 1/  ·   ·   ·   · ● · ● ·   ·    
 E  · 2   ·   ·   ·   ·   · ● ·   ·    
 I  · 3/  ·   ·   ·   ·   · ● · ● ·    
 O  · 5   ·   ·   ·   · ● · ● · ● ·    
 U  · 4   ·   ·   ·   · ● ·   · ● ·    
 Y  · 3   ·   ·   ·   ·   ·   · ● ·    
 
 B  · 8   ·   · ● ·   ·   ·   · ● ·    
 C  · 9   ·   · ● ·   · ● ·   · ● ·    
 D  · 0   ·   · ● ·   · ● · ● · ● ·    
 F  · 5/  ·   · ● ·   ·   · ● · ● ·    
 G  · 7   ·   · ● ·   ·   · ● ·   ·    
 H  · ¹   ·   · ● ·   · ● · ● ·   ·    
 J  · 6   ·   · ● ·   · ● ·   ·   ·    
 Fig. Bl. ·   · ● ·   ·   ·   ·   ·    
 *  · *   · ● · ● ·   ·   ·   · 
 K  · (   · ● · ● ·   · ● ·   · 
 L  · =   · ● · ● ·   · ● · ● · 
 M  · )   · ● · ● ·   ·   · ● · 
 N  · £   · ● · ● ·   ·   · ● · ●
 P  · +   · ● · ● ·   · ● · ● · ●
 Q  · /   · ● · ● ·   · ● ·   · ●
 R  · –   · ● · ● ·   ·   ·   · ●
 S  · 7/  · ● ·   ·   ·   ·   · ●
 T  · ²   · ● ·   ·   · ● ·   · ●
 V  · ¹   · ● ·   ·   · ● · ● · ●
 W  ·  ?  · ● ·   ·   ·   · ● · ●
 X  · 9/  · ● ·   ·   ·   · ● · 
 Z  ·  :  · ● ·   ·   · ● · ● · 
 –  · .   · ● ·   ·   · ● ·   · 
 Let. Bl. · ● ·   ·   ·   ·   ·   ·  

— Preceding unsigned comment added by 86.67.203.56 (talk) 15:47, 29 June 2014 (UTC)

• Comment. I am lost here. Baudot may have used a Gray code for the character assignments, but there does not seem to be any advantage in what is an arbitrary assignment. Where is the encoder-style problem? If I need to send a Q, then being off by 1 bit is an error. I'd remove the reference to Baudot being a Gray code. Glrx (talk) 00:57, 4 July 2014 (UTC)

Here I found a description on how the Baudot system was working:

original version

english version

Le combinateur qui est la cheville ouvrière du système se compose de cinq disques à rayon tantôt métallique tantôt isolant, sur lesquels se meut un frotteur, armé de cinq ressorts, qui tourne synchroniquement (...). Les armatures (...) forment (...) une genre de commutateur d'un genre particulier qui ouvre une issue au courant local chargé de produire l'impression, au moment précis où la caractère transmis passe en regard du papier.

The combinateur which is the main working part of the system is made of five disks à rayon one time metallic, one time non metallic, on which move a frotteur, armed with five ressorts, which turn simultaneously (...). The armatures (...) makes (...) some kind of commutateur from a new specific kind which open one way to local electricity which role is to produce the printing, at the accurate time when the transmitted character is in regard (in front) of the paper.

From my understanding, if you use a code different of the gray one, you might encounter some intermediate values while the disk is turning between two characters which might print something you do not want? — Preceding unsigned comment added by 77.199.96.122 (talk) 23:08, 6 September 2016 (UTC)

Baudot's equipment did not have transition problems because it was synchronous. The operator would hear a click and then press the next code chord. The keys would lock down until the commutator released them. The character assignments are essentially arbitrary, but Baudot apparently made some effort to minimize operator fatigue: vowels did not use the left hand keys.

For Wikipedia's purpose, we would need a reliable reference that says Baudot was a Gray code. I doubt there is such a reference. Baudot was not trying to solve the measurement uncertainty issue, so it seems that Baudot may have done a gray-like sequencing, but that may be because he did not think of a binary code assignment. Also, the gray sequence above had to insert the FIGS shift in the middle of the consonants and the digits are not in numerical order. Some assignments look simple and obvious: the infrequent FIGS and LTRS codes are one left finger assignments with repeats in that shift block being blank.

Glrx (talk) 18:31, 11 September 2016 (UTC)

References

Gray code code example changes

Please look again at my edit to the Gray code article, which you undid. My provided code re-write still makes use of doubling the shift at each step, just like the replaced code. I think that is the point you refer to in your edit comment. My edit just reverses the order of the XORs, which is legitimate, and puts them in a loop that self-detects when it can stop. Thank you -- 64.132.59.226 (talk) 16:28, 14 September 2017 (UTC)

Read the edit summary, "rv - missing the point of that whole example."

Your change is both unencyclopedic, and it misses the point of that whole example. This is not a coding cookbook of examples, it's not a coding tutorial. We're not looking for good coding here, we're looking for good explanations of Gray code itself. The version without the explicit stated shifts is much clearer for that. There's also a loop-based example immediately preceding it. Andy Dingley (talk) 16:41, 14 September 2017 (UTC)

Thank you for clarifying which point you are making. However, since your note is brief, I am not completely sure that you understand the point I am making. At the risk of repeating something that is already obvious to you ... my point is that the grayToBinary example uses a loop that shifts one position at time. The grayToBinary32 example (both as originally and as I have edited it) instead doubles the shift each time. To me, that is the defining difference between these two examples, rather than that one is a loop and that the other is an unrolled loop. Unfortunately, the existing grayToBinary32 has a shortfall, in that it assumes sizeof(unsigned int) == 4, which can silently change if code is moved from one computer to another. It was my hope to repair that shortfall. Can you think of an approach that repairs the shortfall while maintaining the clarity you hope to see? Thank you for entertaining my questions and considering my perspective. 64.132.59.226 (talk) 17:04, 14 September 2017 (UTC)

This is not a coding tutorial. This is an explanation of Gray code. It needs to be the clearest explanation of Gray code that is can be, not the most optimised (for size or run time) code fragment. That alone is reason to keep the original example.

Secondly, this is a Gray code. I've never seen a 32 bit Gray code. I cannot imagine a use for a 32 bit Gray code, at least not out in the physical world of encoders. I once had a very expensive problem where a machine had been fitted with a 7 bit Gray code encoder when it needed a 9 bit encoder. We couldn't afford this (we could, but I was told we couldn't, after wasting far more chasing the problem of using a 7 bit code) and I had to make it work with a 8 bit encoder instead. Now imagine how impossible it would be to rule a grating for a 32 bit Gray code! Two billion increments! Andy Dingley (talk) 17:21, 14 September 2017 (UTC)

I fear that this discussion will not resolve with agreement. Nonetheless, I wish to note some counterarguments. The one-shift-at-a-time grayToBinary example is not an unrolled loop; do you consider it to be in need of clarification / unrolling, or is it only the doubling-shift approach that needs to remain unrolled? If so, why? Second, people may have a need to convert to a Gray code and back even in situations where they are not enumerating all 2³² or larger possibilities. Suppose I want to know the 10¹⁰⁰-th position for the 500-level Towers of Hanoi puzzle? Thank you for your time and energy. 64.132.59.226 (talk) 17:34, 14 September 2017 (UTC)

I modified the comment in the code instead of the code itself. I am hopeful that this is an acceptable compromise. 64.132.59.226 (talk) 13:10, 15 September 2017 (UTC)

I reverted. There should be a clear point to make. Glrx (talk) 03:46, 20 September 2017 (UTC)

I fixed the edit to address the submission comment that the focus should be the algorithm not the code. 64.132.59.226 (talk) 13:23, 26 September 2017 (UTC)

By "fixed" you mean "yet again re-inserted a change that others are clearly against". Andy Dingley (talk) 15:18, 26 September 2017 (UTC)

@Andy Dingley: I am attempting to find a compromise solution that addresses everyone's priorities. If I have failed, I ask you to please try for a compromise yourself. Straight out reverts are less useful in conveying your priorities, but if you feel that that is your best course of action then I understand, and I will try again. 64.132.59.226 (talk) 11:57, 27 September 2017 (UTC)

You need to get consensus on this talk page before you reinsert your edits. Do not continually "try again". Propose the change on the talk page and get consensus for it. WP is interested in algorithms. Adding comments about the potential limitations of shift instructions is about programming detail rather than the algorithm. Glrx (talk) 01:59, 28 September 2017 (UTC)

Yes, please let's try for consensus. Please express your degree of support for the following statements:

1. As I would characterize it, the fast algorithm for converting a gray code to a number is to use a sequence of exclusive-ors with shifts of the previous intermediate results, and the specification of the algorithm necessarily describes how many of these operations are required.
2. The current version of the code assumes 32-bit unsigned integers, which I would characterize as a coding assumption, not an algorithm essential.
3. For reasons of efficiency, we may not want to change the code itself, but we can discuss the removal of the 32-bit coding assumption with a few words in the code comment.

64.132.59.226 (talk) 16:02, 28 September 2017 (UTC)

It has been a week of discussion and there have been no dissenters. A consensus of one is a consensus, but it is pretty weak. Please post your pros and cons. If you can envision an approach that you believe addresses everyone's priorities, please suggest it! 64.132.59.226 (talk) 11:55, 5 October 2017 (UTC)

"there have been no dissenters"

Rubbish. This is getting to the point of WP:TENDENTIOUS Andy Dingley (talk) 12:26, 5 October 2017 (UTC)

Thank you for your correction. I should have said that no one spoke up during the week. Previous to then there were dissenters. I stand corrected.

However, some of that previous dissent was of the form "What's the point?", which was not useful in arriving at consensus. There is currently a disagreement as to whether specifying when the code/algorithm terminates is a coding detail or an essential part of the algorithm. That is the topic for which I have seen no discussion. Please, please address this issue. 64.132.59.226 (talk) 15:47, 5 October 2017 (UTC)

No. You are the one trying to advocate a change. You have to make a case as to why that is a concrete improvement. If you cannot, or if you can only make "change for change sake", then you don't get to make it. Nor can you play "keep at it for longer than anyone else can be bothered". Your editing on other articles, such as United States customary units are based equally on edit-warring against other editors. Andy Dingley (talk) 16:03, 5 October 2017 (UTC)

There were no concrete proposals to edit the page; the three statements were general. I do not see that any response was required. Furthermore, 64.132 has not achieved consensus before; trying to wear down the opposition is not a good tactic. Moreover, consensus is not compromise. Editorial decisions are not trying to make everybody happy. "There is currently a disagreement as to whether specifying when the code/algorithm terminates is a coding detail or an essential part of the algorithm" completely misstates the disagreement. There is no doubt that grayToBinary32 terminates. There is no doubt that it is restricted to codes that are 32 bits or less. As Andy stated, most Gray code applications will be fewer than 16 bits. Glrx (talk) 20:03, 5 October 2017 (UTC)

A downside of using an IP address is that it changes when I move to a different location. To head off any accusations of sock puppetry, I hereby report that I am one and the same as 64.132.59.226.

Thank you, @Glrx for discussing the merits of the changes to the article. I acknowledge that you do not like the way I have formulated the disagreement and I will try to work with your formulation. I am not expert at quantifying how many people would want a Gray code of more than 32 bits for some purpose. However, I am hopeful that we would agree that it is an easy win to support such larger Gray codes if it outweighs any downside. I hope that I am remaining consistent with your formulation if I make a concrete proposal with the intent to minimize such a downside.

I would accommodate these large Gray codes with a few words in the comment without changing the program itself. I would not modify the existing sentence in the comment. I propose a new second sentence, "For Gray codes of N > 32 bits, have the bit shift amounts be the powers of two with value strictly less than N". I see this as minimally impacting the existing strong points of the present article. I see it as a fundamental truism of the algorithm, independent of coding decisions such as C vs. Java vs. Python. As a bonus, it promotes independence from code-dependent values such as sizeof(some type). 74.76.180.38 (talk) 20:05, 6 October 2017 (UTC)

@Glrx, I see you that reverted my edit with the comment "not cleared on talk page". However, the talk page shows nothing but silence on this topic from anyone but me since 5 October 2017. It is this silence that encouraged me to invoke WP:BRD, and the correct response when reverting my WP:BRD edit is not to cite the silence, but to break the silence. Let me re-state my argument: the information that I would like to add is helpful to anyone who wishes to efficiently invert a Gray code of size other than N = 32 bits. In particular, the applicability of the edit is not only to the Gray code sizes that you and Andy Dingley have deemed of little use. 64.132.59.226 (talk) 17:02, 23 October 2017 (UTC)

Yet again, silence from other people who have already opposed your changes does not mean that they have quietly changed their minds. Andy Dingley (talk) 17:15, 23 October 2017 (UTC)

@Andy Dingley, I have never made the argument that you have changed your mind, instead invoking WP:BRD to elicit dialogue on the talk page. On the talk page, I have responded multiple times to the arguments that you have made, but you have since adopted a position of silence with regards to the merits, instead responding on procedural grounds. Please spare just a moment more of your time to respond not on procedural grounds but on the newly described merits of the edit I am making. Please respond to this statement: whether it is a 5-bit Gray code, a 16-bit Gray code or a 100-bit Gray code, it is useful to the reader to know that the bit shift amounts that must be included in an algorithm like grayToBinary32 are those that are powers of two with value strictly less than the number of bits. If you are open to having this information somewhere in the article, please, please let me know. If you are not, please provide an explanation that is not procedural but based upon the merits of the information I propose to include. 64.132.59.226 (talk) 17:47, 23 October 2017 (UTC)

The information you want to add does not add much to the article and probably distracts more. The comment does not help someone trying to understand the given code; instead it is advice on how to extend the code. And the comment is in stilted language. WP is not trying to teach people how to program or provide them with code to use in their projects, code to adapt to their projects, or whatever. The article describes what a Gray code is. That is the fundamental topic. It provides general algorithms for converting arbitrary size Gray codes to and from binary. Those algorithms are relevant to understanding how Gray codes can be used with the conventional binary numbers found in computers. The general algorithms are fast enough for most applications. A programmer won't be fired for using a loop. Then there is the fast 32-bit version. It shows you don't need a loop. Andy has already pointed out that 32-bits is overkill for most applications. In other words, your comment is trying to reach an incredibly small portion of WP's audience. But the article does not need a deep dive into how-to-program-other-powers-of-two-versions of the unrolled loops. Such a digression is a distraction for the average reader. The trick is actually a standard technique for bit-bumming programmers: it is used for bit reversing and ones counting, too. But that programming lore is a needless digression in this article. A high school student or middle manager may want to learn about Gray codes, but that does not mean they need to learn how to program with them or code slightly different versions. WP is neither a how-to guide nor a tutorial.

You also know that nobody else on this page has agreed with your position. If you wanted to elicit more discussion on this page, then you could have made additional comment on this talk page rather than insert disputed content into the article. Do not take silence, once a topic has been discussed, to be consent or consensus. You acknowledge that Andy has not changed his position; neither have I. Glrx (talk) 22:21, 23 October 2017 (UTC)

@Glrx: With respect to your second paragraph: please rest assured that I do not take silence as consent. Please rest assured also that I know what your opinions were on the earlier edits that I made. The only reason that I invoked WP:BRD is that I got no feedback on the merits of the later, proposed compromises. Until now! Thank you for that.

With regard to your substantive comments: you addressed many of my questions and I thank you for that. You did not address that knowledge of the maximum bit shift needed would be of use to someone using, say, a 5-bit Gray code. For such, the quick implementation would be merely "num = num ^ (num >> 4); num = num ^ (num >> 2); num = num ^ (num >> 1);". Do you deem that worthy of mention (if the mention is sufficiently brief and not in stilted language)? Would it make a difference if it were mentioned in the accompanying text rather than as a comment in the code? 64.132.59.226 (talk) 12:40, 24 October 2017 (UTC)

Yes, I did. No. No. Glrx (talk) 14:35, 24 October 2017 (UTC)

"for" loop vs. "while" loop and the superfluous shift operation

@84.153.139.186, thank you for your ongoing edits to the Gray code article. It appears to me that you are advocating for a switch from a "for" loop to a "while" loop because it "removed superfluous shift operation". Is that right? Unfortunately, I fear that your counting is off. In one case, the first shift occurs when "mask" is first set and in the other case it occurs after "mask" has been first set to "num". Either way that counts as 1. The remaining shifts do not depend upon "for" or "while" and continue exactly until "mask" becomes zero.

Because I am not seeing any speed advantage to one formulation over the other, to me it then boils down to a comparison of which code is clearer. Since the loop has an initialization ("mask = num" or "mask = num >> 1") and an update step on the same variable ("mask = mask >> 1"), would you agree that the "for" loop captures that well? 64.132.59.226 (talk) 14:59, 2 November 2017 (UTC)

The current "for" loop implementation also has the advantage that we don't compare mask to 0 when mask == num, a savings except when num happens to be zero. (Though to me, this is minor potatoes compared to the readability issues.) 64.132.59.226 (talk) 12:14, 3 November 2017 (UTC)

OUCH! The former "for" loop had the disadvantage to perform a superfluous shift operation when num == 0, alias always performs an initial shift operation, even when not necessary, produces two shift instructions, and the result of the last shift is never used. Additionally the initial shift obscures how the algorithm works.84.153.128.88 (talk) 04:32, 4 November 2017 (UTC)

The while version is easier to read and interpret, esp. for non C programmers, and no less efficient, shifting exactly the same number of times until mask gets to 0 (and efficiency is certainly not a consideration here). Dicklyon (talk) 01:38, 4 November 2017 (UTC)

Thank you for the clarification that the while loop implementation saves a shift operation only in the case that num equals 0, and that this comes at the expense of an extra comparison against zero when num is not equal to 0. 64.132.59.226 (talk) 13:08, 6 November 2017 (UTC)

Superfluous exclusive or in grayToBinary code example

I would like to change the grayToBinary code example to the following. Reasons: the last iteration of the loop in the existing example is pointlessly taking the exclusive or of num with a mask of zero (except that it doesn't do this when num is zero because there is no looping). Additionally, conceptually there is no reason that the mask should ever be equal to num; the first reasonable mask is num >> 1.

/*
 * This function converts a reflected binary
 * Gray code number to a binary number.
 * Each Gray code bit is exclusive-ored with all
 * more significant bits.
 */
unsigned int grayToBinary(unsigned int num)
{
    unsigned int mask = num >> 1;
    while (mask != 0)
    {
        num = num ^ mask;
        mask = mask >> 1;
    }
    return num;
}

Comments? 64.132.59.226 (talk) 13:15, 10 November 2017 (UTC)

Lucal code?

The table near the top of the article says (and links to) "Lucal code" at top. The link redirects to a nonexistent section in the present article. The table itself is hard to understand; perhaps it needs a legend. What is the relationship between Gray and Lucal codes?--Nø (talk) 13:41, 7 June 2018 (UTC)

It acually doesn't link to a nonexistent section; it links to § Related Codes, which is tagged with anchors for all of the listed (but unexplained) codes:

== {{anchor|MRB|Lucal|Datex|Varec|Gillham|Hoklas|Gray-Excess|Glixon|O'Brien|Petherick|Tompkins|Kautz}}Related codes ==

Looking at the abstract for Lucal's paper that's cited at the various mentions of "Lucal code", it sounds like the major change was to add error detection to the Gray code. According to Lucal this also facilitates performing arithmetic on the encoded data, and he provides algorithms for that as well:

The modification for integral numbers is essentially the addition of an even parity check bit to the Gray code representation. This facilitates both the arithmetic operations and the detection of errors-in the arithmetic process as well as in transmission.

This could definitely be covered in more detail in the article, most likely enough to justify its own section (at which point the anchor should be moved from § Related Codes to the new section). -- FeRDNYC (talk) 16:31, 23 October 2018 (UTC)

Realized it would be polite to ping @Nø: so I shall. -- FeRDNYC (talk) 16:33, 23 October 2018 (UTC)

Animation

The rotary encode and, in particular, the STGC images would benefit enormously from animation! Casual viewers could miss the magic of this concept: making paper versions to explain this to my children was time-consuming and probably less clear than an animation could be. —Preceding unsigned comment added by 81.108.210.118 (talk) 09:49, 8 October 2009 (UTC)

Animated and color-coded STGC rotor.

I have completed an animation based on the svg shown. I agreed that the static image and the discussion were obscuring the functional beauty of STGC. While my image works it may be too colorful for some tastes

The original svg and discussion did not identify the sensors, define when the sensor would switch from on to off and did not even define whether the slots or sensors would be spinning and in which direction the spin would occur. These facts made correlating the chart with the svg difficult.

Note: I discovered that the three slots are at (0, 120) (168, 204) (228, 252), and that the 5 sensors start at 0 degrees and are evenly distributed around the circle with a separation of 72 degrees. The slots rotate as this would most accurately mimic a physical device. The direction of clock-wise rotation and the identity of the sensors (red, purple, yellow, blue and green) were chosen to match the bit-patterns displayed in the Greycode article.

Preceding comment added by Perlygatekeeper (talk • contribs) 18:14, 9 June 2017 (UTC)

@Perlygatekeeper: The animation is really great, and illustrates both the concept and execution well. Thanks for doing that! I have to be honest, though — the font is a horror-show, even at full size but most especially when the image is resized for embedding in the article.

I have to wonder if it wouldn't be better to place the five digits below the animation, full-width (and proportionally taller), so that they're more visible and less corrupted by resizing. -- FeRDNYC (talk) 16:59, 23 October 2018 (UTC)

I've created an updated version incorporating that change; since I uploaded it as a new version of Perlygatekeeper's original, it should already be showing both here and in the article. Caching may occasionally show the old version; if you see a distorted (non-rectangular) version of the circular animation, then you just need to refresh your cache. -- FeRDNYC (talk) 18:47, 23 October 2018 (UTC)

And I updated that again with a gray background behind the numerals, because the yellow was really hard to make out. -- FeRDNYC (talk) 00:18, 24 October 2018 (UTC)

Example image

The example photographic image of an opened Gray code absolute encoder looks like it is actually a plain binary encoder. That should be clear seeing the rotational patterns, that describe binary trees of reflective material. -- Lmatteini (talk) 10:05, 9 November 2018 (UTC)

To me it looks like a gray code. Note how, where one circle change from 0 to 1 or 1 to 0, neither of the neighbouring cirlces change at the same position. Their changes are staggered.--Nø (talk) 12:12, 9 November 2018 (UTC)

• It's correct, that's a Gray code. Yes, they do look like binary trees. Binary looks more like a right-angled triangle, with increasingly large (and obvious) changes in multiple bits at once. Andy Dingley (talk) 13:41, 9 November 2018 (UTC)

Source code?

Since Wikipedia isn't a how-to guide and computer code is the very essence of how-to, should we be spending so much effort on this? There have been so many revisions in the last couple of months, and I'm wondering if source code shouldn't just be deleted instead. --Wtshymanski (talk) 15:59, 2 November 2017 (UTC)

I like source code. Sometimes I just don't understand something until I see an implementation. 64.132.59.226 (talk) 12:09, 3 November 2017 (UTC)

I agree: code is an unambiguous and succinct way of getting the idea across. We do need to avoid the notion that it has to be tuned to a fare-thee-well. -- Elphion (talk) 13:46, 3 November 2017 (UTC)

Source code is unintelligible to majority of our readers. It might be worth looking to see what the general consensus is on including source code. I don't recall seeing any discussions about it in recent years, and do not recall the conclusions. --Ronz (talk) 16:42, 3 November 2017 (UTC)

I can see source code as useful to compare different languages, but if you're explaining an algorithm, surely a flow chart or block diagram or English-language description would be preferred, instead of the unreadable gobbledygook that is most C source. Anyone who understands <<, >>, and the critical difference between == and = as well as English already knows enough about programming not to need our ham-fisted explanation of the trivial. But I'm prejudiced because I've written almost nothing in C. BASIC used to be the universal way to show an implementation of an algorithm, but BASIC has been "improved" so much that it's impossible to give a neutral version that would actually run on every BASIC implementation. --Wtshymanski (talk) 17:00, 3 November 2017 (UTC)

I understand your objection to C, but the language (at least its syntax) is familiar to most programmers. Most of the code I see in WP is in C or some descendant; I think most readers actually interested in the algorithms will get the drift. Flow charts are a disaster largely discarded in the early Neolithic, and English-language descriptions are usually more unintelligible (and more imprecise) even than pseudo-code. -- Elphion (talk) 20:29, 3 November 2017 (UTC)

C is portable, compilable, runnable and testable. That's far better than any pseudocode. Andy Dingley (talk) 20:49, 3 November 2017 (UTC)

A person unfamiliar with C's for-loop syntax is not likely to be able to interpret such code. Using a while is much more obvious, even to a programmer that seldom writes one. The C operators are also pretty uninterpretable to the unititated, but can be explained in comments. So, C or pseudo code, either way, is probably OK; whichever is most clear. Dicklyon (talk) 01:34, 4 November 2017 (UTC)

"...familiar to most programmers...." I submit if you're a programmer, you're not going to need Wikipedia's inept help to code a simple translation between number representations. --Wtshymanski (talk) 02:13, 4 November 2017 (UTC)

No, that's exactly wrong. Most programmers will be familiar with C; but very few will know what Gray codes are. They come here to find out, and we describe them in a way that will be unambiguously understood. They are free to adopt the code, or not; and to fine tune the heck out of it if they so choose. (Added: and this transformation is not exactly trivial.) -- Elphion (talk) 05:53, 4 November 2017 (UTC)

Geeze, I hope the next heart-lung machine I'm hooked up to isn't relying on code someone got off Wikipedia. --Wtshymanski (talk) 18:10, 5 November 2017 (UTC)

@Wtshymanski, Elphion, and Andy Dingley: I'm with Wtshymanski. There's this bias among part of the community recently to include All Information™ in Wikipedia, simply because Wikipedia is where lots of people come for information. But an encyclopedia is not and should not be a compendium of all available knowledge. In fact, the parameters for inclusion are fairly narrow — or, they used to be.

Now we have articles like List of top international association football goal scorers by country — and that article links to a bunch of articles like List of international goals scored by Ali Daei and List of international goals scored by Cristiano Ronaldo — which gets updated every time he scores a goal! It's. A. Freakin'. Encyclopedia!

Even on topics that are relevant to an encyclopedia, there's this resistance to ever removing anything because, well, someone wrote it, and isn't more always better? Doesn't help that the length of an article is too often erroneously viewed as an indicator of the subject's importance.

Computing articles are not immune to this effect. Now we have whole articles on things like XRDS, a particular XML file format — with the complete source of an "example XRDS document" embedded. WHY??? Wikipedia is not a data science textbook or reference manual, and if (as Elphion claims) people come here to find out these things, then we should find more ways to encourage them to use proper reference materials instead.

Honestly, policing all of this crap is beyond the abilities of those who care to reduce, rather than expand, the wiki's amount of unencyclopedic information, so it's never going to get cleaned up. But our failure to hold back the tide of irrelevance doesn't make those things relevant or encyclopedic. Arguments like WP:ILIKEIT and WP:ITSUSEFUL don't, either. And where does this code come from, anyway? Do we have valid WP:CITATIONs for the origin of the code? If editors are writing the code themselves, and it sounds like they are, then that's original research — a much bigger concern — and again, it does not belong here. -- FeRDNYC (talk) 23:13, 23 October 2018 (UTC)

Point? Andy Dingley (talk) 23:18, 23 October 2018 (UTC)

@Andy Dingley: "I agree with Wtshymanski, the pure-OR, unencyclopedic source code listing should be dropped from the article." Apologies if my roundabout path to that point made it unclear. -- FeRDNYC (talk) 12:22, 10 November 2018 (UTC)

(And I see that it was, making my late response here rather pointless. Sorry about that.) -- FeRDNYC (talk) 12:29, 10 November 2018 (UTC)

• So what are you advocating? "Drop the unencyclopedic stuff from the encyclopedia" is rather a tautology. But what do you see as unencyclopedic?

I think we should have some source code here, as an example of comprehensible procedural code to generate Gray codes. It should be here to illustrate this process, not to be an archive of editors' favourite languages. One example should be sufficient. The language chosen should not be pseudocode, as decades of pseudocode has yet to produce anything more comprehensible than a typical language. Personally I hate C, but I'd accept using C here because a C example would be simple enough to be widely comprehensible (C's loop statement is widely known and copied). C would also plausibly be pasteable, compilable and runnable, which is its own advantage. Nor are C's shortcomings evident in this example.

There is no need for a second language example.

Do you want to see "unencyclopedic" code samples removed, or all of them? Andy Dingley (talk) 13:36, 10 November 2018 (UTC)

Up to perhaps ten consecutive lines of code or pseudocode might make sense to illustrate a point, and as there may be more than one point to illustrate, this may occur more than once in the article (and done properly, I am in favour of this). Longer code segments with several lines of comments in the comment syntax of the code language used is absurd in an encyclopaedia article. I think the people wanting to include the code should revise it carefully, keeping in mind it will be gibberish to many readers, and that we primarily communicate in English (and sometimes in pictures), not in coding language. Otherwise, I believe the code should be removed. Points that cannot be made in English probably don't belong in the encyclopaedia at all.--Nø (talk) 18:39, 21 November 2018 (UTC)

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 [2] 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 [3]) 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)

The George Stibitz article links his 1941 patent which describes a code: "A feature of the invention. is the use of a four place, permutation code for representing the digits of the decimal system characterized by the fact that the code for each such digit is the inverse of the code of the nine's complement thereof." But from Table 1 I'd say it's an ordinary binary excess-3 code, not a Gray excess-3, I guess I was mistaken in thinking that the Wilkes book was on the right track for the Gray variant. Dicklyon (talk) 17:41, 23 May 2020 (UTC)

So none of these before the 1956/58 patent is what you're looking for, I guess. Dicklyon (talk) 17:47, 23 May 2020 (UTC)

And there's another patent filed in 1956 with Turvey and others at ITT that doesn't name the code but uses an excess-3 Gray. I wonder if these guys invented it and applied the two names they combined, Gray for the reflected binary property and Stibitz for the excess-3 (applied the names in the Swiss version). Dicklyon (talk) 17:57, 23 May 2020 (UTC)

This 1963-filed patent cites the one above and calls it a Gray excess-3 code. I haven't look at everything else it cites. Dicklyon (talk) 18:08, 23 May 2020 (UTC)

OK, I checked their other 2 cited patents, and this 1954-filed UK patent has decimal Gray codes in 5 variants, probably one of which is excess 3. They prefer their "Example II" code, but it's not clear to me if that's excess-3. Dicklyon (talk) 18:19, 23 May 2020 (UTC)

Bottom line, I think, is this: some people adapted Gray code to "excess 3" for decimal use. They noticed Stibitz had done excess-3 for regular binary. So they combined the names. Why this show up in the Swiss version, and not the US version, of the Turvey patent is hard to fathom. Perhaps the Swiss examiner asked them to cite Stibitz. There's also a german version, with "Stibitz-Gray-Kode (Excess-3-Kode); maybe we need to search the Kode spelling more. Dicklyon (talk) 23:25, 24 May 2020 (UTC)

Knuth also points out that Stibitz had a Gray code already in this 1941-filed patent. But I see no connection to the excess-3 Gray there. Dicklyon (talk) 23:31, 24 May 2020 (UTC)

Actually, Knuth refers to Stibitz's 1941/1943 patent which presents the same code as used by Frank Gray a couple of years later (1947/1953), not what became known as Stibitz-Gray code (the Excess-3 Gray code variant). So, Stibitz was involved with the introduction of both, Excess-3 code aka Stibitz code (apparently in the late 1930s) and also with Gray code some years later, but apparently not with the combination of both, for which I too could not find an earlier source than the 1956/1958 Turvey patent you already mentioned.

--Matthiaspaul (talk) 23:46, 21 December 2020 (UTC)

Proposal: Rotate table in "Related codes"

Two years ago, in an attempt to keep the encoding examples in § Related codes from blowing out beyond the page width, I moved the (IMHO excessive, but that's editorializing) citations out of the table headings into a separate row below the inner tables. That even worked, for a time. But, in the intervening two years, more and more variations have been added and the total width has only grown. As a result, we're right back where we started.

Since the smart money is on that trend inevitably continuing, the list of variations (and therefore the table width) will only grow. However, the list of decimal digits is not likely to grow, so I'm going to propose a solution that embraces these dual realities: Rotating the table. The result may not look familiar, and won't conform to "normal" tabular representations of Gray codes, but it's the only format that's able to handle being expanded with an indeterminate number of alternative representations. Tables can grow indefinitely in the vertical direction; not so horizontally.

So I propose this for the revised format:. It's still wider than I'd like, but at least it won't grow any wider. (Well... except for the slight increase that will be caused by some of the longer names, when all of the rows are added.)

	Decimal 0					Decimal 1					Decimal 2					Decimal 3					Decimal 4					Decimal 5					Decimal 6					Decimal 7					Decimal 8					Decimal 9
	4	3	2	1		4	3	2	1		4	3	2	1		4	3	2	1		4	3	2	1		4	3	2	1		4	3	2	1		4	3	2	1		4	3	2	1		4	3	2	1
Gray	0	0	0	0		0	0	0	1		0	0	1	1		0	0	1	0		0	1	1	0		0	1	1	1		0	1	0	1		0	1	0	0		1	1	0	0		1	1	0	1
Paul	1	0	0	1		0	0	0	1		0	0	1	1		0	0	1	0		0	1	1	0		0	1	1	1		0	1	0	1		0	1	0	0		1	1	0	0		1	1	0	1
Glixon	0	0	0	0		0	0	0	1		0	0	1	1		0	0	1	0		0	1	1	0		0	1	1	1		0	1	0	1		0	1	0	0		1	1	0	0		1	0	0	0
⋮

Obviously, all of the currently-represented codes would be transferred. I just didn't feel like possibly wasting my time transferring all of them, so first I'm seeking consensus regarding the basic concept. That being said, the conversion is fairly easy because the table code turns out to be surprisingly similar to the current tables' source: each code's row is exactly the same as the previous table's content for that code, but with all of the row separators removed. The only other change required when adding row(s) is to increase the rowspan= value on the cells that separate each heading in the second row. Thoughts? -- FeRDNYC (talk) 18:06, 6 December 2020 (UTC)

I forgot to add, for an even better fit with the site template, this could even be split into two sections — there's no reason the digits 0 – 9 have to all be displayed side-by-side, the table could easily be chopped in half and laid out as a table for the digits 0 – 4, then a second table below covering 5 – 9. -- FeRDNYC (talk) 06:27, 12 December 2020 (UTC)

I planned to rotate the table to reduce its width and add some data for some while. However, to help readers recognize the patterns, symmetries, and differences it is important to preserve the general appearance. This would not be possible with your proposed scheme. However, I think, I found another way to rotate the table addressing all requirement.

--Matthiaspaul (talk) 23:46, 21 December 2020 (UTC)