七、循环冗余校验

1、循环冗余码循环冗余码计算机网络计算机网络 七七 循环冗余码循环冗余码1.2.3.4.计算机网络计算机网络 七七 循环冗余码循环冗余码计算机网络计算机网络 七七 循环冗余码循环冗余码 循环冗余码是数据通信中最常用的一种循环冗余码是数据通信中最常用的一种检错码。检错码。计算机网络计算机网络 七七 循环冗余码循环冗余码 任何一个码长为任何一个码长为n的码字都可以用一个的码字都可以用一个n-1次多项式来表示。码字中每个码元次多项式来表示。码字中每个码元 的值就是该的值就是该多项式中相应的系数。多项式中相应的系数。 码字多项式与码字之间的对应关系：码字多项式与码字之间的对应关系：计算机网络计算机网络 七

2、七 循环冗余码循环冗余码 根据欲发的根据欲发的k位信息生成一个位信息生成一个r位的数据序列，位的数据序列，称为循环冗余校验码或帧校验序列称为循环冗余校验码或帧校验序列FCS。K位位信息与信息与r位校验码组成的二进制序列恰好能够被位校验码组成的二进制序列恰好能够被某个预先确定的数（生成多项式）整除。某个预先确定的数（生成多项式）整除。生成多项式生成多项式总是由通信双总是由通信双方事先约定好。方事先约定好。计算机网络计算机网络 七七 循环冗余码循环冗余码第一步：在信息码（第一步：在信息码（k位）的末尾加上位）的末尾加上r个个0。相当于把信息位向左移相当于把信息位向左移r位。位。 第二步：由第一步构

3、成的码字作为被除数，第二步：由第一步构成的码字作为被除数，除以生成多项式所对应的码字，由此除法产除以生成多项式所对应的码字，由此除法产生余数。生余数。计算机网络计算机网络 七七 循环冗余码循环冗余码 例题例题1：发送方要发送数字序列：发送方要发送数字序列101，设采，设采用生成多项式为用生成多项式为G（x）=x4+x3+x2+1，请构，请构造循环冗余码。造循环冗余码。通过计算，通过计算，循环冗余码循环冗余码为为10100111010011计算机网络计算机网络 七七 循环冗余码循环冗余码 接收方用接收到的数据（信息位与校验位接收方用接收到的数据（信息位与校验位的组合）除以相同的数（生成多项式），

4、如果的组合）除以相同的数（生成多项式），如果无余数，则认为无差错；如果有余数，则认为无余数，则认为无差错；如果有余数，则认为传输出错。传输出错。计算机网络计算机网络 七七 循环冗余码循环冗余码 例题例题2：假设接收方收到一循环冗余序列：假设接收方收到一循环冗余序列1010010，采用生成多项式为，采用生成多项式为G （x）=x3+x+1 ，请问传输过程是否出错？，请问传输过程是否出错？通过计算，通过计算，此次传输过程此次传输过程出错。出错。计算机网络计算机网络 七七 循环冗余码循环冗余码能检测出全部单数个错误能检测出全部单数个错误能检测出全部随机二位错误能检测出全部随机二位错误能检测出全部奇数个错误能检测出全部奇数个错误能检测出全部长度小于能检测出全部长度小于k位的突发错误位的突发错误计算机网络计算机网络 七七 循环冗余码循环冗余码本节主要内容：本节主要内容：l 多项式与码字的转换多项式与码字的转换l 循环冗余码的构造循环冗余码的构造l 循环冗余码的校验循环冗余码的校验计算机网络计算机网络 七七 循环冗余码循环冗余码 设生成多项式为设生成多项式为G（x）