格雷码笔记

格雷码的特点、生成及其与二进制之间的转换

格雷码(Gray Code)

在一组数的编码中,若任意两个相邻的代码只有一位二进制数不同。

格雷码有多种编码形式

十进制数 4位自然二进制码 4位典型格雷码 十进制余三格雷码 十进制空六格雷码 十进制跳六格雷码 步进码
0 0000 0000 0010 0000 0000 00000
1 0001 0001 0110 0001 0001 00001
2 0010 0011 0111 0011 0011 00011

为何使用格雷码

  • 特点

    • 反射

      最大数与最小数之间也仅一位数不同,即“首尾相连”

    • 循环

      最大数与最小数之间也仅一位数不同,即“首尾相连”

    • 单步

    • 自补

      所谓自补码,举个例子:2的余三码为0101,各位取反为1010,这正好为7的余三码。而2对9的补码为7,所以说余三码是对9的自补码。

    • 变权

      每一位码没有固定的大小,很难直接进行比较大小和算术运算,也不能直接转换成液位信号,要经过一次码变换,变成自然二进制码,再由上位机读取。

    • 奇偶性

      格雷码的十进制数奇偶性与其码字中1的个数的奇偶性相同

    • 绝对编码方式

      • 循环和单步特性消除了随机取数时出现重大错误的可能

      • 反射和自补特性使得对其进行求反操作也非常方便

    格雷码属于一种可靠性编码。

  • 实际

    是一种错误最小化的编码方式

    • 虽然自然二进制码可以直接由数/模转换器转换成模拟信号,但在某些情况,例如从十进制的3转换为4时二进制码的每一位都要变,能使数字电路产生很大的尖峰电流脉冲。而格雷码则没有这一缺点,它在相邻位间转换时,只有一位产生变化。它大大地减少了由一个状态到下一个状态时逻辑的混淆。由于这种编码相邻的两个码组之间只有一位不同,因而在用于方向的转角位移量-数字量的转换中,当方向的转角位移量发生微小变化(而可能引起数字量发生变化时,格雷码仅改变一位,这样与其它编码同时改变两位或多位的情况相比更为可靠,即可减少出错的可能性。
    • 在数字系统中,常要求代码按一定顺序变化。例如,按自然数递增计数,若采用8421码,则数0111变到1000时四位均要变化,而在实际电路中,4位的变化不可能绝对同时发生,则计数中可能出现短暂的其它代码(1100、1111等)。在特定情况下可能导致电路状态错误或输入错误。使用格雷码可以避免这种错误。

格雷码生成

方式一:直接排列(较复杂)

以二进制为0值的格雷码为第零项,第一项改变最右边的位元,第二项改变右起第一个为1的位元的左边位元,第三、四项方法同第一、二项,如此反复,即可排列出n个位元的格雷码。

假设原始的值从0开始,格雷码产生的规律是:

第一步,改变最右边的位元值;

第二步,改变右起第一个为1的位元的左边位元;

第三步,第四步重复第一步和第二步,直到所有的格雷码产生完毕(换句话说,已经走了(2^n) - 1 步)。

用一个例子来说明:

假设产生3位元的格雷码,原始值位 000

1
2
3
4
5
6
7
第一步:改变最右边的位元值: 001
第二步:改变右起第一个为1的位元的左边位元: 011
第三步:改变最右边的位元值: 010
第四步:改变右起第一个为1的位元的左边位元: 110
第五步:改变最右边的位元值: 111
第六步:改变右起第一个为1的位元的左边位元: 101
第七步:改变最右边的位元值: 100

方式二:镜射排列

n位元的格雷码可以从n-1位元的格雷码以上下镜射后加上新位元的方式快速的得到,如图所示。

格雷码-镜射排列

观察格雷码的结构,可以发现:

  • 除了最高位(左边第一位),格雷码的位元完全上下对称(看下面列表)。比如第一个格雷码与最后一个格雷码对称(除了第一位),第二个格雷码与倒数第二个对称,以此类推。

  • 最小的重复单元是 0 , 1。

    000 001 011 010 110 111 101 100

如此,采用递归,在每一层前面加上0或者1,然后就可以列出所有的格雷码。

  • 第一步:产生 0, 1 两个字符串。

  • 第二步:在第一步的基础上,正向每一个字符串都分别加上0,然后反向迭代每一个字符串都加上1,但是每次只能加一个,所以得做两次。这样就变成了 00,01,11,10 (注意对称)。

  • 第三步:在第二步的基础上,再给每个字符串都加上0和1,同样,每次只能加一个,这样就变成了 000,001,011,010,110,111,101,100。这样就把3位元格雷码生成好了。

  • 如果要生成4位元格雷码,我们只需要在3位元格雷码上再加一层0,1就可以了: 0000,0001,0011,0010,0110,0111,0101,0100,1100,1101,1110,1010,0111,1001,1000.

也就是说,n位元格雷码是基于n-1位元格雷码产生的。

二进制与格雷码的转换

自然二进制码与格雷码的对照表:

二进制 格雷码 二进制 格雷码
0000 0000 1000 1100
0001 0001 1001 1101
0010 0011 1010 1111
0011 0010 1011 1110
0100 0110 1100 1010
0101 0111 1101 1011
0110 0101 1110 1001
0111 0100 1111 1000

二进制转换格雷码

法则:保留二进制码的最高位作为格雷码的最高位,而次高位格雷码为二进制码的高位与次高位相异或,而格雷码其余各位与次高位的求法相类似。

二进制码 ----> 格雷码(编码):从最右边一位起,依次将每一位与左边一位异或(XOR),作为对应格雷码该位的值,最左边一位不变(相当于左边是0)。1

公式:(G:格雷码 B:二进制码)

整个数:$ G(N) = (B(n) >> 1) XOR B(n) $​

单个位:$ G_{i}=B_{i}B_{i+1}( n-1i ) $​​

转换示意图

格雷码转换二进制

法则:保留格雷码的最高位作为自然二进制码的最高位,而次高位自然二进制码为高位自然二进制码与次高位格雷码相异或,而自然二进制码的其余各位与次高位自然二进制码的求法相类似。

公式:$ B_{i}=G_{i}B_{i+1}( n-1i ) $

转换示意图

参考:格雷码Gray Code详解 - 篮球之神Michael - 博客园 (cnblogs.com)


  1. 因为二进制码每次+1时最多只有一个相邻的两个bit对的异或值会发生改变。↩︎