差错控制

检错编码

奇偶检验码

奇（偶）检验码：附加一个检验位之后，码长为 n 的码字中 “1”的个数为奇（偶）数。只能检测出奇数个比特位的错误，因为如果两个比特一起错，将会抵消影响，无法检测。

例如，7 位数据 1001101 对应的奇检验码为 10011011，对应的偶检验码为 10011010

循环冗余码（CRC）

CRC 的基本思想：

1. 收发双方约定生成多项式 G (x)，最高位和最低为必须为 1 。例如，使用 $x^3+x^2+1$ 表示位串 1101
2. 发送方基于待发送的数据和 G (x)，计算出冗余码，将冗余码附加到数据后面一起发送
3. 接收方收到数据和冗余码后，通过逆运算来计算收到的数据和冗余码是否产生差错

循环冗余码的计算：

1. 加 0 。在后面加上 G (x) 的阶数相等数量的 0
2. 模 2 除。模 2 除法规则：加法不进位，减法不借位，相当于对应位进行逻辑异或运算。
3. 除完的余数 R 作为 FCS 加到原来的数据中发送出去

纠错编码（海明码）

$L-1=D+C$ ，其中 L 为码距，D 为检错位数，C 为纠错位数

以数据 1010 为例说明海明码的编码原理和过程：

1. 确定海明码的位数

信息位数 n和检验位数 k 应满足 $n+k\le 2^k-1$ ，数据为 1010，则检验位为三位。

2. 确定检验位的分布

N 位检测位分别在 $2^i$ 的位置上

1 (001)	2 (010)	3 (011)	4 (100)	5(101)	6 (110)	7 (111)
P 1	P 2	1	P 3	0	1	0

3. 分组以形成检验关系

P 1	M 3	M 5	M 7
P 2	M 3	M 6	M 7
P 3	M 5	M 6	M 7

4. 检验位取值 (奇校验为例)

对每一行 M 进行奇校验

P1=0	1	0	0
P2=1	1	1	0
P3=0	0	1	0

此时获得包含海明码的数据串为 0110010

5. 海明码的检验原理

再进行一次奇校验，校验的值放在 E 中，

E1=0	P1=0	1	0	0
E2=0	P2=1	1	1	0
E3=0	P3=0	0	1	0

如果 E3E2E1 是 “000”，则数据无误，如果不是“000”，则值为错误的位置。（E1为最低位）