米国一月游手记之夏校篇·四

姨妈，一场随时随地突如其来的考试。早不来晚不来，偏偏在旅行的第一天来。和两个友友去五百米外的超市买姨妈巾，好巧不巧结账处看到了货架上的 frappuccino，这怎么能拒绝！怀着满心的罪恶感反手一抄带回宿舍…

…然后估计胖了好几公斤，甚至当晚两点也没睡着，用万恶的手抓起万恶的小破站，刷视频推了一篇万恶的文。虽只是普普通通无脑甜宠文，可就是看得浑身激动，最后约摸三点阖的眼…（被自己无语住，三更半夜 + 小破站这个组合应该被划入本人未来大学禁止事物名单）

早上睁眼，室友正准备出发，于是五分钟脱眼镜穿衣洗漱在室友电梯关门前冲了进去。时间是八点半，因平时与室友交流不多，没想到她决定在时间蛮近的情况下吃早餐。无奈本人不识路，只好跟着去吃。谁曾向一个打饭的功夫室友人没了，只好使出七年级养成的五分钟干饭技能，然后在其他疑似隔壁同学的娃子们和谷歌地图的带领下跌跌撞撞往课室赶去。

正文

在解决完前一天的所有 Parity Check 的解码后，这天的内容也正式开始引入。老师讲了好一阵子的多项式求解，又讲了好一阵子的余数定理。睡眠严重不足的熬夜人正欲昏昏欲睡时，老师突然引入了一个不太看得懂的概念。具体过程是，将想好的字符按照二进制编码纵使最后勉强按步骤完成了任务，对该概念还是云里雾里，于是想在这里尝试理清。

小剧场

这种探索形美国高中夏校的教学方式就是如此让人讨厌 [doge]

老师：你看这个，这个，这个，是不是很简单
学生：嗯嗯，嗯呢，嗯嗯
老师：——那你再看这一步，是不是很有道理？
学生（懵逼脸）：？
学生：但是这还是不能解释这一步背后的原理呀？
老师：… it just works，能上手做就行了

老师尝试用有趣的方式向学生展示一些非常难懂的原理，并让学生上手自己做一些过程简单但却涉及到复杂原理的小实验。学生本该觉得自己似乎真的学会了一些高深莫测的数学原理与应用。但学生觉得自己不过是个只会看说明书的 fw。

就好比，带你认识数字，然后教会你加减法，然后告诉你：“你会微积分了！是不是就是如此简单！”

有时候成功答题后连题都看不懂，比会做和不会做题都难受…

数据传输中错误的发现和改正

发现问题的方式在昨天已经说过了。在奇偶校验（Parity Check）的过程中，使用 Even parity（XOR）或 Odd parity（XNOR）可以在一组 bits 中出现奇数数量的错误时发现错误的存在。

但是发现问题是远远不够的，得知问题的具体内容并解决问题才是最重要的一步。最简单的解决方案名曰暴力解决法，解决方案是把所有的 bit 都复制三份，譬如将 \(00011011\) 变为 \(000\,\,000\,\,000\,111\,\,111\,\,000\,\,111\,\,111\)。如此一来，只要将每位数字和相邻的两个数字相比较。如果比较后发现有不同之处，那这三个数字中，0 和 1 必定一个占多数，而占多数的一定是正确的，占少数的数字是在传输中发生错误后得出的数字。不过，这么做的好处是，相较于奇偶校验，一组里出现两个及以上错误时也可以发现。然而，就如昨天老师指出的一样，这么做的代价是将传输数据增加数倍，大大降低效率提升成本。

所以暴力解决问题是行不通的，纠错方法需要做到更加简洁有效。

汉明距离

老师引入了 Hamming Distance（汉明距离）这个概念（没错也是之前设计 Hamming's Coding 的先生）。汉明距离指的是两个二进制 register 之间的不同，譬如 \(1101\,\,1001\) 和 \(1001\,\,1101\) 之间的汉明距离是 2，因为从左往右第二位和第六位不同。汉明距离也可以通过 Register 1 XOR Register 2 找到。

提出这个概念是因为，数据传输中要注意的一个重要的方面是让一个 Codeword 不轻易转成另一个 Codeword，而汉明距离则恰好是一个 Codeword 变成另一个 Codeword 需要出错的数字数量。因此如果要检查出 \(d\) 个错误，那么两个 Codeword 之间的汉明距离就必须是 \(d+1\)。而如果要检查并改正 \(d\) 个错误，那么codeword 之间的最小汉明距离则是 \(2d+1\)（和上面暴力解决办法的规律相似）。

Reed-Solomon，有限域和 𝔽₈

之后老师引入了 Reed-Solomon Coding 的加密方式。从之前提到过的多项式开始 —— 两个三阶多项式最多共享三个点（联立等式等于解一个新的三阶多项式，那么最多有三个不同的根）。那么如果将需要加密的消息变为一个多项式，将该多项式上的八个点作为最终传输的 codeword，除去的三个共享的点，两个 codeword 之间的汉明距离至少为 5，那么就可以纠正多个数据传输过程中产生的错误。

将多项式的值作为 codeword 有一个问题，那便是，当阶数提高时，这些值可能会变得非常大，增加数据传输的负担。这个问题的解决方案是，运用有限域，并在有限域中重新定义加法和乘法。这后面的内容，老师过得非常快而且是跳着过的，似乎没想把它讲懂，咱也就没太懂，一部分靠老师讲的，一部分靠查的，大部分靠猜的…

在数学中，有限域算术是有限域（包含有限个元素的域）中的算术，与具有无限个元素的域（如有理数域）中的算术相反（来自维基百科，查重率百分百)。有限域有无限那么多个，它们中的元素数量必须是 \(p^n\) 个，\(p\) 是一个质数，被称为有限域的特征，而 \(n\) 是一个自然数，是有限域的维数。我们在这里讨论的是 𝔽₈，一个共有八个元素的有限域。因为是二进制数据传输，所以相对应的 \(p^n\) 格式应该是 \(2^3\)。这个有限域可以写作 \(GF(2^3)\)。

有限域加法

有限域中的计算先按照无限域的来，然后要对有限域中的特征取模。譬如，特征为 \(5\) 的有限域中，\(3+4\) 的结果不是 \(7\)，而是 \(2\) 模 \(5\)。而在我们特征为 2 的有限域 8 中，加法的运算方式是在正常计算后对 2 取模，譬如 \(1+1\) 结果并不是 \(2\)（10），而是 \(0\) 模 \(2\)，也就是 0，等于去掉进位 carry，只保留个位数。有趣的是，在特征 2 有限域中，加法、减法和 XOR 的结果都是相同的。

有限域乘法

所有特征为 2 的有限域都可以以多项式的方式计算。有限域 8 中，将编码三个为一组组在一起，以系数的形式插入一个阶数递增的多项式 \(f(x)\)（这时 \(f(2)\) 就是该编码转换为十进制后的值）。

本原多项式 \(P(x)\)（Primitive Polynomial），是生成一个可以生成有限域内元素的多项式，且本身不能被进一步因子分解。\(GF(2^3)\) 的本原多项式之一是 \(P(x)=x^3+x+1\)。有限域中乘法的具体算法是在将八个值代入多项式计算完毕后，对本原多项式进行取模。这个解决了前面提到的问题，即阶数过高后导致的数字太大——数字再大对 \(P(x)=x^3+x+1\) 取模后也一定是 \(GF(2^3)\) 中的八个值之一，即 \(0\)、\(1\)、\(x\)、\(x+1\)、\(x^2\)、\(x^2+1\)、\(x^2 + x\)、\(x^2+x+1\)，二进制形式分别是 \(000\)、\(001\)、\(010\)、\(011\)、\(100\)、\(101\)、\(110\)、\(111\)，也就是 \(0\) 到 \(7\) 八个数字。

前面这一堆不完全对，自己也不完全懂，下面就记录一下按老师指引进行的具体步骤。

首先，将要加密的信息按照 ASCII 表转换为二进制，然后将二进制数字三个分为一组，按照下面的表转换为 t 的倍数：

接下来将得到的几个 \(t\) 的不同次方的变量作为系数插入一个变量为 \(x\) 的多项式中（得到几个 \(t\) 的倍数就整几项。在这之后，分别算出 \(f(0)\)、\(f(1)\)、\(f(t)\)、\(f(t^1)\) 一直到 \(f(t^7)\)。在计算过程中，不作进位处理（联系之前提到的特征 2 有限域加法），将最终答案限制为一个三位的二进制编码。将 \(f(0)\) 到 \(f(t^7)\) 的十组数字拼在一起，得到共三十位的二进制编码，就是最后被传输的 codeword。

譬如，加密文字信息“NO”，根据 ASCII 表，相应的二进制字符是：\(001110\,\,\,001111\)。三个数字分为一组后，\(001\) 对应 \(1\)、\(110\) 对应 \(t^4\)、\(111\) 对应 \(t^5\)，因此最后得出 \(1, \,\,\,t^4, \,\,\, 1, \,\,\,t^5\) 四个系数。 按顺序代入多项式后（系数为蓝色），得到：

$${\color{#0084ff}1}\cdot x^0+{\color{#0084ff}t^{\color{#0084ff}4}}\cdot x^1+{\color{#0084ff}1}\cdot x^2+{\color{#0084ff}t^{\color{#0084ff}5}} \cdot x^3$$

然后依次求 \(f(0)\) 到 \(f(t^7)\)，这里就不一一计算了，最后得到的是 \(001\,\,\,001\,\,\,000\,\,\,100\,\,\,100\,\,\,010\)…的这样一串数字。

此 codeword 妙处在于，数据传输中即使出现了错误，在一定情况下也可以得出正确结果。老师将大家得出的 codeword 进行了一些破坏（将一部分 \(0\) 变成 \(1\)、\(1\) 变成 \(0\)，然后带着大家用自己编写的 python 解码程序对破坏后的 codeword 进行解码。神奇的是，大部分 codeword 都可以被成功转换为最开始的文字，只不过被篡改更多的 codeword 在被解码的过程中，程序对最终结果的正确率预测相较未篡改的 codeword 更高。

解码

前面提到的，解码方式是用老师提前设置好的 python 解码程序。编码就已经不太理解了，解码自然也完全毫无头绪。据助教学长说，手工解码可能要花上上月的时间，可见解码程序的精妙之处，只不过大家都不懂它是怎么运作的就对了。

在最后，老师结束了今天的话题，为了给明天做准备（课上太快时间没上完），展开了对于互联网的一系列话题，包括互联网的定义，互联网的历史和发展等等。通过 Wayback Machine 向大家展示 1960 年的 Yahoo。那时没有搜索引擎的概念，所有网页只能通过索引查看，而该索引是人工维护的，网页数量有限，且查找起来也十分麻烦。于是不出所料不久后，这样麻烦的索引就被谷歌替代了。老师十分自豪地说，谷歌搜索引擎的创始人之一是密歇根大学毕业的，老师还是他的数学老师…

为了模拟网页蜘蛛是怎样根据页面之间的联系，通过权重决定一个网页的重要性，老师举了个扔飞碟的例子 —— 一家四口围成一个圈扔飞碟时每个人可能获得飞碟的概率。这部分实在轻松简单，让我不禁怀疑半个小时前老师是否还在讲一些俺搜了三四天还不太能理解的有限域概念…

极其诱人的午餐和脑子晕得忘记拍的晚餐~

标签： 游记 生活

赞 2

微信

打赏