PDF《有错必究》

he Joy of Mathematics 数学文化/第4卷第2期21 数学趣谈 有错必究 汉明码(Hamming Code)的原理及其应用 万精油 上期的题目是帽子的颜色问题.

为方便解答,我们把上期题目再列一遍. 帽子的颜色问题 : 三个人头上都被戴上一顶帽子.帽子的颜色是蓝色或红色,完 全独立随机.每个人可以看见别人的帽子,但看不见自己的帽子.每个人可以有 两种选择 : 猜自己帽子的颜色,或者放弃(就是不猜) .每个人把自己的决定写 在一张纸上.如果最后的结果是至少一人猜对而且没人猜错,那么他们可以得到 一笔巨额奖金.我们的问题是,他们用什么策略才能最大地提高得奖的概率. 这个问题二十年前曾经在美国数学界、计算机界轰动一时.不光因为它是一道趣味题 目,而且因为这题目背后蕴藏着计算机编码理论中的一个重要思想. 与别的问题不同,这个问题最困难的地方是只要有一个人错则全错.所以不能像别的 题那样用数量来搞概率. 如果每个人都随机猜,那么三个人都猜对的可能性是八分之一.除此之外,好像没有 什么别的出路.因为帽子都是随机选的,你头上的帽子颜色与别人的帽子颜色独立,似乎 没有任何根据让你决定选什么颜色或放弃.其实不然,正因为帽子是随机选的(每个帽子 都有二分之一的机会是红色,二分之一的机会蓝色) ,所以总体帽子的颜色满足一种分布. 有些情况多一些,有些情况少一些.我们可以在这上面做文章. 先看三人的情况 : 三个人的帽子颜色一共有八种情况,红红红,红红蓝,红蓝红,红 蓝蓝,蓝红红,蓝红蓝,蓝蓝红,蓝蓝蓝.如果大家商定,当某人看见两个同色的帽子时, 他就猜另一种颜色,否则放弃.那么,根据上面的八种分布,我们很容易看出,有六种情 况他们都能通过.只有两种情况他们会失败,即全红或全蓝的时候.再仔细数一数,他们 答错和答对的时候一样多,都是六次.唯一的区别是,答错的时候大家都一起答错.而答 对的时候都只有一人答对,别的人都放弃. 这个题目可以推广到更多人的情况.人数多的时候就不能靠一个情况一个情况地数, 必须要有系统方法.这就需要介绍一种叫做汉明码的东西. 现在我们的生活都离不开网络,随时随地都在浏览从网上传来的东西.但是,网上的 传递不能保证 100% 都对,经常会出现错误.计算机怎么发现传递有错误?发现了错误以 趣味数学版he Joy of Mathematics

22 数学文化/第4卷第2期 数学趣谈 后又怎样纠正?汉明码就是用来干这个的. 在介绍汉明码以前,先简单介绍一下如何用奇偶性来检查传递的信息是否出错. 如果我们有

8 个比特可以用.那么我们可以用其中的

7 个比特来传递信息,用一个比 特来作验证码.如果那

7 个比特传递的信息有奇数个 1,验证码就是 1,否则就是 0. 这 样一来,如果信息传递中有一个码出现错误,该是

1 的地方变成了 0,或者该是

0 的地方 变成了 1, 与这个验证码不符, 我们就知道传递有错.这个方法的缺点是它虽然能发现错误, 但不能知道错误出在哪里,也不能纠正,只能要求重新传递.汉明码是在用奇偶性来检查 传递的信息是否出错的基础上发展出来的更高级的方法.它不但能发现错误,而且能知道 错误出现在哪里,从而进行自我纠正. 要知道错误出现在哪里,一个验证码是不够的,汉明码需要用到多个验证码,具体个 数根据能够传递的信息长度.假设有 2N -