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

迎接夏校活力满满的第一天从一巴掌拍掉可怕的铃声开始。室友早早去干午饭，微信留了条消息，有点暖心。日常不吃早餐的减肥人于是慢吞吞起床等室友回来。

距离上课二十分钟，跟着室友便出发了。校园里风很大，像是无形的巴掌乎乎地拍在脸上，使人愈发清醒。本人的刘海还处于尴尬期，本就不太蓬松，劲风一吹全部向后飞，好像秃头人掉了假发一样，于是仓皇继续向教室赶去。

教室在东楼，而宿舍远在南楼。屁颠屁颠跟在室友后面穿过七扭十八弯的各科教学楼，作为一个路痴无时无刻不在想，我是谁，我在哪，我怎么来这的，我要去哪里…索性十分钟后便到达了上课所在的数学部门。

早上第一节课前是一个 Computing Orientation，登录学校账号邮箱以及一系列邮箱配置的组织下的免费谷歌服务。

这一天的内容围绕 Parity check，也就是奇偶校验。这才意识到前一天帽子游戏的目的，原来是想通过游戏对大家进行启发。

奇偶校验 Parity Check，通过给每一行每一列的数字加上一个 parity bit，来保证整行或整列数字“1”的数量是一个偶数。譬如原来一行或一列数字中“1”的数量为奇数，那么补上一个 1，如果原来是偶数，那便加上一个“0”。在接受数据的时候进行 parity check，如果某行和某列的的 parity 检查结果同时异常，那么传输错误的数据很可能就在这一行的这一列上。

班上同学大部分都是对数学非常感兴趣的，学计算机的似乎并不多。喜欢 Robotics 的不少，很多甚至参加过同一个比赛。好在这次的课程和 Robotics 关系并不大。关于 parity check 的相关知识，同学似乎没怎么学过，老师问起这个问题时大部分小组讨论出的答案是将数字多传输几次，进行反复检查，不过耗费资源且不容易得知出错数据的具体位置。

如何用最少的数字进行 Parity Check - 这是部分内容蛮有意思，在计算机课上学的 parity check 都是按照行和列进行的，譬如传输内容为“1 1 1 1”的四个 bit，那么就将四个数字变成一个正方形：

$$1\,\,\,1\\1\,\,\,1$$

然后在数字的行和列的边缘加上 parity bit，因行和列上“1”的数量为偶数，所以 parity bit 都是 0。

$$1\,\,\,1\,\,\,{\color{#0084ff}0}\\1\,\,\,1 \,\,\,{\color{#0084ff}0}\\\color{#0084ff}0\,\,\,\color{#0084ff}0\,\,\,\,\,\,$$

这种情况下，需要传输的数据大小为 4 bit，encode 后传输的数据大小为 8 bit。 问题来了，有没有可以进一步减少数据大小的方式呢？

其中尝试过许多添加 parity check 的方式，将数据划成几组，分别用一个 parity bit 检查，但尝试多次连连失败

大家哀嚎：“我们是 fw——”

索性最后有个同学想了出来，老师让给这个划分方法起个名，耿直的理工男孩往旁边一扫，道：“就叫柠檬水划分法！”

这玩意的正解和同学想的所差无几，不过工整许多。划分法是有名字的，大名“Hamming's Code"

上图：Hamming's Code 示意图，侵删

其中，\(m_1\)、\(m_2\)、\(m_3\)、\(m_4\) 是要传输的四个数字，而 \(p_1\)、\(p_2\)、\(p_3\) 则是会使用到的三个 parity bits，比之前按行和列分的方法少用一个 bit，在传输大量数据时可大大提高效率。

接下来下午的时间便开始了一个游戏——同学们通过对照着 ASCII 表用二进制表达一段词句，然后用 Hamming's Code 对数据进行 encode。老师则会模拟坎坷重重的数据传输过程，随机修改数据，1 变成 0、0 变成 1（但是一个字符最多只会改一个数字，否则 parity check 看不出端倪）。然后向同学们分发篡改后的数据。同学需判断错误的数据，改成正确的，从而推断出想要传输的信息。

在这一游戏中总结出几个看起来显而易见、实践起来颇为脑壳疼的规律：

1. 用三个 parity bits 和相应的数字进行对照，如果出现了错误：

1. 如果只有一个错误，那么一定是 parity bits 出错

2. 如果前两个 parity check 出错，那一定是 \(m_1\) 出错

3. 如果后两个 parity check 出错，那一定是 \(m_3\) 出错

4. 如果收尾两个 parity check 出错，那一定是 \(m_2\) 出错

5. 如果三个 parity check 一起出错，那一定是 \(m_4\) 出错

2. 根据以上步骤，如果解出来的数据奇奇怪怪的，那么一定看岔了

3. 如果检查后数据仍旧奇奇怪怪，那么是 encode 数据的同学的脑壳出错

下课时刚好解出隔壁桌同学的二进制加密内容，内容是“柠檬汁”，怪可爱的。四点半，天色尚早，回到宿舍是五点。但是食堂六点半关，赶紧急匆匆赶去干饭。好长一段时间没体验过的独在异乡的慌乱感再次席卷上心头。不过填饱肚子之后哪里还会有什么胡思乱想。此处再次大夸学校的伙食。学校是自助餐式的，每日三餐各式各样且供应量很足（此处想让某些参加完中午学校活动后汤面只剩汤墨西哥饼只剩饼皮的某某书院学着点）午餐——

右边大概是东南亚风味的甜酸面，左边是 Fish and Chips 但是为了减少碳水只吃了 Fish。晚餐——

鸡肉 French Beans 和鸡扒。虽然还未特别深度了解过密歇根大学，它绝对是一个能用超棒伙食和浴室让人踏实安适的学习圣地。

万里飞来颜愈少，笑道，此心安处是吾乡。

标签： 游记 生活

赞 2

微信

打赏