An n-bit Gray code is a way to encode numbers 0, 1, ..., 2n-1 in binary such that any two consecutive numbers (including 0 and 2n-1) differ in exactly one bit. For example, {00, 01, 11, 10} is a 2-bit Gray code, and {00, 10, 11, 01} is the only other one if we assume that 0 must be encoded as 00.
(1) list all the different 3-bit Gray codes.
(2) how many different 4-bit Gray codes can you construct? Explain your answer. It is not necessary to list all of them unless that is the only way you can find them (in that case, you can skip the next part :) .
(3) how many different n-bit Gray codes do you think there will be?
(4) Explain whether it is possible to construct an n-bit binary code such that any two consecutive numbers (including 0 and 2n-1) differ in exactly k bits for k=2 and k=3. Note that when k=1, it is Gray code.