校验码

校验码

校验码确保计算机系统运行时，数据传输过程的正确性。
常用校验码：

$$校验码 \begin{cases} 奇偶校验码\\ 循环冗余校验码CRC\\ 海明校验码 \end{cases}$$

1. 奇偶校验码

奇偶校验码是奇校验码、偶校验码的统称。

①奇校验码：奇校验加上校验位后，编码中的1的个数是奇数。
②偶校验码：偶校验加上校验位后，编码中的1的个数是偶数。
③奇偶校验码：校验位只有一位，可以检查错误，但无法检测错误位，也无法矫正错误；

示例：

奇偶校验码有3种：

$$奇偶校验码 \begin{cases} 水平奇偶校验码\\ 垂直奇偶校验码\\ 水平垂直奇偶校验码 \end{cases}$$

2. 循环冗余校验码CRC

循环冗余校验码CRC是基于模2运算的校验码。
可查错，不可纠错。
暂不详述。

3. 海明校验码

海明校验码是利用奇偶性校验检错的，通过扩大码距，实现检错和纠错。
海明校验码的校验位有多位，可以检查错误，也可以矫正错误。

码距：两个合法码字之间不同的二进制的位数。
最小码距：一组合法码字之间的最小的码距。

公式：

$$\left. \begin{aligned} 数据位:m\\ 校验位:K \end{aligned} \right\} 2^k>m+k+1$$

校验码位置： $p_i$在海明码的第 $2^{i-1}$位。

示例：数据位是 $m=8$位

1. 计算校验位数：

数据位是 $m=8$位，则根据公式 $2^k>m+k+1$，得 $k=4$。

2. 数据位D与校验位P的位置：

校验位是4位，根据 $2^{i-1}$计算：

校验位P1的位置=1；
校验位P2的位置=2；
校验位P3的位置=4；
校验位P4的位置=8；

3. 确定校验关系

数据位的海明码的下标，用校验位所对应的海明码下标表示出来。

4. 计算校验位

P1校验：P1 = D0 $\oplus$ D1 $\oplus$ D3 $\oplus$ D4 $\oplus$ D6

P2校验：P2 = D0 $\oplus$ D2 $\oplus$ D3 $\oplus$ D5 $\oplus$ D6

P3校验：P2 = D1 $\oplus$ D2 $\oplus$ D3 $\oplus$ D7

P4校验：P4 = D4 $\oplus$ D5 $\oplus$ D6 $\oplus$ D7

5. 终上所述，得出海明码

6.校验

P1校验结果：S4 = P1 $\oplus$ D0 $\oplus$ D1 $\oplus$ D3 $\oplus$ D4 $\oplus$ D6

P2校验结果：S3 = P2 $\oplus$ D0 $\oplus$ D2 $\oplus$ D3 $\oplus$ D5 $\oplus$ D6

P3校验结果：S2 = P3 $\oplus$ D1 $\oplus$ D2 $\oplus$ D3 $\oplus$ D7

P4校验结果：S1 = P4 $\oplus$ D4 $\oplus$ D5 $\oplus$ D6 $\oplus$ D7

$\overline{S1S2S3S4}$即为出错位