循环冗余码循环冗余码.pptVIP

9-5 循环冗余码 循环冗余码（CRC码）是数据通信领域中最常用的一种差错检验码。在循环冗余校验中，不是通过将各位相加来得到期望的校验，而是通过在数据单元末尾加一串冗余位，称作循环冗余校验码或循环冗余校验余数，使得整个数据单元可以被另一个预定的二进制数所整除。 9-5 循环冗余码 CRC校验常用场合 奇偶校验对一个字符校验一次，适合异步通讯；而CRC对一个数据块（frame）校验一次，适合同步通讯。在串行同步通信中，几乎都使用这种校验方法。如磁盘信息的读/写等。 码多项式 任何一个n位的x进制数都可以用一个n-1 次的多项式来表示,这种多项式叫码多项式（又叫信息多项式） 。码字中每个码元的值就是该多项式中的相应的系数。 码多项式与x进制序列之间的一一对应关系： （an-1 an-2……a1a0） A (x)= an-1Xn-1+an-2Xn-2 +……+a1X+a0X0 多项式 二进制序列实例 以n=3位二进制数为例 二进制数 对应多项式 000 001 010 011 100 101????? 111????? 码多项式运算法则: 两个码多项式相加减时，对应项系数进行模2加减。 乘除运算与普通多项式类似； 模2加减：二进制码多项式的加减运算为模2加减运算。即各位做不带进位、借位的按位加减。加减运算实际上就是逻辑上的异或运算⊕ 。因此，加法和减法等价。 9-5 循环冗余码 CRC校验的基本思想是： （1）根据欲发的k位信息生成一个r位的数据序列，称为循环冗余校验码或帧校验序列FCS。k位信息与r位校验码组成的二进制序列恰好能够被某个预先确定的数（生成多项式）整除。发送时发送的是k位信息与r位校验码的组合。 （2）接收器用传来的数据（信息位与校验位的组合）除以相同的数（生成多项式），如果无余数，则认为无差错；如果余数不为0，则认为传输出错。 9-5 循环冗余码 生成多项式G(x): 求校验码时所用的“除数”所对应的多项式叫生成多项式。 在串行通信中通常使用下列四种生成多项式G（X）来产生CRC码。 CRC-16：G(x)=X16+X15+X2+1，美国二进制同步系统中采用。（主要应用于帧中继） CRC-8：G(x)=x8+x2+x+1。（主要应用于ATM信元头） CRC-CCITT：G(x)=X16+X12+X5+1，CCITT推荐。（主要应用于HDLC高级数据链路控制 ） CRC-32：G(x)=X32+X26+X23+X22+ X16+X12+ X11+X10+X8+X7+ X5+X4+X2+X+1（主要应用于以太网、令牌总线、令牌环、FDDI、HDLC光纤分布式数据接口 ） 9-5 循环冗余码 产生CRC校验码的步骤： 第一步：在信息码(k位）的末尾加上r个0。假设生成多项式对应的比特位数是h，则r=h-1。相当于把信息位向左移r位。 第二步：采用二进制除法将新的加长的数据单元（k+r位)除以除数(生成多项式对应的二进制序列)。由此除法产生余数。 如果余数的位数m=r，则余数就是循环校验码。 如果余数的位数mr，则在余数的左边补r-m个零，产生的新序列即为循环校验码。 如果余数为0，则循环校验码为r个0 9-5 循环冗余码 循环冗余校验的发送与接收 发送时发送的是k位信息码再拼接r位校验码。 在接收方，用收到的数据除以用来约定好的生成多项式对应的二进制序列。如果余数0，将通过检验。如果余数非零，将通不过检验，说明传输出错。 循环冗余编码工作原理 9-5 循环冗余码 例1：在循环冗余校验码系统中，设其生成多项式为G(x)=x4+x3+x2+1，试求出信息序列101的循环冗余校验码。 求解步骤： 第1步：通信双方约定的生成多项式为 G(x)=x4+x3+x2+1。从给出的多项式中得到它的系数（G=11101） 第2步：在发送端，假设待发送的信息为M（M=101）将M向左移动4位，后面补上4个0，得到（1010000）后除以G,得到商Q和余数R=11,因为求得的余数位数2小于r，所以在左边补2个零，得到0011即为检验码。 第3步：发送端发送：信息码M附加检验码R（1010011）。 接收端将接收到的码元除以同一个生成多项式系数G，若所得到的余数为0，则说明无码元差错；若所得到的余数不为0，则说明存在差错。 算法 1 1 1 1 1 1 0 1√1 0 1 0 0 0 0 1 1 1 0 1