曾彪彪的个人博客 -- 格雷码总结

格雷码（Gray Code），又称循环二进制码或反射二进制码，是一种二进制数的编码方式。其核心特点是相邻的两个数之间仅有一位二进制数不同。这种特性在数字电路、异步 FIFO、计数器设计以及避免竞争条件等领域有重要应用。可能这些年这个知识点的应用领域比较热门，或者未来这个知识点会用得比较多，所以近几年信奥赛初赛中频繁出现格雷码的题目。

## 格雷码计算

### 反射法
反射法可以手动生成格雷码，反射发的思路是：
抄写上一位格雷码，以及格雷码的反射，所谓反射，就是对称的顺序，也叫逆序，如0，1的反射就是1，0.
对上一位格雷码，前面依次加0，对于反射格雷码，前面依此加1。

格雷码计算方式如下，以4位格雷码为例：
1位格雷码 0，1
2位格雷码  抄写1位格雷码，以及它的反射：
0 1 
1 0，
对于1位格雷码，前面加0，变成 00  01，
对于反射格雷码，前面加1变成11 10，
所以2位格雷码是
 00 01 
 11 10
3位格雷码，抄写两位格雷码如下：
00 01 11 10
10 11 01 00
生成如下，
000 001 011 010
110 111 101 100
4位格雷码，抄写三位格雷码如下：
000 001 011 010 110 111 101 100
100 101 111 110 010 011 001 000
生成如下
0000 0001 0011 0010 0110 0111 0101 0100
1100 1101 1111 1110 1010 1011 1001 1000

### 公式法
给定一个二进制数，其格雷码的计算公式如下：
g=b^(b>>1)。
我们以11为例，它的二进制码是1011
那么g11=b11^b11>>1
 1011
^0101
-----
 1110
 所以，g11=1110，从4位格雷码中，找到第12位格雷码（下标从0开始），是1110，结果正确。

公式推导：
 我们观察格雷码 1110和二进制码1011的关系，发现
 11的格雷码和二进制码的最高位一样，都是1
 从最低为开始，格雷码的值等于当前位与更高位的值的异或运算。
 所以11的格雷码的计算如下：
 G11的最高位为与二进制码一致1，我们从右向做，标记位次依此为第0位，第1位，第2位，第3位，最高位是第三位。
 现在开始计算格雷码的第0位=二进制的第0位^二进制的第1位，二进制数是1011，第0位和第1位分别是1和1，那么格雷码的第0位是0.
 现在格雷码变为1XX0，其中XX表示还未计算。
 计算格雷码第1位=二进制第1位^二进制第2位=1^0=1
 现在g11=1X10
 同理格雷码第2位=0^1=1，最终得到g11=1110。

有了这个结论之后，我们用数学归纳法证明：
 g=b^(b>>1)
 我们假设b由n位组成，b=b_{n-1}b_{n-2}...b_1b_0， 其中b_{i}表示第i+1位，i的范围是[0,n-1]
 对于b=1，我们计算
 g1=1^(1>>1)=1^0=1，公式成立。
 假设对于n位的二进制数，上面公式成立，也就是
 g=b^(b>>1)=b_{n-1}b_{n-2}...b_1b_0 ^ (0b_{n-1}b_{n-2}...b2b_1)公式成立
 也就是g=
  b_{n-1}b_{n-2}...       b_1b_0
 ^0      b_{n-1}b_{n-2}...b_2b_1 
 上面的计算，表达的意思是最高位与b的最高位相同，从第0位开始，每一位的值=b_{i}^b_{i+1}

那么对于n+1位的二进制数：
 g'=b' ^ (b' >> 1)
 设b' = b_{n}b_{n-1}b_{n-2}...b_1b_0
 那么g'= b_{n}b_{n-1}b_{n-2}...b_1b_0 ^ (0b_{n}b_{n-1}b_{n-2}...b_2b_1)
 b_{n}b_{n-1}b_{n-2}...       b_1b_0
^0    b_{n}  b_{n-1}b_{n-2}...b_2b_1

上面代码的意思是：
最高位与二进制最高位相同，从第0位其，g_{i}=b_{i} ^ b_{i+1}，这个结论和n位的二进制计算公式计算吻合，所以公式g=b^(b>>1)成立。

## 格雷码转二进制

通过公式g=b^(b>>1)，可以得到b=g^(b>>1)

这个公式的意思是：b_{i}=g_{i}^b_{i+1}，因为二进制最高位保持与格雷码最高位相同，所以可以知道二进制码的最高位，通过递推，可以得到二进制码。我们举个列子，还是以11为例。
g11=1110，现在计算这个格雷码对应的二进制编码：
b_{3}=g_{3}=1，最高位相等，位次从右到左依此为0，1，2，3位。
b_{2}=g_{2}^b_{3}=1^1=0
b_{1}=g_{1}^b_{2}=1^0=1
b_{0}=g_{0}^b_{1}=0^1=1
所以g11=的二进制码位1011. 计算正确。

格雷码总结

评论(0)