CRC算法的应用理论研究

《CRC算法的应用理论研究》由会员分享，可在线阅读，更多相关《CRC算法的应用理论研究（4页珍藏版）》请在金锄头文库上搜索。

1、2012-07-13#2012-07-13#2012-07-13#CRC 算法的应用理论研究欧海文 1,2 李起瑞 1,2,3胡晓波 3赵静 1,21 西安电子科技大学通信工程学院 陕西 7100712 北京电子科技学院 北京 1000703 北京中电华大电子设计有限责任公司 北京 100102摘要：本文从理论上系统的研究了循环冗余校验(CRC)码的原理和性质，解决了在实际应用中经常碰到的如何设置寄存 器的初始值及如何选取生成多项式的问题；同时，通过分析不同长度下算法的性能差异提出了 CRC 算法对校验数据的长度 没有限制的观点。最后，提出了 CRC 逆运算的概念。关键词：循环冗余校验(CRC

2、)；数据位长度；扩展缩短码；CRC 逆运算0引言在通信领域，由于数据在传输和存储过程中受到各种干 扰，使信号码元发生变化，所以需要进行数据校验以确保数 据的完整性。循环冗余校验 CRC(Cyclic Redundancy Code)由 于其具有检错效率高、原理简单、易于实现的特点得到了广 泛的应用。1CRC 算法基本原理CRC 校验码由分组线性码的分支而来，其应用主要 为二元码组，由一个生成多项式(最高次幂为 r)产生，r 次的生成多项式可产生 r 位的冗余码， 所有码字的运算是 封闭的。设每个信号码元的序列为 m = mn 1mn 2 Lm1m0 用多项(1) 对原始数据采用与发送方同样的生

3、成 CRC 校验码的 方法生成 r ( x) ，然后与 r(x)比较，相等则校验通过，否则认 为数据传输出现差错。(2) 对接收的数据计算 m ( x) 0 mod g ( x) 是否成立，成立则校验通过，否则认为数据传输出现差错。2CRC 的 INTI 和 XOROUT 值 定义 1：函数 CRC (INIT , m) 表示以 INIT 为寄存器初始 值，输入数据为 m 计算 CRC 校验值，默认 CRC (m) = CRC (0, m) 。性质 1： m 0,1r , CRC (m, m) = 0性质 2： m 0,1r , a 0,1iiCRC (m1 , a1 ) CRC (m2 ,

4、a2 ) = CRC (ma m2 , a1 a2 )性质 3： m，a 0,1r , CRC (m, a) = CRC (a, m)CRC 算法虽然选择相同的生成多项式， 但开始时寄存器 中设置的初始值不同得到的 CRC 结果也不同。 初始值对 CRC 算法的结构性能没有任何影响，可以任意设置，通常为了使 得传输数据最前面的 0 能够正确传输，会将 INIT 设置为0xFFFF 同时，出于相同的目的会在 CRC 计算完成后将寄存 器中的结果异或上一个 XOROUT = 0xFFFF 值，然后结果输 出，函数表示为： CRC (m) = CRC (INIT , m) XOROUT 。3 CRC

5、 的生成多项式生成多项式在 CRC 校验中具有决定性的作用，应该指 出并非任何一个多项式都可以作为生成多项式，文献1, 2, 3xn 1 + mxn 2 + L + m x + m式表示为： m( x) = m(1)n 1n 21 0CRC 编码步骤可归纳如下：设生成多项式 g(x)的最高次幂为 r， 上式两端乘以 xr 得：rr + n 1r + n 2r +1rx m( x) = mn 1 x+ mn 2 x+ L + m1 x+ m0 x用 g(x)模 2 除 xr m( x) ，得商 Q(x)和余式 r(x)：xr m( x) = Q( x) g ( x) + r ( x) 编出的码为

6、：T ( x) = xr m( x) + r ( x) 可得输出码序列为：m = mn 1mn 2 Lm1m0 rr 1rr 2 Lr1r0 接收方校验数据有两种方法：(2)(3)(4)(5)男，2011.8532012-07-13#2012-07-13#2012-07-13#作者简介：欧海文，男，博士，北京电子科技学院教授，研究方向：密码编码与密码应用技术。李起瑞， 硕 士研究生，研究方向：信息安全，侧信道攻击与防御技术。胡晓波，女，高级工程师，研究方向：信息安 全理论与应用技术。赵静，女，硕士研究生，研究方向：信息安全，随机数发生器。等给出了选择生成多项式的具体要求和准则。目前国际上已经公

7、布了几种 CRC 生成多项式的标准供我们使用，例如 CRC CCITT = x16 + x12 + x5 + 1 ，通常国际上用其反射多项 式表示为 0x8404， 且已证明好的生成多项式的反射生成多项 式也是好的生成多项式。4 CRC 可校验数据长度和性能CRC 可校验的数据位的长度是可变的，生成多项式 g(x)或其某个因子为 t 次本原多项式时，我们将数据位长度以2t 1 为界分两种情况讨论。 4.1 缩短循环码CRC 在本质上是一种缩短循环码， 在 (n i, k i) 循环码 的 2k 个码字中挑选出前 i bit 为 0 的码字作为 (n i, k i) 缩短 循环码的码字，它的码集

8、是(n, k)循环码集的子集，所以它是 一种系统循环码，当数据位长 n 小于 2t 1 时，除了不具有 循环码的循环性外具有循环码的全部特性。根据有限域相关知识，生成多项式 g(x)或其某个因子为 t 次本原多项式时，这个本原多项式能够整除的 x n + 1 中，n 的最小值是 2t 1 ，它能产生的循环码长就为 2t 1 。以 CRC16 为例，它的生成多项式 g(x) = x16 + x12 + x5+1 = ( x + 1)( x15 + x + 1) 其中 ( x15 + x + 1) 是本原多项式， 能够整 除的 x n + 1 中，n 的最小值是 215 1 = 32767 ，所以

9、原始循环 码是(32767, 32751)循环码。它保留了原始循环码除循环性的 特性，也决定了用 CRC16 校验时的最大信息长度平凡情况 下不超过 32751。4.2 扩展缩短码在 GF(2)上， 生成多项式 g(x)或其某个因子为 t 次本原多 项式时，这个本原多项式能够整除的 x n + 1 中，n 的最小值随机差错；(5) 能 l00%检测出长度小于等于校验位长 r 的单个突发 差错；(6) 能以1 2 ( r +1) 的概率检出长度为 r + 1 的单个突发 差错；(7) 能以1 2 r 概率检出长度大于 r + 1 的单个突发差错； 扩展缩短码和缩短循环码一样是线性分组码，易知它们

10、具有相同的平均不可检错误概率，但二者的差错检测性能仍 有稍微不同。汉明码校验矩阵包含 r 重的所有码，任何两列是线性无 关的，校验矩阵的线性相关性决定了(n, k)线性码分组码的最 小距离，汉明码最小距离等于 3。缩短码校验多项式的列数 小于汉明码校验多项式的列数，在此情况下缩短循环码的最 小距离不小于 3。扩展缩短码校验多项式的列数大于汉明码 校验多项式的列数，其校验矩阵至少有两列是线性相关的， 所以扩展缩短码的最小距离一定等于 2。所以， CRC 作为扩展循环码时将不能 100%检测随机 2bit错误，同样也不能纠正随机 1bit 错误。 6CRC 的实现及应用规范目前，CRC 的计算方法

11、主要有串行和并行两种，实现方 式也可分为软件实现和硬件实现，大量的文献对此进行了研 究，但鲜有文献介绍 CRC 的应用规范，这里以 CRC-CCITT 为例对各个参数进行说明(如表 1)。表 1 CRC16-CCITTtn minnn min = 2 1 ，当 g(x)能整除 x+ 1 时，g(x)定能整除 x + 1 ，t其中 n = m n min ， 这样由 g(x)生成了一个码长大于 2 1 的(n,k, r)循环码，然后从中挑选出前 n-N 位为全 0 的信息位得到(N, N-r, r)扩展缩短码，其中 (m 1)nmin p N n 。 5CRC 算法性能CRC 作为缩短循环码时的

12、性能研究已经得到了较好的 解决，CRC 的检错性能由最小码距和编码本身的特性决定， 以 CRC-CCITT 为例，由于其最小码距为 4，则：(1) 能纠正 1bit 的随机差错；(2) 能 100%检测出奇数个差错；(3) 能 100%检测出任意的 2bit 的随机差错；(4) 能 100%检测出小于等于生成多项式码重 dmin 1 的其中各参数意义为：Name：名称。 Alias：别名。 Width：校验位长度，设为 r。Poly：生成多项式，以十六进制表示，最高位省略。Init：初始化值，以十六进制表示。Refin：设置为布尔值。2504 12-07-13#20#1.#8 #2012-07

13、-13# 2# 0# 1# 2-07-13#NameKERMITAliasCRC16-CCITTWidth16Poly0X1021Init0X0000RefinTrueRefoutTrueXorout0X0000Check0X2189Xcheck0X8921(1) False 取信息多项式的反射多项式，即将信息位反序输入；(2) True 正常输入。Refout：设置为布尔值。的漏检概率而未被采用。其实，CRC 也存在着逆运算，即由校验码可 以倒 推出信息 码或 信息码的 部分 信息。对于 CRC (INIT , m) = r ，若 INIT 和 r 已知，显然，当信息码长度 小于等于校验码长

14、度时，二者成一一对应关系，此时可以通 过查表法倒推出信息码，否则不能惟一确定信息码。因此， 已知 INIT 和 r 求解 m 或已知 r, m 求解 INIT 是一个值得我们 去研究的有趣问题。参考文献1马吉明,魏艳.探究缩短循环码性能与生成多项式的选取.通 信技术.2008. 2杨杰,朱建锋,安建平.无线传输中的循环冗余校验码纠错应 用扩展.北京理工大学学报.2005.3瞿中,袁威,徐问之.CRC 算法在计算机网络通信中的应用. 微机发展.2002. 4王新梅,肖国镇.纠错码原理与方法M.西安： 西安电子科 技大学出版社.2001.5周秦英,王新梅,葛晖.CRC 在中扩展缩短码的设计与性能

15、分析.西北工业大学学报.2004.6 朱荣华. 一种 CRC 并行计算原理及实现方法. 电子学 报.1999. 7蒋安平.循环冗余校验码(CRC)的硬件并行实现.微电子学 与计算机.2007.8Martin Stigge, Henryk Plotz, Wolf Muller. Reversing CRC- Theory and Practice.HU Berlin Public Report.2006.9Ross N. Williams. A painless guide to CRC error detectionalgorithms.www.cse.sc.edu/jimdavis/Courses/crc-Ross.pdf.1993.(1) False 运算完毕后寄存器中的 CRCXorout 步操作；值直接进行(2) True 运算完毕后寄存器中的 CRC 值进行反序操作；Xorout：一个 r 比特长的十六进制值，在 Refout 步骤进 行后与寄存器中 CRC 值进行异或操作。Check：ASCII 字符串“123456789”即31 32 33 34 35 3637 38 39的 CRC 校验值