8
\$\begingroup\$

After googling, I found that a Gray code is not unique and the only requirement for a sequence of binary strings to be a Gray code is that two adjacent binary strings differ by only one bit. Can we consider 010110100000 to be a Gray code sequence?

If so, it seems that many sequences comply with the requirement to be a Gray code, so when we apply a Gray code in real life, such as for error correction, can we use our own Gray code (such as defining a sequence of my choosing that meets the requirement of being a Gray code)?

\$\endgroup\$
4
  • 6
    \$\begingroup\$ @Antonio51 that is a possible, yet very wide definition of a Gray code. It for example also allows to call a code for 16 different values "Gray code" if you used 15 bit values to represent these 16 different values, and just do the sequence 1. 000…000, 2. 100…000, 3. 110…000, 4. 1110…000, …, 14.111…110, 15. 111…111. Is allowing arbitrary many bits for representing values a useful definition? IMHO, not. Gray's patent expicitly refers to binary-reflected codes, and the definition you found looks like what a lazy student wrote down as a note, not an actual definition. \$\endgroup\$ Commented Nov 22, 2023 at 12:52
  • 6
    \$\begingroup\$ @Antonio51: geeksforgeeks is one of the least authoritative sites you could cite. Most of the stuff I've found there is tutorials written by beginners as they try to understand a new subject, so misunderstandings and misconceptions are not rare. Without any voting mechanism, and comments not displayed prominently, many problems go unfixed with future readers none the wiser. \$\endgroup\$ Commented Nov 22, 2023 at 21:10
  • 6
    \$\begingroup\$ Note that you used 3 bits to encode 4 states. \$\endgroup\$ Commented Nov 22, 2023 at 23:20
  • \$\begingroup\$ @LamarLatrell: In many situations, the number of states that could be encoded with the available bits will exceed the number of states that need to be handled, and codes other than a binary reflected code may be advantageous. In a binary reflected code, the state of one of the bits will be depedent upon the state of all of the remaining bits. In something like a Johnson counter, by contrast, each bit's state is dependent upon only one other bit (or maybe two bits outside itself if one needs the counter to recover from arbitrary invalid states). \$\endgroup\$
    – supercat
    Commented Nov 25, 2023 at 19:41

4 Answers 4

17
\$\begingroup\$

Your example is a code that only changes in a single position between successive elements. But: It's not a well-chosen code, especially not one found as binary reflected code, the method described in said patent to construct such codes, because it uses 3 bits to encode only four states. That's superfluous, 01, 11, 10, 00 would have done the same, and having more bits doesn't help.

I'll go and say that if you want to Gray-encode a sequence of \$2^n\$ values, a Gray code must consist of words of exactly \$n\$ bits length, otherwise the encoding is wasteful.

Then, Gray refers to binary-reflected codes in his patent.

Let us look at these: by design, binary-reflected codes not only have a Hamming distance between successive values, but also between the first and the last element – by design. I'd require that property from any code you're calling Gray Code. Transistor's answer's rotational encoding disk graciously illustrates why: only these can encode things that happen in cycles (angles, phases) with the desired 1-bit difference between successive values.

Therefore, any cyclic shift of a binary-reflected code still has the Hamming distance property you want – neighbors differing only in a single bit.

I'm willing to call these shifts of binary-reflected codes "Gray Codes" as well. So, if you construct one \$2^n\$-length Gray code, you automatically get \$n\$ Gray codes, as there's inherently \$n\$ positions by which you can shift the code.

So, yes, there's a lot of them – since we can always a construct a binary-reflected code for any word length \$n\in\mathbb N\$, and due to the shifting, there's at least \$n\$ different Gray Codes.

There's actually more! You can choose a Gray Code according to your needs. Due to shift invariance as described above, you can freely choose any sequence element from a Gray Code you find as a starting point – handy if you don't want to start with the all-0 code word, for example. But, there's also opportunities to change properties.

Binary-reflected codes have bad properties if you want, for example, send them through a parallel data connection, where the first physical line transports the first bit, the second line the second bit, and so on. Look at the disk in Transistor's answer: the outermost bit toggles every two code elements, the next-inner every four, and so on. Therefore, the physical line to transport the outermost bit would need to have \$2^n\$ the bandwidth than the innermost one! Terrible! Different kinds of cables for different bits, with different delays? That is very annoying to implement. So, balanced Gray Codes change bits by a different order. There's also at least one set of \$n\$ such codes that you can find (again, due to finding one meaning finding \$n\$ that are just cyclic shifts) for \$n\$-length words for \$n=2^m,\quad m\in\mathbb N\$, and because by definition binary-reflected codes (and their shiftings) are not possibly balanced and hence a disjoint set, we've now already found at least \$2n\$ different Gray Codes for power-of-two word lengths.

So, yes, you get to choose your Gray code.

\$\endgroup\$
11
  • 2
    \$\begingroup\$ Some one-change-at-a-time encodings may not assign values to all combinations of bit values, but be advantageous for other reasons. For example, there's a rotary encoder that has an 8-bit output, and has the property that rotating a wheel right 1/8 turn will cause the code to be rotated one bit to the right, which allows the encoder to be simpler than a binary reflected code encoder. \$\endgroup\$
    – supercat
    Commented Nov 22, 2023 at 23:17
  • 1
    \$\begingroup\$ @MarcusMüller I'm an engineer. I know. I still can't find the stuff I was reading, but from my POV it was interesting that- at least according to the authors- once tags got big it took a substantial mount of time to precompute the "best" set with guaranteed Hamming distance. \$\endgroup\$ Commented Nov 23, 2023 at 12:59
  • 2
    \$\begingroup\$ In fact, any bit permutation of the "standard" binary-reflected Gray code is still a Gray code, so there are at least \$n! = 1 \cdot 2 \cdot 3 \cdots (n-1) \cdot n\$ equivalent \$n\$ bit Gray codes. You can also invert any bit(s) of the code, giving a total of \$2^n \cdot n!\$ equivalent codes. And that still doesn't include e.g. the balanced Gray codes (which also have at least \$2^n \cdot n!\$ equivalents each). \$\endgroup\$ Commented Nov 23, 2023 at 13:25
  • 1
    \$\begingroup\$ @MarkMorganLloyd yeah, I was very tempted to write a short program to just list all Gray codes for a given block length, but out of the \$2^n!\$ possible non-repeating sequences of \$n\$ length words, it's still dauntingly many that you'd have to try in a naive way ("start with an arbitrary word, flip one bit, giving you the next word, flip any other bit than in the last step, check whether you've already had that word…, flip any bit (aside from the one that you flipped last step)…"); \$n\cdot (n-1)^{n-1}\$ is still a metric fudgeton of a lot. \$\endgroup\$ Commented Nov 23, 2023 at 14:43
  • 1
    \$\begingroup\$ @MarcusMüller Elsewhere, I once asked a question about the knight's tour problem and was rewarded by a couple of solutions within minutes. It turned out that the elderly gentleman who provided them had access to top-of-the-line constraint-solving software, and used it to supplement his pension by designing Sodoku puzzles of carefully-tailored difficulty. \$\endgroup\$ Commented Nov 23, 2023 at 14:53
11
\$\begingroup\$

Tip: "Gray Code" is a proper noun so it gets capitalised.

I found that Gray Code is not unique ...

Your meaning is unclear here. If you mean that it can repeat within itself than that is correct. The most common example would be a 2-bit rotary encoder which would have a sequence 00-01-11-10.

... and the only requirement for a sequence of binary numbers to be gray code is that two adjacent binary numbers differ by only one bit.

That is generally corrct.

So, can we consider 010->110->100->000 to be a sequence of gray code?

It looks OK to me but we can see that the third bit is redundant as it never changes.

If so, it seems that many sequences of code comply with the requirement to be Gray Code, then when we apply Gray Code in real life, such as error correction, we can use our own Gray Code (such as defining a sequence of code I like that meets the requirement of being Gray Code)?

I suspect that this is not quite true. As far as I can see (see the Wikipedia article, for example) a true Gray Code as envisaged by Gray is a "reflected binary code". This is most easily seen in the patterns of absolute rotary encoders which use a true Gray Code.

enter image description here

Figure 1. Encoder pattern. Source: Rozum.

There's a good little paper on Encoder.com which explains some techniques that I wasn't aware of regarding conversion of Gray to binary. You might be interested.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Tip: "Gray" is capitalised since even minimum research will show that it was somebody's name. "Code" doesn't have to be, since as OP points out it's not unique. \$\endgroup\$ Commented Nov 23, 2023 at 8:28
  • \$\begingroup\$ @MarkMorganLloyd: By interesting linguistic coincidence, the first time I encountered the term Gray code was in an article about a grayscale video digitizer. \$\endgroup\$
    – supercat
    Commented Nov 23, 2023 at 17:27
  • \$\begingroup\$ I think I can see where it could overlap with dithering etc. In my case it was in the context of Karnaugh charts (contrary to what some believe, 7400-series TTL did exist when I was a student). \$\endgroup\$ Commented Nov 23, 2023 at 19:51
  • \$\begingroup\$ "corrct" is incorrect, was it intentional? :) \$\endgroup\$ Commented Nov 25, 2023 at 18:56
6
\$\begingroup\$

According to Wikipedia:

In principle, there can be more than one such code for a given word length, but the term Gray code was first applied to a particular binary code for non-negative integers, the binary-reflected Gray code, or BRGC.

However, in practice I have seen the term "Gray code" applied very loosely to any sequence where a single bit is changed.

\$\endgroup\$
5
\$\begingroup\$

If you were to use scholar.google for a search on Gray codes, you will find that there is quite a bit of mathematical literature on the existence of (generalized) Gray codes. In Combinatorics, a Gray code is any complete enumeration of binary numbers of a given length (padded with zeroes at the beginning if necessary) so that any two consecutive elements of the enumeration change in only one bit. In addition, the beginning and the end element of the enumeration also have to differ by at most one digit. Your example is not a Gray code because it is not a complete enumeration, you would need to have 2**3 = 8 elements.

Knuth's Art of Computer Programming Volume 4 has a lot of information on Gray codes and their uses.

As other answers already pointed out, the original Gray code was a specific code. The term Gray code for the generalizations is however already well-established.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.