crc编码原理及应用

crc编码原理及应用

在数据传输中，通常把误码率作为通信质量的衡量标准，但误码率是一个整体的平均衡量，是一种长期的性能评估。不能提供特定代码源和码源组的源信度评估，也不能在短时间内对通信质量进行评估。一种常用的解决方法是将数据分组传输,每组码元采用称为帧校验序列(FCS,FrameCheckSequence)的差错控制编码进行编码/解码,从而获得具体每一帧的误码性能和置信度。在帧校验序列的实现中,循环冗余校验码(CRC,CyclicRedundancyCheckCode)以其高效率、高性能获得了广泛应用,其中具有16个冗余比特的CRC编码进入了多个国际通信标准,本文的研究重点就是16位冗余CRC编码。常见的16位CRC多项式有两个:CRCCCITTg(x)=x16+x12+x5+1=(x+1)(x15+x14+x13+x12+x4+x3+x2+x+1)CRCANSIg(x)=x16+x15+x2+1=(x+1)(x15+x+1)这两个多项式都由两部分组成,前部分是因式(x+1),可以提供具有差分运算的功能,后一部分是一个周期为215-1=32767的本原多项式,可以证明两个本原多项式的周期都是32767,即(x32767+1)mod(g(x))=0,生成多项式的组成和周期在很大程度上决定了CRC的性能。1编码性能的控制CRC的基本原理在一般的通信教科书中都有较为详细的描述,这里只给出简单的数学描述,本文的目的是找出数学原理中和编码性能相关的部分,本文不考虑发送接收长度不相等的情况,实际应用中可以通过其他方法进行控制。为了推导方便全文设定下列符号:1.1编码程式的生成CRC编码分析在GF(2)上进行,分析的工具是近世代数的多项式理论。基本过程如下:设m(x)xr=p(x)g(x)+q(x),p(x)为商式,q(x)为余式两边同时加余式q(x)m(x)xr+q(x)=p(x)g(x)+q(x)+q(x)=p(x)g(x)令s(x)=m(x)xr+q(x)=p(x)g(x)显然s(x)modg(x)=0,即发送编码多项式可以被生成多项式整除。如果传输中没有错误则r(x)=s(x),应有r(x)modg(x)=0。很明显如果信息传输的过程中没有发生错误,则接收到的信息多项式一定可以被生成多项式整除,这就是CRC的检错原理。值得注意的是这一命题的逆命题并不成立,也就是说接收到的信息多项式可以被生成多项式整除,并不代表信息在传输中没有发生错误,下文将对这一问题仔细分析。1.2crc编码的检错能力CRC在本质上一种缩短循环码,是分组码的一种特例,同时由于编码后的前k位是信息,所以是一种系统循环码。因此当n小于2r-1时,除了不具有循环码的循环性外具有分组码和循环码的全部特性:1)[n,k]循环码构成n维线性空间的一个k维子空间,在长度为n中2n个组和中仅有2k个组和属于码空间;2)任意两个码字的和仍然是一个码字;3)码的最小距离等于非零码的最小重量;下面分析传输有错情况下的s(x)、r(x)和e(x)关系:r(x)modg(x)=(s(x)+e(x))modg(x)=s(x)modg(x)+e(x)modg(x)=e(x)modg(x),由此可得到的结论:CRC编码的检错能力与信息码序列无关,只和差错序列有关。分析下列两种情况:1)e(x)modg(x)≠0,CRC可以检出传输有错,通信系统一般采用ARQ机制进行重传:2)e(x)modg(x)20,且e(x)≠0,CRC检错失效,产生漏检,可以看出此时的e(x)也属于一个码字,即r(x),s(x),c(x)都是合法的码字,这种情况下CRC就是失去了检错的能力。推论1:当错误图样多项式e(x)是码空间的一个样本时,CRC无法检出错误,这时r(x)、s(x)和e(x)都是属于码空间的合法码字。1.3crc编码参数11生成的矩阵和验证矩阵由于RIC是循环码的一种特例,所以可以按照循环码用生成多项式g(x)的通用方法来生成CRC码的生成矩阵和校验矩阵。2编码的偶校验特性码重分布是指一个[n,k]线性分组码的码字重量分组,它是计算各种错误概率的主要依据之一,也是研究码结构的重要窗口,通过它可以透彻地了解码的内部结构。设Ai为[n,k]分组码中重量为i的码字数目,则集合{A0,A1,…,An}称为该分组码的重量分组。一般而言求出一个码组的算法复杂度是2k,属于一个NP完全问题。当K>n-k时就是信息位的数目大于校验位数目,可以求取对偶码的重量分布利用Mac-Willians恒等式获得,这样可以将算法复杂度降低到2n-k,在本文中提到的两种CRC方案里r=n-k=16,这种复杂度下可以利用计算机搜索获得,文献提供了具体的实现方法。这里给出一个CRC缩短循环码的特殊性质,这一性质对分析码距和差错误码率有着重要的作用。推论2:以CRC-ANS1和CRC-CCITT多项式为生成多项式的缩短循环码中非零项的个数为偶数个,即码重分布中奇次项都为零,或者说码字本身具有偶校验特性。证明如下:由于CRC-ANSI和CRC-CCITT多项式中都包含(x+1)项,所以任何码字都可以被(x+1)整除。即s(x)mod(x+1)=0同时xmmod(x+1)=1(xm+xn)mod(x+1)=0m≠n,m≥0,n≥0所以,当且仅当码字多项式中包含偶数个非零项时才能被x+1整除,证毕。3最小码重/码距分组码的性质指出,码字的最小码距决定纠错能力,而最小码距等于非零码字的最小码重。CRC-ANSI和CRC-CCITT的最小码重分析如下:●由于生成多项式本身码重为4,且都属于码字,所以最小码重d小于等于4;●由于所有码字中非零项的个数为偶数个,所以最小码重不等于1、3;●任何包含两个非零项的码字可以表示为xn(xm-n+1),其中xn不能被g(x)整除,(xm-n+1)也不能被g(x)整除,否则与g(x)的周期为32767相矛盾。综上所述:推论3:CRC-ANSI和CRC-CCITT的最小码重w和最小码距d*为4。根据分组码的纠错能力可知,最小码距d*为4的CRC蝙码至少具有下列性能:(1)可以纠正所有1个错误;(2)可以检出所有3个以下错误;事实上出于CRC的特殊设计,其检错能力远远高于通用的分组码。2crc编码复杂模型的检错性能衡量编码方案的标准是检错能力和译码错误概率,一般译码错误概率可以分成不可检错概率、译码失效概率和译码错误概率,由于CRC编码主要用于ARQ机制中的检错,所以我们重点分析它的检错性能。2.1单个突发错误CRC的检错性能由最小码距和编码本身的特性距定,文献都给出了部分性能,本文拓展描述如下:1)所有奇数个错误。由CRC码字的性质可知,所有的码字的重量都是偶数,所有重量为奇数的错误都不属于码空间,都可以被检出。2)检所有单个突发错误。推论4:CRC可以检出任意长度的单个突发错误。证明如下:设e(x)=xm+i+xm+i-1+…+xm=xm(xi+xi-1+…+1)=xm(xi+1+1)/(x+1)对于任意i<2n-k,m≥0,i≥0,xmmodg(x)≠0;(xi-1+1)mod(g(x))≠0;所以即e(x)modg(x)≠0,即e(x)不属于码空间,则必定可以被检出。3)检所有两个错误设e(x)=xm+i+xm=xm(xi+1)=xm(xi+1),显然e(x)的两项因式都不是g(x)的因式,所以e(x)也不属于码空间,可以被检出。这一点也可以用距小码距为4来证明。2.2求解pud的概率由推论1可知当错误图样e(x)为码空间上的一个矢量时,CRC检错功能失效,产生不可检测错误(undetectederror),系统无法进行重传或者纠错,传输的信息被丢失。因此在通信系统设计中必须对CRC,的漏检概率(probabilityofundetectederror,Pud)进行分析,并采取必要的技术措施,这一点在高速数据传输中尤其重要。在[n,k]CRC循环码中,设传输信道为BSC信道,误码率为p,则各种的概率分布如下:正确传输的概率:Pok=(1-p)n发生错误的概率:Po=1-Pok=1-(1-p)n单个码重为w的错误发生的概率:pew=pw¯¯¯(1−p)n−w¯¯¯¯¯¯¯pew=pw¯(1-p)n-w¯设码重分布为[A0,A1,A2,…,An],则发生不可检测的概率为Pud=∑i=0nAiPi(1−P)n−iΡud=∑i=0nAiΡi(1-Ρ)n-i所以,求解的关键在于求出CRC的码重分布,一般在P<0.5,k>n-k时需要借助对偶码来降低求解的复杂度。一般而言对于n比较大的情况,精确求解Pud是很困难的。这里可以通过整体分析的方法获得平均的Pud,对于[n,k]CRC编码而言,存在2n个接收矢量r(x),2k个码元矢量s(x),其中2k-1个非零矢量可以是可能的不可检测错误矢量e(x),在信道误码率为p的BSC信道上,不可检测错误发生的概率为Pud=2k(1-(1-p)n)/2n<1/2n-k因此,可以将1/2n-k作为Pud分析的上限,对于CRC-ANSI和CRC-CCITT而言,Pud的上限是1/216,约为1.52×105,就是说大约65000个数据包中才会发生一个不可检测错误,这对于中低速的串行已经足够好了,甚至可以忽略。但是近年来随着高速数据通信的飞速发展,不可检测错误的影响已经不可忽视,例如在CISCOGSR12000路由器中每秒钟转发的数据包可以达到4500万个,就是每秒钟可能会发生多达686次不可检测错误,这种情况不可以忽略不记,一般要考虑更高次数的CRC-32或者其它措施。2.3单比特纠错性能作为分组码的一种特例,CRC本身具有一定的纠错能力,CRC-ANSI和CRC-CCITT都具纠正单比特错误的能力,在传统的低速通信中由于误码较高,发生单比特错误的比例较小,纠错的效率不高;随着光纤通信的等低误码率信道的出现,发生单比特错误在总的错误中的比例大大提高,因此采用单比特纠正错误可以大大提高信道的吞吐量和降低对反向信道占用,一种典型应用(CRC-CCITT,帧长1024比特)下的单比特纠错性能如下表。由上表可知,当错误发生的数学期望np<=l时,单比特是帧错误的主要组成,在低误码率时这一点尤其明显,利用CRC的单比特纠错特性,可以显著地降低误码率,并提高网络的吞吐量。纠正单比特错误的方法也很简单,首先将单比特错误图样依次送入编码器进行编码,选取最后输出n-k为构成一个长度为n的表,如果r(x)不能被g(x)整除,将余数和表中的数据逐个对比,如果相等则纠正相应位置的单个化特,如果全