今天我们来学习编码中一个非常重要的编码类型——纠错码，以及自然地，这种纠错码的思想是如何应用到魔术中的。通信一般至少需要信源和信宿的一对才能完成，上个通信初步系列中，魔术师是信宿接受信息没什么说的，信源的话，要不就是明目张胆地就是表演者之一（《傅氏幻术》和我的心灵感应），要不就是观众在不经意间当了信源（《3 * 7的感应》和《街头猜姓氏》），而在这类魔术中还有一类，是需要托帮忙的。且不同于一般地托在魔术过程中帮助通信，这个则是托通过预设的纠错码，来帮助魔术师直接完成判断，使得魔术师仅仅是在判断纠错点位，而并非直接拿信息解码，这样就能更好的地把托隐藏起来，魔术上做到效果制造与呈现的分离，十分巧妙。在编码通信领域，噪音的降低和去除是一个十分重要的议题，好在我们数学魔术里用到的这些简单的通信模型，在不是表演特别离谱或者出现错误的情况下，可以看作是没有噪音的。但是，编码上有一个对噪音重要的处理方法——添加冗余的校验码作信息校验，这虽然不直接为通信编码的魔术所用，但是可以作为一个思路，创作出一系列比直接用托来编码通信更加令人信服的表演。因为在这种表演中，托显式的编码通信过程是不存在的，而是在起点处就暗藏信号本身的某种规律，类似于使得一系列向量并不线性相关的暗中关系。自然地，真正的观众再去做一些选择的信号，就会自动地在这套系统里毫不被不察觉地表达出来了。
那在真正的编码通信领域，是怎么降低噪音影响的呢？大体有3种方法，而且都非常朴素和直观，完全不像真的数学那样难以理解。一为重复，无非就是把同一条信息多传输几次，在人类语言中，经常不也有类似于I beg you pardon这样请求重复通信的语言；二为冗余，我们存储和传输的信息是很难做到按照信息论估计的上界那样刚好用平均用熵那么多bit来编码一个对象的，这里有我们对估计不准，二进制编码方式的限制，以及我们其实并不能够真的去追求那样的极限情况，得均衡些。除了计算机领域已经数学化得越快越好，压缩越大越好这种定义边界清晰的问题，冗余和长度一定是在一个中间态取到合适的值，再冗余就没必要了，再精简又怕有更多错误了。比如我们的自然语言，包括文字的写法图片，都是有大量冗余的，但这是我们的文化，我们习惯的编码方式，是可执行的小步迭代下的当下最优。
而其三，就是校验，也是这个系列魔术想分享的主要原理。业界常用的比如奇偶校验，和校验应该是我们耳熟能详的经典了。此外，还有作为散列函数的循环冗余校验CRC，以及加密散列函数等，而格雷码则是在编码的过程中引入相邻数代码仅有1位不同，使得其自动具有纠错码的功能。当然还有专门用来不仅检错还要完成有限数量的纠错的错误纠正码，比如我们接下来要讲的Hamming码就是其中一个典型代表。汉明码，是一种线性纠错码，由汉明于1950年发明。相比而言，简单的奇偶校验码除了不能纠正错误之外，也只能侦测出奇数个的错误。汉明码是完备码，它在与它分组长度相同、最小距离为3的码中能达到最高的码率。用数学术语来说，汉明码是一种二元线性码。对于所有整数 r ≥ 2，存在一个分组长度 n = 2 ^ r − 1、k = 2 ^ r − r − 1 编码。因此汉明码的码率为 R = k / n = 1 − r / (2 ^ r − 1)，对于最小距离为3、分组长度为 2 ^ r − 1 的码来说是最高的。汉明码的奇偶校验矩阵的是通过列出所有长度为 r 的非零列向量构成的。我知道你已经犯迷糊了，这都什么乱七八糟的啊，别担心，我给你说下思路，推导一番，你就明白了。一般的奇偶校验，如上期所说，只有一个校验位，也就是自由度仅仅下降1，提供1bit的隐含信息。故只能判断奇数个错误的有无，这种最多1个bit的信息。更多的比如具体哪一个bit位，是什么错误（如果是二进制编码，没有错位的情况下，错误只有一种，就是位取反）就无法获取了。理论上，这种哪个位置的信息的信息量就是原信息的位数取对数，前提是仅检测1个错误的位置；若全部都有可能出错，那信息量就是位数了。不过完全没必要为了保证通信的纠错能力到那么高的级别使得效率如此之低，我们仍然先假设仅有1个可能错误。
设待传输的信号长度为k位，我们试图寻找一个长度为n的编码，带(n - k)位纠错码，能够保证定位到1位错误以及其位置。注意这里的位置包括原信号位，也可能是校验位，共n种可能，故根据信息论，有logn的信息，需要由r位校验位编码出来，则2 ^ r >= n。这是理论值，但实际上，因为这里不是真的在编码，而是校验，不一定能够达到，于是我们尝试找一个思路来构造这个校验位的位置和取值方式。
可以看到，校验位数约摸是编码长度的对数级大小，那怎样设置校验码位置恰好满足这一点呢？自然是取2的整数次幂位置，1, 2, 4, ......2 ^ (r - 1)共计r位设其值为p1, p2, ......, pr，其余k位顺序填在依次相应的空格里，分别为c1, c2, ......, ck，其位置为q1, q2, ......, qk。而在整个加了校验位的序列上，即为p1, p2, c1, p3, c2, c3, c4, p4,......, pr, ......, ck，重新设这个序列为sn。于是每个位置都可以表达为一个r位的2进制数，其中one-hot的为校验位。那么，我们可以构造校验位的r个线性方程为：sum(j in 1:k)(cj * qj[i]) = ci，i in 1:r，qj[i]表示位置编号qj的第i位的二进制值，其中加法采用的是二进制的不进位加法，也就是亦或运算，或者mod2加法。
由此我们可以看到，我们需要的r的大小实际满足log(k + r + 1) <= r，即最差的情况是填满k位后下一个就要填r的位置了，此时对应码率最高的情况，其综合码率是：R = k / n = 1 - r / (2 ^ r - 1)，可以看到，当r增大的时候，码率是越来越趋向于1的。而这个最优的情况取2 ^ r - 1 = n，离我们的n的最大传输量n仅仅小了。
这就是Hamming Code的全部内容了，它本质上就是加上校验位以后最大位数那么多个线性方程组的校验。其实方程组本身是不区分哪个是校验位哪个是原码位的，这里把校验位和原码位分开看反而掩盖了本质。有一条很有意思的性质，就是mod2的加法和减法，本来是互逆的两个运算，却完全相同。这本质也是C2群的性质，f ^ 2 = e也即f ^ - 1 = f。表面上它也表述为亦或运算的逆运算和本身相同，不进位减法性质同加法，但本质都是C2群性质。于是，我们的线性方程组可以改写为：
sum(j in 1:n)(sj * j[i]) = 0，i in 1:r看到了吧，还要多简单，就是n位的编码，用r个方程校验n个未知数sn，校验方式就是取每个位的码值和位的位编码的内积等于0，即正交。
于是怎么用Hamming码校验就一目了然了，假设有且仅有1个编码位改变，那我们只需要观测这r个方程有否有不再成立的，第i个方程不再成立，说明改变位一定在使得j[i] = 1的系数位置上，也即，改变位的第i位编码值为1。反之，如果确定是1个改变，那如果第i个方程仍然成立，改变位的第i位编码值就是0了。所以，这r个方程的成立与否，直接编码出了唯一的错误编码的位置！妙啊！同时也可以看到，因为0位置无法被编码，因为方程一旦成立总就会多一个可能是0，所以必须要浪费一个编码位0。因此我们的方案要比信息论理论方案多的一点点，也得到了合理的解释，因为我们其实想去把整个方程组全部成立编码成没有错误，这样实际多了一种可能，代替了0位的信息，也是十分地巧妙。
好了，以上就是正统的Hamming Code的全部内容，希望对数学感兴趣的小伙伴仔细研读消化，一定可以让你有所收获。不过，在魔术中，我们可用不上这么复杂的编码校验，你会看到，下一篇中的《矩阵校验码》就以数量取胜，直接通过9个校验码把横纵坐标都编码出来了，虽然浪费，倒也简单。接着还会介绍几个在《Mathematical Card Tricks》里的几个作品，都是类似Hamming编码的简单应用，看看我们如何在数学魔术里以小见大，窥探其中的神奇奥秘。
|
