循环冗余校验码课件.pptx

循环冗余校验编码（循环冗余校验编码（CRC） Cyclic Redundancy checking (CRC)循循环冗余校验，又称多项式码。环冗余校验，又称多项式码。 在循环冗余校验中，不是通过将各比特位在循环冗余校验中，不是通过将各比特位相加来得到期望的校验，而是通过在数据相加来得到期望的校验，而是通过在数据单元末尾加一串冗余比特，称作单元末尾加一串冗余比特，称作循环冗余循环冗余校验码校验码或或循环冗余校验余数循环冗余校验余数，使得整个数，使得整个数据单元可以被另一个预定的二进制数所整据单元可以被另一个预定的二进制数所整除。除。1.CRC校验基本思想校验基本思想 CRC校验的基本思想是： (1)(1)根据欲发的根据欲发的k位信息生成一个位信息生成一个r比特的序比特的序列 ， 称 为 帧 校 验 序 列列 ， 称 为 帧 校 验 序 列 F C S （ F r a m e checking Series）。）。 （2 2）求出实际发送的数据帧（）求出实际发送的数据帧（k+rk+r位），位），这这个帧所对应二进制序列恰好能够被某个预先个帧所对应二进制序列恰好能够被某个预先确定的确定的数数（生成多项式）整除。（生成多项式）整除。 （3 3）接收器用相同的数）接收器用相同的数（生成多项式）（生成多项式）去除去除传来的帧。如果无余数，则认为无差错；如传来的帧。如果无余数，则认为无差错；如果余数不为果余数不为0 0，刚认为传输出错。，刚认为传输出错。 奇偶校验对一个字符校验一次，适合异奇偶校验对一个字符校验一次，适合异步通讯；而步通讯；而CRC对一个数据块（对一个数据块（frame）校验一次，适合同步通讯。在串行同步校验一次，适合同步通讯。在串行同步通信中，几乎都使用这种校验方法。如通信中，几乎都使用这种校验方法。如磁盘信息的读磁盘信息的读/写等。写等。2.CRC校验常用场合校验常用场合 CRC码生成和校验基本分为三步码生成和校验基本分为三步：第一步：在数据单元第一步：在数据单元(k(k位）的末尾加位）的末尾加上上r r个个0 0。r r是一个比预定除数的比特位是一个比预定除数的比特位数数(r+1)(r+1)少少1 1的数。的数。第二步：采用二进制除法将新的加长第二步：采用二进制除法将新的加长的数据单元（的数据单元（k+rk+r位位) )除以除以除数除数。由此。由此除法产生的除法产生的余数余数就是循环冗余码校验就是循环冗余码校验码。码。3.CRC码的生成码的生成 第三步：求第三步：求CRCCRC循环冗余校验码循环冗余校验码 (K+r)被除数被除数+r(余数余数)如果余数位数小于如果余数位数小于r，最左的缺省位数为，最左的缺省位数为0。如果余数为如果余数为0,则则r=0。CRC码的生成码的生成 CRC码校验码校验：到达接收方的数据单去除以用来产生到达接收方的数据单去除以用来产生循环冗余校验余数的循环冗余校验余数的G G（X X）。）。如果余数如果余数0 0，将通过检验。如果余数，将通过检验。如果余数非零，将通不过检验。非零，将通不过检验。4.CRC码的校验码的校验 任何一个二进制数序列可以和一个只含有任何一个二进制数序列可以和一个只含有0和和1两个系数的代数多项式建立起一一对两个系数的代数多项式建立起一一对应的关系。因此，用来求应的关系。因此，用来求CRC码的那个除码的那个除数通常用多项式来表示。原因如下：数通常用多项式来表示。原因如下： 代数多项式很短代数多项式很短 可以通过多项式来进行概念的数学证明。可以通过多项式来进行概念的数学证明。5.多项式多项式 多项式多项式 任何一个任何一个n位的二进制数都可以用一个位的二进制数都可以用一个n-1 次的次的多项式来表示多项式来表示,这种多项式叫这种多项式叫码多项式（又叫信息（又叫信息多项式）多项式） 。 码多项式与二进制序列之间的一一对应关系：码多项式与二进制序列之间的一一对应关系： （an-1 an-2a1a0）N A (x)= an-1Xn-1+an-2Xn-2 +a1X+a0X0码多项式多项式多项式 二进制序列实例二进制序列实例 以以n=3位二进制数为例位二进制数为例 二进制数二进制数 对应多项式对应多项式 000 001 010 011 100 101 111 01xx+1x2x2+1x2+ x+1n1011011 x6+x4+x3+x+1nx5+x4+x2+x 110110 码多项式运算法则码多项式运算法则: 二进制码多项式的加减运算为二进制码多项式的加减运算为 模模2加运算，加运算，即两个码多项式相加时，对应项系数进行即两个码多项式相加时，对应项系数进行模模2加减。加减。 乘除运算与普通多项式类似；乘除运算与普通多项式类似； 模模2加减：即各位做不带进位、借位的按加减：即各位做不带进位、借位的按位加减。这种加减运算实际上就是逻辑位加减。这种加减运算实际上就是逻辑上的异或运算。即加法和减法等价。上的异或运算。即加法和减法等价。码多项式码多项式 生成多项式生成多项式G(x): 求求CRC码时所用的码时所用的“除数除数”所对应的多项所对应的多项式叫式叫生成多项式。 在串行通信中通常使用下列三种生成多在串行通信中通常使用下列三种生成多项式项式G（X）来产生）来产生CRC码。码。CRC-16CRC-16：G(x)=XG(x)=X1616+X+X1515+X+X2 2+1+1，美国二进制同，美国二进制同步系统中采用。步系统中采用。CRC-CCITTCRC-CCITT：G(x)=XG(x)=X1616+X+X1212+X+X5 5+1+1，CCITTCCITT推荐。推荐。CRC-32CRC-32：G(x)=XG(x)=X3232+X+X2626+X+X2323+X+X2222+ X+ X1616+X+X1212+ + X X1111+X+X1010+X+X8 8+1X+1X7 7+ X+ X5 5+X+X4 4+X+X2 2+X+ 1+X+ 1码多项式码多项式 循环冗余码生成器采用模循环冗余码生成器采用模2 2除法。下图显除法。下图显示了这一过程。示了这一过程。 CRCCRC校验器的功能完全像发生器一样，当校验器的功能完全像发生器一样，当收到附加了收到附加了CRCCRC码的数据后，做同样的模码的数据后，做同样的模2 2 除法。如果余数是全除法。如果余数是全0 0，则将，则将CRCCRC码丢码丢弃，接受数据。否则，丢弃收到的数据。弃，接受数据。否则，丢弃收到的数据。6.CRC码生成器和校验器码生成器和校验器 CRC校验码的生成器和校验器校验码的生成器和校验器r个比特0数据g(x)CRC校验码r+1r余数先发数据位先发数据位后发校验位后发校验位g(x)余数r+1r数据0接收，非接收，非0拒绝拒绝数据发送方发送方接收方接收方 0G(X) 111010100011010 CRC校验码校验码 信息码信息码 CRC冗余校验码冗余校验码7.CRC码性能码性能 CRCCRC码是很有效的差错校验方法。码是很有效的差错校验方法。除了正好除了正好数据块的比特值是按除数值变化的错误外，数据块的比特值是按除数值变化的错误外，循环冗余校验循环冗余校验(CRC)将检测出其他所有错误。将检测出其他所有错误。而且，常用的而且，常用的CRC除数通常有除数通常有17，或是，或是33个比特，使得不可检测的错误可能降低到几个比特，使得不可检测的错误可能降低到几乎近于零。乎近于零。 CRC接收电路再配上适当的硬件电路不仅可接收电路再配上适当的硬件电路不仅可以检错，而且可以纠错，纠错能力很强特别以检错，而且可以纠错，纠错能力很强特别适合检测突发性错误，在数据通信中得到较适合检测突发性错误，在数据通信中得到较广泛的应用。广泛的应用。检错性能检错性能 能检测出全部单个错误能检测出全部单个错误 能检测出全部随机二位错误能检测出全部随机二位错误 能检测出全部奇数个错误能检测出全部奇数个错误 能检测出全部长度小于能检测出全部长度小于k位的突发错误位的突发错误 能以能以1-（1/2）k-1概率检测出长度为（概率检测出长度为（k+1）位的突发性错误位的突发性错误课堂练习题课堂练习题 设某一循环码，其生成多项式为设某一循环码，其生成多项式为G（X）=X5 + X2+1，试求出信息序列，试求出信息序列1101010101011的循环校验码的循环校验码CRC（要求（要求写出计算步骤）。写出计算步骤）。 设某一循环码，其生成多项式为设某一循环码，其生成多项式为G（X）= X5+X4+ X2+1，试求出信息序列，试求出信息序列1010001100的的CRC循环校验码（要求写出循环校验码（要求写出计算步骤）。计算步骤）。