0

gray codes for $n = 4 $.

Attempt : The codes for $n = 4 $ :

$0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111$

$0000, 0001, 0011, 0010, 0110, 0111, 0101, 0100, 1100, 1101, 1111, 1110, 1010, 1011, 1001, 1000$

Is the answer true for my question ? Anyone can give me an example about codes, i am still not clear about it.

user273952
  • 319
  • @MikePierce I just edited, it just exclamation mark – user273952 Mar 25 '16 at 06:05
  • In a Gray code, each successive string differs from the previous by a single changed bit. This is not true of your first code: $0001$ and $0010$ have two bits different. – Dan Uznanski Mar 25 '16 at 06:08
  • @DanUznanski I learn from this site http://www.icodeguru.com/Embedded/Hacker's-Delight/090.htm. Do you have any reference about this question ? – user273952 Mar 25 '16 at 06:14

1 Answers1

1

In the binary codes, the term distance is defined as:

Distance: Number of bits which one bitstring differs from another bitstring.

For example: $$ \begin{align} d(0010,0011) &= 1 \mbox{ (different bits)} \\ d(1010,0011) &= 2 \mbox{ (different bits)} \\ d(1111,0000) &= 4 \mbox{ (different bits)} \\ \end{align} $$

Now, it is good to remember that the order in which is defined a code is extremely important. This is because the concept of code is precisely encode a set of symbols in others.

So, never lose sight that the order of a code is important.

Your problem then lies in the definition of gray code:

Gray Code-$n$: is that two consecutive bitstrings should always have distance equals to 1.

Again, order is importante here to define "consecutive bitstrings". In this way, you can build a Gray code of $n=4$ (in red, the bit that diffiers from one bitstring to each consecutive bitstring): $$ \begin{matrix} \mbox{Hex Code} & \mbox{Gray Code} & & & & & & \mbox{Hex Code} & \mbox{Gray Code} \\ \hline 0 & 0000 & & & & & & 8 & {\color{red} 1}100 \\ 1 & 000{\color{red} 1} & & & & & & 9 & 110{\color{red} 1} \\ 2 & 00{\color{red} 1}1 & & & & & & A & 11{\color{red} 1}1 \\ 3 & 001{\color{red} 0} & & & & & & B & 111{\color{red} 0} \\ 4 & 0{\color{red} 1}10 & & & & & & C & 1{\color{red} 0}10 \\ 5 & 011{\color{red} 1} & & & & & & D & 101{\color{red} 1} \\ 6 & 01{\color{red} 0}1 & & & & & & E & 10{\color{red} 0}1 \\ 7 & 010{\color{red} 0} & & & & & & F & 100{\color{red} 0} \\ \end{matrix} $$

If you look carefully , this code actually has an interesting property is that a Gray code of $n$, can be generated from a reflection of a Gray code of $n-1$. By example, Gray code $n=1$: $$ \begin{matrix} \mbox{Hex Code} & \mbox{Gray Code} \\ \hline 0 & 0 \\ 1 & 1 \\ \end{matrix} $$ This generates Gray code $n=2$ (blue the reflected bits, green the fill bits): $$ \begin{matrix} \mbox{Hex Code} & \mbox{Gray Code} \\ \hline 0 & {\color{green}0}{\color{blue} 0} \\ 1 & {\color{green}0}{\color{blue} 1} \\ \hline 2 & {\color{green}1}{\color{blue} 1} \\ 3 & {\color{green}1}{\color{blue} 0} \\ \end{matrix} $$ And this generates Gray code $n=3$ (blue the reflected bits, green the fill bits): $$ \begin{matrix} \mbox{Hex Code} & \mbox{Gray Code} \\ \hline 0 & {\color{green}0}{\color{blue}0}{\color{blue}0} \\ 1 & {\color{green}0}{\color{blue}0} {\color{blue}1} \\ 2 & {\color{green}0}{\color{blue}1} {\color{blue}1} \\ 3 & {\color{green}0}{\color{blue}1} {\color{blue}0} \\ \hline 4 & {\color{green}1}{\color{blue}1} {\color{blue}0} \\ 5 & {\color{green}1}{\color{blue}1} {\color{blue}1} \\ 6 & {\color{green}1}{\color{blue}0} {\color{blue}1} \\ 7 & {\color{green}1}{\color{blue}0}{\color{blue}0} \\ \end{matrix} $$ And go on...

Noir
  • 703
  • You can start with $0\to0000$ and generate one gray code for $n=4$. Or you can start with $0\to0001$, and generate other gray code for $n=4$. But both codes doesn't the same, because for one code $0$ is equivalent to $0000$, and for other code $0$ is equivalent to $0001$. So, you two different Gray codes for $n=4$. Again, order is important. – Noir Mar 25 '16 at 08:33
  • No, doesn't. See this example. The first gray code:

    $$0000,0001,0011,0010,0110,0111,0101,0100,1100,1101,1111,1110,1010,1011,1001,1000$$

    Other gray code:

    $$0001,0011,0010,0110,0111,0101,0100,1100,1101,1111,1110,1010,1011,1001,1000,0000$$

    See that this last gray code starts with $0001$ and ends with $0000$, and the sequence is the same, but code doesn't the same because encoded $0\to 0000$ in first gray code and $0\to 0001$ in second gray code. You understand?

     – Noir Mar 25 '16 at 09:05
  • yes, I got it now. Thank you – user273952 Mar 25 '16 at 09:25
  • Your welcome! :) – Noir Mar 25 '16 at 09:30