典型的二进制格雷码（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等）。在特定情况下可能导致电路状态错误或输入错误。使用格雷码可以避免这种错误。格雷码有多种编码形式。
码表
播报编辑
格雷码有多种编码形式
十进制数 | 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 | ---- | ---- | ---- | ---- |
表中典型格雷码具有代表性。若不作特别说明，格雷码就是指典型格雷码，它可从自然二进制码转换而来。
特点
播报编辑
- 格雷码是一种绝对编码方式，典型格雷码是一种具有反射特性和循环特性的单步自补码，它的循环、单步特性消除了随机取数时出现重大误差的可能，它的反射、自补特性使得求反非常方便。
- 典型格雷码是一种采用绝对编码方式的准权码，其权的绝对值为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”，当初是为了通信，后来则常用于模拟－数字转换中。
转换方法
播报编辑
递归生成码表
这种方法基于格雷码是反射码的事实，利用递归的如下规则来构造：
- 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]
异或转换
例如：二进制码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
格雷码→二进制码（解码）：
从左边第二位起，将每位与左边一位解码后的值异或，作为该位解码后的值（最左边一位依然不变）。依次异或，直到最低位。依次异或转换后的值（二进制数）就是格雷码转换后二进制码的值。
公式表示：
原码：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，忽略余数；或者左移一位，再异或除以三，忽略余数。
应用
播报编辑
角度传感器
编码盘格雷码
九连环问题
九连环中的每个环都有上下两种状态，如果把这两种状态用0/1来表示的话，这个状态序列就会形成一种循环二进制编码（格雷码）的序列。所以解决九连环问题所需要的状态变化数就是格雷码111111111所对应的十进制数341。
程序实现
播报编辑
根据格雷码的特点，即：对于两个相邻的十进制数，对应的两个格雷码只有一个二进制位不同。另外，最大数与最小数间也仅有一个二进制位不同。以下给出用长度n的二进制数来表示十进制数m的格雷码c实现，运行结果如右图所示：
#include<stdio.h>
voidmain()
{
intm,n,i,j,b,p,bound;
intgr[14];
//输入n,m并判断m是否合法
bound=1;
printf("Pleaseinputtwonumber:n,m\n");
scanf("%d,%d",&n,&m);
for(i=1;i<=n;i++)
bound*=2;
if(m<0||m>=bound)
{
printf("Dataerror!");
exit(0);
}
b=1;
for(i=0;i<n;i++)
{
p=0;
b*=2;
for(j=0;j<=m;j++)
{
if(j%b-b/2==0)
p=1-p;
}
gr[i]=p;
}
printf("m=");
for(i=n-1;i>=0;i--)
{
printf("%d",gr[i]);
}
printf("\n");
}
格雷码解码的Pascal 程序：
var
x,y,i:longint;
begin
readln(x);
fori:=30downto0do
begin
y:=(xand(1shli))xor((xand(1shl(i+1)))shr1);
x:=xandnot(1shli)ory;
end;
writeln(x);
end.
2
var
x,i,n:longint;
begin
readln(n);
x:=n;
fori:=1to31do
begin
x:=xshr1;
n:=nxorx;
end;
writeln(n);
end.
