edited by
3,134 views
20 votes
20 votes

For any natural number $n$, an ordering of all binary strings of length $n$ is a Gray code if it starts with $0^n$, and any successive strings in the ordering differ in exactly one bit (the first and last string must also differ by one bit). Thus, for $n=3$, the ordering $(000, 100, 101, 111, 110, 010, 011, 001)$ is a Gray code. Which of the following must be TRUE for all Gray codes over strings of length $n$?

  1. the number of possible Gray codes is even
  2. the number of possible Gray codes is odd
  3. In any Gray code, if two strings are separated by $k$ other strings in the ordering, then they must differ in exactly $k+1$ bits
  4. In any Gray code, if two strings are separated by $k$ other strings in the ordering, then they must differ in exactly $k$ bits
  5. none of the above
edited by

4 Answers

Best answer
21 votes
21 votes
  1. In the question it is stated that -> Thus, for $n=3$, the ordering $(000, 100, 101, 111, 110, 010, 011, 001)$ is a Gray code.
  2. We have to find orderings such that they start with $0^{n}$, must contain all bit strings of length n and successive strings must differ in one bit. 

Options c and d are clearly wrong. 
Now, consider $n=1$. The only Gray code possible is $\left \{ 0,1 \right \}$. Hence no of Gray code $=$ odd for $n=1$.
For $n=2$ only two Gray code exists $\left \{ 00, 10, 11, 01 \right \}$ and $\left \{ 00, 01, 11, 10 \right \}$. Thus no of Gray code $=$ even for $n=2.$
Thus it is not the case that number of Gray codes is only even or only odd.
Hence, option e is correct.

PS: Official answer given was A - probably a mistake

selected by
6 votes
6 votes

Option A and B says about number of possible gray codes of length n.

"A gray code is  a ordering of all n length binary strings starting with 0^n and successive n length strings will differ by one bit and first and last string also will differ by one bit".

So let's see how many possible gray codes can be found when n=1,2

when n=1 there is only one possibility {0 , 1}

when n=2 there is two possibilities {00,01,11,10} , {00,10,11,01}. It is because the gray code must start with 0^n and we can only have 01 or 10 after 00, and that is why we got two possibilities.

So from above observation we can clearly reject Option A and B because number of possible gray code for a given 'n' can be odd(in case of n= 1 it is 1) and also can be even(in case of n= 2 it is 2).

So A and B can not be our option

Now lets check for Option C and D

Lets take a possible gray code for n = 3 

 {000, 100, 101, 111, 110, 010, 011, 001}

Here 000 and 110 are separated by 3 strings (100,101,111) but they differ by 2 bits So That makes option C and D false.

So from above observations it is clear that Option E is the right choice.

 

3 votes
3 votes
option A is correct!

when n=1 possible gray codes={0,1}=2^1=2

when n=2 possible gray codes={00,01,11,10}=2^2=4

when n=3 possible gray codes={000,001,011,010,110,111,101,100}=2^3=8

and so on ; hence always even.
edited by
0 votes
0 votes

Official answer (option A) is correct.

Number of Gray Codes will always be even. Gray Code is an ordering of codewords.

For eg., in the question, the ordering (000, 100, 101, 111, 110, 010, 011, 001) is a Gray code. 000, 100 and all the other elements of this ordered set are codewords.

For n = 1, we have 2 Gray Codes. {0, 1} and {1, 0}.

For n = 2, we have 8 Gray Codes. {00, 01}, {01, 00}, {00, 10}, {10, 00}, {11, 01}, {01, 11}, {11, 10} and {10, 11}.

Observations :
1. There are $2^{n}$ codewords in every Gray Code of n bits..
2. For a given Gray Code, its reverse will also be a Gray Code.
3. Reverse of a Gray Code will always be distinct from the original Gray Code, as all elements are distinct.

Hence, number of all possible Gray Codes over n bits will always be even. (Don't confuse this with number of codewords in every Gray Code over bits, although that will also be even and equal to $2^{n}$.)

Answer:

Related questions