格雷码

格雷码（Gray code）是把一组离散状态排列成序列，使相邻状态只在一个位置发生变化的编码方式。最常见的是二进制格雷码：它列出全部 $n$ 位二进制字，每个出现一次，相邻字的汉明距离为一。若首尾也只差一位，称为循环格雷码。

普通二进制计数从 $011$ 变到 $100$ ，三位都发生变化；一种三位格雷码则按 $000, 001, 011, 010, 110, 111, 101, 100$ 排列。每步只翻一位，最后的 $100$ 也只需翻最高位便回到 $000$ 。这使它适合按单个开关变更状态、增量枚举子集等场景；它本身并不是纠错码。

汉明距离与超立方体

两个长度相同的二进制字的汉明距离，是不同位置的个数。例如 $d_{H} (011, 010) = 1$ ， $d_{H} (011, 100) = 3$ 。把全部 $n$ 位字作为顶点，只连接汉明距离为一的两个字，得到 $n$ 维超立方体图 $Q_{n}$ 。

因此，列出全部状态的格雷码对应这张图中经过每个顶点恰一次的路径；当 $n \geq 2$ 时，循环格雷码对应首尾也相连的环。 $n = 1$ 的序列 $(0, 1)$ 仍满足循环相邻字只差一位，但 $Q_{1}$ 只有一条边，不构成简单图中的环。这个图论解释约束的是状态的先后关系，不表示二进制数值的大小顺序。^[1]

三维立方体的八个顶点标注三位二进制，粗线按反射格雷码依次连成环 — 粗线按 000→001→011→010→110→111→101→100→000 行进；每条粗边只改变一个坐标。空间图采用斜投影。

反射构造与完整归纳证明

二进制反射格雷码从 $G_{1} = (0, 1)$ 开始。已有 $G_{n - 1}$ 时，先按原顺序给所有字添加前缀零，再按反序给它们添加前缀一： $G_{n} = (0 G_{n - 1}, 1 G_{n - 1}^{r e v}) .$ 例如 $G_{2} = (00, 01, 11, 10)$ 。构造 $G_{3}$ 时，前半段是 $000, 001, 011, 010$ ，后半段是倒过来的 $110, 111, 101, 100$ 。

证明。 假设 $G_{n - 1}$ 已包含每个低 $n - 1$ 位字恰一次，且相邻字只差一位。新序列前、后两半的最高位不同，因此互不重复；每一半的低位又穷尽全部可能字，合起来恰有全部 $2^{n}$ 个状态。

在同一半内部，最高位固定，低位沿旧序列或其反序移动，仍只差一位。两半的交界处，低位都是旧序列的最后一个字，只改变新添加的最高位。新序列的最后一个字与第一个字，低位也都等于旧序列的第一个字，仍只差最高位。基础 $n = 1$ 可直接检查，因此对所有 $n \geq 1$ 都得到循环格雷码。

用两位序列正序加零前缀、反序加一前缀组成三位格雷码，交界低位相同 — 反射保证两半的接缝只翻最高位。若后半段也照正序排列，接缝一般会改变多位。

直接编码与解码

把整数 $i \in {0, \dots, 2^{n} - 1}$ 的普通二进制字记为 $b_{n - 1} \dots b_{0}$ 。反射码在第 $i$ 个位置的字为 $g (i) = i \oplus ⌊ i / 2 ⌋,$ 其中 $\oplus$ 是逐位异或：两位相同得零，不同得一。逐位表达为 $g_{n - 1} = b_{n - 1}, g_{j} = b_{j + 1} \oplus b_{j} (0 \leq j < n - 1) .$ 最高位先确定，其余每位比较普通二进制相邻两位，便得到格雷字。这个关系与前述反射递推一致：最高位固定为零时沿旧顺序，高位由零变一后低位的顺序反转。

还可直接证明相邻字只差一位。若 $i$ 末尾恰有 $k$ 个连续的一，则从 $i$ 加一时，最低 $k + 1$ 位翻转，即 $a = i \oplus (i + 1) = 2^{k + 1} - 1.$ 因此 $g (i) \oplus g (i + 1) = a \oplus ⌊ a / 2 ⌋ = 2^{k} .$ 结果只有第 $k$ 位为一，证明相邻格雷字确实只差这一位。这里相邻索引取 $i < 2^{n} - 1$ ；首尾关系由 $g (2^{n} - 1) = 10 \dots 0$ 单独核对。

解码可从最高位向下恢复： $b_{n - 1} = g_{n - 1}, b_{j} = b_{j + 1} \oplus g_{j} .$ 例如 $g = 101$ ，先得最高位一，接着得 $1 \oplus 0 = 1$ ，最后得 $1 \oplus 1 = 0$ ，所以普通二进制为 $110$ ，即索引六。每一位都被唯一恢复，也证明直接编码是双射。

Python 实现

以下函数生成反射格雷码的字符串列表，位数为正整数；另一个函数把非负格雷整数解回普通整数。返回的列表包含全部状态，不依赖全局可变数据。

Python 3

def gray_words(bits):
    if type(bits) is not int or bits < 1:
        raise ValueError("bits must be a positive integer")
    return [format(i ^ (i >> 1), f"0{bits}b")
            for i in range(1 << bits)]


def gray_to_integer(gray):
    if type(gray) is not int or gray < 0:
        raise ValueError("gray must be a nonnegative integer")
    result = 0
    while gray:
        result ^= gray
        gray >>= 1
    return result


print(gray_words(3))
print(gray_to_integer(0b101))
# ['000', '001', '011', '010', '110', '111', '101', '100']
# 6

解码中的逐次异或，将格雷字与其右移一位、两位等的结果叠加。每个输出位得到相应高位格雷位的异或前缀，恰好实现上述递推。生成字符串列表至少需输出 $n 2^{n}$ 个字符，所以时间和结果空间均为 $O (n 2^{n})$ ；不能因为直接编码只有一条异或表达式，就把枚举全部状态说成常数时间。解码循环运行至多字的位数次；若按大整数位操作计成本，还要计入每次异或和移位涉及的位长。

变式。 两位输出是 $00, 01, 11, 10$ ，最后回到开头只翻最高位。一位输出是 $0, 1$ ；零位只有一个空字，无法满足“相邻状态恰差一位”的同一循环定义，因此本实现要求正位数。

单位变化与纠错的区别

把 $n$ 位字看作一个子集的指示向量，格雷顺序每步只增加或删除一个元素。例如三位 $011 \to 010$ 只删除最低位对应元素；若维护子集元素权重之和，每步可以只加减一个权重，而不用重新扫描全部元素。

但格雷码仍使用全部 $2^{n}$ 个字，最小距离为一。把某一位读错，结果可能恰好是另一个合法字，编码本身无法保证检测或纠正错误。位置编码器可借它减轻相邻位置交界时多位同时变化的歧义，但电气抖动、采样时序和跨越多个位置仍需另行处理。数学上的单比特邻接条件不是对真实传感系统无误差的承诺。

参考资料

↑ Pavel Tvrdík：Embeddings and simulations of INs I+II，CS838，1999，“Embeddings of paths and cycles”中的 Gray sequence、binary reflected Gray code 递推式与逐位代数公式。访问日期：2026年10月25日。

[tvrdik-1] Pavel Tvrdík：Embeddings and simulations of INs I+II，CS838，1999，“Embeddings of paths and cycles”中的 Gray sequence、binary reflected Gray code 递推式与逐位代数公式。访问日期：2026年10月25日。

[1]