订阅程序员杂志RSS CSDN首页> 程序员杂志

Gray码及其应用

发表于2013-12-18 11:10| 次阅读| 来源《程序员》| 0 条评论| 作者程序员杂志

摘要:控制台上有四个开关和一个按钮,每个开关都可以扳到ON和OFF中的一个,只有当四个开关的ON/OFF状态处于某个唯一的正确组合时,按动按钮之后才能打开密室的大门。为了以最快的速度逃脱密室,你打算怎么办?
控制台上有四个开关和一个按钮,每个开关都可以扳到ON和OFF 中的一个,按钮上用粗体写着OPEN。只有当四个开关的ON/OFF状态处于某个唯一的正确组合时,按动按钮之后才能打开密室的大门(但你不知道这个正确 的组合是什么)。你需要做的事情很明确:不断扳动开关,尝试各种各样的ON/OFF组合,然后按动按钮,直到成功把门打开为止。为了以最快的速度逃脱密室,你打算怎么办?

一个游戏引发的思考

几年前,我玩过一个第三人称冒险游戏,游戏的名字已经不记得了,唯一印象深刻的就是上面这个场景。为了避免自己忘记哪些组合已经试过,我们只需要按照某种规律逐一尝试所有的组合就行了。比方说,用数字0来表示OFF状态,用数字1来表示ON状态,然后按照二进制数的规律依次尝试2⁴=16种不同的组合:0000, 0001, 0010, 0011, 0100, …, 1110, 1111。其中,从0000到0001需要扳动一次开关,从0001到0010需要扳动两次开关……最恐怖的是,从0111到1000需要扳动全部四个开 关。在最坏情况下,最后试到的那个组合才是正确的组合,那么整个过程下来,我们一共要扳动26次开关!更要命的是,在游戏中,扳动一次开关非常费劲,你需要持续按住某个按键很长时间才行。

于是,一个有意思的问题出现了:换一种尝试的顺序,能让我们少扳动几次开关吗?最少需要扳动几次开关呢?

容易看出,由于我们一共要试16种不同的组合,因此整个过程至少要扳动15次开关。会不会扳动15次开关就足够了呢?这意味着,每两个相邻的组合之间都只相差一个开关的位置。如此理想的解是否真的存在,这我不太清楚;但我当时立即想到,如果要试遍三个开关的所有2³=8种组合,只扳动7次开关确实是可以办到的。这相当于沿着立方体的棱既无重复又无遗漏地经过每一个顶点。其中一种方案如图1所示,它所对应的试验顺序如下。

000 → 001 → 011 → 010 → 110 → 111 → 101 → 100


图1 把8个三位01串看作立方体的8个顶点,两个01串之间有一条棱当且仅当它们只相差一位

当时我的想法很简单:既然知道怎样快速遍历三个开关的所有组合,那就干脆让第一个开关保持OFF状态,把所有形如0???的组合都先试一遍吧:

0000 → 0001 → 0011 → 0010 → 0110 → 0111 → 0101 → 0100

接下来呢?我的想法是,把第一位扳成1,然后像刚才那样再遍历一次后三位的组合吧。把0100变成1000需要扳动2次开关,再把后三位的组合全试一遍又需 要7次开关,最后一共扳动了16次开关,嗯,已经很不错了。但是,刚扳完第一个开关,把0100变成了1100后,本想继续把后三位还原成000的,却突 然一下意识到:1100本来就是一个新的组合呀。干脆先把这个组合试了再说。

0100 → 1100

紧接着,就像有人用一根大棒把我敲醒了一样,我猛然意识到:然后就从1100出发,逆着刚才的顺序遍历后三位的所有组合,最后回到1000不就行了吗?

1100 → 1101 → 1111 → 1110 → 1010 → 1011 → 1001 → 1000

这样,我们就实现了扳动15次开关既无重复又无遗漏地遍历四个开关的所有16种组合,每扳动一次开关得到的正好都是一种新的组合!

利用类似的方式,我们可以继续扩展,把32个五位01串也排成一列,使得每个01串到下个01串都只需要变动一位。当然,刚才那8个三位01串的排列顺序, 本身也可以看作是由更基本的情况扩展而来的。事实上,我们可以像表1那样,从一位01串这种最最基本的情况出发,不断通过“镜像”和“添首位”的方法,最 终得到把2ⁿ个n位01串排成一列的方案,使得相邻两个01串总是只差一位。


表1 生成镜像二进制编码的方法

我们姑且给它起个名字,叫做“镜像二进制编码”吧。

PCM信号转换器的故事

人 们刚开始实现数字通信的时候,曾经为如何把模拟信号转化为数字信号而伤透脑筋。1937年,英国科学家Alec Reeves发明了一种将模拟信号进行数字化的方法,即我们现在所说的脉冲编码调制(pulse-code modulation,缩写成PCM或许大家会更熟悉一些)。假设我们有一段声音,它的波形图如图2所示。那么,我们就间隔相等地在时间轴上取一些点,看 看此时波形图的高度在什么位置,并用二进制数来表示。如果使用五位二进制数的话,那么每个采样结果都有32种不同的取值,可以与十进制中的0到31相对 应。对于普通的人声来说,为了充分刻画出波的形状,理论上每秒至少需要采样8000次才行;采样频率越高,还原真实声音的效果也就越好。


图2 脉冲编码调制示意图

这种编码方式确实不错,关键是,如何设计一种信号转换器,让它能自动地按照这种方式把模拟信号转换成数字信号?总不能雇几个员工去人肉完成每秒上千次的采样和转换吧。

图3 用阴极射线管制作一个信号转换器

人们巧妙地用阴极射线管和X、Y两组偏转板解决了这个问题。如图3所示,电子枪射出的电子束首先从两块Y偏转板之间穿过,并且受到Y偏转板所产生的电场的影 响而上下偏转,其偏转幅度由输入电信号决定;偏转后的电子束继续从两块X偏转板之间穿过,并受其产生的电场影响而左右偏转。X偏转板上的电位差由某个锯齿 波发生器决定,其效果就是让电子束不断地从左至右扫描。在电子束到达电子收集屏之前,还必须经过一个上面有穿孔的“编码盘”。如果我们想要把每一个采样值都转化成五位01串的话,那么编码盘上的孔应该如图4所示。把所有的东西结合起来,电子束便能根据输入信号在不同的高度处从左往右扫描,每扫描一次都会产 生一个五位01串,其中1意味着电子束穿过了编码盘上的孔,0意味着电子束被编码盘挡住了。如果电子束在r₁所示的高度处扫描一次,得到的五位01串就是 01101,或者说十进制的13。


这种信号转换器的原理的确巧妙,但理论与实际之间还是有一定距离的。在实际应用时,我们会遇到一个有些意想不到的问题。让我们假设,某个采样值正好是 23.5,于是电子束会在图4的r₂高度处从左往右扫描一次。注意,这条扫描线经过了四个孔的边界,于是完全有可能出现这样的误差:电子束穿过了第二位对 应的孔,同时也穿过了第三位、第四位和第五位所对应的孔。于是,这个值最后就被编码为了11111。或者,电子束完全错过了后面四个位置上的孔,于是这个 值就被编码为了10000。在最坏情况下,我们甚至会把15.5编码为11111或者00000,这是不能容忍的错误。怎么办呢?

1947年,贝尔实验室的Frank Gray提交了一项专利,漂亮地解决了这个问题。Frank Gray的方法非常简单:把传统二进制编码改为镜像二进制编码!新的编码盘如图5所示。我们用五位镜像二进制编码中的第一项,即00000,来表示最小的 高度值,或者说十进制的0;用镜像二进制编码中的下一项,即00001,来表示次小的高度值,或者说十进制的1;类似地,用00011表示2,用 00010表示3,用00110表示4,以此类推,一直到用10000表示31。这样,任意两个相邻高度所对应的数字编码都只有一位的差异,换句话说恰好 从它们中间穿过去的扫描线只会遇到一处边界。如果扫描线的高度恰好是15.5,则转换后的结果要么就是01000(它代表15),要么就是11000(它 代表16),刚才的误差问题就解决了。


Frank Gray在专利文件中说,这种新的编码方式还没有一个名字,并且首次提出了“镜像二进制编码”(reflected binary code)这个名字。后来,人们逐渐开始用“Gray码”来指代这种编码方式,“Gray码”这个名字也就慢慢固定了下来。

Gray码的其他应用

在工业上,Gray码还有很多应用。假如有一个温度(或水位、气压、比分等)检测系统,当它探测到数值从7变到8时,系统便会把0111改成1000。万一 在改动的过程当中正好出现了读取操作,此时读到的数据就是错误的。采用Gray码的话,数值的加1和减1操作将会成为真正的原子操作,这个问题也就能避免 了。

有趣的是,n位Gray码的第一个01串和最后一个01串之间也只差一位。因此,如果把n位Gray码看作是循环的,任意两个相邻的 01串仍然满足要求。有些方向传感器会使用Gray码来表示方向,便是用到了Gray码的这个性质。例如,不妨用000, 001, 011, 010, 110, 111, 101, 100依次表示八个方向,那么不管是从哪个方向转到哪个相邻的方向,所对应的01串都只变了一位,这样也就不会产生错误的“中间数值”了。

作者顾森,网名Matrix67,数学爱好者。2005年开办数学博客www.matrix67.com,至今已积累上千篇文章,有上万人订阅。新书《思考的乐趣》已在图灵公司出版。

0
0

近期活动

更多

2015中国大数据技术大会

为了更好帮助企业深入了解国内外最新大数据技术,掌握更多行业大数据实践经验,进一步推进大数据技术创新、行业应用和人才培养,2015年12月10-12日,由中国计算机学会(CCF)主办,CCF大数据专家委员会承办,中国科学院计算技术研究所、北京中科天玑科技有限公司及CSDN共同协办的2015中国大数据技术大会(Big Data Technology Conference 2015,BDTC 2015)将在北京新云南皇冠假日酒店隆重举办。

微博关注

程序员移动端订阅下载

相关热门文章