crc循环冗余码讲课课件.ppt

循环冗余校验码的原理及应用 crc产生背景 放映结束 謝謝您的觀看 * 1 crc简介 2 crc原理 3 crc的实现 4 实现框图 Content 循环冗余校验码 crc冗余校验码是常用的校验码，在早期的通信中运用广泛，因为早期的通信技术不够可靠（不可靠性的来源是通信技术决定的，比如电磁波通信时受雷电等因素的影响），不可靠的通信就会带来‘确认信息’的困惑，书上提到红军和蓝军通信联合进攻山下的敌军的例子，第一天红军发了条信息要蓝军第二天一起进攻，蓝军收到之后，发一条确认信息，但是蓝军担心的是‘确认信息’如果也不可靠而没有成功到达红军那里，那自己不是很危险？于是红军再发一条‘对确认的确认信息’，但同样的问题还是不能解决，红军仍然不敢贸然行动。对通信的可靠性检查就需要‘校验’，校验是从数据本身进行检查，它依靠某种数学上约定的形式进行检查，校验的结果是可靠或不可靠，如果可靠就对数据进行处理，如果不可靠，就丢弃重发或者进行修复。 明日正午进攻，如何？ 同意 收到“同意” 收到：收到“同意” … … … … … … 这样的协议无法实现！ t crc的特点 应用范围广 zip，arj等压缩软件采用的是crc-32 GIF,TIFF等图像存储格式 所有链路层或网络接口层协议中 差错检测 crc校验码的应用情况 在传输过程中可能会产生比特差错：1 可能会变成 0 而 0 也可能变成 1。 在一段时间内，传输错误的比特占所传输比特总数的比率称为误码率 BER (Bit Error Rate)。 误码率与信噪比有很大的关系。 为了保证数据传输的可靠性，在计算机网络传输数据时，必须采用各种差错检测措施。 传播快速性 传播可靠性 消息在传播过程中，我们往往希望它传播的迅速，又希望它的可靠性强，可是鱼和熊掌不能兼得，这两个条件要同时实现又有点困难，怎么解决呢？于是........ 采用差错控制 crc产生啦！ crc产生啦！ 编码规则 相除 　　运用一个生成多项式g(x)（也可看成二进制数）用模2除上面的式子，得到的余数就是校验码.有了加减法就可以用来定义模2除法，于是就可以用生成多项式g(x)生成CRC校验码。 移位 　　将原信息码(kbit)左移r位(k+r=n) 生成多项式应满足以下原则 a、生成多项式的最高位和最低位必须为1。 　　b、当被传送信息（CRC码）任何一位发生错误时，被生成多项式做模2除后应该使余数不为0。 c、不同位发生错误时，应该使余数不同。 d、对余数继续做模2除，应使余数循环。 循环冗余检验的原理 在发送端，先把数据划分为组。假定每组 k 个比特。 在数据链路层传送的信息中，广泛使用了循环冗余检验 CRC 的检错技术。 假设待传送的一组数据 M = 101001（现在 k = 6）。我们在 M 的后面再添加供差错检测用的 n 位冗余码一起发送。 多项式除法 循环冗余检验的原理说明 举例 11010110110000 被除数 10011 1100001010 10011 10011 10011 10110 10011 10100 10011 1110 余数 商数 除数 模2加=模2减 模2 乘 模2除=乘的可逆运算 接收端对收到的每条信息进行 CRC 检验 (1) 若得出的余数 R = 0，则判定这个信息没有差错，就接受(accept)。 (2) 若余数 R ? 0，则判定这个信息有差错，就丢弃。 但这种检测方法并不能确定究竟是哪一个或哪几个比特出现了差错。 只要经过严格的挑选，并使用位数足够多的除数 P，那么出现检测不到的差错的概率就很小很小。 冗余码的计算举例 现在 k = 6, M = 101001。 设 n = 3, 除数 P = 1101， 被除数是 2nM = 101001000。 模 2 运算的结果是：商 Q = 110101， 余数 R = 001。 把余数 R 作为冗余码添加在数据 M 的后面发送出去。发送的数据是：2nM + R 即：101001001，共 (k + n) 位。 2.“无差错接受”是指：“凡是接受的信息（即不包括丢弃的信息），我们都能以非常接近于 1 的概率认为这些信息在传输过程中没有产生差错 3.也就是说：“凡是接收端接受的信息都没有传输差错”（有差错的信息就丢弃而不接受）。 4.要做到“可靠传输”（即发送什么就收到什么）就必须再加上确认和重传机制。 1.仅用循环冗余检验 CRC 差错检测技术只能做到无差错接受(acc