格雷码的工作原理

Question

我正在尝试理解灰色代码的工作原理。如果我们给出任何非负整数n(其中n是位数)，那么我们需要打印它的格雷码序列。下面是一些例子

2位格雷码序列

Input = 2 bits
00 - 0
01 - 1
11 - 3
10 - 2
Output = [0,1,3,2]

3位格雷码序列

Input  = 3
000 0
001 1
011 3
010 2
110 6
111 7
101 5
100 4
Output = [0, 1, 3, 2, 6, 7, 5, 4]

根据我的理解，格雷码序列从0开始，在格雷码中，两个连续的值仅相差一位。我不知道2的格雷码是怎么来的[0,1,3,2]，3的格雷码是怎么来的[0,1,3,2,6,7,5,4]

Answer 1

生成n比特的格雷码的通常方法是取n-1比特的序列，其前缀为0，然后是n-1比特的反向序列，其前缀为1。1比特的基本情况序列为0，1。您可以很容易地编写一个递归函数来生成此序列：

void printgrey(int len, int pfx=0, int rev=0) {
    if (--len >= 0) {
        printgrey(len, pfx + (rev<<len), 0);
        printgrey(len, pfx + (!rev<<len), 1);
    } else
        printf("%d\n", pfx);
}

Answer 2

在硬件中，格雷码的描述如下：

function bin2gray(value : std_logic_vector) return std_logic_vector is
  variable result       : std_logic_vector(value'range);
begin
  result(result'left)   := value(value'left);
  for i in (result'left - 1) downto result'right loop
    result(i) := value(i) xor value(i + 1);
  end loop;
  return result;
end function; 

来源：PoC.utils

什么意思？来自输入的最高位(MSB)被复制到结果。现在，循环遍历从MSB-1到LSB的每个输入位，并将该位与其左邻进行异或运算。

示例：

in = 0x2 = 0010b
res(3) := 0
res(2) := in(3) xor in(2) = 0
res(1) := in(2) xor in(1) = 1
res(0) := in(1) xor in(0) = 1
return 0011

Answer 3

生成格雷码序列的最简单方法是从一个正常的数字序列开始，然后对每个数字进行xor运算，并将其自身向右移位一位。在Python中，它看起来像这样：

def graycodes(bits):
    return [x ^ (x >> 1) for x in range(1 << bits)]

>>> graycodes(2)
[0, 1, 3, 2]
>>> graycodes(3)
[0, 1, 3, 2, 6, 7, 5, 4]
>>> graycodes(4)
[0, 1, 3, 2, 6, 7, 5, 4, 12, 13, 15, 14, 10, 11, 9, 8]