CM · 噪声与信息

纠错编码

香农保证了在容量之下差错可以接近 0，却没有透露方法。本单元要说明：在数据后面附加按规则算出的多余比特，就能察觉被噪声翻转的比特，甚至能找出错的是哪一位并把它纠正过来。

一个翻转的比特，三种编码的应对

蓝色格子是收到的数据位，金色格子是附加的校验位，红框格子是被噪声翻转的那一位。依次按下无保护、奇偶校验、汉明，就能并排比较三种码如何处理同一个一位错误。只发数据时连出错都察觉不到；一个奇偶校验位只能察觉出错；汉明码则能找出是哪一位并把它纠正。

码长与最小距离

n = 4, k = 4 · d_min = 1

无保护

噪声翻转比特

噪声偶尔会在接收端把 0 变成 1、把 1 变成 0。图中原来的数据是 1011，第二位被翻转，结果以 1111 到达。如果只发送数据位，1111 也是一个完好的 4 位数据，接收机连出了错都无从知道。因为任何位模式作为数据都同样合理。

冗余比特当哨兵

附加上按规则从数据算出的校验位，情况就不同了。最简单的奇偶校验位是所有数据位的 XOR，它总让 1 的个数保持为偶数。原数据 1011 中有三个 1，所以校验位是 1；第二位一翻转，1 就变成五个，成了奇数，校验便对不上。接收机由此知道出了错，但单凭一个奇偶校验位，查不出错的是哪一位。

观察p = d₁ ⊕ d₂ ⊕ d₃ ⊕ d₄

奇偶校验是数据比特的 XOR。

选择detect 1: d_min ?

要检出一位错误，最小距离 2 就够了。

距离带来纠正

把码字看成点，好的码会让有效的点彼此离得远远的。两个码字取值不同的位数叫作汉明距离；有效码字之间的最小距离为 2 时能检出一位错误，为 3 时还能纠正。因为错了一位的字，依然离原来的码字最近。汉明(7,4)码用 3 个校验位，就能在 7 位中找出任意一位的错误。三个校验位各自守护一组不同的数据位，所以哪些校验对不上的组合，会唯一地指向被翻转的位置。代价是码率 R = k/n = 4/7，也就是为了传 4 位信息要付出 3 位的冗余。

填空correct 1: d_min ≥ ?

要纠正一位错误，最小距离必须是 3。

自己来R = kn = ?

码率是数据位数除以总位数的值。

回到第一屏

没有保护时，被翻转的位看起来就像正常的数据，呈红色。加上一个奇偶校验位后，出现了“有地方不对”的信号，却不知道是哪一位，呈橙色；汉明码的校验位把不一致之处汇总起来，准确找出那一位并把它翻回去，就变成了金色。要记住的只有一点：用多余的比特让有效的字彼此远离，被噪声推开一步的字也会回到离它最近的原字上。香农所承诺的、容量之下的可靠性，就是这样实现的。

差错编码在数据后附加按规则算出的多余校验位，用来检出并纠正被噪声翻转的比特。一个奇偶校验位(最小距离 2)能检出一位错误；最小汉明距离不小于 3 的码(例如汉明(7,4))能找出并纠正一位错误。有效码字离得越远，码就越强，但代价是码率 R = k/n 小于 1。这正是香农容量定理在构造层面的另一面。

通信单元到此结束

从“为什么要调制”出发，我们一路跟着一条消息走完了全程。把基带的微小起伏加载到载波上、搬到频率轴高处(AM·FM)，变成数字(采样·PCM)，再用比特去摇动载波(ASK·FSK·PSK)。接着遇到了带宽的上限，测量了噪声与 SNR，用概率驯服了随机，看到了香农的绝对极限，最后在这个极限之下用编码把差错纠正回来。说到底，通信就是在充满噪声的世界里把消息完整地递过去的技术。