0
$\begingroup$

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 ?

A. the number of possible Gray codes is even

B. the number of possible Gray codes is odd

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

D. In any Gray code, if two strings are separated by k other strings in the ordering, then they must differ in exactly k bits

E. none of the above

==================================================================== My take-

Now, consider n=1. The only Gray code possible is {0,1}. Hence no of Gray code = odd for n=1.

For n=2 only two Gray code exists {00,10,11,01} and {00,01,11,10}. Thus no of Gray code = even for n=2.

So, what should be the answer? A or E.

Also, how to check option C and D?

Any help to understand this question is highly appreciated.

$\endgroup$
1

1 Answer 1

0
$\begingroup$

C and D are false because in $000, 001, 011, 010$ we have only one bit difference for two strings separated by $2$ strings. You already showed A and B wrong.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .