【计算机网络】数据链路层 : 差错控制 ( 检错编码 | 奇偶校验码 | CRC 循环冗余码 )★

举报
韩曙亮 发表于 2022/01/11 01:06:36 2022/01/11
【摘要】 文章目录 一、 奇偶校验码二、 奇偶校验码 特点三、 奇偶校验码 示例四、 CRC 循环冗余码 ( 原理说明 )五、 CRC 循环冗余码 计算示例六、 CRC 循环冗余码 生成多项式 ...





一、 奇偶校验码



奇偶校验码 组成 :

① 信息元 : n − 1 n-1 n1 位 ; 要发送的有效数据 ;

② 校验元 : 1 1 1 位 ; 冗余码 ;

③ 奇校验码 : 1 1 1 的个数为 奇数 ; 冗余位 1 1 1 ;

④ 偶校验码 : 1 1 1 的个数为偶数 ; 冗余位 0 0 0 ;





二、 奇偶校验码 特点



奇偶校验码 特点 : 该编码方法 , 只能检查 奇数个 比特错误 , 如果有 偶数个比特错误 , 无法检查出来 , 检错率是 50 % 50\% 50% ;





三、 奇偶校验码 示例



奇偶校验码 示例 :

传输 字符 ‘S’ 的 ASCII 码 1100101 1100101 1100101 , 使用 奇校验码 , 在 数据前 添加 1 1 1 位 冗余位 1 1 1 , 表明 1 1 1 的个数为奇数 , 上述数据的 1 1 1 的个数为 5 5 5 个 , 是奇数个 ;

奇数个错误 : 如果接受到的数据中 1 1 1 的个数是 偶数个 , 此时就能检测出数据错误 ;

偶数个错误 : 如果接收到的数据中 1 1 1 的个数为 奇数个 , 那么就会判断接收的数据是正确的 ; 无法检查出 偶数个错误 ;





四、 CRC 循环冗余码 ( 原理说明 )



发送端 :

① 要传输的数据 : 5 5 5 ;

② 生成多项式 : 2 2 2 ;

③ 计算冗余码 : 使用 要 传 输 的 数 据 生 成 多 项 式 = 5 2 \cfrac{要传输的数据}{生成多项式} = \cfrac{5}{2} =25 , 商是 2 2 2 , 余数是 1 1 1 ;

④ 冗余码 : 余数 1 1 1 就是 FCS 帧检验序列 , 也就是 冗余码 ;

⑤ 最终发送的数据 : 5 + 1 = 6 5 + 1 = 6 5+1=6



接收端 :

① 接收到的数据 : 6 6 6 ;

② 生成多项式 : 2 2 2 ;

③ 判定差错 : 计算 接 收 到 的 数 据 生 成 多 项 式 \cfrac{接收到的数据}{生成多项式} 余数是否为 0 0 0 , 如果余数为 0 0 0 , 说明传输过程中没有错误 ;



数据链路层 使用 CRC 循环冗余校验编码 , 进行差错控制 , 只能做到无差错接收 , 凡是接收到的数据帧 , 都是正确的 ;





五、 CRC 循环冗余码 计算示例



发送数据 1101011011 1101 0110 11 1101011011 , 使用 CRC 循环冗余码 , 生成多项式是 10011 10011 10011 , 求最终的发送数据 ? ? ?


最终发送的数据组成 : 原始数据 1101011011 1101 0110 11 1101011011 + 帧检验序列 FCS ;

计算 帧检验序列 FCS :

① 数据加 冗余码 位数个 0 0 0 : 首先确定 冗余码 位数 , 冗余码的位数是 生成多项式的 阶 , 即 生成多项式 10011 10011 10011 的 总位数 减去 1 1 1 , 相当于 离散数学 中的生成函数的 最高位次幂 ; FCS 的位数是 4 4 4 位 ;

生成多项式 是 N N N 位 , 那么阶 就是 N − 1 N-1 N1 位 , FCS 帧检验序列就是 N − 1 N-1 N1 位 ;

数据加 4 4 4 0 0 0 后为 11010110110000 1101 0110 11 0000 11010110110000


② 模 2 2 2 除法 : 数据 加上 0 0 0 后 , 除以 生成多项式 , 余数就是 FCS 帧检验序列 ;

二进制除法 , 与十进制除法不同的是 , 每个除法相除的计算是 异或操作 ;

异或运算 : 同 0 0 0 , 异 1 1 1 ;

在这里插入图片描述
2 2 2 除法计算过程分析 :

  • 11010 11010 11010 异或 10011 10011 10011 计算得到 1001 1001 1001 , 然后下一位 1 1 1 落下来 , 得到 10011 10011 10011 ;
  • 10011 10011 10011 异或 10011 10011 10011 计算得到 00000 00000 00000 , 然后下面 5 5 5 位 落下来 , 得到 10110 10110 10110 ;
  • 10110 10110 10110 异或 10011 10011 10011 计算得到 101 101 101 , 然后下 2 2 2 位落下来 , 得到 10100 10100 10100 ;
  • 10100 10100 10100 异或 10011 10011 10011 计算得到 1110 1110 1110

最终计算出来的 帧检验序列 是 1110 1110 1110 ;

最终发送的数据是 : 1101011011 1101 0110 11 1101011011 1110 1110 1110



接收端接收数据并校验 :

① 检验过程 : 接收端接收 上述 1101011011 1101 0110 11 1101011011 1110 1110 1110 数据 , 将上述数据 与 生成多项式 10011 10011 10011 相除 , 如果余数为 0 0 0 说明该数据帧没有差错 ;

② 结果判定 : 如果余数不为 0 0 0 , 说明数据帧错误 , 而且不知道哪里出现错误 , 丢弃该数据帧 , 重新发送 ;





六、 CRC 循环冗余码 生成多项式



生成多项式 : G ( x ) = x 3 + x 2 + 1 G(x) = x^3 + x^2 + 1 G(x)=x3+x2+1

相当于 : G ( x ) = x 3 + x 2 + 0 x 1 + x 0 G(x) = x^3 + x^2 + 0x^1 + x^0 G(x)=x3+x2+0x1+x0

对应的模二运算的除数 : 1101 1101 1101 ;

  • x x x 0 0 0 次幂系数为 1 1 1 , 对应第 0 0 0 位 为 1 1 1 ;
  • x x x 1 1 1 次幂系数为 0 0 0 , 对应第 1 1 1 位 为 0 0 0 ;
  • x x x 2 2 2 次幂系数为 1 1 1 , 对应第 2 2 2 位 为 1 1 1 ;
  • x x x 3 3 3 次幂系数为 1 1 1 , 对应第 3 3 3 位 为 1 1 1 ;

生成多项式对应的 二进制数 , 总位数是最高次幂加一 , 每一位是对应位前的系数 0 0 0 1 1 1 ;

文章来源: hanshuliang.blog.csdn.net,作者:韩曙亮,版权归原作者所有,如需转载,请联系作者。

原文链接:hanshuliang.blog.csdn.net/article/details/108045879

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。