写在前面备考软考学到校验码这一章时我一直以为自己懂了——不就是加个奇偶校验位嘛。直到最近和几个笨问题较劲才发现我之前的理解几乎全是错的。这篇文章把颠覆我认知的几个点整理出来希望帮到和我一样以为懂了的朋友。一、先说我以前的错误理解在真正搞懂之前我的脑子里大概是这样一幅图景数据位是正经货校验位是监工负责盯着数据位接收方收到数据后让监工检查一下没问题就放行既然校验位也可能出错那校验这事多少有点看运气的成分。如果你也是这么想的恭喜你这篇文章就是为你写的。这三个理解全错。正确答案一句话就能说完校验的本质是通过加冗余位人为地把码距撑大。校验位不是监工而是和数据位平起平坐的参与者接收方验收的是整个码字不是验收校验位。下面慢慢展开。二、码距是什么先把这个概念摁死码距 两个编码之间有多少个位置不一样。数一数就行。举例0011和0010只有最后一位不同 → 码距是 10011和1100四个位全不同 → 码距是 4一个编码系统里有很多合法码字事先约定好、有意义的编码。把所有合法码字两两比较最小的那个距离就是这个系统的码距。三、用间谍暗号理解码距为什么重要这是我觉得最好用的类比后面全程用它。假设间谍接头只约定了两个暗号000代表平安和111代表有情况。这两个合法暗号差 3 位所以系统码距 3。现在对方发来一个暗号传输中可能被干扰改了几位场景 1收到001这不是合法暗号——你知道出错了这叫检错。再看它离谁近离000差 1 位离111差 2 位明显更可能是000被改错的 →你能猜回原意这叫纠错。场景 2收到011同样不合法你知道出错了。但它离000差 2 位离111只差 1 位——等等这个例子离111近那就纠成111。好那换个更刁钻的错 2 位时错码可能离两个合法码字一样近分不清原配是谁只能干瞪眼——能检错不能纠错。场景 3运气极差3 位全错000变成了111——恰好撞上另一个合法暗号接收方毫无察觉把平安读成了有情况。彻底漏检。三个场景看完结论自己浮出来了码距越大暗号之间差得越多传错之后越容易落进非法区域被发现也越容易离原配最近被猜回去。码距就是衡量一套编码抗揍能力的尺子。四、两条铁律所有校验码的能力都从这里推表格目标需要的码距检出d 位错误≥ d 1纠正d 位错误≥ 2d 1为什么检错是 d1因为只要码距大于 d错 d 位之后的结果必然不是任何合法码字——落在非法区域一眼看穿。为什么纠错是 2d1因为要猜回原配必须保证错码离原码字距离 d比离任何其他码字至少 d1都近加起来就是 d (d1) 2d1。以码距 3为例走一遍错 1 位错码离原码字距离 1离其他合法码字至少 2最近的就是原配 →能纠 1 位错 2 位可能离两个合法码字一样近分不清原配但这不是合法暗号还是看得出来的 →能检 2 位。所以码距 3 纠 1 位或检 2 位注意是或同一套编码同一时刻只能选一种用法后面讲为什么。常用结论对照表软考可以直接背表格码距能干什么典型代表1啥也干不了错 1 位就变成另一个合法码字无校验的裸数据2检 1 位奇偶校验3纠 1 位或检 2 位海明码4纠 1 位 检 2 位扩展海明码SEC-DED五、颠覆点一校验的本质是花钱买距离这是我第一个被颠覆的地方。以前以为校验是加个监工现在明白了校验是在撑大码距。不加校验时n 位二进制2ⁿ 种组合全是合法码字。3 位就是 000~111 八个全有意义任意两个合法码字最小只差 1 位码距 1。错一位000变001还是合法的——错了也看不出来神仙都救不了。加 1 位奇偶校验后3 位数据变 4 位。4 位共 16 种组合但只有 8 种合法满足奇偶规则的那 8 个。合法码字在更大的空间里被摊薄了彼此之间的距离自然被拉开了。奇偶校验合法码字占一半码距从 1 撑到 2 → 能检 1 位海明码加更多冗余位码距撑到 3 → 能纠 1 位重复码同一内容发三遍码距直接到 3 甚至更大纠错能力强但浪费惊人。逻辑链条加冗余位 → 编码空间变大、合法码字数量不变 → 合法码字之间距离变大 → 出错更容易落进非法区域检错且离原码字仍然最近纠错。代价也明明白白冗余位占带宽、占存储。校验能力越强冗余越多效率越低。所以工程上永远在可靠性和开销之间找平衡——内存用 ECC、网络用 CRC、简单场景一位奇偶就够全是这个权衡的产物。一句话校验不是变魔法是花钱买距离。六、颠覆点二承诺范围内检错是 100% 确定的我以前以为校验位也可能出错所以检错这事多少有点概率成分。这个理解要拆成两段修正第一段在码距承诺的范围内检错是数学上 100% 保证的没有概率。奇偶校验码距 2只要恰好错 1 位必然被发现。因为错 1 位后结果必然落在非法区域这是数学保证死的不存在碰巧没发现。第二段超出承诺范围才可能漏检。奇偶校验错 2 位奇偶性又变回去了恰好撞上另一个合法码字 → 彻底漏检接收方毫无察觉。错 4 位、6 位同理。所以准确的说法是校验码保证发现 d 位以内的错误d 码距 − 1超出这个位数才可能漏检。那实际工程为什么敢用因为多位同时错的概率极低。比如 CRC-32漏检概率在 2⁻³² 量级——这不是校验机制不可靠而是坏到那个程度的概率可以当成工程上不可能。七、颠覆点三数据全对却被判错真的会发生顺着校验位也可能出错往下推有个很真实的场景数据位一个都没错只有校验位自己翻了。这时校验不通过系统判定出错了。数据明明是对的却被判成了错的。但注意这不是校验机制的失误。因为接收方根本无法区分错的到底是数据位还是校验位——站在它的角度整个码字就是坏了报警是唯一合理的选择。大不了重传一次数据本来没错重传来的还是那份对的数据没有实际损失。还有一个更狠的情况专治带纠错能力的编码越纠越错。码距 3 的海明码如果实际错了 2 位错码可能离另一个合法码字更近。纠错机制会自信地把数据纠成那个错的码字——本来只是传错了纠完反而变成一份看起来合法的错误数据。这就是为什么工程上的海明码普遍配成纠 1 检 2码距 4即 SEC-DED错 1 位就纠错 2 位老实报警宁可多报错绝不瞎纠。八、颠覆点四校验位不是监工是参与者回到开头那个监工的比喻它错在哪错在把校验位当成了特殊角色。真相是接收方收到的是一整串比特它从来不问校验位对不对只问这一整串是合法码字吗是合法的 → 认为没出错取数据部分用不合法 → 整个码字作废报错或按纠错规则找最近的合法码字。码距是定义在整个码字数据位 校验位上的距离抗错能力是整串的性质不是校验位单独提供的。校验位只是这串比特里普普通通的一位。海明码把这个体现得最彻底它算出来的校正子syndrome是一个位置编号指出第几位错了——这个位置可能是数据位也可能是校验位纠错机制一视同仁翻到谁改谁。如果接收方真是依赖校验位检查数据的思路那校验位自己错了它就没辙了。正因为它是把整串当整体看待校验位错了照样能定位、能纠正。校验位不是监督者而是参与者——它和数据位一起组成了合法的暗号接收方验收的是暗号本身。九、把整件事串起来码距 合法码字之间的最小距离是编码抗揍能力的尺子检 d 位错需要码距 ≥ d1纠 d 位错需要码距 ≥ 2d1校验的本质 加冗余位撑大码距是花钱买距离承诺范围内检错是 100% 确定的超范围才可能漏检但漏检概率低到工程可忽略数据对却被判错真实存在校验位自己翻了不是缺陷是无法分辨错位的必然纠错可能越纠越错所以工程上爱用纠 1 检 2接收方永远整体看待码字校验位与数据位完全平等。整章校验码的知识其实就是从码距这一个概念里长出来的。把尺子握住剩下的都是推论。
