Official Ans - Option A.

The Gateway to Computer Science Excellence

+12 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$?

- the number of possible Gray codes is even
- the number of possible Gray codes is odd
- 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
- In any Gray code, if two strings are separated by $k$ other strings in the ordering, then they must differ in exactly $k$ bits
- none of the above

+13 votes

Best answer

- 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.
- 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 that gray codes could be only even or only odd.

Hence, option **e **is correct.

PS: Official answer given was A - probably a mistake

+2

I think option A is correct.

It says that "the number of possible Gray codes is even" or the number of gray codes possible from n bits. It doesn't say anything about the particular gray code that it is odd or even.

Please clarify

It says that "the number of possible Gray codes is even" or the number of gray codes possible from n bits. It doesn't say anything about the particular gray code that it is odd or even.

Please clarify

+4

The number of Gray codes possible will always be even. Hence, option A is correct. When n = 1, possible gray codes =2. When n =2, number of gray codes =4 and so on.

0

set2018

why is that? 00,01,11,10 make gray code. Why would you discard 00 and 11? In the question, they have included 000&111 for N=3.

why is that? 00,01,11,10 make gray code. Why would you discard 00 and 11? In the question, they have included 000&111 for N=3.

+2

line in question "the ordering (000, 100, 101, 111, 110, 010, 011, 001) is a Gray code"

says that whole order is gray code and not just single string is gray code.

even though official answer is A , it can be incorrect

I think above answer is perfect

says that whole order is gray code and not just single string is gray code.

even though official answer is A , it can be incorrect

I think above answer is perfect

0

No, that is not true.

C and D are false because in 000,001,011,010000,001,011,010 we have only one bit different for two strings separated by 22 strings.

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

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.

+1 vote

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.

–1 vote

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 *n *bits, although that will also be even and equal to $2^{n}$.)

52,345 questions

60,483 answers

201,810 comments

95,288 users