格雷码相关知识-谷穗社区

本词条由“科普中国”科学百科词条编写与应用工作项目审核。

典型的二进制格雷码（Binary Gray Code）简称格雷码，因1953年公开的弗兰克·格雷（Frank Gray，18870913-19690523）专利“Pulse Code Communication”而得名，当初是为了通信，现在则常用于模拟－数字转换和位置－数字转换中。法国电讯工程师波特（Jean-Maurice-Émile Baudot，18450911-19030328）在1880年曾用过的波特码相当于它的一种变形。1941年George Stibitz设计的一种8元二进制机械计数器正好符合格雷码计数器的计数规律。

格雷码（Gray code）曾用过Grey Code、葛莱码、葛兰码、格莱码、戈莱码、循环码、二进制反射码、最小差错码等名字，它们有的是错误的，有的易与其它名称混淆，建议不再使用它们。^[1]

中文名格雷码

外文名Binary Gray Code

全称二进制格雷码

提出者弗兰克·格雷

提出时间1940年

基本信息

播报

编辑

在一组数的编码中，若任意两个相邻的代码只有一位二进制数不同，则称这种编码为格雷码（Gray Code），另外由于最大数与最小数之间也仅一位数不同，即“首尾相连”，因此又称循环码或反射码。^[2]在数字系统中，常要求代码按一定顺序变化。例如，按自然数递增计数，若采用8421码，则数0111变到1000时四位均要变化，而在实际电路中，4位的变化不可能绝对同时发生，则计数中可能出现短暂的其它代码（1100、1111等）。在特定情况下可能导致电路状态错误或输入错误。使用格雷码可以避免这种错误。格雷码有多种编码形式。

格雷码（Gray Code）曾用过Grey Code、葛莱码、格莱码、戈莱码、循环码、反射二进制码、最小差错码等名字，它们有的不对，有的易与其它名称混淆，建议不要再使用这些曾用名。^[3]

码表

播报

编辑

格雷码有多种编码形式

十进制数	4位自然二进制码	4位典型格雷码	十进制余三格雷码	十进制空六格雷码	十进制跳六格雷码	步进码
0	0000	0000	0010	0000	0000	00000
1	0001	0001	0110	0001	0001	00001
2	0010	0011	0111	0011	0011	00011
3	0011	0010	0101	0010	0010	00111
4	0100	0110	0100	0110	0110	01111
5	0101	0111	1100	1110	0111	11111
6	0110	0101	1101	1010	0101	11110
7	0111	0100	1111	1011	0100	11100
8	1000	1100	1110	1001	1100	11000
9	1001	1101	1010	1000	1000	10000
10	1010	1111	—-	—-	—-	—-
11	1011	1110	—-	—-	—-	—-
12	1100	1010	—-	—-	—-	—-
13	1101	1011	—-	—-	—-	—-
14	1110	1001	—-	—-	—-	—-
15	1111	1000	—-	—-	—-	—-

表中典型格雷码具有代表性。若不作特别说明，格雷码就是指典型格雷码，它可从自然二进制码转换而来。

特点

播报

编辑

格雷码属于可靠性编码，是一种错误最小化的编码方式。因为，虽然自然二进制码可以直接由数/模转换器转换成模拟信号，但在某些情况，例如从十进制的3转换为4时二进制码的每一位都要变，能使数字电路产生很大的尖峰电流脉冲。而格雷码则没有这一缺点，它在相邻位间转换时，只有一位产生变化。它大大地减少了由一个状态到下一个状态时逻辑的混淆。由于这种编码相邻的两个码组之间只有一位不同，因而在用于方向的转角位移量－数字量的转换中，当方向的转角位移量发生微小变化（而可能引起数字量发生变化时，格雷码仅改变一位，这样与其它编码同时改变两位或多位的情况相比更为可靠，即可减少出错的可能性。
格雷码是一种绝对编码方式，典型格雷码是一种具有反射特性和循环特性的单步自补码，它的循环、单步特性消除了随机取数时出现重大误差的可能，它的反射、自补特性使得求反非常方便。
由于格雷码是一种变权码，每一位码没有固定的大小，很难直接进行比较大小和算术运算，也不能直接转换成液位信号，要经过一次码变换，变成自然二进制码，再由上位机读取。^[3]
典型格雷码是一种采用绝对编码方式的准权码，其权的绝对值为2^i-1(设最低位i=1)。
格雷码的十进制数奇偶性与其码字中1的个数的奇偶性相同。

发展历史

播报

编辑

法国工程师Jean-Maurice-Émlle Baudot在1880年曾用过的波特码是典型格雷码的一种变形。^[3]

Gray Code是由贝尔实验室的Frank Gray在1940年代提出的，用来在使用PCM（Pusle Code Modulation）方法传送讯号时避免出错。

Frank Gray于1947年申请、1953年获得批准的专利“Pulse Code Communication”，当初是为了通信，后来则常用于模拟－数字转换中。

1941年George Stibitz设计过一种8元格雷码计数器。^[3]

转换方法

播报

编辑

递归生成码表

这种方法基于格雷码是反射码的事实，利用递归的如下规则来构造：

1.
1位格雷码有两个码字
2.
(n+1)位格雷码中的前2n个码字等于n位格雷码的码字，按顺序书写，加前缀0
3.
(n+1)位格雷码中的后2n个码字等于n位格雷码的码字，按逆序书写，加前缀1^[4]
4.
n+1位格雷码的集合 = n位格雷码集合(顺序)加前缀0 + n位格雷码集合(逆序)加前缀1

2位格雷码	3位格雷码	4位格雷码	4位自然二进制码
00	000	0000	0000
01	001	0001	0001
11	011	0011	0010
10	010	0010	0011
	110	0110	0100
	111	0111	0101
	101	0101	0110
	100	0100	0111
		1100	1000
		1101	1001
		1111	1010
		1110	1011
		1010	1100
		1011	1101
		1001	1110
		1000	1111

异或转换

二进制码→格雷码（编码）：

此方法从对应的n位二进制码字中直接得到n位格雷码码字，步骤如下：

1.
对n位二进制的码字，从右到左，以0到n-1编号
2.
如果二进制码字的第i位和i+1位相同，则对应的格雷码的第i位为0，否则为1（当i+1=n时，二进制码字的第n位被认为是0，即第n-1位不变）^[4]

异或转换

公式表示：

（G：格雷码，B：二进制码）

例如：二进制码0101，为4位数，所以其所转为之格雷码也必为4位数，因此可取转成之二进位码第五位为0，即0 b3 b2 b1 b0。

0 xor 0=0，所以g3=0

0 xor 1=1，所以g2=1

1 xor 0=1，所以g1=1

0 xor 1=1，所以g0=1

因此所转换为之格雷码为0111

格雷码→二进制码（解码）：

从左边第二位起，将每位与左边一位解码后的值异或，作为该位解码后的值（最左边一位依然不变）。依次异或，直到最低位。依次异或转换后的值（二进制数）就是格雷码转换后二进制码的值。

公式表示：

（G：格雷码，B：二进制码）

原码：p[n:0]；格雷码：c[n:0](n∈N）；编码：c=G(p）；解码：p=F（c）；

书写时按从左向右标号依次减小，即MSB->LSB，编解码也按此顺序进行

……………….c[n]=p[n]，

解码：

利用卡诺图

利用卡诺图相邻两格只有一位变化以及卡诺图的变量取值以低阶格雷码的顺序排布的特征，可以递归得到高阶格雷码。由于此方法相对繁琐，使用较少。生成格雷码的步骤如下：

1.
将卡诺图变量分为两组，变量数目相近（最好相等）
2.
以逻辑变量高位在左低位在右建立卡诺图
3.
从卡诺图的左上角以之字形到右上角最后到左下角遍历卡诺图，依次经过格子的变量取值即为典型格雷码的顺序

三位格雷码（三位格雷码由建立在二位基础上）

AB╲ C	0	1
00	0→	1↓
01	↓2	←3
11	6→	7↓
10	4	←5

格雷码次序：000起点→001→011→010→110→111→101→100终点

四位格雷码

AB╲CD	00	01	11	10
00	0→	1→	3→	2↓
01	↓4	←5	←7	←6
11	12→	13→	15→	14↓
10	8	←9	←11	←10

格雷码次序：0000起点→0001→0011→0010→0110→0111→0101→0100→1100→1101→

1111→1110→1010→1011→1001→1000终点

使用异或乘除

用异或代替加减进行二进制竖式乘除，称为异或乘除，它的特点是无进退位。

如：10101除以11将变成1100余1。

二进制转格雷码：

只要异或乘以二分之三，即二进制的1.1，然后忽略小数部分；也可以理解成异或乘以三（即11），再右移一位。

格雷码转二进制：

异或乘以三分之二，即除以1.1，忽略余数；或者左移一位，再异或除以三，忽略余数。

应用

播报

编辑

角度传感器

编码盘

机械工具，汽车制动系统有时需要传感器产生的数字值来指示机械位置。如图是编码盘和一些触点的概念图，根据盘转的位置，触点产生一个3位二进制编码，共有8个这样的编码。盘中暗的区域与对应的逻辑1的信号源相连；亮的区域没有连接，触点将其解释为逻辑0。使用格雷码对编码盘上的亮暗区域编码，使得其连续的码字之间只有一个数位变化。这样就不会因为器件制造的精确度有限，而使得触点转到边界位置而出现错误编码。^[4]

格雷码

在化简逻辑函数时，可以通过按格雷码排列的卡诺图来完成。^[4]

九连环问题

智力玩具九连环的状态变化符合格雷码的编码规律，汉诺塔的解法也与格雷码有关。

九连环中的每个环都有上下两种状态，如果把这两种状态用0/1来表示的话，这个状态序列就会形成一种循环二进制编码（格雷码）的序列。所以解决九连环问题所需要的状态变化数就是格雷码111111111所对应的十进制数341。

程序实现

播报

编辑

根据格雷码的特点，即：对于两个相邻的十进制数，对应的两个格雷码只有一个二进制位不同。另外，最大数与最小数间也仅有一个二进制位不同。以下给出用长度n的二进制数来表示十进制数m的格雷码c实现，运行结果如右图所示：

1#include<stdio.h>

2voidmain()

3{

4    intm,n,i,j,b,p,bound;

5    intgr[14];

6//输入n,m并判断m是否合法

7    bound=1;

8    printf("Pleaseinputtwonumber:n,m\n");

9    scanf("%d,%d",&n,&m);

10    for(i=1;i<=n;i++)

11        bound*=2;

12    if(m<0||m>=bound)

13    {

14        printf("Dataerror!");

15        exit(0);

16    }

17    b=1;

18    for(i=0;i<n;i++)

19    {

20        p=0;

21        b*=2;

22        for(j=0;j<=m;j++)

23        {

24            if(j%b-b/2==0)

25                p=1-p;

26        }

27        gr[i]=p;

28    }

29    printf("m=");

30    for(i=n-1;i>=0;i--)

31    {

32        printf("%d",gr[i]);

33    }

34    printf("\n");

35}

格雷码解码的Pascal 程序：

1var

2    x,y,i:longint;

3begin

4    readln(x);

5    fori:=30downto0do

6    begin

7        y:=(xand(1shli))xor((xand(1shl(i+1)))shr1);

8        x:=xandnot(1shli)ory;

9    end;

10    writeln(x);

11end.

122

13var

14    x,i,n:longint;

15begin

16    readln(n);

17    x:=n;

18    fori:=1to31do

19    begin

20        x:=xshr1;

21        n:=nxorx;

22    end;

23    writeln(n);

24end.

词条图册更多图册

概述图册(1张)

词条图片(2张)

参考资料

1

李正生,马文彦,闫杰.格雷码辨析[J].电子科技,2011,24(10):77-80
2

柯利弗德·皮寇弗; 陈以礼（翻译）. The Math Book:From Pythagoras to the 57th Dimension, 250 Milestones in the History of Mathematics [数学之书]. 时报文化. 2013-04-16. ISBN 978-957-135-699-0 （中文（繁体）‎）.
3

格雷码的发展历史．北京信息科技大学电子信息与控制实验教学中心 [引用日期2013-07-28]
4

John F.Wakerly．数字设计原理与实践（原书第3版）．机械工业出版社．2003