软考-软件设计师--校验码

---

一、奇偶校验码：基础错误检测

原理：通过在数据尾部(或者头部)添加奇偶校验位，使数据中"1"的数量为奇数个（奇校验）或偶数个（偶校验）。
公式：
设数据位为 $d_1{d}_2...d_n$，校验位 $p$ 满足：
$$p=d_1\oplus d_2\oplus \cdots \oplus d_n(\text{奇校验})$$
$$p=\neg (d_1\oplus d_2\oplus \cdots \oplus d_n)(\text{偶校验})$$

示例：
假设要传输的数据为 1011，采用偶校验的方式计算流程如下：

• 计算校验位：$1\oplus 0\oplus 1\oplus 1=1$ → $p=0$（使"1"总数为偶数）
• 发送帧：1011 0
• 若接收端检测到 1011 1（"1"总数为奇数），则判定错误。

能力与局限：

• ✅ 检测单比特错误
• ❌ 无法检测偶数个错误位
• ❌ 无纠错能力

---

二、海明码：单比特纠错技术

原理：利用多个校验位覆盖数据位的不同组合，通过校验子定位错误位置。
关键公式：
首先确定要使用检验位的位数 $r$ ，需满足：
$$2^r\ge k+r+1$$
其中 $k$ 为数据位数。

示例 假设需要传送4位数据 1101，则代入上公式，r=3,既需要3位校验位。

1. 数据位：$D_1{D}_2{D}_3{D}_4=1101$
2. 校验位位置：检验位的位置为2的i次方，既$P_1$=1,$P_2$=2,$P_3$=4,$P_4$=8, 其中$P_i$表示第i个校验位的位置。
3. 计算校验位：第i个检验码的计算方式为找出数据所有位置的二进制对的倒数第i位为1的位置。
   对于$P_1$，需要找出末尾带1的所有位置，对于$P_2$，要找出倒数第二位带1的所有位置，对于$P_3$，要找出倒数第三位带1的所有位置，对于$P_4$，要找出倒数第四位带1的所有位置,以此类推。将这些位置上的数进行异或操作。即可计算出对应位置的校验码。
   • $P_1=D_1\oplus D_2\oplus D_4=1\oplus 1\oplus 1=1$
   • $P_2=D_1\oplus D_3\oplus D_4=1\oplus 0\oplus 1=0$
   • $P_3=D_2\oplus D_3\oplus D_4=1\oplus 0\oplus 1=0$
4. 完整码字：$P_1{P}_2{D}_1{P}_3{D}_2{D}_3{D}_4=1010101$

纠错过程：
若接收端检测校验子 $S=(S_3{S}_2{S}_1)=101$（二进制5），则第5位（$D_2$）出错。

校验位覆盖关系图：

位位置: 1(P1) 2(P2) 3(D1) 4(P3) 5(D2) 6(D3) 7(D4)
覆盖组: P1 → [1,3,5,7]P2 → [2,3,6,7]P3 → [4,5,6,7]

---

三、循环冗余校验码（CRC）：高效批量检测

原理：将数据视为多项式，通过模2除法生成校验码。
关键公式：
数据多项式 $D(x)$ 与生成多项式 $G(x)$ 运算：
$$\text{校验码}=D(x)\cdot x^r\text{mod}G(x)$$

示例（数据 110101，生成多项式 $x^3+x+1$）：

1. $D(x)=x^5+x^4+x^2+1$
2. $G(x)=x^3+x+1$（二进制 1011）
3. 计算步骤：

        110101000  ← 数据左移3位（r=3）1011      ← G(x)---------1101101011-----110101011-----1110   ← 余数（校验码）
   

4. 发送帧：数据 + 余数 = 110101 110

检测能力：

• ✅ 检测所有单比特和双比特错误
• ✅ 检测奇数个错误
• ✅ 检测长度 ≤ $r$ 的突发错误

---

三、三大技术对比

特性	奇偶校验码	海明码	CRC
检测能力	单比特	双比特	多比特突发
纠错能力	无	单比特	无
校验位开销	1位	${\log }_{2}n$位	固定位（16/32）
典型应用	内存模块	ECC内存	网络传输

总结：奇偶校验码适合低成本检测，海明码提供纠错能力，CRC则是高速数据传输的首选。理解其数学本质（异或运算/多项式除法）是掌握核心的关键！