Give two distinct codes for $n = 4 $

Question

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.

Answer 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...