Talk:Gray code

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 [1]) 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)

Baudot

Can Baudot's use of reflected binary codes be explained, or even verified? What I find in sources don't show any Gray-like code, nor how we might have used them. Dicklyon (talk) 01:33, 19 December 2020 (UTC)

I mean, I can see that if you sort his codewords in Gray-code order, the vowels come out first, in alphabetical order, then a few things and the consonants in order. Presumably there's a reason for that. But what? I can't see a relationship between how Baudot codes were used and the properties of Gray codes. And I can't find a source that mentions it. Anyone? Dicklyon (talk) 03:16, 21 December 2020 (UTC)

(edit-conflict) Hi Dick, I have meanwhile added many references describing this in better details. I'm still trying to dig deeper in the history to find answers to a few of my own open questions, but regarding your question, what I found in the sources so far is that this particular arrangement was chosen to make it easier for the operator to memorize the patterns, and possibly also to make it easy to enter the chords. The synchronous Baudot telegraph used a chorded keyboard and the operator's input had to be manually kept in sync with the machine while keying in the chords, so this was very timing-sensitive.

One source also mentioned that the codes were arranged in order of frequency, but this is wrong (the later Murray code was arranged this way, but not the 5-level Baudot code).

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

What sources say such things? My impression was that it was more about the scanning machine's teeth, nothing to do with the operator. Dicklyon (talk) 04:25, 22 December 2020 (UTC)

I trimmed that section down. I couldn't find anything in sources to suggest the Mimault's telegraph used a Gray-like code and there was a bunch of text and excess refs unrelated to Gray code. Baudot and his code have their own articles. Dicklyon (talk) 23:36, 21 December 2020 (UTC)

@Matthiaspaul: Could you be so kind as to explain how the material you added back helps understand how the Gray code was used? Can you explain how it was used and why it mattered? Is there a sourced explanation we can incorporate, or just the somewhat cryptic French one? Dicklyon (talk) 20:18, 22 December 2020 (UTC)

@Matthiaspaul: That section on telegraphy remains cryptic and uninterpretable, and has now been bloated up with fancy tables that don't help at all. Why/how do the properties of a Gray code become relevant in that context? I'd delete the section if no relevance can be shown. Dicklyon (talk) 05:33, 29 December 2020 (UTC)

Huh? The section is top relevant here per the sources because it documents the usage of what we now call Gray code or reflected binary code long before Stibitz and Gray, and even by two people independent of each other, Schäffler and Baudot (both in the telegraphy business). Schäffler's usage can be traced down to a telegraph he produced in 1874 (and Lambert claimed to have shown him this code in 1872). Baudot's usage can be traced down to a telegraph he built in 1875/1876 (many sources attribute this to his 1874 patent, but the prototype documented there still used a 6-level rather than a 5-level code). Baudot's research on this started in 1872 as well. (Mimault - at his time unsuccessfully - claimed priority on some aspects of Baudot's telegraph, including the code, so this would deserve at least being mentioned for NPOV.)

The 1872 date is relevant because it coincidentally matches the date when Gros described his "baguenodier".

The Schäffler and Baudot code tables clearly show that they actually used codes very similar to Gray's. Some of the modern sources (even top RS ones) actually call them "Gray codes".

Like you I want to find answers as to why they used these codes because this is historically interesting, but the question if this belongs here or not is already answered by the fact that they used these codes, not why.

It is relevant to describe the codes as fixed-length 5-level codes - ideally, we would avoid the term 5-bit, as some authors do, because this is long before Shannon's introduction of bits, and even the idea of binary codes was new and terminology non-established (that's why some of the historical descriptions are what you call "cryptic" - they weren't in the context of their times).

As I mentioned already, the Baudot multiplexing telegraph was still a synchronous telegraph and it used a chorded keyboard. The operator's input had to be manually kept in sync with the machine while keying in the chords, which was very timing-sensitive.

These timing constraints could have been one of the reason(s) for why the code was arranged the way it was.

What I also found in the sources is that the code was arranged to be easy to type and remember for the operator. I don't know if this was the primary goal or a by-product of the timing constraints. Either case, it certainly contributed to reducing the error rate and increasing the speed an operator was able to key in the chords while keeping in sync with the machine.

--Matthiaspaul (talk) 14:40, 30 December 2020 (UTC)