Share
Explore BrainMass

# Gray Code

PROBLEM: For what N is it possible to list all the positive integers less than N in a
Gray code, i.e., in such a way that successive numbers differ in exactly one
position when the numbers are represented in binary form? For example we can
do so for N = 4 since the numbers 1, 2, 3 can be listed as 01, 11, 10 in binary
form, whereas for N = 5 the numbers 1, 2, 3, 4 cannot be listed in a Gray code.
SOME WORK DONE: Note first of all that we are considering
?
N &#8805; 2 since there are no
positive integers less than N if
?
N < 2. To get some more information, let us consider all
?
2 &#8804; N &#8804;16.
Number Binary Form Number Binary Form
1 0001 9 1001
2 0010 10 1010
3 0011 11 1011
4 0100 12 1100
5 0101 13 1101
6 0110 14 1110
7 0111 15 1111
8 1000 16 10000
Next we consider for what N is it possible to list all the positive integers less than N in a
Gray code, i.e., in such a way that successive numbers differ in exactly one position when
the numbers are represented in binary form. We have
N Can positive integers
?
&#8804; N be listed in a Gray
code?
Gray code Decimal listing
2 Yes 0001 1
3 No
4 Yes 0001, 0011, 0010 1, 3, 2
5 No
6 No
7 Yes 0001, 0011, 0010, 0110, 0100, 0101 1, 3, 2, 6, 4, 5
8 Yes 0001, 0011, 0010, 0110, 0100, 0101, 0111 1, 3, 2, 6, 4, 5, 7
9 No
10 Yes 1000, 1001, 0001, 0011, 0010, 0110,
0100, 0101, 0111
8, 9, 1, 3, 2, 6, 4, 5,
7
11 Yes 1010, 1000, 1001, 0001, 0011, 0010,
0110, 0100, 0101, 0111
10, 8, 9, 1, 3, 2, 6,
4, 5, 7
12 Yes 1011, 1010, 1000, 1001, 0001, 0011,
0010, 0110, 0100, 0101, 0111
11, 10, 8, 9, 1, 3,
2, 6, 4, 5, 7
13 * No
14 Yes 1011, 1010, 1000, 1001, 0001, 0011,
0010, 0110, 0100, 1100, 1101, 0101, 0111
11, 10, 8, 9, 1, 3,
2, 6, 4, 12,13, 5, 7
15 * No
16 Yes 1011, 1010, 1000, 1001, 0001, 0011,
0010, 0110, 0100, 1100, 1101, 0101,
0111, 1111, 1110
11, 10, 8, 9, 1, 3,
2, 6, 4, 12,13, 5, 7,
15, 14
I am not 100 % sure about these, however, I cannot find a possible Gray code listing, but
might be able to do so, given more time.
&#8208; See next page for some other additional information that may be useful &#8208;
OTHER INFORMATION THAT MAY BE USEFUL (GOOGLE BOOKS)

\$2.19