1

我试图了解格雷码的工作原理。如果我们给出任何非负整数 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]

4

3 回答 3

0

为 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);
}
于 2015-07-28T21:33:31.470 回答
0

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

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
于 2015-07-28T22:09:29.013 回答
0

生成格雷码序列的最简单方法是从一个正常的数字序列开始，然后将每个数字与自身右移一位进行异或。在 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]
于 2021-03-09T04:12:47.783 回答