1
$\begingroup$

Some Information on Gray Codes

If you're rusty or unfamiliar with Binary Reflected Gray Code, but want to try and help, here is a youtube tutorial explaining what they are:

https://www.youtube.com/watch?v=eGgkcf62xl8

My Question

Looking at some basic Reflected Binary Gray Code sequences:

enter image description here

We can see that the first and last entry of each sequence differ only by one bit. Wikipedia referred to this as the "cyclic property" of gray codes, but did so without citation or further elaboration. I understand why two entries right beside each other would differ by 1 bit, but not why the first and last would. Could anyone explain this to me?

$\endgroup$
1
$\begingroup$

The binary reflected Gray code is defined inductively:

  • The binary reflected Gray code of length $0$ is $G^0 = ()$ (empty list).
  • Let $G^n = (g^n_1, \ldots, g^n_{2^n})$ be the binary reflected Gray code of length $n$. Then the binary reflected Gray code of length $n+1$ is

    $$G^{n+1} = (0g^n_1, \ldots, 0g^n_{2^n}, 1g^n_{2^n}, \ldots, 1g^n_1).$$

For example:

$$\begin{align} G^0 &= ()\\ G^1 &= (0, 1)\\ G^2 &= (00, 01, 11, 10)\\ G^3 &= (000, 001, 011, 010, 110, 111, 101, 100) \end{align}$$

As to your question, the first and last entries of $G^{n+1}$ are defined as $0g_1^n$ and $1g^n_1$, which differ only in the first position (i.e., only by $1$ bit).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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