21 1使用点到点信道的数据链路层12数链路层的基本功能 口差错检测: ■CRC的基本原理 口在发送端: 先把数据划分为组,假定每组k个比特 通过CRC运算,在数据M的后面添加供差错检测用的η位冗余码, 然后构成一个帧发送出去,一共发送(k+n)位。 在接收端 先从接收的数据帧中提取出n位冗余码,进行CRC检验。 如果检验的结果正确,则接受( accept)数据帧。 如果检验的结果不正确,则直接丢弃。 aCRC检验不能确定错误发生的原因,只能判断数据帧是否正确 河南中医药大学/阮晓龙(13938213680/http://network.xg.hactcm.edu.cn
河南中医药大学 / 阮晓龙 / 13938213680 / http://network.xg.hactcm.edu.cn 1.使用点到点信道的数据链路层 差错检测： ◼ CRC的基本原理： 在发送端： ▪ 先把数据划分为组，假定每组k个比特。 ▪ 通过CRC运算，在数据M的后面添加供差错检测用的n位冗余码， 然后构成一个帧发送出去，一共发送（k+n）位。 在接收端： ▪ 先从接收的数据帧中提取出n位冗余码，进行CRC检验。 ▪ 如果检验的结果正确，则接受（accept）数据帧。 ▪ 如果检验的结果不正确，则直接丢弃。 CRC检验不能确定错误发生的原因，只能判断数据帧是否正确。 21 1.2数据链路层的基本功能
22 1使用点到点信道的数据链路层12数链路层的基本功能 口差错检测: ■CRC的基本原理 k位 n位 k位 位 原始数据 CRO 原始数据000 除数Pn+1位 原始数据 CRO 除数Pn+1位 余数R 余数 cRCn位 若余数=0,接受 若余数≠0,丢弃 接收方 发送方 河南中医药大学/阮晓龙(13938213680/http://network.xg.hactcm.edu.cn
河南中医药大学 / 阮晓龙 / 13938213680 / http://network.xg.hactcm.edu.cn 1.使用点到点信道的数据链路层 差错检测： ◼ CRC的基本原理： 22 1.2数据链路层的基本功能 k 位 n 位 除数 P n + 1 位 原始数据 00…0 CRC 余数 R n 位 原始数据 CRC k 位 n 位 除数 P n + 1 位 原始数据 CRC 余数 若余数=0，接受 若余数≠0，丢弃 接收方 发送方
23 1使用点到点信道的数据链路层12数链路层的基本功能 口差错检测: ■循环冗余校验码(CRC)的基本原理是 口在K位信息码后再拼接R位的校验码,整个编码长度为N位,因此,这 种编码也叫(N,K)码。 口对于一个给定的(N,K)码,可以证明存在一个最高次幂为N-K=R的 多项式G(x) 口根据G(x)可以生成K位信息的校验码,而G(x)川叫做这个CRC码的生成多 项式 口假设要发送的信息用多项式C(Ⅹ表示,将C(x)左移R位(可表示成 C(x)*2R),这样C(x)的右边就会空出R位,这就是校验码的位置。 口用C(x)*2R除以生成多项式G(×)得到的余数就是校验码 河南中医药大学/阮晓龙(13938213680/http://network.xg.hactcm.edu.cn
河南中医药大学 / 阮晓龙 / 13938213680 / http://network.xg.hactcm.edu.cn 1.使用点到点信道的数据链路层 差错检测： ◼ 循环冗余校验码（CRC）的基本原理是： 在K位信息码后再拼接R位的校验码，整个编码长度为N位，因此，这 种编码也叫（N，K）码。 对于一个给定的（N，K）码，可以证明存在一个最高次幂为N-K=R的 多项式G(x)。 根据G(x)可以生成K位信息的校验码，而G(x)叫做这个CRC码的生成多 项式。 假设要发送的信息用多项式C(X)表示，将C(x)左移R位（可表示成 C(x)*2R），这样C(x)的右边就会空出R位，这就是校验码的位置。 用 C(x)*2R 除以生成多项式G(x)得到的余数就是校验码。 23 1.2数据链路层的基本功能
24 1使用点到点信道的数据链路层12数链路层的基本功能 口差错检测: ■循环冗余校验码(CRC)的两个计算 口发送端:如何计算出冗余码 ¤接收端:如何通过冗余码判断数据帧是否错误 ■冗余码的计算 口用二进制的模2运算进行2n乘M的运算,这相当于在M后面添加 n个0 口得到的(k+n)位的数除以事先选定好的长度为(n+1)位的除数P, 得出商是Q而余数是R,余数R比除数P少1位,即R是n位。 ¤将余数R作为冗余码拼接在数据M后面,一起发送出去。 河南中医药大学/阮晓龙(13938213680/http://network.xg.hactcm.edu.cn
河南中医药大学 / 阮晓龙 / 13938213680 / http://network.xg.hactcm.edu.cn 1.使用点到点信道的数据链路层 差错检测： ◼ 循环冗余校验码（CRC）的两个计算： 发送端：如何计算出冗余码 接收端：如何通过冗余码判断数据帧是否错误 ◼ 冗余码的计算： 用二进制的模 2 运算进行 2n 乘 M 的运算，这相当于在 M 后面添加 n 个 0。 得到的 (k + n) 位的数除以事先选定好的长度为 (n + 1) 位的除数 P， 得出商是 Q 而余数是 R，余数 R 比除数 P 少 1 位，即 R 是 n 位。 将余数 R 作为冗余码拼接在数据 M 后面，一起发送出去。 24 1.2数据链路层的基本功能
25 1使用点到点信道的数据链路层12数链路层的基本功能 口差错检测: ■循环冗余校验码(CRC)的两个计算 口发送端:如何计算出冗余码 ¤接收端:如何通过冗余码判断数据帧是否错误 ■通过冗余码判断数据帧是否错误 口若得出的余数R=0,则判定这个帧没有差错,就接受( accept 口若余数R≠0,则判定这个帧有差错,就丢弃。 ¤但这种检测方法并不能确定究竟是哪一个或哪几个比特岀现了差错。 ¤只要经过严格的挑选,并使用位数足够多的除数P,那么出现检测不 到的差错的概率就很小很小。 河南中医药大学/阮晓龙(13938213680/http://network.xg.hactcm.edu.cn
河南中医药大学 / 阮晓龙 / 13938213680 / http://network.xg.hactcm.edu.cn 1.使用点到点信道的数据链路层 差错检测： ◼ 循环冗余校验码（CRC）的两个计算： 发送端：如何计算出冗余码 接收端：如何通过冗余码判断数据帧是否错误 ◼ 通过冗余码判断数据帧是否错误： 若得出的余数 R = 0，则判定这个帧没有差错，就接受 (accept)。 若余数 R ≠ 0，则判定这个帧有差错，就丢弃。 但这种检测方法并不能确定究竟是哪一个或哪几个比特出现了差错。 只要经过严格的挑选，并使用位数足够多的除数 P，那么出现检测不 到的差错的概率就很小很小。 25 1.2数据链路层的基本功能