搜索
heJoyofMathematics数学文化/第4卷第2期21数学趣谈有错必究汉明码（HammingCode）的原理及其应用万精油上期的题目是帽子的颜色问题。为方便解答，我们把上期题目再列一遍。帽子的颜色问题：三个人头上都被戴上一顶帽子。帽子的颜色是蓝色或红色，完全独立随机。每个人可以看见别人的帽子，但看不见自己的帽子。每个人可以有两种选择：猜自己帽子的颜色，或者放弃（就是不猜）。每个人把自己的决定写在一张纸上。如果最后的结果是至少一人猜对而且没人猜错，那么他们可以得到一笔巨额奖金。我们的问题是，他们用什么策略才能最大地提高得奖的概率。这个问题二十年前曾经在美国数学界、计算机界轰动一时。不光因为它是一道趣味题目，而且因为这题目背后蕴藏着计算机编码理论中的一个重要思想。与别的问题不同，这个问题最困难的地方是只要有一个人错则全错。所以不能像别的题那样用数量来搞概率。如果每个人都随机猜，那么三个人都猜对的可能性是八分之一。除此之外，好像没有什么别的出路。因为帽子都是随机选的，你头上的帽子颜色与别人的帽子颜色独立，似乎没有任何根据让你决定选什么颜色或放弃。其实不然，正因为帽子是随机选的（每个帽子都有二分之一的机会是红色，二分之一的机会蓝色），所以总体帽子的颜色满足一种分布。有些情况多一些，有些情况少一些。我们可以在这上面做文章。先看三人的情况：三个人的帽子颜色一共有八种情况，红红红，红红蓝，红蓝红，红蓝蓝，蓝红红，蓝红蓝，蓝蓝红，蓝蓝蓝。如果大家商定，当某人看见两个同色的帽子时，他就猜另一种颜色，否则放弃。那么，根据上面的八种分布，我们很容易看出，有六种情况他们都能通过。只有两种情况他们会失败，即全红或全蓝的时候。再仔细数一数，他们答错和答对的时候一样多，都是六次。唯一的区别是，答错的时候大家都一起答错。而答对的时候都只有一人答对，别的人都放弃。这个题目可以推广到更多人的情况。人数多的时候就不能靠一个情况一个情况地数，必须要有系统方法。这就需要介绍一种叫做汉明码的东西。现在我们的生活都离不开网络，随时随地都在浏览从网上传来的东西。但是，网上的传递不能保证100%都对，经常会出现错误。计算机怎么发现传递有错误？发现了错误以趣味数学版heJoyofMathematics22数学文化/第4卷第2期数学趣谈后又怎样纠正？汉明码就是用来干这个的。在介绍汉明码以前，先简单介绍一下如何用奇偶性来检查传递的信息是否出错。如果我们有8个比特可以用。那么我们可以用其中的7个比特来传递信息，用一个比特来作验证码。如果那7个比特传递的信息有奇数个1，验证码就是1，否则就是0。这样一来，如果信息传递中有一个码出现错误，该是1的地方变成了0，或者该是0的地方变成了1，与这个验证码不符，我们就知道传递有错。这个方法的缺点是它虽然能发现错误，但不能知道错误出在哪里，也不能纠正，只能要求重新传递。汉明码是在用奇偶性来检查传递的信息是否出错的基础上发展出来的更高级的方法。它不但能发现错误，而且能知道错误出现在哪里，从而进行自我纠正。要知道错误出现在哪里，一个验证码是不够的，汉明码需要用到多个验证码，具体个数根据能够传递的信息长度。假设有2N－1个比特可以传递。那么我们用其中的N个比特来做验证码，剩下的2N－1－N个比特来传递信息。要用这N个验证码来发现错误并确定其位置，这N个码的设置就很有讲究。具体的方法我们用N＝4的情况作一个说明。N＝4时，我们有15个比特可以用。用其中11个来传递信息，4个来做奇偶性验证码。我们假设这4个比特的位置是1,2,4,8。其余的11个比特就是真正要传递的信息。如果我们把这11个位置都用二进制表示，每个位置就有4个比特，我们把它们叫作位置比特，如“3”的位置比特为“0011”。第一个验证码验证的是所有位置比特第一比特（自右数）是1的位置（其实就是所有