首先，很多人一开始接触到格雷码一定见过下表：
| 二进制 | 格雷码 |
|---|---|
| 0000 | 0000 |
| 0001 | 0001 |
| 0010 | 0011 |
| 0011 | 0010 |
| 0100 | 0110 |
| 0101 | 0111 |
| 0110 | 0101 |
| 0111 | 0100 |
| 1000 | 1100 |
| 1001 | 1101 |
| 1010 | 1111 |
| 1011 | 1110 |
| 1100 | 1010 |
| 1101 | 1011 |
| 1110 | 1001 |
| 1111 | 1000 |
但是，你们知道二进制和格雷码之间是存在公式转换关系的吗？
我们定义二进制数为x[n - 1:0]，y[n - 1:0]（这里采用的Verilog的表示法）
则y = x ^ (x >> 1) （这里采用的C/Verilog语言的异或/右移符号）
我们可以认为y[k] = x[k] ^ x[k + 1]（定义x[n] = 0）
那么，对于这么一种定义，你是否“显然”觉得每一个二进制数对应的格雷码都不相同？或者进一步说，是否二进制数与格雷码之间一一对应的关系是“显然”的，我觉得未必，下面我们来证明二者的一一对应关系：
命题1：证明所有二进制数对应的格雷码都不同
我们定义二进制数为x与p，格雷码为y和q（位宽定义与上述一致）
则
y[k] = x[k] ^ x[k + 1]
q[k] = p[k] ^ p[k + 1]
若y = q，则可以推出y[n - 1] = q[n - 1]，又知y[n] = q[n] = 0（假定定义），则可以推出x[n - 1] = p[n - 1]，我们也知道y[n - 2] = q[n - 2]，因此可以推出x[n - 2] ^ x[n - 1] = p[n - 2] ^ p[n - 1]，我们刚才已经推出x[n - 1] = p[n - 1]，因此可以推出x[n - 2] = p[n - 2]，继续推下去，最终可以推出x[0] = p[0]，因此x = p
我们这里证明的是“对于两个相同的格雷码而言，其对应二进制数都一致”，也就同时证明了其逆反命题的成立性“对于两个不一致的二进制数而言，其对应的格雷码都不一致”。
命题2：证明所有格雷码对应的二进制数都不同
我们定义二进制数为x与p，格雷码为y和q（位宽定义与上述一致）
则
y[k] = x[k] ^ x[k + 1]
q[k] = p[k] ^ p[k + 1]
若x = p，则可以很容易推出对于每一个k而言，y[k] = q[k]，因此“对于两个相同的二进制数而言，其对应格雷码都一致”这一命题被证明，也就同时证明了其逆反命题的成立性“对于两个不一致的格雷码而言对应的二进制数都不同”。
由命题1与命题2，我们就可以推出：“二进制数与格雷码是一一对应的”。
我们大家都知道，格雷码一个最重要的特点是：相邻的两个格雷码其汉明距离只有1（所谓相邻是指格雷码对应的二进制数的绝对值之差为1，所谓汉明距离为1是指的两个格雷码只有一个二进制位不同）。
我们来证明这个问题：
我们定义二进制数为x与p，格雷码为y和q（位宽定义与上述一致），同时x = p + 1
则
y[k] = x[k] ^ x[k + 1]
q[k] = p[k] ^ p[k + 1]
我们将x分为两种情况：
1、x的最后一位为1，则此时x与p的格雷码为：
| x | x[n - 1] | x[n - 2] | ... | x[1] | 1 |
|---|---|---|---|---|---|
| x >> 1 | 0 | x[n - 1] | ... | x[2] | x[1] |
| y | 相同 | 相同 | 相同 | 相同 | 不同 |
| p | p[n - 1] | p[n - 2] | ... | p[1] | 0 |
| p >> 1 | 0 | p[n - 1] | ... | p[2] | p[1] |
| q | 相同 | 相同 | 相同 | 相同 | 不同 |
很显然，此时当k>=1时，x[k] = p[k]，因此y[k] = q[k]，只有y[0] != q[0]，因此在这种情况下，相邻两个格雷码的汉明距离确实为1。
2、x的最后一位为0，则此时x与p的格雷码为：
| x | x[n - 1] | x[n - 2] | ... | x[m] | 1 | 0 | 0 | ... | 0 |
|---|---|---|---|---|---|---|---|---|---|
| x >> 1 | 0 | x[n - 1] | ... | x[m + 1] | x[m] | 1 | 0 | ... | 0 |
| y | 相同 | 相同 | 相同 | 相同 | 不同 | 1 | 0 | ... | 0 |
| p | p[n - 1] | p[n - 2] | ... | p[m] | 0 | 1 | 1 | ... | 1 |
| p >> 1 | 0 | p[n - 1] | ... | p[m + 1] | p[m] | 0 | 1 | ... | 1 |
| q | 相同 | 相同 | 相同 | 相同 | 不同 | 1 | 0 | ... | 0 |
很显然，此时当k>=m时，x[k] = p[k]，因此y[k] = q[k]，当k<m时，显然10...0减1等于01...1，从上述运算可以看出，对于y和q而言仅y[m - 1] != q[m - 1]，因此在这种情况下，相邻两个格雷码的汉明距离确实为1。
综上所述，相邻的两个格雷码其汉明距离只有1。