奇偶校验码与循环冗余校验码CRC

物理层只管传输比特流，无法控制是否出错，所以数据链路层负责起“差错监测”的工作，检测比特流传输是否有出现错误。

奇偶校验码

在比特流尾部添加一位比特位来检查比特率传输完成后是否有出差。

假设需要传输 00110010 这个8位的比特流，使用奇偶校验码时，则在这个 00110010 后增加一位比特位 1，当接收端接收到这个比特流之后，就会根据最后一个比特位来检测该比特流是否有出错。

那么怎么决定添加的这个校验码是 1 还是 0 呢？

其实是通过技术需要传输的比特流之和的奇偶来决定的。

如：
当传输比特流 00110010 时，0 + 0 + 1 + 1 + 0 + 0 + 1 + 0 = 3，3为奇数，所以添加的校验码为 1
当传输比特流 00111010 时，0 + 0 + 1 + 1 + 1 + 0 + 1 + 0 = 4，4为偶数，所以添加的校验码为 0

但是这个检测方法有个明显的缺陷，如果比特流在传输过程中出错两位，奇偶校验码就校测不到错误。因此有了CRC方法。

循环冗余校验码CRC

◆ 一种根据传输或保存的数据而产生固定位数校验码的方法
◆ 检测数据传输或者保存后可能出现的错误
◆ 生成的数字计算出来并且附加到数据后面

相关算法 — 异或

0 xor 0 = 0
0 xor 1 = 1
1 xor 0 = 1
1 xor 1 = 0

相关算法 — 模"2"除法

◆ 模“2”除法是二进制下的除法
◆ 与算术除法类似，但除法不借位，实际是“异或”操作

image.png

CRC

步骤：

1. 选定一个用于校验的多项式G(x)，并在数据尾部添加r个0
2. 将添加r个0后的数据，使用模“2”除法除以多项式的位串
3. 得到的余数填充在原数据r个0的位置得到可校验的位串

例子1：使用CRC计算101001的可校验位串
第一步：
假设选定的多项式G(x) 为：

展开后为：

可得：二进制位串为1101、最高阶为3。

所以 在数据尾部添加r个0 中的 r 为 3。

第二步：
将添加 3 个0后的数据 101001000，使用模“2”除法除以多项式的位串1101

得到余数 001

第三步：
将得到的余数001 填充在原数据 3 个0的位置，即得到可校验的位串 101001001

最后得到的可校验的位串 101001001 就是需要发送的比特流。

这个三个步骤都是在发送端完成的，发送端在计算出这个可校验位串之后 101001001，就可以把这个比特流发送给接收端 。接收端在接收到该比特流后，就可以进行校验来判断该比特流是否是正确的，接收端怎么判断呢？

接收端接收的数据除以双方约定好的G(x)的串位，根据余数是否为0来判断，余数为0则接收的数据没有错误。

例子2：使用CRC计算10110011的可校验位串

第一步：

第二、三步：

小结

• CRC的错误检测能力与位串的阶数r有关；
  通过上面两个例子，我们能发现，阶数越高，在位串里添加越多的0，检测的能理就越强。
  当阶数为1时，往位串里添加一个0，就是就奇偶校验码了。
• 数据链路层只进行数据的检测，不进行纠正；
  如果数据链路检测到数据发生了错误，会直接丢弃错误的数据，而不是进行纠正。