数据表示系列最后一站。前面几篇解决的是数怎么存这篇解决数存错了/传错了怎么办。网线里有干扰内存条会受电磁影响数据翻个位是常有的事。校验码就是给数据配的防摔包装——软考上午题每年 1~2 分考点就三个奇偶校验、海明码、CRC。在讲具体编码之前必须先建立一个统一的概念码距。它是理解所有校验码的钥匙不懂它三种码的能力边界你只能死记硬背。一、码距衡量编码抗揍能力的尺子码距两个码字之间不同二进制位的个数。比如0011和0010只差最后 1 位码距为 1。一个编码系统的码距取任意两个合法码字之间的最小距离。直觉类比合法码字就是约定好的暗号。码距越大任意两个暗号之间差得越多——这时候某个暗号在传输中错了几位错完之后的样子不是任何合法暗号→ 你能发现出错了检错错完之后的样子离某个合法暗号仍然最近→ 你能猜回原来是哪个纠错。两条铁律记下来所有校验码的能力都从这里推检出 d 位错误需要码距 ≥ d1纠正 d 位错误需要码距 ≥ 2d1以码距 3 为例错 1 位后错码离原码字距离 1、离其他合法码字至少 2最近的就是原配——能纠错错 2 位后可能离两个合法码字一样近分不清原配是谁但这不是合法暗号还是看得出来的——只能检错。所以码距 3 纠 1 位或检 2 位。二、奇偶校验最简单的一位冗余原理在数据后面加 1 个校验位使整个码字中1 的个数满足约定奇校验1 的总数为奇数偶校验1 的总数为偶数。例数据1011011数一下有 5 个 1已经是奇数。奇校验 → 校验位补0偶校验 → 校验位补1。接收方重新数 1 的个数不符合约定就是出错了。能力边界考点所在奇偶校验的码距是2加了一位之后任意两个合法码字至少差 2 位套公式码距 2 ≥ 11只能检 1 位错码距 2 2×11不能纠错。更精确地说只能发现奇数个位出错1 位、3 位……偶数个位同时出错检不出来——1 的个数奇偶性没变错误完美隐身就算发现了也不知道是哪位错无法纠正。因为便宜只加 1 位、能力弱奇偶校验用在出错率低的场景早期内存、串口通信。三、海明码能纠错的聪明编码想要纠错冗余位就得加多。问题是加几位才够这就是软考最爱考的公式2ᵏ ≥ n k 1n 数据位数k 校验位数这个公式不用背推一遍就记住了k 个校验位能组合出 2ᵏ 种状态这些状态要覆盖nk 位中某一位出错的 nk 种情况外加没出错这 1 种情况共 nk1 种。所以 2ᵏ ≥ nk1。试几个数n4 → k38≥8 ✓n8 → k416≥13 ✓n16 → k532≥22 ✓注意 k4 时 1621不够。工作机制了解即可校验位放在编号的 2 的幂次位置第 1、2、4、8……位每个校验位管一组数据位的奇偶性。接收方逐组检查哪几组不过把组号加起来——得到的数字就是出错的位置直接翻转纠正。相当于多个奇偶校验交叉定位所以能纠错。能力海明码码距为3套公式纠 1 位错或检 2 位错。内存 ECC 技术就是它的后代。四、CRC网络通信的检错主力CRC循环冗余校验思路完全不同把数据当一个大数除以一个约定的除数余数贴在数据后面一起发。接收方把收到的整个码字再除以同一个除数除得尽余 0就认为没出错。这里的除法是模 2 除法加减都按异或算无进位、无借位。那个约定的除数由生成多项式给出比如 G(x) x³ x 1对应二进制1011x³、x¹、x⁰ 的系数为 1其余为 0。计算三步走用例题走一遍数据1100G(x) x³x1。plain第1步除数 1011 是 4 位 → r3数据后补 3 个 0 → 1100000 第2步模 2 除法异或 1100000 ⊕ 1011 ----- 1110 余111拉下一位 ⊕ 1011 ----- 1010 余101拉下一位 ⊕ 1011 ----- 0010 余001拉下一位首位是0不够除商0 010 ← 最终余数3 位 第3步CRC 校验码 010发送码字 1100 010接收方验证1100010模 2 除1011余数为 000 → 传输无误 ✓。特点考点只检错不纠错检错能力极强尤其擅长抓连续多位的突发错误硬件实现就是移位寄存器加异或门又快又便宜。以太网帧尾的 FCS、WiFi、各种存储协议里全是它——这就是为什么网络里到处都是 CRC。五、三种校验码对比表格奇偶校验海明码CRC冗余位1 位k 位2ᵏ≥nk1r 位多项式次数码距23—检错奇数个位错2 位强含突发错误纠错无1 位无典型应用串口、早期内存ECC 内存理论基础以太网、存储协议六、10 道练习题基础题1~51.关于奇偶校验下列说法正确的是 。A. 可以纠正 1 位错误 B. 可以检测出所有错误 C. 能定位出错的位 D. 只能检测奇数个位出错不能纠错2.数据 1011011 采用奇校验校验位应设置为 。A. 0 B. 1 C. 10 D. 取决于传输方向3.采用海明码校验数据位为 8 位至少需要的校验位位数为 。A. 3 B. 5 C. 4 D. 84.海明码的码距为 3其检错纠错能力为 。A. 检 3 位错 B. 纠 1 位错 C. 纠 2 位错 D. 只能检错不能纠错5.接收方收到 CRC 码字后判断传输是否出错的方法是 。A. 用生成多项式对应的除数对码字做模 2 除法余数为 0 则认为无错 B. 检查码字中 1 的个数是否符合奇偶约定 C. 将码字与原数据逐位对比 D. 重新计算一次奇偶校验位进阶题6~10带坑6.某编码系统的码距为 4其检错和纠错能力为 。A. 检 2 位错纠 2 位错 B. 检 3 位错纠 2 位错 C. 检 4 位错纠 1 位错 D. 检 3 位错纠 1 位错7.数据 0110001 采用偶校验传输过程中有 2 位同时出错接收方 。A. 一定能发现出错 B. 不能发现出错因为偶数位同时出错不改变 1 的个数的奇偶性 C. 能发现并纠正出错位 D. 能发现出错但无法定位8.采用海明码校验数据位为 16 位至少需要的校验位位数为 。A. 4 B. 6 C. 5 D. 169.数据信息为 1100生成多项式 G(x) x³x1则 CRC 校验码为 。A. 011 B. 010 C. 101 D. 11010.关于三种校验码下列说法错误的是 。A. 奇偶校验码距为 2只能检 1 位错 B. 海明码码距为 3可纠正 1 位错误 C. CRC 可以纠正 1 位错误 D. CRC 广泛应用于网络通信中七、答案与详解1. D奇偶校验码距 2只能检奇数个位错、不能定位、不能纠错。A、C 把纠错能力安给了它B 忽略了偶数位错误的盲区。2. A数 11011011有 5 个 1已是奇数。奇校验要求总数为奇 → 校验位补0。选 B 的是把奇校验理解成校验位必须是 1——校验位是为了凑齐约定奇偶都可以是 0。3. C代公式 2ᵏ ≥ nk1k3 时 8 ≥ 83112不够k4 时 16 ≥ 13够了。答案 4 位。4. B码距 3检错上限 d13 即检 2 位纠错上限 2d13 即纠 1 位。软考标准表述是纠 1 位错。5. ACRC 的判定法就是再除一遍看余数是不是 0。B、D 是奇偶校验的活C 根本不现实——接收方要是有原数据还要校验干什么。6. D套公式检错 d ≤ 码距-1 3 位纠错 2d1 ≤ 4 即 d ≤ 1.5取整1 位。所以检 3 纠 1。选 C 的把码距 4直接当成了检错位数记混了公式的左右两边。7. B奇偶校验的经典盲区2 位同时出错1 的个数变化量是偶数奇偶性不变校验位检查通过错误隐身。这正是只能检奇数个位错的考题形态。8. C本题大坑k4 时 2⁴16看着和 n16 相等但公式比的是 nk1211621不够k5 时 32≥22✓。答案 5 位。很多考生背了公式却不代入 k 自身错选 4。9. B按正文例题的三步走补 3 个 0 →1100000模 2 除1011→ 余数010。可以自己验算1100010除以1011余 000。这类题考场上就是送分题前提是你亲手算过一遍——没算过的现在就在草稿纸上走一遍。10. C选错误的A、B、D 都是正文原话C 错CRC 只检错不纠错——出错就要求重传这是网络协议的哲学不是 CRC 的缺陷。八、五句话带走码距是总开关检 d 位需码距 d1纠 d 位需码距 2d1奇偶校验加 1 位凑奇偶码距 2检奇数位错、不纠错海明码2ᵏ ≥ nk1码距 3纠 1 检 2CRC数据补 r 个 0、模 2 除生成多项式、余数贴上只检不纠网络主力算 CRC 就三步补 0 → 异或除 → 取余。至此数据表示系列四篇进制转换、原反补移码、浮点数规格化、校验码全部完结上午题计算机组成原理里数据表示这块的分应该一分不丢了。下一篇预告开新战场——流水线。吞吐率怎么算、加速比怎么算、流水线的效率公式里那个时空图到底怎么看软考每年必考一道计算题公式会了就是 30 秒拿分。