校验码

码距：就单个编码A:00而言，其码距为1，因为其只需要改变一位就变成另一个编码。在两个编码中，从A码到B码转换所需要改变的位数称为码距，如A:00要转换为B:11,码距为2。

一般来说，码距越大，越利于纠错和检错。

---

码距：两个编码之间至少需要改变的位数。码距越大，检错纠错能力越强。

校验码	能力	关键特性
奇偶校验	检错（仅奇数位）	增加 1 位校验位使 1 的个数为奇/偶，码距=2，不能纠错
海明码	检错 + 纠错（1位）	校验位在 2 的幂次方位置（1,2,4,8...），公式 2^k ≥ n+k+1
CRC	检错	模 2 除法（异或），只能检错不能纠错，约定生成多项式 G(x)

海明码解题流程：确定校验位数量 k（2^k ≥ n+k+1）→ 校验位放 2 的幂次方位置 → 按位负责关系计算各校验位（偶校验）→ 写出编码。

CRC 解题流程：原始信息后补 r 个 0（r = G(x) 最高次）→ G(x) 转二进制除数 → 模 2 除法得余数 → 拼接发送。

奇偶校验码

在编码中增加1位校验位来使编码中1的个数为奇数（奇校验）或者偶数（偶校验），从而使码距变为2。

奇校验可以检测编码中奇数个数据位出错，即当合法编码中的奇数位发生了错误时，即编码中的1变成0或者0变成1，则该编码中1的个数的奇偶性就发生了变化，从而检查出错误。

但无法纠错。

循环冗余校验码 CRC

CRC只能检错，不能纠错，

其原理是找出一个能整除多项式的编码，因此首先要将原始报文除以多项式，将所得的余数作为校验位加在原始报文之后，作为发送数据发给接收方。

使用CRC编码，需要先约定一个生成多项式G(x)。生成多项式的最高位和最低位必须是1。假设原始信息有位，则对应多项式M(x)。生成校验码思想就是在原始信息位后追加若干校验位，使得追加的信息能被G(x)整除。接收方接收到带校验位的信息，然后用G(x)整除。余数为0，则没有错误；反之则发生错误。

---

例：假设原始信息串为 10110，CRC 的生成多项式为 ( G(x)=x^4+x+1 )，求 CRC 校验码。

• （1）确定生成多项式的阶数并添零

生成多项式的最高次幂为 ( r = 4 )。

在原始信息位后添加 ( r ) 个 0，得到被除数：

10110 + 0000 = 101100000

• （2）由多项式得到除数（生成多项式对应的二进制串）

多项式 ( x^4 + x + 1 ) 中，幂指数 4、1、0 的系数为 1，幂指数 3、2 的系数为 0。

因此对应的二进制串为 10011（从 ( x^4 ) 到 ( x^0 ) 排列）。

• （3）模 2 除法计算 CRC 校验码

模 2 除法采用异或运算（不进位、不借位）。

将被除数 101100000 与除数 10011 进行模 2 除，过程如下：

得到余数 1111。

注意：余数的位数应与生成多项式的阶数 ( r ) 相同。若余数不足 ( r ) 位，则需要在左边补 0 至 ( r ) 位。本例余数为 4 位，无需补齐。

• （4）生成最终发送的信息串

将计算得到的 CRC 校验码（余数）附加在原始信息串后面：
原始信息 10110 + 余数 1111 = 101101111
发送方将此数据帧发送给接收方。

• （5）接收方校验

接收方收到带校验码的帧后，用相同的生成多项式 10011 进行模 2 除法。

• 若余数为 0，说明传输无错误（或错误概率极低）；
• 若余数不为 0，则说明数据在传输过程中发生了错误，请求发送方重传。

注意：收发信息双方需使用相同的生成多项式。

---