1

我清楚地理解了格雷码的目的。 EE Times：格雷码基础

但是我无法从概念上理解为什么可以如下生成格雷码

G i = B i+1 ⊕ B i , i = n - 1, . . . , 0，其中 B n取为 0。

有人可以在概念上帮助我。

4

3 回答 3

1

在标准二进制文件中，如果您排除或小于n**2with的数字n**2-1，则您有效地颠倒了该计数的顺序：

x   x^11
00  11
01  10
10  01
11  00

因此，对于两位数，如果我们将下一位与下一位异或：

x   x^(x>>1)
00  00
01  01
10  11
11  10

我们交替反转底部位的计数顺序，具体取决于它上面的位是设置还是清除。这确保了当位 1 更改时，位 0 保持不变（否则它会回绕到零并重新开始计数）。

对于添加到计数器顶部的每个位，我们需要重复对下面位的计数的这种反映，以确保在新位被设置时它不会被清除。其余位遵循相同的模式，由它们上方的位反映，以便它们向后计数而不是环绕。

于 2013-06-29T11:44:09.710 回答
0

当您查看维基百科时，您会看到它是：

G0 = B0
Gi = Bi EXOR Gi-1

这更有意义吗？检查您阅读的页面中给出的格雷码 - 您会看到它成立。

你想看看上面的证明，还是看例子就够了？

于 2012-10-14T17:15:49.233 回答
0

我发现Vovanium的答案对于理解生成格雷码序列的公式非常有帮助。这个想法是我们想要生成一个序列，其中 G(n+1) 仅从 G(n) 更改一位，即 G(n+1) xor G(n) 仅设置了 1 位。Vovanium的答案部分复制如下。

如果您查看二进制计数序列，您会注意到，相邻代码在最后几个位（没有孔）处不同，因此如果您对它们进行异或，则会出现几个尾随 1 的模式。此外，当您将数字右移时，xor 也会右移：(A xor B)>>N == A>>N xor B>>N。

        N                    N>>1                  gray
 0000           .        0000           .      0000           .
    | >xor = 0001             >xor = 0000           >xor = 0001
 0001          .         0000          .       0001          .
   || >xor = 0011           | >xor = 0001           >xor = 0010
 0010           .        0001           .      0011           .
    | >xor = 0001             >xor = 0000           >xor = 0001
 0011         .          0001         .        0010         .
  ||| >xor = 0111          || >xor = 0011           >xor = 0100
 0100                    0010                  0110

原始异或结果和移位结果在单个位上有所不同（我在上面用点标记了它们）。这意味着如果您对它们进行异或，您将获得设置为 1 位的模式。所以，

(A xor B) xor (A>>1 xor B>>1) == (A xor A>>1) xor (B xor B>>1) == gray (A) xor gray (B)

于 2018-11-28T19:38:57.030 回答