访问量： 108 次浏览
2002年8月，国际数学家大会在北京举行，这场盛大的会议每四年举办一次， 来自世界各地共襄盛举的数学家高达数千人， 这是一个表扬杰出人才中的佼佼者的好机会。1982年，奈旺林纳奖， 为纪念芬兰数学家罗尔夫•奈旺林纳而命名首次颁发给在理论计算机学领域有卓越表现的人士。 2002年的得主是麻省理工学院教授苏丹，对他的赞词中特别提到他在纠错码方面的贡献。
计算机使用者可能都十分熟悉错误修正软件， 例如大多数文字处理软件都有拼字检查功能，如果键入“hte”， 就会有一条红色波浪状线条出现在这组无意义的字母组合下方， 告诉我们英文中没有这个单字，而这种功能通常被称为“误差检测”。
有些文字处理软件的功能不只如此。举例来说， 英文中的t，h，e这三个字母组成的单字只有一个，因此打字者想打的字是无庸置疑的， 于是先进的文字处理软件会自动以“the”取代错误的字符串，而这种情况就称为纠错。
相较于更正错误，检测错误简单多了！在传输文本或复制文件时， 纳入“校验和”就可以检测错误。例如，对于数字串， 可以用串中数字的总和来做检测；如果传送端与接收端的校验和不一致， 就知道至少有一个错误发生，必须重新传送一次。
传输的重复是一件费时的工作，所以若能在接收端自动纠错， 就能提高效率。因此，优良的软件不会要求你重打“the”这个字， 而是自动以正确的单词取代错误的“hte”。
这种功能是何时、如何发明的？令人讶异的是， 它源于17世纪上半叶天文学家及数学家开普勒长时间研究的一个完全不相干的问题。 他提出的问题是：在蔬果店小货车上堆橙子或西红柿时， 哪种排列方式最有效率？换言之，如何让这些水果间的空隙最小？
堆西红柿问题和纠错有什么关系？想象在一个三度空间中， 字母沿着三个坐标轴依相同间距排列，假设间隔是1厘米。 三个字母组成的单字可以被视为空间中的一点，x轴代表第一个字母， y轴是第二个字母，z轴则为第三个字母。如此一来， 每个单字都可以表示为\(26 \times 26 \times 26\)厘米方块中的一点， 英文中没有的字则维持空白。于是如果传输的是无意义的字母序列， 就会对应到一个空的空间，误差检测程序会自动产生标志。 纠错程序则还会有更进一步的动作：自 动寻找最接近的“合法”单词。
合法点彼此之间的距离愈远，对可能的错误的疑虑就愈小， 也更容易以正确的单字取代错误的字母序列。因此，为了避免模糊不清， 必须确保在每个合法单词周围一定距离内，没有其他合适的单词。 另一方面，我们又想把尽量多的词塞到这个方块中， 于是问题变成是：如何在方块中储存最多的点，同时各点之间又保持最小距离？ 这也是开普勒自问的问题：如何将橙子或西红柿堆放得尽可能紧密，又不把彼此挤烂？
几个世纪来，蔬果店皆熟知蔬菜水果的最佳堆栈方式， 就是排成蜂巢的形状或六边形，但直到1998年美国数学家黑尔斯才严谨地证实了这个猜想。 理论上，由26个字母组成的方块中，总共可以储存17576（=263；） 个三字母单词。开普勒问题的解答却表明，彼此相距一厘米的单词， 若用最紧密的迭法，可以在相同的空间中储存25000个单词。 另一方面，如果想在两个单词间建立一个较宽的安全地带，假设是两厘米， 那么最有效率的迭法只容许储存约3000个单词。
若要处理超过3个字母以上的单词，必须利用三维以上的空间。 但截至目前，更高维空间里最有效率的堆栈方式仍未有定论。