|
星系的颜色从哪里来？我们一定要担心宇宙射线吗？太阳将所归何处？存在其他的宇宙吗？为什么只有我们的宇宙演进化出了智慧生命？ 如何才能得到这本《宇宙之美：从大爆炸到大坍缩，跨越200亿年的宇宙编年史》呢？参与的方式非常简单！只要你认真阅读下面的这篇文章，思考文末提出的问题，严格按照 互动：你的答案 的格式在评论区留言，就有机会获得奖品！（PS：格式不符合要求者无效）截止到本周四中午12点，精选留言点赞数前三名的朋友将获得一本《宇宙之美：从大爆炸到大坍缩，跨越200亿年的宇宙编年史》。
我生活在充满各类信息的社会。人们可以轻松的与地球另一端的同胞交流。这就是为什么21世纪又被称作信息时代。但是无论信息以什么形式传播，通过电话，互联网或者卫星，都有可能在传播过程中混入一些错误。背景噪声，系统错误，甚至宇宙射线都可能打乱我们传递的信息。幸运的是，人类提出了一些编码数据的方式，让传输中的错误可以被检测到甚至纠正。下面我们简单介绍一下这类编码是如何起作用的。 错误检测码 早在人们用手抄来实现书籍复制的时候，纠错的需求也随之出现了。当然对于重要的手抄本，比如律法或者行政命令，保证手抄本无错误是非常重要的。但是，逐一检查每个词是一个极其费时费力的过程。所以人们想出了一些替代方案，比如统计原文每个段落的单词数，再数一数抄写得到的复制本中对应的单词数，如果两者不一致，说明一定出了问题。 15世纪的抄写员，装裱家，翻译家和作家Jean Miélot在他的书桌前 现代数字信息是由很多0和1组成的序列。当我们采用如同上面一样思路来检查我们的信息时，通常会涉及到所谓的哈希函数。需要传递的信息序列通过一个哈希函数计算后会得到一小段数据。我们将这段数据贴在需要传递的数据后面。接收者就可以拿接受到的信息利用同一个哈希函数重新这段数据，并与接受到的数据尾部结果对比，如果不一致说明传递过程引入了错误。 举个最简单的例子，我们就将所有需要传递的信息序列按位加在一起，按照二进制的运算法则：0+0=0,0+1=1,1+0=1,1+1=0，最后我们会得到一个0或者1，将它放在数据序列最后再传递数据，比如开始信息为111，则传递时候变成1111，如果开始为101，传递出的信息为1010。收到信息的人检查每一位的和就可以判断信息是否可能出错。 另外一个更常见的例子是商品上的条形码，条形码通常按照UPC-A或者EAN-13标准编码。以UPC-A为例，其由12位数字组成，第一位一般表示生产者的国籍或者其他特定信息，比如ISBN号。第2到6位放在一起表示产品生产商编号，第7到11位放在一起表示产品的编号，最后一位是矫正位，作用和上面一致，可以纠正扫码时候出现的错误。 同样的手法也被用在信用卡卡号上，其运用了Luhn算法（专门用来计算10进制数列的一种算法）来计算纠正位。 错误纠正码 当我们发现得到的信息有错误时，我们会怎么做呢？当然有很多办法。比如最简单有效的，让整个系统停下来，直到问题被解决。比如大家都遇见过的windows蓝屏。 Windows8的蓝屏死机 之所以会这样，是因为一般不做任何处理比做一些明知道是错的事情更好。然而我们在这种情况下，一般可以做的事只有重启系统，这样我们很可能会漏掉系统运行过程中得到的其他信息。 第二种处理方法叫自动重复请求。顾名思义，我们重新索取传递中出问题的信息直到我们认为信息正确为止。这广泛运用在互联网通讯。当然生活中也会遇到，在超市里你买的商品条形码第一次扫描没成功，一般你都会再扫一遍。 然而有时候这种重复操作也不可行，比如我们需要实时通讯，像在卫星通讯，移动电话或者读取CD中。这些情况下我们必须试图修正错误。通常的办法是向传递的数字序列里加入一些多余的位用于修复可能发生的错误。其简单的原理是一些字母编码不同于其他字母，当发生少量错误时候，它们彼此应该依然不同。这种纠错码最先由贝尔实验室的理查德·卫斯里·汉明（Richard Wesley Hamming）于1947年发明。（译注：他也因此获得了1968年图灵奖） 为了理解纠错码是如何工作的，我们先定义两个序列的hamming距离，其就是两个序列对应不同位数的个数，比如111010和101111的hamming距离就是3，因为显然它们有三位不一样。如果噪声改变了这两个序列其中一位，我们依然可以分辨它们。同样的，我们可以给字母编码使不同字母编码之间的hamming距离足够大，使少量错误发生时候我们依然能分辨出来。 举个简单例子，0到7这8个数字写成二进制，为 000 (0) 001 (1) 010 (2) 011 (3) 100 (4) 101 (5) 110 (6) 111 (7) 显然每个数字编码之间最小的hamming距离为1，比如011(3)发生一位错误就可能变成010(2)显然这种编码没有纠错能力。 我们在上面的编码后面每个再加三位，变成： 000 000 (0) 001 110 (1) 010 011 (2) 011 101 (3) 100 101 (4) 101 011 (5) 110 110 (6) 111 000 (7) 这样每个数字编码之间的hamming距离变为3.假设错误发生概率很低，每个编码传递时候最多只能发生一个错误，我们就可以纠正这种错误，比如我们传递101 011 (5)时候，接受者得到的序列变成了100 011，那接受者就可以寻找离得到序列的hamming距离最小的编码，即101 011，其与结果序列的hamming距离为1，错误就得到了纠正。 星际航行，Facebook和CD 所有错误纠正码都是同样的设计，受到一个序列后，如果不在编码表里，我们就寻找一个离它最近的编码。当然设计一套编码方案是非常复杂的，需要很多高深的数学知识。但最基本的都需要每个编码之间尽可能的不同。此外，一个优秀的编码方案要求纠正错误时候尽可能的高效可靠。 1960年，里德和所罗门提出用他们名字命名的RS码（Reed-solomon codes）。它的第一个大规模商业运用是1982年的CD上面，用于恢复被刮伤的CD上面的音乐。尽管在很多地方，RS码渐渐被更容易并行的LDPC码取代，但是它现在仍广泛用于数字存储和数字通讯里。RS码最常用于大规模存储器，纠正由储存介质缺陷造成的偶发错误，平均32比特数据可以纠正2比特错误。值得一提的是，1977年发射升空的旅行者一号，它与地球的通讯就采用RS码编码，它向地球传回了土星、木星和其他一些遥远星星的图片。 今天最大的RS码使用者是Facebook。Facebook或许是现在世界上最大信息库，每天约有3亿张照片被存储在Facebook上。这些信息被分散存在世界各个数据服务器上，虽然每个数据存储器发生错误的可能非常小，但是由于Facebook获得的数据量太大，造成必须利用RS码纠正或许每时每刻都会发生在某个存储器磁盘的错误，保证Facebook的正常运转。 数学细节 最后一部分我们将给有兴趣的同学一些数学细节。研究如何高效编码的学科被称为编码理论，是很重要的应用数学分支之一。 我们先介绍Hamming（7，4）码。它是一种3个冗余位4个信息位组成的编码，如果x是序列x=(d1,d2,d3,d4)，传输的信息是y=(p1,p2,d1,p3,d2,d3,d4)， p1,p2,p3都是冗余位，如何确定它们可以参考下图，我们要求选定 p1,p2,p3使得每个圈里相加都必须为0。 即必须有 p1+d1+d2+d4=0 p2+d3+d1+d4=0 p3+d3+d2+d4=0 比如 x=(1,1,0,1),可以计算出y=(1,0,1,0,1,0,1) 如果我们收到一个错误信息比如y=(1,0,1,0,1,1,1)，我们重新计算每个圈的位数的和，如果为1说明该圈内某个量出现了错误。对于我们的例子y=(1,0,1,0,1,1,1)，简单计算得到只有红色和蓝色的圈内的求和为1，那么我们知道是d3位出现了错误。 实际上，RS码的构造是先将需要传递的n位信息映射到多项式的系数上的，传递的数据实际上是n+t维多项式的系数（t为冗余位数目）。不过神奇的是，正如Hamming（7，4）码一样，我们可以写出编码结果和原始信息之间的矩阵，熟悉近世代数的同学或许直接就看出这是有限域GF(2)上面的线性空间之间的线性变换。换言之我们似乎利用了线性代数和多项式理论的某种联系，这就是Galois理论，由伟大的法国数学家Galois在其年仅19岁时候提出。 编辑：山寺小沙弥 |
|
|
来自： 人老颠东 > 《人工智能和机器学习》
