文章目录奇偶校验Parity Check基本原理示例检错能力优缺点典型应用循环冗余校验码CRCCyclic Redundancy Check基本原理计算步骤示例简化检错能力常见标准优缺点典型应用海明码Hamming Code基本原理核心思想编码步骤以海明(7,4)码为例纠错过程检错与纠错能力码率与效率优缺点典型应用三者对比总结奇偶校验Parity Check基本原理在原始数据后面附加1 位校验位使得整个码字中1的个数满足约定的奇偶性。偶校验加上校验位后1的总数为偶数奇校验加上校验位后1的总数为奇数示例原始数据1011001其中1的个数为 4偶数。偶校验校验位 0码字 101100101 的个数仍为 4奇校验校验位 1码字 101100111 的个数变为 5检错能力能检测1 位错误不能纠错偶数个比特同时出错时无法检测例如 2 位翻转奇偶性不变优缺点优点缺点实现极其简单硬件开销小检错能力弱适合对可靠性要求不高的场景不能纠错典型应用ASCII 字符传输、简单的串口通信、内存的早期检错。循环冗余校验码CRCCyclic Redundancy Check基本原理将待发送的数据看作一个多项式用一个预定义的生成多项式 G(x)做模 2 除法得到的余数就是校验码FCS帧检验序列附加在数据后面发送。计算步骤将数据位表示为多项式 M(x)在 M(x) 后面补 r 个 0r 生成多项式的阶数阶数就是最高次幂用生成多项式 G(x) 对补零后的数据做模 2 除法得到的 r 位余数即为 CRC 校验码将余数附加到原始数据后发送示例简化数据110101生成多项式 G(x) x³ x 1对应二进制1011阶数 r 3数据补 3 个 0110101000模 2 除法求余数得到 3 位校验码附加后发送模 2 除法的特点减法等同于异或XOR没有进位和借位。检错能力CRC 的检错能力取决于生成多项式的选择能检测所有奇数个比特错误若 G(x) 含有因子 x1能检测所有突发长度 ≤ r的错误r 为校验位长度对突发长度 r 的错误漏检概率极低约为 2⁻ʳ不能纠错标准 CRC 只用于检错常见标准名称生成多项式校验位长度应用CRC-4x⁴x14 bitITU-T G.704CRC-8x⁸x²x18 bit蓝牙、SMBusCRC-16x¹⁶x¹⁵x²116 bitModbus、USBCRC-32x³²x²⁶…132 bit以太网、ZIP、PNG优缺点优点缺点检错能力远强于奇偶校验不能纠错硬件实现简单移位寄存器 XOR软件实现比简单校验慢对突发错误检测效果极好需要收发双方约定同一生成多项式典型应用以太网帧校验FCS、磁盘存储、ZIP/RAR 文件校验、通信协议HDLC、PPP。海明码Hamming Code基本原理海明码是一种既能检错又能纠错的线性分组码。通过在数据位中插入多个校验位使得每个校验位覆盖不同的数据位组合从而在接收端定位并纠正错误。核心思想校验位放在码字中2 的幂次位置第 1、2、4、8、16… 位每个校验位负责校验一组特定的位由其位置的二进制表示决定接收端计算校正子Syndrome其值直接指向出错位的位置编码步骤以海明(7,4)码为例原始数据 4 位D₃D₂D₁D₀需插入 3 个校验位 P₁P₂P₃组成 7 位码字。位位置安排位置1234567内容P₁P₂D₀P₃D₁D₂D₃校验关系偶校验P₁ 覆盖位置 1,3,5,7二进制末位为 1 的位置P₂ 覆盖位置 2,3,6,7二进制倒数第二位为 1 的位置P₃ 覆盖位置 4,5,6,7二进制倒数第三位为 1 的位置纠错过程接收端重新计算各校验组的奇偶性得到校正子 S S₃S₂S₁S 000 → 无错S ≠ 000 → S 的值就是出错位的位号翻转该位即可纠正检错与纠错能力标准海明码纠正 1 位错误检测 2 位错误但不能同时纠正 1 位又检测 2 位扩展海明码加一位总校验位纠正 1 位错误 检测 2 位错误SECDED码率与效率海明码需满足关系2ʳ ≥ m r 1其中 m 为数据位数r 为校验位数。数据位 m校验位 r码字长度 n4371141526531优缺点优点缺点能自动纠正 1 位错误只能纠正单比特错误编码和译码逻辑清晰数据量大时校验位开销增加硬件实现相对简单多位错误可能导致误纠典型应用计算机内存 ECCSECDED 就是扩展海明码、深空通信、RAID 存储系统。三者对比总结特性奇偶校验CRC海明码校验位开销1 位r 位通常 16/32r 位随数据量增长检错能力1 位错误强突发错误2 位错误纠错能力❌ 无❌ 无✅ 纠正 1 位实现复杂度极低低中等典型场景简单通信网络/存储帧校验内存 ECC简单来说奇偶校验最简单但最弱CRC检错能力最强但只检不纠海明码是唯一能自动纠错的方案代价是校验位开销更大。