更新时间:2024-03-31 10:27
典型的二进制格雷码(Binary Gray Code)简称格雷码,因1953年公开的弗兰克·格雷(Frank Gray,18870913-19690523)专利“Pulse Code Communication”而得名,当初是为了通信,现在则常用于模拟-数字转换和位置-数字转换中。法国电讯工程师波特(Jean-Maurice-Émile Baudot,18450911-19030328)在1880年曾用过的波特码相当于它的一种变形。1941年George Stibitz设计的一种8元二进制机械计数器正好符合格雷码计数器的计数规律。
在一组数的编码中,若任意两个相邻的代码只有一位二进制数不同,则称这种编码为格雷码(Gray Code),另外由于最大数与最小数之间也仅一位数不同,即“首尾相连”,因此又称循环码或反射码。在数字系统中,常要求代码按一定顺序变化。例如,按自然数递增计数,若采用8421码,则数0111变到1000时四位均要变化,而在实际电路中,4位的变化不可能绝对同时发生,则计数中可能出现短暂的其它代码(1100、1111等)。在特定情况下可能导致电路状态错误或输入错误。使用格雷码可以避免这种错误。格雷码有多种编码形式。
格雷码(Gray Code)曾用过Grey Code、葛莱码、格莱码、戈莱码、循环码、反射二进制码、最小差错码等名字,它们有的不对,有的易与其它名称混淆,建议不要再使用这些曾用名。
格雷码有多种编码形式
表中典型格雷码具有代表性。若不作特别说明,格雷码就是指典型格雷码,它可从自然二进制码转换而来。
法国工程师Jean-Maurice-Émlle Baudot在1880年曾用过的波特码是典型格雷码的一种变形。
Gray Code是由贝尔实验室的Frank Gray在1940年代提出的,用来在使用PCM(Pusle Code Modulation)方法传送讯号时避免出错。
Frank Gray于1947年申请、1953年获得批准的专利“Pulse Code Communication”,当初是为了通信,后来则常用于模拟-数字转换中。
1941年George Stibitz设计过一种8元格雷码计数器。
这种方法基于格雷码是反射码的事实,利用递归的如下规则来构造:
二进制码→格雷码(编码):
此方法从对应的n位二进制码字中直接得到n位格雷码码字,步骤如下:
公式表示: (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],
解码:
利用卡诺图相邻两格只有一位变化以及卡诺图的变量取值以低阶格雷码的顺序排布的特征,可以递归得到高阶格雷码。由于此方法相对繁琐,使用较少。生成格雷码的步骤如下:
三位格雷码(三位格雷码由建立在二位基础上)
格雷码次序:000起点→001→011→010→110→111→101→100终点
四位格雷码
格雷码次序: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。使用格雷码对编码盘上的亮暗区域编码,使得其连续的码字之间只有一个数位变化。这样就不会因为器件制造的精确度有限,而使得触点转到边界位置而出现错误编码。
智力玩具九连环的状态 变化符合格雷码的编码规律,汉诺塔的解法也与格雷码有关。
九连环中的每个环都有上下两种状态,如果把这两种状态用0/1来表示的话,这个状态序列就会形成一种循环二进制编码(格雷码)的序列。所以解决九连环问题所需要的状态变化数就是格雷码111111111所对应的十进制数341。
根据格雷码的特点,即:对于两个相邻的十进制数,对应的两个格雷码只有一个二进制位不同。另外,最大数与最小数间也仅有一个二进制位不同。以下给出用长度n的二进制数来表示十进制数m的格雷码c实现,运行结果如右图所示:
格雷码解码的Pascal 程序: