日志

CRC的错误校验能力

已有 8127 次阅读| 2007-1-12 05:24 |个人分类:信道编码

天气: 晴朗

心情: 高兴

循环冗余校验码(Cyclic redundancy code: CRC)作为线性分组码的一种，由於其编解码的软硬件实现简单，被广泛应用于信息技术的各个领域。循环冗余校验码是循环码的一种，循环码的编码可以通过多项式乘积来进行。如果信息字(infoword)通过信息多项式u(x)表示，即信息字的各位字符是信息多项式的各项系数，码字(codeword)可以通过生成多项式g(x)与u(x)相乘后模x^n+1来获得的选取。其中，参数n是能使x^n+1除尽g(x)的最小值。CRC是系统码，校验字是由u(x)*x^(n-k)模g(x)来获得。无论系统码还是非系统码，码字多项式都是可以整除g(x)。这也是错误校验的基础，如果接收字不能整除g(x)，则传输过程中必定出现错误。另一方面，如果错误字恰好是g(x)的倍数，则错误无法被校验出来。

CRC码的生成多项式通常采用g(x)=(1+x)p(x)的形式，其中p(x)为本原多项式(primitive polynomial)。CRC的验错能力可以分析如下：

1）由于采用(1+x)，所以码字多项式作为g(x)的倍数必定有偶数项，因此，所有奇数个错误可以被检验出来。

2）双比特错误可以表示为x^j+x^k=x^j(1+x^(k-j))，由于p(x)为本原多项式，可以整除p(x)的最小(k-j)的值为n，所以，所有双比特错误可以被检验出来。

3）生成多项式具有g(x)=1+g_1*x+…+g_n-k-1*x^n-k-1 + x^n-k的形式，所以所有个数小于或等于(n-k)的错误都不可能整除g(x)，即可被检验出来。

关于CRC码的另一个重要的特性是无法被校验错误(undetectable error)的概率，如果知道CRC校验之前的误比特率，就可以通过码重的分布来计算。通常CRC码的校验位个数远远低于信息比特个数，所以可以通过它的对称码的码重分布利用MacWilliams定理来计算无法被校验错误的概率。关于如何选用CRC及相关文献，可参见http://www.ietf.org/rfc/rfc3385.txt。