奇偶校验码与循环冗余校验码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,就是就奇偶校验码了。
  • 数据链路层只进行数据的检测,不进行纠正;
    如果数据链路检测到数据发生了错误,会直接丢弃错误的数据,而不是进行纠正。
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容