格雷码（Gray Code）的生成与应用

格雷码是一种二进制编码方式，相邻两个数值的二进制表示仅有一位不同。例如，2位格雷码序列为：00, 01, 11, 10。这种特性使其在数字电路、错误校正和旋转编码器中广泛应用。

1. 格雷码的特性

• 相邻性：相邻两个格雷码的二进制形式仅有一位变化。
• 循环性：首尾两个格雷码也仅有一位不同（循环相邻）。
• 唯一性：每个格雷码对应唯一的十进制数值。

2. 格雷码的生成方法

方法一：反射法（递归构造）

步骤：

1. 基础情况：1位格雷码序列为 [0, 1]。
2. 递归步骤：
   • 将前一个序列的每个码前加 0（保持顺序不变）。
   • 将前一个序列逆序后每个码前加 1。
   • 合并两部分得到新序列。

示例（生成2位格雷码）：

• 1位格雷码：[0, 1]
• 前加0：[00, 01]
• 逆序前加1：[11, 10]
• 合并：[00, 01, 11, 10]

代码实现（递归）：

def gray_code(n):
    if n == 0:
        return [0]
    prev = gray_code(n - 1)
    return prev + [x | (1 << (n - 1)) for x in reversed(prev)]

方法二：公式法（二进制转格雷码）

公式：

\[G_i = B_i \oplus B_{i+1} \]

其中：

• \(B_i\) 是二进制数的第i位（从右往左，最低位为第0位）。
• \(\oplus\) 表示异或操作。

示例（二进制数1101转格雷码）：

1. 二进制：1 1 0 1
2. 右移一位：1 1 0（高位补0）
3. 异或操作：
   • 最高位：1 ⊕ 0 = 1
   • 次高位：1 ⊕ 1 = 0
   • 第三位：0 ⊕ 1 = 1
   • 最低位：1 ⊕ 0 = 1
4. 格雷码：1011

代码实现：

def binary_to_gray(n):
    return n ^ (n >> 1)

3. 格雷码的应用场景

1. 旋转编码器：物理旋转传感器通过格雷码避免位置检测的瞬时错误。
2. 数字电路：减少状态切换时的信号抖动和功耗。
3. 汉诺塔问题：格雷码序列对应汉诺塔移动的最优解。
4. 遗传算法：用格雷码编码参数，增强局部搜索能力。

4. 格雷码与二进制的互相转换

• 二进制转格雷码：gray = binary ^ (binary >> 1)
• 格雷码转二进制：

  def gray_to_binary(gray):
      binary = gray
      while gray > 0:
          gray >>= 1
          binary ^= gray
      return binary
  

5. 总结

• 格雷码的核心优势是相邻码仅一位变化，避免了二进制编码在相邻值切换时可能出现的多位跳变。
• 生成方式灵活，反射法直观，公式法高效。
• 实际应用中需注意格雷码与二进制的转换开销。