基于 crc的多比特纠错算法研究与实现

1、代号分类号10701TN919学号密级0808320356公开题（中、英文）目基于 CRC 的多比特纠错算法研究与实现The Research and Implementation of theAlgorithm of Multi-bits Error CorrectionBased on CRC作者姓名王栋指导教师姓名、职务肖嵩教授学科门类工学学科、专业通信与信息系统提交论文日期二一二年十二月创新性声明本人声明所呈交的论文是我个人在导师的指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其它人已经发表或撰写过的研究成果；也不包含为获得西

2、安电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志所做的任何贡献均已在论文中做了明确的说明并表示了谢意。申请学位论文与资料若有不实之处，本人承担一切相关责任。本人签名：_日期：_关于论文使用授权的说明本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内容，可以允许采用影印、缩印、或其它复制手段保存论文。 保密的论文在解密后遵守此规定）本人签

3、名：_导师签名：_日期：_日期：_（摘要摘要随着互联网技术不断的发展，以及计算机计算能力的不断提高，大数据存储和通信日益频繁，人们对数据存储质量和通信质量要求也越来越高。循环冗余检验（CRC）以其简单的算法和良好的检错性能得到广泛应用,特别是在网络数据传输，数据存储检错，嵌入式等方面。在网络数据传输方面， CRC 检错配合了错误重传机制，从而能够对出现错误的数据进行重传以保证其正确性。而 CRC 纠错能力的发现则有望缩小重传时延，在一定程度上提高 CRC 的应用效率及改善网络通信质量，减小数据存储误码率。CRC 纠错能力是建立在其检错性能基础之上，是对检错性能的一个延伸与强化。单比特纠错现在已

4、经得到了初步应用，本文的工作则是在单比特纠错的基础上，研究 CRC 多比特纠错，以及纠错性能极限情况。另外，还对其纠错和检错性能的局限性做了阐述。本文做了如下工作：在 CCITT 的 CRC-16 单比特纠错算法的基础上，研究 CRC-32的单比特及其双比特纠错算法可能性，并验证了算法思想，进一步对 CRC-32 四比特纠错算法的可能性进行了验证，并完成最终算法的实现。在对多比特错误数据分析的基础上，最后得出多比特纠错与其检错极限之间的一般关系，并验证了多比特纠错理论证明。最终可以将我们的算法思想应用于任何一个知道其检错能力的 CRC 进行多比特纠错。最终得出结论，在知道任何的一个生成多项式对

5、一定长度信息位最大检错能力的情况下，均可以获得其最大的纠错能力。ABSTRACTWith the development of the Internet and the evolvement of computation of thecomputer, the big data is frequently used in the peoples life. Then the quality of datagets big concern. In the data transmission on the internet, the CRC( CyclicRedundancy Check) is

6、wildly implemented for its simplicity in algorithm and hardware implementation. Along with its using, the ARQ (Automatic Repeat Quest)method is also used for data retransmitted in case the errors happen. The CRC methodis also used for detection the bit riot in big block data storage. The CRCerror-co

7、rrection will be promising in improving the quality of the data in the Internettransmission as well as reducing the bit riot in data storage. The single biterror-correction has been adopted in some fields. Multi-bits error-correction as well itslimit will be investigated in this paper.The contributi

8、on as following has done in this paper: First, it presents theerror-correction basement and the single bit and double bits of CRC-16 and CRC32error-correction algorithm is presented followed by the single bits and double bits errorcorrection algorithm .Third, it presents the CRC-32 bits error-correc

9、tion algorithm andC source code .Finally, after the bits-errors data is analyzed, the relationship betweenthe ability error detection and multiple error correction, as well as its proof. All theerror correction method is based on the fact the bits errors correspond with its CRCand no duplicated ones

10、 appear so that we can find the riot bits precisely. Of course ourmethod perhaps has a constraint that the I/O from file perhaps will prolong the delay,especially in Internet use. Also the resolution is offered in the last section.Key Words: CRC error-control error-detection error-correctionABSTRACT

11、ABSTRACT3目录目录第一章绪论. 11.1 选题背景. 11.1.1 差错控制的作用. 11.1.2 差错控制方式. 11.2 纠错码概要. 31.2.1 纠错码发展概况. 31.2.2 纠错码性能简析. 31.3 本文的主要工作. 41.4 本文的结构安排. 5第二章 CRC 校验数学背景及发展概况. 72.1CRC 校验原理及计算. 72.1.1 CRC 校验原理. 72.1.2CRC 校验的计算. 82.1.3 CRC 校验字的局限性. 152.2 CRC 的发展与应用. 162.2.1 CRC 标准及其多项式. 162.2.2 CRC 在实际应用中的发展. 192.2.3CRC

12、检错性能总结. 202.3 本章小结. 23第三章 CRC 纠错算法研究. 253.1 单比特算法. 253.1.1 CRC-16 单比特纠错算法思想 . 253.1.2 基于 CRC-16 的单比特纠错的实现 . 263.1.3CRC-32 单比特纠错算法验证 . 283.1.4 性能分析. 283.1.5 单比特纠错的结论. 283.2 双比特纠错算法实现. 283.2.1 CRC-16 双比特纠错算法思想 . 283.2.2 CRC-32 的双比特纠错算法实现思路 . 293.3 双比特纠错分析. 293.4 四比特纠错算法实现. 303.5 本章小结. 33第四章 CRC 多比特纠错分

13、析. 35目录4.1 多比特纠错理论分析. 354.1.1 多比特纠错与检错之间的关系. 354.1.2 多比特纠错与检错关系理论证明. 354.1.3 CRC 多比特纠错能力分析. 374.2 最大检错能力的验证方法. 384.3 多比特纠错极限验证. 394.4 本章总结. 40第五章总结与期望. 41致谢. 43参考文献. 45附录 A. 47第一章绪论1第一章绪论1.1.1随着互联网技术和电脑硬件技术的不断发展，个人电脑的运行速度已经不是信息处理和数据传输的主要瓶颈。硬盘的容量不断提高，数据读取速度不断加快，于此同时互联网网速也随着光纤的应用呈现出疯狂增长的趋势。但是由于各种原因，我们

14、的存储数据会损坏，比如光盘划痕会造成一连串的数据差错。同样，数据在传输过程中，也会由于各种原因而出错，比如噪声干扰所产生的随机错误，以及在通信过程中信号衰落而产生的突发错误，以及各种条件下的混合式的数据差错。对于存储数据我们需要检查其有效性，是否出现错误特别是一些对我们工作生活至关重要的数据，一旦出现数据损坏，那么数据的差错恢复就有了及其重要的作用。对于通信中的传输数据，最重要的是保证其可靠性。这就需要引入对数据的差错检验，甚至差错恢复等措施。而对于存储数据有效性的检验也需要差错控制。数据的差错控制是必不可少的。而且随着互联网的不断发展，差错控制技术会越来越得到长足发展。循环冗余校验编码（Cy

15、clic Redundancy Codes）是一种广泛应用于各种计算机网络和数据存储设备中得编码手段，是一种相对于其他方法来说代价小，效率比较高的一种检测错误的编码方式。随着数据传输和数据存储量的不断加大，人们对鲁棒性比较高，而且相对简单，代价小的错误检测方案的需求也不断的增加。那么如果能保证正在广泛使用的循环冗余校验码能够非常有效的被利用起来，不仅能检错，在一定程度上亦可纠错，那么无论是对于信息传输措施还是数据存储设备都将将在性能上获得巨大改善。首先我们先简单的认识下差错控制的基本知识。在数字通信中，常用的差错控制方式 1,2 有，检错重发式（ARQ），前向纠错式（FEC），混合纠错检错式（

16、HEC），反馈校验方式（IRQ）。1.1 选题背景1.1.2 差错控制方式差错控制的作用2基于 CRC 的多比特纠错算法研究与实现发收可以纠正错误的码FEC能够发现错误的码ARQ应答信号可以发现和纠正错误的码HEC应答信号信息信号IRQ信息信号图 1.1 差错控制的基本方式1.检错重发式（ARQ）采用检错重发方式，发端经编码后发出能够发现错误的码字，接收端收到后经检验如果发现传输中有错误，则通过反向信道把这一判断结果反馈给发送端。然后发送端把信息重发一次，直到接收端确认为止。采用这种方法需要具备双向通信。一般在计算机通信中，ACK 为确认信号，NAK 为否认信号。检错重发分为三种类型:（1）停

17、发等待重发，发对或发错，发送端均要等待接收端的回应。特点是系统简单，但时延长。（2）返回重发，无 ACK 信号，当发端收到 NAK 信号后，重发错误码组以后的所有码组。特点是系统复杂，时延小。（3）选择重发。无 ACK 信号，当发端收到 NAK 信号后，重发错误码组，特点是系统复杂，时延最小。2前向纠错方式（FEC）发送端经编码发出能纠正错误的码字，接收端收到这些码组后，通过译码能发现并纠正误码。前向纠错方式不需要反馈通道，特别适合只能提供单向信道的场合，特点是时延小，实时性好，但是系统复杂。但随着编码理论和微电子技术的发展，编译码设备成本下降，加上有单向通信和控制电路的优点，在实际应用中会日

18、益增多。3.混合纠错检错方式（HEC）混合纠错检错方式是通过前向纠错方式和检错重发方式的结合，发送端发出的码不单有一定的纠错能力。这种方式在实时性和复杂性方面是前向纠错码和检错重发方式的折中，因而今年来在数据通信系统中采用较多。第一章绪论34.反馈检验方式（IRQ）反馈校验方式又称回程校验。收端把收到的数据序列全部由反向信道送回发送端，发送端比较发送数据与会送数据，从而发现是否有错误，并把认为错误的数据重新发送，直到发生送段没有发现错误为止。这种方式的优点是不需要纠错、检错的编译器，设备简单。但缺点是需要反向信道，实时性查，发送端需要一定容量的存储器。IRQ 方式仅适用于低速传输、低数据差错率

19、的简单系统中。1.2.1差错控制技术随着差错控制编码理论的完善和数字电路技术的飞速发展不断得到发展，例如信道编码已经成功的应用于各种通信系统中，并且在计算机，磁记录与各种存储器中也得到日益广泛的应用。差错控制编码的基本实现方法是在发送端将被传输的信息附上一些监督码，这些监督码元与信息码元之间以某种确定的规则互相联系和约束。接收端按照既定的规则校验信息码元与监督码元之间的关系，一旦传输发证差错，则信息码元与监督码元的关系就遭到破坏，从而接收端可以发现错误乃至纠正错误。因此研究各种编码和译码方法是差错控制编码所需要解决的问题。这些编码方式包括：前向纠错编码（FEC），线性分组码（汉明码 1 、循环

20、码）、里德-所罗门码（RS码）、BCH 码、交织码、卷积码 Turbo 码等等。在其发展过程中分组码和卷积码成为两类最重要的纠错码。分组码是对信源特发的信息进行分组编码，他的校验位仅同本组的信息位有关。自分组码发展以来，其在数字通信和信息存储方面得到了广泛的应用。卷积码不对信息序列进行分组编码，它的校验元不仅与当前的信息元有关，而且同以前有限时间段上的信息元有关。在编译码方面，卷积码都要比分组码的效率更高。在串行通信技术中, 由于交直流电信号的特性而形成的静态事件可引起传输中的信号失真和信号衰减, 同时, 由于传输通道上的脉冲噪声或者雷电等随机现象而引起的瞬变事件也会引起传输的错误。串行通信是

21、比并行通信更为脆弱的通信方式, 任何细微的噪声都可能在多个位上造成严重的错误。所以, 对错误的检测和处理是串行通信技术的一个重要方面, 对于在地球和星际太空飞行器之间的不可重复的“实时”，数据的传送或者其它大面积远距离的数据传送, 错误检测和处理就显得更为重要。1.2 纠错码概要1.2.2 纠错码性能简析纠错码发展概况4基于 CRC 的多比特纠错算法研究与实现许多错误检测机制都使用了冗余位。奇偶校验是所有可能的冗余位中最低级的一种，它只能检测那些影响了奇数个位的错误，只能提供最低级的错误检测，故它在异步串行通信中普遍效率低下，而且其花费时间也长。在一种 10 位的SDU(1 个 START 位

22、、7 个 DATA 位、1 个 STOP 位)中，便有 10%的系统时间在传送奇偶校验位, 然而, 竟有 40%的错误会检测不到。对于数据块也可以在行、列上增加冗余位以进行奇偶校验，但是，同单个字符的奇偶校验一样，数据块的行奇偶校验不能检测出双位错误，也不能检测出同一列中出现的偶数个错误。而对于增加了算术校验和冗余位的数据块，其校验和能够检测出行中的双位错误，但不能检测出同一列中的偶数位错误, 而且，不能校验和检测出排序错误。由此可见, 以上所述的校验方法都内含有各种不容忽视的缺陷，而对于效率较高的纠错码，其复杂度同时也比较高，不适合数据传输应用。而循环冗余检验码以其较小复杂度和比较高的有效性

23、得到各种应用场合的青睐。这就是循环冗余位校验(Cyclical Redundancy Check)，简称 CRC 校验。当采用 16 位长的校验值时，它对单个位错误、偶数位错误、奇数位错误、一定长度的偶数位错误以及突发性错误的发现率均为 100%，而当采用更长的生成多项式时就会得到更好的检错性能。1.3 本文的主要工作本文针对 CRC 在实际应用中的强的检错能力提出了将其用于多比特纠错环节，其完成的工作主要如下：第一：基于单比特的纠错方案提出多比特纠错的设想，找出多比特纠错的理论可能性。第二：采用 CRC-32 实现四比特纠错，C 代码验证。第三：对 CRC 多比特纠错的理论可能进行理论证明。

24、第一章绪论51.4 本文的结构安排第一章简介纠错码的知识，提出 CRC。第二章详细介绍 CRC 的理论背景知识以及其目前发展概况。第三章实现 CRC-16，CRC-32 的单双比特的纠错算法的探索。第四章经过 C 语言算法验证以及数据分析，并证明出一般情况下 CRC 检错与纠错之间的关系。第五章对 CRC 纠错算法的展望，提出自己的看法。6基于 CRC 的多比特纠错算法研究与实现第二章 CRC 校验数学背景及发展概况 72.1.1循环冗余检验码（Cyclic Redundancy Check, CRC）属于现行纠错码，同时是一种检错能力很强的数据校验码。主要用于计算机网络、同步通信以及磁表面存

25、储器，数据存储设备等应用场合以检测原始数据由于噪声等原因而出现的数据损坏，即数据错误。特别是在通信领域由于其简单易于硬件实现和数学分析，在检测通信信道中由于噪声造成的数据错误十分有效。循环冗余校验码之所以被叫做校验值，是因为其校验值是冗余，而且其实现算法是基于循环码而实现的。这个算法思想是由 W.Wesley Peterson 在 1961 年发明的。而用于以太网的 CRC-32 位多项式以及用于其他标准的多项式其均源自于多位研究人员在 1975 年的研究成果。其算法基本思想是对信息做一个多项式除法运算，得到校验位，并将其加在原信息数据后面，在信息收端对所收到的数据做同样的计算，如果计算结果不

26、匹配则进行一系列的纠错或者其他能消除错误的措施。CRC 是基于循环纠错码理论的。利用系统循环编码思想，为了检测在通信网络传输中的错误，给信息端后加一个定长的校验值。循环码不仅容易实现，而且很适合检测突发错误，以及数据信息中的连续错误。这点很重要，因为在突发错误在通信信道中很常见。同时磁和光学存储设备也容易发生类似的情况。通常情况下，n 比特长的 CRC 能检测1 出任意长度数据的不超过其校验字长度的单个突发错误，能检测出长于定义的。用这个多项式对信息数据做除法，余数就是所求的结果。其运算过程是一个有限域的算数。实际中，所有的 CRC 计算都采用的是有 2 的限域。这个域中的两个元素，不是 1

27、就是 0，很好的与计算机算数吻合。循环冗余检验码是通过除法运算来建立有效信息位的约定关系。假设待编码的有效信息以的用多项式 M(x)表示，信息位分别为多项式的系数。将多项式左移若干位后用另一个约定的多项式 G(x)去除，所产生的余数就是校验位。有效信息位与校验位拼接构成了 CRC 码字。当接收方收到 CRC 码后，对信息用约定多项式做模 2 除法，如果余数为 0，则表明数据无误，否则表明有错误出现。其数据结构如下图所示：第二章 CRC 校验数学背景及发展概况2.1CRC 校验原理及计算( )1 2 n 的突发错误。CRC 码字是由生成多项式CRC 校验原理8基于 CRC 的多比特纠错算法研究与

28、实现图 2.1CRC 校验码的结构其具体步骤如下：（1）将待编码的 N 位有效信息表示成一个 n-1 阶的多项式 M(x)。k决定)。k（4）将左移 K 位后的有效数据与余数做加法，即形成 N+K 的 CRC 码。（5）在接收端对数据用同样的 G(x)进行模 2 除法，余数为 0 即无误，否则有误。其中生成多项式的选择对其算法的可靠性起到了至关重要的作用。在后续章节中，我们将进行进一步的说明。CRC 的标准是多种多样的，由于生成多项式对检错性能起到了决定性的作用，一般是依据生成多项式的长度来区分的。例如：CRC-12 码，CRC-16 码，CRC-CCITT 等等。其中后两种是用来传送 8-b

29、it 字符串的，CRC-16 为美国所采用，CRC-CCITT 为欧洲国家所采用。CRC-32 则在大多数的通信传输中被采用。在以多项式长度分类的同时，随着时间的推移，人们不断的发现性能更好的计算多项式。使得 CRC 校验的检错能力不断的增强。比如一般情况下 CRC-12 有 12 种，CRC-16 有是 16 种，而 CRC-32 则有 6 种之多。以下为几种比较常见的生成多项式:CRC8 = X 8 + X 5 + X 4 +1CRC CCITT = X 16 + X 12 + X 5 +1CRC16 = X 16 + X 15 + X 5 +1CRC12 = X 12 + X 11 +

30、X 3 +X 2 +1CRC32 = X 32 + X 26 + X 23 + X 22 + X 16 + X 12 + X 11 + X 10 + X 8 + X 7 + X 5 + X 4 + X 2 + X +12.1.2CRC基于前面我们讲过的校验原理，我们本节主要介绍校验码的数学计算。CRC 校验码的计算是经过多项式除法而得到。完整的 CRC 校验码计算一共由以下几部分组成：（2）将 M(x)左移 K 位，得到 M(x) X (K 由预选的 K+1 位的生成多项式 G(x)（3）用一个预选好的 K+1 多项式 G(x)对 M(x) X 做模 2 的除法。第二章 CRC 校验数学背景及

31、发展概况9(1)二进制数据的多项式表达：我们将任何数据均可以写成一串由 0、1 组成的二进制的码流。用二进制码作为多项表达式的系数例如：1010111 可以表示成6 4 3 2 1制数的最高位，以下各位对应多项式的各幂次。X 的最高幂次为 R 的话，转化成对应的二进制数有 R+1 位。7一个长多项式、信息。7定，也就是一个二进制数，在整个传输过程中始终保持不变。生成多项式应该满足以下条件：a）生成多项式的最高位和最低位必须为 1。b)当被传输信息的任何一位发生错误时，被生成多项式做除后应使余数不为0。c)不同位发生错误时，应余数不同。d)对于余数继续做除法，应使余数循环。(4)CRC 生成器（

32、CRC Generator）：一个电路或者一种用于计算 CRC 校验值的软件算法。(5) CRC 累加器（CRC Accumulator）：CRC 余数和余数寄存器。CRC 的计算是一种模 2 的除法，与普通的除法主要的差别是在计算过程中减法，使用的不借位或者进位的模 2 加运算，也就是按位异或。二进制序列数据流，可以用 2 进制多项式表示，多项式的系数就是序列的值。如 101011 可以表示为：1 x5 + 0 x 4 + 1 x3 + 0 x 2 + 1 x + 1。下面我们以一个 CRC-3 的求法来说明CRC-3 生成过程来说明。生成多项式序列为 1011，我们做一个模 2 除法，即按

33、位的异或计算：（1）首先将数据序列左移 3 位：101011000（2）做按位异或：101011000101100011100010110000101001011000000010那么余数为 010,010+101011000 = 101011010 即传输码字为 x +x +x +x +x +1。多项式系数和二进制数一一对应：x 的最高幂次对应二进(2)信息段多项式 （Message Polynomial）：即信息本身，一个信息被理解为(3)生成多项式 （Generator Polynomial）：是数据接收方和发送方的一个约10基于 CRC 的多比特纠错算法研究与实现（3）假设在传输过程中

34、没有发生传输错误：那么我们对此码字继续按位异或101011010101100011101010110000101101011000000000可以看出在无误传输的情况下计算的结果为 0.与预计结果相符合。为了表达方便，接下来给出以多项式的形式证明：校验码具体实现步骤7：假设要传输的n位长度的二进制序列，表示为：n-1i=0使用的CRC生成多项式，记为：k 1i =0如果将二进制序列和生成多项式，进行下面的计算：k= Q( x) +G( x) G( x)(2-1)得到的R（x）就是 CRC校验码，它的长度应该是比生成多项式少一位，k在接收端，对数据进行校验就是将接收到数据和已定的CRC生成多项式

35、进行模 2 除，即：k= +G( x) G( x) G( x)根据式 2-1，可以得到：（2-2）M ( x) x k + R( x)G( x)R( x) R( x)G( x) G( x)R( x) + R( x)G( x)（2-3）M ( x)= mi xiG( x) = gi xiM ( x) x R( x)要发送的数据就是： M ( x) x + R( x) 。M ( x) x k + R( x) M ( x) x R( x)= Q( x) + + = Q( x) +第二章 CRC 校验数学背景及发展概况根据相同的序列按位异或的结果为 0，因此，式 2-3 的就可以化为：11M ( x)

36、 x k + R( x)G( x)= Q( x)（2-4）因此整个CRC计算过程就是将要发送的信息左移k位，然后将与生成多项式进行模 2 除法，等到的k位长的余数就是CRC校验信息。从中就可以看出，接收端计算的结果是整除的，没有余数，这也就是CRC在接收端判断数据是否正确的标准。另外还有一种校验方法，CRC被用于检查通信过程中产生的错误。传送数据期间, 发送器计算每数据块的CRC，每块发送出去以后, CRC也发送出去。接收器用同样的多项式去除接收到的信息段，如果收到的数据块没有错，则接收器计算的CRC和附加在信息段后的CRC保持一致。目前常用的CRC16 多项式包括 x16 + x12 + x

37、5 + 1以及 x16 + x15 + x5 + 1。前者为CCITT定义的CRC16 生成多项式，根据其系数将其记为 1021(最高位不记)；后者主要使用于X.25、GFP以及ATM封装定帧，记为 8005。下文所指的CRC16 多项式为 0x1021。针对 CRC16 实现，目前存在以下三种主要实现方法：逐比特计算法5、查表法6.8.10和并行计算法9，。下面我们将介绍经典的CRC-16 的校验算法。1.传统的 CRC 计算-逐比特计算法逐比特计算法就是根据CRC的多项式定义，采用除法硬件电路实现CRC计算，按照一组线性反馈移位寄存器和模 2 加单元完成硬件上的除法功能。这种方法实现简单、

38、容易理解，但是不能在高速前提下应用。下面以CRC-CCITT为例介绍传统的CRC计算，使用CRC-CCITT多项式（ x16 + x12 + x5 + 1x16+x12+x5+1即 1021H）的传统CRC硬件回路如图 2图 2.2 传统CRC硬件回路其硬件模拟算法如下：12基于 CRC 的多比特纠错算法研究与实现unsigned short crcCal(unsigned char *ucData,int iLen)unsigned char i;unsigned short crc=0x0;while(iLen-)for(i=0x80;i!=0;i=1)if(crc&0x8000)!=0)

39、crc=1;crc=0x1021;else crc=1;if(*ucData&i)!=0)crc=0x1021;ucData+;return(crc);在函数crcCal( )中, 无需给信息段补“0”字节，代码也比较简单，但需反复移位, “与”（AND）、“异或”(XOR) 运算都非常慢，因此，这种计算方法会影响数据传送的速度。2. 以字节处理的查表法计算 CRC根据图 2.1 可以看出, 当一个 8 位的信息字节加到 16 位的累加器中去时，只有累加器的高 8 位或低 8 位与数据位相“异或”而得到组合值，累加器中的新值为组合值加上累加器中未改变的那一半得到CRC值。因为只有 28 = 2

40、56 种可能的组合值,因此可以先计算好它们的CRC并存入一张表中, 这样便大大简化并加快了第二章 CRC 校验数学背景及发展概况13CRC的计算。可以利用函数crcCal( )计算合成值的CRC并存入表ucTable中。一个通用的建立查询表的函数如下：#define POLY 0x1021void crc_ucTable(unsigned short *ucTable)int i,j;unsigned short c;for(i = 0;i256;i+)c = (unsigned short) i;c =8;for(j=0;j15)=1)c = (c1)POLY;elsec = c1;ucTablei = c;而每次我们会先检查register的最高位是否为 1，如果为 1，则将生成多项式与register进行抑或操作。然后将register左移一位