|
小编自小喜好各类电脑游戏，不过小时候不太懂英文，无奈只好将满腔热血释放在各种国产RPG中（角色扮演类游戏，例如《仙剑》、《剑侠情缘》等）。那时候笨手笨脚，又没有游戏攻略可参考，因此遇到难度较大的战斗时常常被对手虐得生活不能自理。 然而小编不是一个轻易服输的人，尤其不愿输给由一堆芯片硬壳组成的电脑，便开始动起了歪脑筋——修改游戏。只要功夫深铁杵磨成针，凭借着对电脑游戏的敏锐嗅觉，小编总算在找到一些关键的游戏文件。然而用记事本格式打开以后却往往是这样的： 或许是当时受到任天堂小霸王游戏系列的影响，上面这种汉字和其他字符的结合体全都被不谙世事的小编统称为“日文”。这些“日文”文件很奇怪，稍微改一个汉字，游戏就翻脸不认人，直接无法载入了。于是各色各样的“日文”就成为了小编记忆中的阴影。 童年的小编无法分辨乱码和日文 我们当然知道，乱码和日文并不是一回事。那么乱码到底是怎么回事呢？事实上，乱码出现这个锅完全应该由电脑来背，是由于电脑内部沟通出现了问题。这就就好比来自不同地方的人用方言交流，有时会驴唇不对马嘴：
显然，不同国家的电脑也会说不同的“方言”，不同的“方言”甚至会使用不同的字符。这就需要人们设计出一种最通用的“普通话”，也就是设计出一套通用的编码方案。 工欲善其事，必先利其器。在设计编码方案之前，我们先来看看什么叫做编码。 编码初体验——计算机如何识别字符？ 我们知道，计算机能读懂的语言归根结底都是由“0”和“1”两个数位组成的二进制数。如果把不同的二进制数和一个基本字符（character，例如“abcd”、“ABCD”、“1234”、“!@#$”等）对应起来，我们就构成了一套编码系统。或许最经典的计算机编码系统就是ASCII码（读作阿斯克码），它由不超过七位的二进制数构成，包含了2^7=128个基本字符。下表就是ASCII码和二／八／十六进制数的对照表[1]： Bin表示二进制，Oct表示八进制，Dec表示十进制，Hex表示十六进制[1] 例如，字符“／”在上面这套体系中，对应的二进制数是“01011111”，也就是十进制数的“47”。或许很多读者听说过摩尔斯电码（Morse Code），但一来摩尔斯电码是通过音节编码，二来莫斯电码只编码了26个英文字母和10个数字，所以摩斯电码主要用于电报而非计算机编码。 不过随着人们要求的日益提高，阿斯克码所代表的128个字符已经不能满足要求了，因为不同的国家会采用不同的字符。如今在网络上更加通用的是一种叫做Unicode（万国码）的编码标准。Unicode字符最多可由32位（4个bytes）构成，一共可以编码2^21个字符，例如在本文前言部分中的乱码，在Unicode编码下就变成了如下效果： 在Unicode编码下“日文”进化成了“火星文” 这不是更乱了嘛！不过如果我们仔细对比，可以发现在Unicode解码（解码就是编码的拟过程）下，出现的全都是确定的字符，而在上面这张图中有大量不明字符（用“？”表示），表明这些字符没被编码。之所以Unicode解码没有得到中文，是因为小编有意屏蔽掉了这台电脑的中文字库，让读者们体会一下一些码农的工作日常。 如果我们查看上述文档的十六进制（和二进制同理）表达，结果是这样的： 可用Unix终端的xdd命令来查看文件的十六进制表达 我们不难看出，上图中间部分就是原文本文件的十六进制表示，左边部分是每一行的起始地址，而右边部分是把这些内容翻译为对应的ASCII码。之前提到过ASCII码只能编码128个字符，所以超出阈值或不便显示的字符都被显示成了“.”。由于经由不同编码系统解码后得到的输出会有差异，因此要想翻译出信息的正确内容，必须得先找到正确的编码系统。 编码理论和密码学的差异 在上一节中，我们过了一下译电员的瘾。但不少读者会因此把编码理论和密码学弄混淆。事实上，密码学可以看作编码学的一个分支，因为在广义上说来，编码无非就是把信息从一种形式转换为另一种形式的过程。从这个角度看来，学习外语其实也是一个“编码和解码”的过程。 左图为新东方创始人——俞敏洪 编码理论的创建者就是大名鼎鼎的信息论之父——克劳德·香农（Claude Elwood Shannon）。他在著名的文章《通讯的数学理论》[1]中用严谨的语言对“信息”和、通信”、“解码编码”等诸多概念给出了数学框架，并将热力学中的“熵”（Entropy）这一概念引入到了信息论中，成为了信息论这一全新学科的开山著作。 信息传播六部曲 不过编码理论发展到现在，它所关心的问题渐渐和密码学独立开来。编码理论关心的主要问题是：
前两条都不难理解，它们都体现出了编码系统的效率（Efficiency）。第三点容易被忽略，但其实也非常重要，毕竟环境因素往往是没法人为控制的，因此编码系统的稳定性（Robustness）也是一个很值得研究的问题。在一定误差范围内，信息得以被还原，这样的码被称为纠错码（Error Correcting Code）。当然，纠错码对误差的容忍度是有限的，如果上图中俞敏洪老师的笑容再灿烂一些，那么信息就没法被还原了。 尽管密码学也研究和信息传播相关的问题，但它更关注信息的安全性。和编码（Encoding）的过程相似，加密（Enciphering）本质上也需要对原始信息进行转换，不过对安全性的高要求使得加密后的信息要难以解密。在信息爆炸时代的今天，安全性较高的加密算法还依赖于数论中大质数的复杂性，例如RSA、DSA和椭圆曲线码等[3]。这些密码方案都属于公开密钥加密（Public-key cryptography），拥有私钥和公钥两种密钥。在私钥未知的情况下，仅凭公钥是很难还原出正确信息的。 值得一提的是，量子通信技术的兴起为密码学的发展打开了全新的思路，它的安全性由量子状态的随机性得到保证，不需要像公开密钥那样，依赖于复杂的数学算法[4]。限于篇幅，此处不再展开对密码学的讨论了。 编码理论的数学定义 那么编码如何研究编码系统的有效性和稳定性呢？其实编码理论是数学的一门分支，我们可以以代数为工具来研究它[5]。不过在运用数学工具之前，我们必须清楚地知道要解决什么样的问题以及如何用数学语言描述这些问题，否则一切计算过程和数学定理都是纸老虎。 在编码理论中，一个码（Code）C就是n维线性空间（更一般地，内积空间）的某个线性子空间，而这个n就是每个码字（字符）的长度。考虑到信息总是可以用有限个字符来表示，因此一般情况下，C的每个分量取值于含有q个元素的有限域F_q={0,1,2,...,q-1}上。如果再令M表示C中码字的总个数（一般总有2^n > M），d表示C中码字之间的最小距离（一般说来码字之间的距离就是它们之间不同数位的个数，例如'00001'和'00011'距离为1，'00001'和“30000”距离为2），那么C就是一个q进制的(n,M,d)码。值得一提的是，“有限域”这个概念在编码理论中是一个核心概念，因为域在数学上具有可逆性，这个性质在解码（Decoding，编码的逆）过程中起到关键作用。 例如，容易验证（这些码都定义在有限域F_2 = {0,1}上）：
在这些定义之下不难发现，对于一个好的编码系统C，我们总是希望n尽可能小（消耗内存小）、M尽可能大（编码的个数多）并且d尽可能大（稳定性高）。因此我们就把编码系统的设计问题转化为了一个代数问题——如何在n、M、d三个参数中找到一个折衷点。 也许一些读者会问，为什么d可以用来表示码的稳定性呢？事实上，d如果较大，表明C中任意两个码字都有较大差别，因此就算信息在传递过程中受到了干扰，我们依然有较大概率还原出“正确”的信息。如果一个码字c∊C最多有e个数位出现错误，但依然能还原出正确的c，那么我们就称C是e-纠错码。用三角不等式容易证明，d大于等于2*e+1。如果d=2*e+1，我们称C为完美码（Perfect Code）。 那些能入数学家法眼的“好”码 数学家们大都是完美主义者，可想而知，他们对寻找完美码具有浓厚的兴趣。然而遗憾的是，完美码只有两种，著名的汉明码（Hamming (7,4,3)-code）就是其中一种。它把4位二进制数编码为7位，便因此得以检查并纠正出4位二进制数上的一位错误，算法本身仅依赖于线性代数的基本知识，可参考文献[5]的第三章。汉明码在计算机内存（例如RAM）的设计中应用广泛。 除了汉明码之外，另一种完美码叫Golay码，可惜它和汉明码一样，只能有效对付有限长度的信息。既然完美码应用受限，数学家们当然也不能闲着，他们不再追求完美，转而寻找得以设计出“好”码的一般方式。 功夫不负有心人，数学家们很快就发现了另一类应用广泛的码——BCH码。在数学上，BCH码的生成基于有限域的多项式扩张，也就是著名的伽罗瓦理论（Galois Theory）。粗略地讲，BCH码由某个多项式的根所生成，而伽罗瓦理论则刻画了BCH码的维数以及它的纠错效率，并保证了解码的可能性。因为能同时纠正多个数位错误，二维码、DVD和固态硬盘中都用到了BCH码。 伽罗瓦理论使得较为复杂的域扩张（多项式求根）问题得以转化为相对容易的群论问题 BCH码是一个纯粹数学理论（伽罗瓦理论）和计算机科学的完美结晶，那么还有没有比BCH码更为一般的例子呢？正好在编码理论兴起的年代，代数几何的研究热潮在数学界兴起。数学家们发现，有限域上的代数曲线不仅是研究数论的极佳工具，而且还能通过寻找这些代数曲线上的有理点来定义出一个线性空间！这样的线性空间正好满足一个码的所有需求，这样的码就是代数几何码（或者Goppa码）。 代数几何码的存在唯一性和生成方式都由著名的黎曼-罗赫定理（Riemann-Roch Theorem）所保证。这个定理把数论、拓扑、复分析和代数几何等多个现代数学学科串联为一体，其重要性不言而喻。值得一提的是，密码学中的椭圆曲线加密（Elliptic-curve cryptography）算法也和有限域上的代数曲线有紧密联系（可参考顾险峰老师的文章[6]），但不要把椭圆曲线加密和代数几何码混淆了，两者关心的问题和算法都不相同。小编会在以后的文章中继续探讨这些问题。 黎曼-罗赫定理。左式给出了代数几何码的维数，右式给出了计算维数的方法 总结 到这里，相信读者们已经对编码理论有了一个大概的认识。尽管本质上说来，编码理论是数学的分支，但一个码的好坏与否还需要通过实践来验证，并不是用到的数学越高大上，设计出的码就越“好”。还有许多有名的码未在本文中出现，例如AN码、卷积码（Convolutionary codes）等，具体可参考文献[5]。 在身处信息时代的今天，上网已成为家常便饭，通过网络获取信息已逐渐成为最有效的方式。然而机遇和风险并存，许多人对现代的信息理论认识并不多，因而对通信的原理、信息的鉴别和网络的安全等问题了解颇为有限。这些知识在学校的课本中难以学到，希望这篇文章能在一定程度上引起读者们对这些领域的关注。 站在数学的角度看来，尽管编码理论是数学的应用，但在思维模式上，这种应用和我们所熟知的应用数学有很大不同。事实上，编码理论中用到的数学主要是代数，而我们熟知的应用数学主要是分析。分析和代数是数学学科中两种相对独立的思想，它们的特点和区别可总结如下：
左：曲面上测地线方程的推导；右：把洛伦兹变换和矩阵群（李群）及对应李代数（可以看作曲面上的切向量）关联起来 每种思维都有各自的长处和短处，也都有各自的适用范围。从中学到本科，我国的数学教育都更加强调对学生计算能力的训练，这本质上就是分析思想的体现。然而过多的计算训练容易使得学生对数学这门学科产生偏见，甚至害怕数学，殊不知数学的美妙之处并不仅在于计算过程本身，更在于不同思维模式之间的水乳交融、交相辉映。数学更像是包罗万象的交响乐，而非婉转却单一的独奏曲。 本文来源：科普最前线 |
|
|
