gray code

格雷码(gray code/reflected binary code),循环二进制单位距离码,是任意两个相邻编码只有一位差异的编码,属于可靠性编码。

一个简单的例子,普通二进制中011->100(3->4)时,三个bit位都需要取反,因此在三位未完全转换时,存在6种中间状态(之转换了一位+剩一位没转换),但是格雷码中010->110只需要一位取反,避免了其他的可能。

二进制转格雷码

假设四位格雷码起始为0000,则二进制abcd对应的格雷码为(0^a)(a^b)(b^c)(c^d)

二进制 格雷码
000 000
001 001
010 011
011 010
100 110
101 111
110 101
111 100
1
gray = binary ^ (binary>>1)

格雷码转二进制

1
2
3
4
5
6
7
gray = binary ^ (binary>>1)
# 两边同时异或 'gray >> 1',即 '(binary ^ (binary>>1)) >> 1'
gray ^ (binary ^ (binary>>1)) >> 1 = binary ^ (binary>>1) ^ (binary>>1) ^ (binary>>2)
gray ^ (binary ^ (binary>>1)) >> 1 = binary ^ (binary>>2)
# 可以发现等号右边 (binary>>1) 变成了 (binary>>2)
# 以此类推,两边继续异或下去,当 (binary>>n) == 0时,右边就剩binary了,二左边自然就是二进制表示了
# ...

其他

其他生成格雷码的方法还有镜像法,观察以0为起始码的格雷码即可发现该规律