托斯卡纳

The data communication technology is the basis of development of the Internet technology，and has became the necessary part of modern life．The purpose of communication is to transmit the timely and reliable information to the other side, thus requiring a communication system of transmissing information to be reliable and fast, it often is a paradox in a digital communication system. In order to solve the reliability, the communications system has all used the error control. Cyclic Redundancy check (CRC) code is recommended by International Telecommunications Organization , used in the digital communication system error control coding way (given several coding generator polynomial), they have been widely used by the people in the digital communication system. The CRC code belongs to the cyclic code, and cyclic code has the advantage of ease of using relatively simple circuits or software to achieve. Regarding CRC coding in all the general communication Theory textbooks or treatises,it has the simple introduction, but very rarely in-depth discussion.
In order to achieve the CRC quickly ,most of occasions use look-up table method to achieve the CRC. This paper has done the system research to the basic theory of CRC,and take the CRC-CCITT standard as example, with the way of constructing a single-byte form about the remainder at first , through looking up the table to produce many bytes CRC. And studied the ability of checking error with the software simulation . Research for the validation of the length of less than 16 burst error, all random odd error and two bit error, the rate of detecting error is 100% ;for a length of 17 burst error, the rate of detecting error is 99.9969%; a length of more than 18 unexpected errors, the rate of detecting error is 99.9985%.

KEY WORDS error control，CRC，look-up table method

目 录
摘要 I
ABSTRACT II
第一章 概 述 1
1.1 差错控制技术 1
1.1.1 信道编码 1
1.1.2 差错控制的方式 2
1.1.3 差错控制编码的方法 3
1.1.4 差错控制编码的分类 4
1.1.5 常用的几种简单分组码 4
1.2 线性分组码 6
1.2.1 汉明码的构造原理 6
1.2.2 线性分组码的一般原理 8
1.2.3 系统线性分组码的编码的方法 9
1.2.4 线性分组码的译码的方法 10
1.3 循环码 10
1.3.1 循环码原理 11
1.3.2 生成多项式的选取 13
1.3.3 循环码的编解码方法 14
1.4 课题设计的任务及安排 16
第二章 循环冗余校验CRC的基本理论研究 17
2.1 循环冗余校验CRC码 17
2.1.1 循环冗余校验CRC码 17
2.1.2 CRC校验原理分析 19
2.2 CRC编解码方法设计 19
2.2.1 编码方法设计 20
2.2.2 解码方法设计 21
第三章 CRC编解码的实现 22
3.1 硬件实现CRC 22
3.1.1 CRC码的编码电路设计 22
3.1.2 CRC码的译码电路设计 23
3.2 设计快速查表程序 23
3.2.1 按位求余式 24
3.2.2 快速查表法设计 26
3.2.3 余数表的设计 32
第四章 CRC检错性能的研究 35
4.1 关于研究检错能力的方法 35
4.2 CRC检错性能研究 35
4.2.1 检错性能分析 36
4.2.2 漏检错误概率分析 37
4.2.3 单比特错误纠正的原理和方法 39
4.3 程序仿真CRC的性能 40
4.3.1 检单比特错误仿真程序 40
4.3.2 检所有双错的仿真程序 42
4.3.3 检四位错的仿真程序 45
4.3.4 检突发错的仿真程序 47
第五章 设计总结 50
5.1 设计中存在的不足 50
5.2 总结与心得 50
结束语 51
参考文献 52
附 录 53
摘要
数据通信技术是计算机网络技术发展的基础，已经成为现代生活中必不可少的一部分。通信的目的是要把信息及时可靠地传送给对方，因此要求一个通信系统传输消息必须可靠与快速，在数字通信系统中可靠与快速往往是一对矛盾。为了解决可靠性，通信系统都采用了差错控制。循环冗余检错编码（CRC）是国际通信组织推荐的用于数字通信系统的差错控制编码方式（给出了几种编码的生成多项式），已被人们在数字通信系统中广泛地使用。CRC编码属于循环码，而循环码的优点是便于用比较简单的电路或软件来实现。对于CRC编码一般的通信原理教材或专著中都有简单的介绍，但是很少深入讨论。
为了快速实现CRC,大多数场合都用查表法来实现CRC校验码。本文对CRC的基本理论做了系统研究；以CRC-CCITT标准为例,用先离线构造单字节的余数表格的方法,通过查表生成多个字节的CRC，并且用软件仿真研究了CRC-CCITT的错误检测能力；研究验证了对于长度小于等于16位的突发错,所有奇数个随机错误和双错,检错率为100%；对于长度等于17位的突发错误,检错率为99.9969%；长度大于等于18位的突发错误,检错率为99.9985%。

关键词：差错控制，CRC，查表法

ABSTRACT

第一章 概 述
计算机网络是把分布在不同地理位置上的、自治的实体（用户应用程序、文件传送包、数据库管理系统、电子邮件设备、终端等）用数据通信线路连接起来利用通信协议进行通信，以实现整个系统的资源共享。在网络中交换信息，实体间必须建立数据通信线路，以便高效率而又准确地传输信息。在实际应用中，无论是远程数据通信线路还是局部数据通信线路，都不可避免地要受到各种干扰的影响，使接收端收到的信息与发送端发出的信息不一致，即接收端收到的信息产生了误码。
由信道中乘性干扰引起的码间串扰，通常可以采用均衡的方法纠正；而加性干扰的影响则要通过其他途径解决。为了降低数据通信线路传输的误码率，通常有改善数据通信线路传输质量和进行差错控制[1][2][3][4]两种方法。改善数据通信线路传输质量就是引入新的交换设备、新的数据通信线路、新的技术等。但是，这种方法由于受到经济上和技术上的限制，要想做到很低的误码率，花费代价大而收效甚微。实际上所有的计算机网络通信系统都采用差错检测控制，即承认数据通信线路传输信息的出错情况，有效地检测出错情况，并进行纠正，以此提高数据通信线路传输的质量。可见，差错控制的目的是使一个不可靠的通信链路变成一个可靠的链路。我们分析差错控制编码[1][2][3][4]的目的，正是为了寻求较好的编码方式，能在增加冗余不太多的前提下来实现检错和纠错。
差错检测控制的方法很多，有奇偶校验,行列冗余码校验法,反向循环等。然而这些方法仅仅能反映数据信息行、列奇偶情况,漏判的概率较高。循环冗余校验(CRC)码[1][2][5][6][7] 是由线性分组码[1][2][3][4][5][6][7]的分支而来，其主要应用是二元码组，编码和解码方法简单，检错和纠错能力强且误判概率很低，且其编码效率高，在通信领域广泛地用于实现差错控制。
1.1 差错控制技术
1.1.1 信道编码
在数字通信中，根据不同的目的，编码可分为信源编码和信道编码[1][2][3][4][5]。信源编码是为了提高数字信号的有效性以及为了使模拟信号数字化而采取的编码。信道编码是为了降低误码率，提高数字通信的可靠性而采取的编码。
数字信号在传输过程中，加性噪声、码间串扰等都会产生误码。为了提高系统的抗干扰性能，可以加大发射功率，降低接收设备本身的噪声，以及合理选择调制、解调方法等。此外，还可以采用信道编码技术。
差错控制随着差错控制编码理论的完善和数字电路技术的飞速发展，信道编码已经成功地应用于各种通信系统中，并且在计算机、磁记录与各种存储器中也得到日益广泛的应用。
1.1.2 差错控制的方式
差错控制方式基本上分为两类，一类称为”反馈纠错”，另一类称为”前向纠错”。在这两类基础上又派生出一种称为”混合纠错”。
 (1) 反馈纠错即检错重发(ARQ)
 这种方式在是发信端采用某种能发现一定程度传输差错的简单编码方法对所传信息进行编码，加入少量监督码元，在接收端则根据编码规则收到的编码信号进行检查，一旦检测出(发现)有错码时，即向发信端发出询问的信号，要求重发。发信端收到询问信号时，立即重发已发生传输差错的那部分发信息，直到正确收到为止。所谓发现差错是指在若干接收码元中知道有一个或一些是错的，但不一定知道错误的准确位置。这种方式的优点是译码设备简单，对突发错误和信道干扰较严重时有效，可达到良好的性能；缺点是需要双向信道，实时性差，主要在计算机数据通信中得到应用。系统构成如图1.1所示。

图1.1 检错重发(ARQ)

(2) 前向纠错(FEC)
 这种方式是发信端采用某种在解码时能纠正一定程度传输差错的较复杂的编码方法，使接收端在收到信码中不仅能发现错码，还能够纠正错码。采用前向纠错方式时，不需要反馈信道，也无需反复重发而延误传输时间，对实时传输有利，但是随着纠错能力的提高，编译码设备相对复杂。主要用于语音，广播，TV等通信。系统构成如图1.2所示。

图1.2 前向纠错(FEC)

(3) 混合纠错（HEC）
 混合纠错的方式是：少量纠错在接收端自动纠正，差错较严重，超出自行纠正能力时，就向发信端发出询问信号，要求重发。因此，”混合纠错”是”前向纠错”及”反馈纠错”两种方式的混合。具有自动纠错和检错重发的优点，可达到较低的误码率。较适合于环路延迟大的高速数据传输系统。系统构成如图1.3所示。

图1.3 混合纠错(HEC)

(4) 反馈检验（IRQ）
接收端将收到的信息原封不动的送回发送端并与原发送信码比较。如果发现错误，则发送端再进行重发。特点：需要双向信道、设备简单；可以纠正任何错误；引入较大的停顿（不实时）。

图1.4 反馈校验IRQ

因此，在传输过程误码率比较低时，用FEC方式比较理想。在传输过程误码率较高时，采用FEC容易出现”乱纠”现象。在许多数字通信中，广泛采用ARQ方式，此时的差错控制只需要检错功能。
1.1.3 差错控制编码的方法
差错控制编码的基本实现方法是在发送端将被传输的信息附上一些监督码元，这些多余的码元与信息码元之间以某种确定的规则相互关联（约束）。接收端按照既定的规则校验信息码元与监督码元之间的关系，一旦传输发生差错，则信息码元与监督码元的关系就受到破坏，从而接收端可以发现错误乃至纠正错误。因此，研究各种编码和译码方法是差错控制编码所要解决的问题。
1.1.4 差错控制编码的分类
根据差错控制编码的功能不同分为：检错码、纠错码、纠删码（兼检错、纠错）。检错码仅具备识别错码功能 而无纠正错码功能；纠错码不仅具备识别错码功能，同时具备纠正错码功能；纠删码则不仅具备识别错码和纠正错码的功能，而且当错码超过纠正范围时可把无法纠错的信息删除。
根据信息位和校验位的关系分为：线性码和非线性码。如果两者呈线性关系，即满足一组线性方程式，就称为线性码；否则，两者关系不能用线性方程式来描述， 就称为非线性码。
根据信息码元和监督码元的约束关系分为：分组码和卷积码。分组码是将k个信息比特编成n个比特的码字，共有 个码字。所有 个码字组成一个分组码。传输时前后码字之间毫无关系。
1.1.5 常用的几种简单分组码
1. 奇偶监督码
奇偶校验码是分组码（n，k）中当k＝n－1时的一个特例，即可以表示成为（n，n-1）。如果是奇监督码，在附加上一个监督元以后，码长为n的码字中”1″的个数为奇数个；如果是偶监督码，在附加上一个监督元以后，码长为n的码字中”1″的个数为偶数个。一般地由监督位构成的奇偶检验条件为
（1.1）
… 是（n－1）个信息位， 是一个监督位。
奇偶监督码具有较高的编码效率:R=(n-1)/n，且随n的增加而趋于1。它能检测出所有奇数个差错，而不能检出偶数个差错。
2. 行列监督码
行列监督码又称二维奇偶监督码，有时还被称为矩阵码。它不仅对水平（行）方向的码元，而且还对垂直（列）方向的码元实施奇偶监督。例如要发送的信息序列为11001010000100001101011110000110011100001010101010，现将每10个信息码元分为一组，然后编成方阵，按行、列分别加上监督码元，则再发送端可构成如图所示的方阵。它的各行和各列对l的数目都实行偶数监督。可以逐行传输，也可以逐列传输。译码时分别检查各行、各列的监督关系，判断是否有错。

图1.5 矩阵码

二维奇偶监督码适于检测突发错码。二维奇偶监督码不仅可用来检错，还可用来纠正一些错码。
3. 恒比码
恒比码又称等重码，该码的码字中1和0的位数保持恒定的比例。目前我国电传通信中普遍采用3：2码，该码共有 个许用码字，用来传送10个阿拉伯数字，如表8-3所示。这种码又称为5中取3数字保护码。因为每个汉字是以四位十进制数来代表的，所以提高十进制数字传输的可靠性，就等于提高汉字传输的可靠性。实践证明，采用这种码后，我国汉字电报的差错串大为降低。

表1.1 3:2数字保护码
数字 码字
0 0 1 1 0 1
1 0 1 0 1 1
2 1 1 0 0 1
3 1 0 1 1 0
4 1 1 0 1 0
5 0 0 1 1 1
6 1 0 1 0 1
7 1 1 1 0 0
8 0 1 1 1 0
9 1 0 0 1 1

目前国际上通用的ARQ电报通信系统中，采用3：4码即7中取3码，这种码共有 个许用码字，93个禁用码字。35个许用码字用来代表不同的字母和符号。实践证明，应用这种码，使国际电报通信的误码率保持在 以下。
1.2 线性分组码
分组码是一组固定长度的码组，可表示为（n , k），通常它用于前向纠错。在分组码中，监督位被加到信息位之后，形成新的码。在编码时，k个信息位被编为n位码组长度，而n-k个监督位的作用就是实现检错与纠错。当分组码的信息码元与监督码元之间的关系为线性关系时，这种分组码就称为线性分组码。
对于长度为n的二进制线性分组码，它有 种可能的码组，从 种码组中，可以选择 个码组（k<n）组成一种码。这样，一个k比特信息的线性分组码可以映射到一个长度为n码组上，该码组是从 个码组构成的码集中选出来的，这样剩下的码组就可以对这个分组码进行检错或纠错。
线性分组码是建立在代数群论基础之上的，各许用码的集合构成了代数学中的群，它们的性质有：全零字总是一个码字；任意两个码字的和（对于二进制码这个和的含义是模二和）仍是该分组码的码字，也就是说，线性分组码具有封闭性；最小码距等于任何非零码字的最小汉明重量；编码效率为 。
对偶校验时的监督关系。在接收端解码时，是由模2加建立监督关系的监督方程来完成，即实际上就是在计算：
（1.2）
若S＝0，则无错；若S＝1就认为有错。
线性分组码的码率 , R越大，有效性越高。当监督码的长度r给定后，要纠正≤e个错误，则码长n与r之间必须满足约束关系：当e=1时，有n ≤ -1。当r给定时，n越大，R越小，即该分组码的有效性越高，因而，在保证e=1的纠错能力时，n = -1的码有效性最高，这种码就称为汉明码，是分组码中的高效码。
1.2.1 汉明码的构造原理
汉明码是一种能够纠正一位错码且编码效率较高的线性分组码。偶数监督码的一位监督位和信息位构成一个代数式，
（1.3）
在接收端计算
（1.4）

监督关系式，S称为校正子。
1. r与n的关系
(1) 一位S的取值只有这样两种，只能代表有错和无错，不能指出错码的位置。
(2) 两个校正子的可能值有4种不同信息。若用其一表示无错，则其余3种用来指示一位错码的3种不同位置。
(3) r个监督关系式,能指示一位错码的 -1个可能位置。
（1.5）
2. 如何具体构造这些监督关系式
设分组码(n,k)中k = 4.
为了纠正一位错码。监督位数r≥3,取 r＝3，则 n＝k＋r＝7。规定校正子的值与错码位置的对应关系如下：
表1.2 校正子的值与错码位置的对应关系

错码位置
001

010

100

011

101

110

111

000 无错
由表中规定可见
(1) 仅当一错码位置在 , , 或 时，校正子 =1；否则 =0.
（1.6）
(2) 仅当一错码位置在 , , 或 时，校正子 =1；否则 =0
（1.7）
(3) 仅当一错码位置在 , , 或 时，校正子 =1；否则 =0
（1.8）
3. 发送端编码
监督位应根据信息位的取值按监督关系来确定，即监督位应使 , , 的值为零（表示编成的码组中应无错码）

（1.9）

由上式经移项运算，解出监督位

（1.10）

信息位与监督位的对应关系如表1.2所示。

表1.3 信息位与监督位的对应关系
信息位 监督位 信息位 监督位

0000 000 1000 111
0001 011 1001 100
0010 101 1010 010
0011 110 1011 001
0100 110 1100 001
0101 101 1101 010
0110 011 1110 100
0111 000 1111 111

若接收码组为0000011，计算可得校正子

（1.11）

由表1.2可知在 位有一错码。
线性分组码满足封闭性。表1.3中所列的(7,4)汉明码的最小码距 =3，能纠正一个错码或检测两个错码。
1.2.2 线性分组码的一般原理
式(1.8)可改写为

（1.12）

将上式写成矩阵形式后，为
（1.13）
简记为
（1.14）
其中

（1.15）
（1.16）
（1.17）
将[H]称为监督矩阵。[H]的行数就是监督位的数目r。[H]是r×n矩阵.
1.2.3 系统线性分组码的编码的方法
利用矩阵分块方法有

（1.18）

式中

（1.19）
（1.20）

具有[PIr]形式的[H]称为典型监督矩阵。
式(1.9)改写成

（1.21）

（1.22）
（1.23）
码的生成矩阵

（1.24）

由生成矩阵产生整个码组
（1.25）
具有[IkQ]形式的[G]称为典型生成矩阵。典型生成矩阵得出的码组[A]为系统码。要求[G]矩阵的k行是线性无关的。任一码组[A]都是[G]的各行的线性组合。可组合出2k种不同的码组[A]，恰是有k位信息位的全部码组。
1.2.4 线性分组码的译码的方法
线性分组码(n,k)发送的码组为
（1.26）
接收码组为
（1.27）
发送码组和接收码组之差为
（1.28）
则传输中产生的错码行矩阵(错误图样)
（1.29）

（1.30）
（1.31）
校正子
（1.32）
若[S]和[E]之间一一对应，则[S]将能代表错码的位置。
1.3 循环码
循环码[1][2][3][4][5][6][7]是线性分组码的一个重要子集，是目前研究得比较成熟的一类码。它的编译码设备比较简单，用具有反馈的一位寄存器就可实现。它的检纠错能力也较强，所以在实现差错控制中已得到广泛应用。
循环码的结构完全建立在有限域基础上，具有以下两个特点：一是码的编码电路及伴随式计算电路非常简单，易于用移位寄存器电路实现；二是循环码的代数结构具有很多有用的性质，易于找到有效的译码方法，并且目前已发现的大部分线性码与循环码有密切关系。正是循环码具有码的代数结构清晰、性能较好、编译码简单和易于实现等特点，因此目前在实际的计算机纠错系统中使用的线性分组码，几乎都是循环码。
1.3.1 循环码原理
循环码除具有线性码的一般性质外,还具有循环性,即循环码中任一码组循环一位以后,仍为该码中的一个码组。
在表1.4中给出一种（7，3）循环码的全部码组。由此表可以直观地看出这种码的循环性。
表1.4 一种（7，3）循环码
码组编号 信息位 监督位 码组编号 信息位 监督位

1 000 0000 5 100 1011
2 001 0111 6 101 1100
3 010 1110 7 110 0101
4 011 1001 8 111 0010

一长为n的码组可表示成码多项式
（1.33）
1. 码多项式的按模运算
若
F(x) = N(x) Q(x) + R(x) （1.34）
则
F(x) ≡ R(x) ( 模 N(x) ) （1.35）
例：
（1.36）
因为

在循环码中,若 C(x)是一个长为n的许用码组,则xi C(x)在按模xn +1运算下,也是一个许用码组.即若
（1.37）
则C′(x)也是一个许用码组。
证明：设
（1.38）
则
（1.39）

所以这时有
（1.40）
还是一个许用码组。
的码组向左循环移位i次的结果。例如表1.4中循环码
（1.41）
，则
（1.42）

对应的码组为0101110，正是第3码组。
2．循环码的生成矩阵
在(n,k)循环码中，用g(x)表示其中前k - 1位皆为 “0″的码组.g(x)唯一的次数为(n - k)次,必须是一个常数项不为”0″多项式.称这唯一的(n - k)次多项式g(x)为码的生成多项式。一旦确定了g(x) ，则整个(n,k)循环码就被确定了。
g(x) ，x g(x) ， g(x) ，…， g(x)是k个线性无关的码组.
循环码的生成矩阵[G]可以写成
（1.43）
[例]表1.4所给出的循环码中,对应的生成多项式为 。代入上式，得

（1.44）

或
可以写出此循环码组，即
（1.45）
所有码多项式C(x) 都可被g(x)整除，且任一次数不大于(k-1) 的多项式乘g(x)都是码多项式。
1.3.2 生成多项式的选取
并不是任何一个多项式都可以作为生成多项式的，因为在循环码中除全”0″码组外，再没有连续k位均为”0″的码组，即连”0″的长度最多只能有（k－1）位，否则，再经过若干次循环移位后将得到一个k位信息位全为”0″，但监督位不为”0″的码组，这在线性码中显然是不可能的。因此G(x)必须是一个常数项不为”0″的（n－k）次多项式，即最高位和最低位必须都是1。
如果余数为0，就不能检测错误，即会出现漏检。
当不同位发生错误时，根据余数不同可以纠正一位错误。
余数作为冗余位，和信息码共同组成CRC码，由CRC码定义知，它应该满足循环规律的。
从检错与纠错的要求出发，由上面分析可知，生成多项式应能满足下列要求：生成多项式的最高位和最低位必须为1；任何一位发生错误都应使余数不为0；不同位发生错误应当使余数不同；应满足余数循环规律。
假定A(X)为一CRC循环冗余码，因为 是A(X)代表的码组向左循环移位i次的结果，所以 也必为该码中一个码组。因此可以得出结论：
在CRC码中，若A(x)是一个长为n的许用码组，则 在按模 运算下亦是一个许用码组，即若
（模 ） （1.46）
则 也是一个许用码组。
由上面的分析可见，一个长为n的CRC码，它必为按模（ ）运算的一个余式。
另外，任一CRC码A(X)都是G(X)的倍式，故可以写成
（1.47）
而生成多项式G(X)本身就是一个码组，即有
（1.48）
由于码组 为一（n－k）次多项式，故 为一n次多项式。由上面可知 在模（ ）运算下亦为一码组，故可以写成
（1.49）
上式左端分子和分母都是n次多项式，故商式Q(x)＝1，因此上式可化成
（1.50）
代入并化简得
（1.51）
上式表明，生成多项式G(X)应该式 的一个因式，即g(x)是 的一个(n-k)次因式。
例如 ( )可以分解为
（1.52）
为了求(7,3)循环码的生成多项式g(x)，要找到一个(n-k)=4次的因子即有
（1.53）
（1.54）
选用的生成多项式不同，产生出的循环码码组也不同。
循环码是一种重要的线性码，它有三个主要数学特征：循环码具有循环性，即循环码中任一码组循环一位(将最右端的码移至左端)以后，仍为该码中的一个码组；循环码组中任两个码组之和(模2)必定为该码组集合中的一个码组；循环码每个码组中，各码元之间还存在一个循环依赖关系。
循环码的每个码多项式 ，都是 的倍式；对系统码来说，就是已知信息多项式 ，求 被 除以以后的余式 。所以循环码的编码器就是 乘 的乘法器，或者是 的除法电路。它们均可以用移位寄存器实现。
1.3.3 循环码的编解码方法
1. 系统循环码的编码方法
(n,k)循环码的信息码多项式为M(x), M(x)次数小于k.由上述原理可归纳编码步骤为：
(1)用 乘M(x)。
(2)用 除 M(x) ，得到商Q (x)和余式R(x)，即

（1.55）
(3)编出的码组C(x)为
（1.56）
例如： (7,3)循环码,信息码为110，生成多项式为 ，信息码多项式为 ,移位后有 ，用G(x)除有

（1.57）
余式为
（1.58）
因此编出的码组为
（1.59）
在用硬件实现时，可以由除法电路来实现。
例： (7,3)循环码,生成多项式为

图1.6 (7,3)循环码编码电路

2．循环码的解码方法
在接收端可以将接收码组T(x)用原生成多项式去除，即
（1.60）

若余式 传输中未发生错误，则发送码组为

图1.7 循环码译码电路框图
1.4 课题设计的任务及安排
本课题要求：
(1) 对CRC编码的基本理论进行研究；
(2) 完成至少一种CRC码的软件编程（使用查表方法）；
(3) 通过软件仿真对CRC编码的错误检测能力进行研究。
针对任务要求，本文完成了各项任务，并分了几个部分进行阐述。在第一章中，引用了文献中和CRC的有关概念，并对其应用和目前国内外发展现状做了简要说明。第二章是对CRC编解码原理、检错原理等基本理论进行了研究。第三章介绍了CRC的实现方法，其中分硬件设计和软件设计进行实现，文中着重研究CRC查表算法[13]及用C语言[8]实现CRC－CCITT编码、译码和生成表的设计，设计了一种快速的CRC生成算法。第四章详细分析了CRC检错能力，用理论证明和程序仿真两种研究方法对CRC的检错能力进行深入的研究，得出了可靠的结论。第五章主要是对此次设计的总结，分析设计中存在的不足和需要改进的地方，以及收获和心得。

第二章 循环冗余校验CRC的基本理论研究
循环冗余校验CRC的全称为Cyclic Redundancy Check。CRC在本质上一种缩短循环码，是分组码的一种特例，同时由于编码后的前k位是信息，所以是一种系统循环码。由于CRC是几种特别生成多项式的循环码，所以具有循环码的所有性质，因此对CRC码的研究就是对循环码研究进行拓展。
CRC编码和解码方法简单，检错和纠错能力强且误判概率很低，在通信领域广泛地用于实现差错控制。
2.1 循环冗余校验CRC码
2.1.1 循环冗余校验CRC码
CRC校验码实际上是由原始数据位串和紧跟其后的与G(x)位串少一位的冗余位串组成,只要求出此位串,发送方即可将原始数据和冗余位串装配成一CRC位串序列后再发送。CRC校验码译码非常简单,只需从接收到的正确CRC校验码尾部截掉与G(x)位串等长冗余位串,余下的部分即为原始数据位串。CRC校验码错误检测按模2除法运算,用接收到的CRC位串除以G(x)位串,看是否能够除尽即可确定。
CRC校验码的基本思想是利用线性编码理论，在发送端根据要传送的k位二进制码序列，以一定的规则产生一个校验用的监督码r位，并附在信息后边，构成一个新的二进制码序列数共(k+r)位，最后发送出去。在接收端，则根据信息码和冗余码之间所遵循的规则进行检验，以确定传送中是否出错。接收方将接收到的二进制序列数（包括信息码和冗余码）除以多项式，如果余数为0，则说明传输中无错误发生，否则说明传输有误。用软件计算CRC码时，接收方可以将接收到的信息码求冗余码，比较结果和接收到的冗余码是否相同。
CRC的本质是模-2除法[5][6][7][9][10]的余数，采用的除数不同，CRC的类型也就不一样。通常，CRC的除数用生成多项式来表示。最常用的CRC码的生成多项式有CRC16,CRC－CCITT。求CRC码所采用模2加减运算法则，既是不带进位和借位的按位加减，这种加减运算实际上就是逻辑上的异或运算，加法和减法等价，乘法和除法运算与普通代数式的乘除法运算是一样，符合同样的规律。
CRC是一种高性能的检错码,广泛应用在计算机数据存储、数字程控交换机PCM 数据的传输,嵌入式系统数据传输等场合。
CCITT建议：2048 kbit/s的PCM基群设备采用CRC-4方案，使用的CRC校验码生成多项式 = 。采用16位CRC校验，可以保证在 bit码元中只含有一位未被检测出的错误 。在IBM的同步数据链路控制规程SDLC的帧校验序列FCS中，使用CRC-16，其生成多项式 = ；而在CCITT推荐的高级数据链路控制规程HDLC的帧校验序列FCS中，使用CCITT-16，其生成多项式 = 。CRC-32的生成多项式 。CRC-32出错的概率比CRC-16低16倍 。由于CRC-32的可靠性，把CRC-32用于重要数据传输十分合适，所以在通信、计算机等领域运用十分广泛。在一些UART通信控制芯片（如MC6582、Intel8273和Z80-SIO）内，都采用了CRC校验码进行差错控制；以太网卡芯片、MPEG解码芯片中，也采用CRC-32进行差错控制。CRC校验在医学仪器数据通讯中也得到了广泛的应用。
ARJ、LHA等压缩工具软件采用的是CRC32，磁盘驱动器的读写采用了CRC16，通用的图像存储格式GIF、TIFF等也都用CRC作为检错手段。
目前CRC的使用分为标准和非标准两种，非标准为用户自定义CRC的生成多项式，而标准是已被国际标准化组织规定的标准生成多项式，这也是目前广泛使用的几种。CRC一12码通常用来传送6-bit字符串。CRC一16及CRC-CCITT码则用是来传送8一bit字符，其中CRC一16为美国采用，而CRC-CCITT为欧洲国家所采用。CRC一32码大都被采用在一种称为Point-to-Point的同步传输中。
在通信协议中常见并被广泛使用的标准列于表2.1中。多项式为奇数个非零项的虽然在有些文献中给出，在标准中也有应用，但是由第四章研究发现，这样的多项式是不具备检所有奇数个错误的性能的，具体说明见第四章。

表2.1 在通信协议中常见并被广泛使用的标准
名称 多项式 简记 应用
CRC－4
0×3 ITU G.704
CRC－16
0×8005 IBM SDLC
CRC－CCITT
0×1021 ISO HDLC,ITU X.25,SDLC,V.34/V.41/V.42,
PPP-FCS
CRC－32

0×04C11DB7 ZIP,RAR,IEEE 802 LAN/FDDI,IEEE1394, PPP-FCS
注：最高位都一定是1，在简记中都省略了最高位。
非标准的CRC一般是为了某种用途而采用不同于标准的生成多项式，而实际的操作原理是相同的，主要用于需要CRC而需要低成本的应用，或者为了减轻计算机处理负担而又能够保证数据可靠性的折中办法，此外，部分的加密算法也是用CRC来生成。
2.1.2 CRC校验原理分析
CRC校验原理实际上就是在一个k位二进制数据序列之后附加一个r位二进制校验码序列，从而构成一个总长为n=k+r位的二进制序列，例如，k位二进制数据序列 ，r位二进制校验码 ；所得到的这个n位二进制序列就是 ；附加在数据序列之后的这个校验码R与数据序列M的内容之间存在着某种特定的关系。如果因干扰等原因使数据序列中的某一位或某些位发生错误，这种特定关系就会被破坏，因此通过检查这一关系，就可以实现对数据正确性的校验。这一关系，在差错控制理论中称为”生成多项式”。因此可以做如下推导：设
（2.1）
为商式， 为余式，两边同时加余式 后有：
（2.2）
令
（2.3）
显然
（2.4）
即发送编码多项式可以被生成多项式整除。如果传输中没有错误则
（2.5）
应有
（2.6）
很明显如果信息传输的过程中没有发生错误，则接收到的信息多项式一定可以被生成多项式整除，这就是CRC的检错原理。
值得注意的是这一命题的逆命题并不成立，也就是说接收到的信息多项式可以被生成多项式整除，并不代表信息在传输中没有发生错误，第四章将会对这一问题详细分析。
2.2 CRC编解码方法设计
CRC在本质上一种缩短循环码，是分组码的一种特例，同时由于编码后的前k位是信息，所以是一种系统循环码。因此当n小于 -1时，除了具有循环码的循环性外具有分组码和循环码的全部特性：
(1) (n，k)循环码构成n维线性空间的一个k维子空间，在长度为n的 个码组中仅有 个码组属于码空间；
(2) 任意两个码字的和仍然是一个码字；
(3) 码的最小距离等于非零码的最小重量。
CRC校验采用多项式编码，一个二进制位串可以用一个系数为0和1的单变量多项式来表示。例如10010001可表示为 。设有一个K位的信息位串，对应于多项式M(x)，那么它的CRC码的计算方法是:用一个事先约定的r次的生成多项式G(x)作除数，把在信息位串尾添上r个0所构成的新位串对应的多项式 作为被除数，两者作模2除法，最后得到的r位余数是冗余码，将这r位冗余码加在原来的信息位串的尾部后便构成了一个k十r位的CRC码。在校验时，用同样的生成多项式G(x)直接去除，若除尽，说明数据传输正确，把接收到的k+r位的二进制序列去掉尾部r位，即得所需的k位数据信息;若不能除尽，则说明一定有传输错误需要进行相应的纠错处理。图2.1为信息代码结构。
n位
k位 r位

M(x) R(x)
新的信息代码多项式 校验位
图2.1 信息代码结构
2.2.1 编码方法设计
根据CRC校验原理及循环码编码方法，可以设计下面CRC编码方法：
(1) 将被校验数据的k位有效信息M(x)左移r位，得 。这样做的目的是空出r位，以便拼装将来求得的r位余数。
(2) 选取一个r+1位的生成多项式 ,对 作模2除法
(模2除) （2.7）
要产生r位余数，所以生成多项式G(x)应为r+1位。
(3) 将左移r位的待编有效信息与余数R(x)作模2加（减），即拼接为循环校验码。输出码多项式为
（2.8）
在按位运算中，模2加法与模2减法的结果是一致的，所以有
- = + （2.9）
所以由公式（2.1）有
+ （模2加） （2.10）
因此有
（2.11）
的末尾r位是0，所以与余数R(x)的加、减实际上就是将M(x)与R(x)相拼接。拼接成的校验码必定能为约定的G(x)所除尽。
2.2.2 解码方法设计
译码与纠错将收到的循环校验码，将收到的编码用生成多项式去除,若码字无误则余数为0。即若
（2.12）
则说明传输中没有错误。否则，传输中出错。
如果某一位出错，余数不为0,通过查表可以确定出错位。若多位出错则要求重发。CRC校验可用于检错、纠错或检纠错,但不论用途如何,如果校验码(余数)求出,只需简单的判断便可进行检错或纠错。显然，它也可以像发送端一样，在全部m + r后再增加r个0，再除以生成多项式，如果没有差错发生，余数仍然为0。

第三章 CRC编解码的实现
根据具体情况（如需校验的数据速率、CPU 的负荷及处理能力），循环冗余校验CRC可以采用硬件方法实现，也可以采用软件方法实现。对于某些不宜用硬件实现CRC校验而又需要用CRC校验码进行差错控制的系统中，或者对于那些采用软件方法不至于严重影响CPU 响应时间的校验可通过软件实现编码、检错和译码功能，这种实现方法不增加新硬件，减少了硬件成本，降低了硬件设计复杂度。当然，采用这种方法实现的前提是实现算法要合理，校验速度要足够快。
3.1 硬件实现CRC
CRC硬件电路简单，目前已有自动生成CRC码的中规模集成电路。应用这种硬件电路时,软件无需考虑CRC的生成、译码问题,具有速度快的特点。
3.1.1 CRC码的编码电路设计
在硬件实现时，设计CRC码的编码电路，其实就是设计循环码编码电路，由前两章的分析可知，可以由除法电路来实现，除法电路的主体由一些移位寄存器和模2加法器组成，下面举例来设计编码电路。
信息码为xxxx，生成多项式为 的CRC-4编码电路如图3.1所示。

图3.1 CRC-4编码电路

一开始时移位寄存器 中都清成”0″，信息位由该输入端从高位至低位逐位输入，在从码字输出端输出的同时，又进入编码电路，经过k次移位后，在编码电路的移位寄存器中得到的就是r位冗余位，再经过r次移位，所产生的r位冗余位也就从码字输出端紧接在信息位后面输出了。与门的作用是只传前四个有效位，无需传后四个0。
3.1.2 CRC码的译码电路设计
由于任一码组多项式S(x)都应能被生成多项式G(x)整除，所以在接收端可以将接收码组T(x)用原生成多项式G(x)去除。当传输中未发生错误时，接收码组与发送码组相同，即 ，故接收码组T(x)必定能被G(x)整除；若码组在传输中发生错误，则 ，T(x)被G(x)除时可能除不尽而有余项，即有
（3.1）
因此我们就以余式是否为0来判别码组中有无错码。根据这一原理可以构成如图3.2所示的解码器。

图3.2 CRC－4译码电路

由图可见，解码器的核心就是一个除法电路和缓冲移存器，而且这里的除法电路与发送端编码器中的除法电路相同。若在次除法器中进行 的运算的结果，余项为零，则认为码组R(x)无错，这是就将暂存与缓冲移存器中的接收码组送出到解码器输出端；若运算结果余项不为零，则认为R(x)中有错，但错在何位不知，这时就可以将缓冲移存器中的接收码组删除，并向发送端发出一重发指令，要求重发一次该码组。
3.2 设计快速查表程序
在有些场合, 在不具备硬件CRC编、译码电路的情况下,或者要求设备有更小的体积,更低的成本,并且由于任何硬件系统的寄存器资源都是有限的,所以选取一个数十位、甚至数百位宽度的寄存器实现除法运算是不可行的。这时, 可以选一个宽度为r位(生成多项式的次数)的寄存器,采用反馈的方法实现n位(信息位宽度与校验位宽度之和)除法运算。因为模2运算恰好等价于异或运算。用软件实现CRC码的生成校验更为合理。为了能够提高检错能力,当需要采用CRC方式时,就要用软件实现CRC检错码。本文提出一种查表实现CRC码的编程方法,具有程序结构紧凑、简洁的特点。
由公式（2.15） 可知，求CRC码的过程就是求余数的过程。软件实现的方法大致有两种，一种是模拟硬件长除法，另一种是查表法。模拟硬件长除法就是依据CRC校验码的产生原理来设计程序。其优点是模块代码少，修改灵活，可移植性好；其缺点为计算量大。算法的依据和多项式除法性质有关。如果一个m位的多项式 除以一个r阶的生成多项式G(x)，将每一位 （0=<k<m）提出来，在后面补r个0后，单独去除G(x)，得到的余式为 。则将 后得到的就是M(x)由生成多项式G(x)得到的余式。
下面从CRC原理出发根据按位计算法导出最常用的CRC－CCITT查表法。
3.2.1 按位求余式
由编码方法可以写出以下步骤：
(1)置寄存器初值为0。
(2)寄存器进行左移运算,下一个信息位移入,最高位移出。
(3)判断第(2)步中移出的最高位,如果为1,则用寄存器与生成多项式的低r位异或的结果对寄存器重新赋值。否则,执行(4)。
(4)如果还有信息位(包括附加的r个0),返回(2),否则结束。
(5)最终该寄存器中的值去掉最高一位就是我们所要求的余数。
所以可以将上述步骤用下面的流程描述：
把reg中的值置0。
把原始的数据后添加16个0。
While (数据未处理完)
Begin
If (移出reg位是1)
reg = reg XOR 0×1021
把reg中的值左移一位，读入一个新的数据并置于reg的0 bit的位置
End
reg的后16位就是我们所要求的余数。
程序流程图如图3.3所示。
图3.3 逐位求余数的流程图

*ptr 指向发送缓冲区的首字节，len 是要发送的总字节数，0×1021 与多项式有关。
逐位求余数的主要代码如下：
unsigned int cal_crc(unsigned char *ptr, unsigned char len)
{
unsigned int reg=0; /*对存储余式的内存空间进行初始化*/
reg＝reg<<1；
while(len–!=0) /*判断数据是否结束*/
{
if((reg&0×8000)!=0) /*判断高位是否为1*/
{reg<<=1; reg^=0×1021;} /* 余式CRC左移再异或求余式 */
else reg<<1;
ptr++;
}
return(reg);
}
这种算法简单，容易实现，所占用的内存比较少，对任意长度生成多项式的G(x)都适用。在发送的数据不长的情况下可以使用。但是如果发送的数据块很长的话，或是在高速通讯的场合，这种方法就不太适合了。它一次只能处理一位数据，效率太低，占用很多的处理器处理时间。为了提高处理效率，可以一次处理4位、8位、16位、32位。由于处理器的结构基本上都支持8位数据的处理，所以一次处理8位比较合适。
为了对导出的算法有一种直观的了解，先将上面的算法换个角度表示。在上面例子中，可以将编码过程等价为如下过程：
由于最后只需要余数，所以我们只看后16位。构造一个16位的寄存器reg，初值为0，数据依次移入reg0（reg的0位），同时reg15的数据移出reg。由上面的算法可以知道，只有当移出的数据为1时，reg才和G(x)进行XOR运算；移出的数据为0时，reg不与G(x)进行XOR运算，相当与和0000 0000 0000 0000进行XOR运算。就是说，reg和什么样的数据进行XOR移出的数据决定。由于只有一个bit，所以有 种选择。上述算法可以描述如下，
//reg是一个16bits的寄存器
初始化t[]={0001 0000 0010 0001,0000 0000 0000 0000}
把reg中的值置0.
把原始的数据后添加16个0.
While (数据未处理完)
Begin
把reg中的值左移一位，读入一个新的数据并置于reg的0 bit的位置。
reg = reg XOR t[移出的位]
End
3.2.2 快速查表法设计
上面算法是以bit为单位进行处理的，为了提高编码和解码的速度,考虑将上述简明方法中每次处理一位改为每次处理8位，即以Byte为单位进行处理。构造一个两个Byte的寄存器reg，初值为0×0000，数据依次移入reg0（reg的0字节，以下类似），同时reg1的数据移出reg。用上面的算法类推可知，移出的数据字节决定reg和什么样的数据进行XOR。由于有8个bit，所以有 种选择。上述算法可以描述如下：
//reg是一个2 Byte的寄存器
初始化t[]＝{…}//共有 ＝256项，每项两个字节
把reg中的值置0.
把原始的数据后添加2个0字节.
While (数据未处理完)
Begin
把reg中的值左移一个字节，读入一个新的字节并置于reg的第0个byte的位置。
reg = reg XOR t[移出的字节]
End
重复上述的由高至低的移位8次，第一个8-bit数据处理完毕，用此时寄存器的值与下一个8-bit数据异或并进行如前一个数据似的8次移位。所有的字符处理完成后寄存器内的值即为余数值。

图3.4 按字节求余数的流程图

不难看出,经过8次循环后,寄存器中的最高位是由寄存器8次循环前的高8位数据和生成多项式决定的,即8次循环后,生成多项式与寄存器是否异或,仅由循环前寄存器的高8位数据和生成多项式决定。所以,若8次循环后的异或运算结果result已经计算出来,则将寄存器中的数据左移8位后再与result异或,得到的结果和采用直接实现方法逐位处理的结果是一致的。因此,可提前计算出8次循环后的异或运算结果,将其存于表中,并用寄存器的高8位作为索引值,从而可将上述的8次循环简化为一次查表运算和一次异或运算。
由于索引值为8位,所以表长为256，本文采用CRC-CCITT,查找表的每个单元就是16位,故为512字节。在设计CRC算法时，预先开辟存放512字节的缓冲区存放参数表，令不同的变量存放余数和中间结果。依次取数据包中数据的每一个字节，从参数表中查到它的参数值1。本字节异或上一字节经校验后的低8位，再异或本字节找出的高8位得到结果1，把结果1送高8位字节。本字节找出的低八位值异或上一字节经校验后的高8位值得到结果2，把结果2送低8位字节。上一字节经校验的低8位，再从参数表中找出其参数值2。把结果1、结果2和参数值2异或后，作为该字节的校验码。直到此数据包数据被校验完，得到一个CRC码。这样,可将寄存器中的每个字节看做直接实现方法中的一位。
对于CRC-CCITT，可以将每个字节在后面补上16个0后与生成多项式进行运算，得到余式和此字节唯一对应，这个余式就是上面算法中t[]中的值，由于一个字节有8位，所以t[]共有 ＝256项。这种算法每次处理一个字节，通过查表法进行运算，大大提高了处理速度，故为大多数应用所采用。
综上分析，快速生成余式 的步骤为：
(1) 查余式表得出数据的第一字节 的余式高字节 和低字节 ；
(2) 将数据的第二字节 和 进行异或处理，从余式表中查出异或结果的余式 和 ；
(3) 将 和 进行异或处理，其结果作为余式数据 ；
(4) 重复(2)和(3)，直至求出余式数据 和 ；
(5) 组成如图3.5所示的发送序列。

…

图3.5 CRC码结构示意图

快速生成余式的过程如图3.6所示：

图3.6 求解余式示意图
以两个字节的数据求CRC的例子来说明导出的快速查表实现过程。随机取一个数据0×0102，可以看出，CRC差错校验码标准编码过程需要15次移位，4次异或，还不算判断时间，整个过程如图3.8所示：
图3.8 0×0102 CRC一般编码过程图示

用上文导出的方法有以下步骤：
(1) 对 =0×01，查表得出 和 分别为0×10和0×21；
(2) ，再查表得0×12的 、 分别为0×32和0×73；
(3) ； ＝0×73；
(4) 由信息码和余式组成的序列0×01021373即为CRC码。
尽管此例仅以2字节部分数据值CRC差错校验过程给出运算比较，但可以看出在完成同样任务的前提下，该方法只用了两次查表，两次异或运算。对于8q(q为信息数据流M(x)的字节计数长度)比特的信息数据流，标准模2除法过程中，其移位次数是固定的，总共要移位8q-1次，异或运算次数是个不固定数，而本文提供的方法只需q次异或，q次查表，对于比特长度固定的数据流，其编、解码时间是固定的，不会随数据流中”1″，”0″的随机变化而不定。本文中所介绍的CRC检测法，不但简化了软件的编程难度，而且提高了CRC校验码的实时性。其流程图如3.7所示。

图3.7 快速查表求余式的流程图
其代码如下：
unsigned short CRC_16( unsigned char * aData, unsigned long aSize )
{
unsigned long i;
unsigned short nAccum = 0; /*初始化寄存器*/
for ( i = 0; i < aSize; i++ ) /*判断数据是否结束*/
nAccum = ( nAccum << 8 ) ^ ( unsigned short )Table_CRC[( nAccum >> 8 ) ^ *aData++]; /*查表求余式*/
return nAccum;
}
为了更清楚得到按字节查表程序的过程，再对其做公式推导。将多字节信息的余式值用单位字节余式值经过特定算法来实现。设M(x)为n个字节信息,由CRC校验原理中的公式（2.14） 可知，当信息为双字节时,有
（3.2）
当M(x)增加1个字节时
（3.3）
有
（3.4）
由以上推理可知,当已知n字节信息的余式,求取n+1字节信息的余式时,首先由增加的字节异或原余式的高8位,形成一新的字节。求取该字节的余式,再与原余式的低8位相异或,便可求得全部信息字节的余式。这说明,如果能求得单字节信息的余式值,就可求取多字节信息的余式值，进而实现CRC码。
按照上述步骤完成的CRC差错校验码和其一般编码方法所得的结果完全相同，但在实时性和简单性方面具有非常明显的优势。在接收端的解码步骤与上述步骤相同，如果得出的余式中的 、 分别都相同，则传输正确无误，否则说明传输过程中数据出错。
3.2.3 余数表的设计
查表算法的思路是先离线构造一个单字节信息的余式编码表,根据此编码表进行查表及异或运算即可求得多字节信息的余式。
产生表的过程就是分别求出从0×00－0xFF的余式的过程，而此时求余式用的是按位异或，然后按照这个影射关系构成的一个数据表。
产生参数表的代码如下：
#include <stdio.h>
#include <stdlib.h>
unsigned long Table_CRC[256];
void BuildTable16( unsigned short aPoly )
{
unsigned short i, j;
unsigned short nData;
unsigned short nAccum;
for ( i = 0; i < 256; i++ )
{
nData = ( unsigned short )( i << 8 ); /*判断数据是否结束*/
nAccum = 0;
for ( j = 0; j < 8; j++ )
{
if ( ( nData ^ nAccum ) & 0×8000 )
nAccum = ( nAccum << 1 ) ^ aPoly;
else
nAccum <<= 1;
nData <<= 1;
}
Table_CRC[i] = ( unsigned long )nAccum; }
}
因此其步骤逐位异或的相似，其程序流程图如图3.9所示。

图3.9 做表流程图
程序运行得出表的部分如图3.10所示：

图3.10 余数表结果示意图

第四章 CRC检错性能的研究
4.1 关于研究检错能力的方法
在传输有错情况下的S(x)、T(x)和E(x)关系有：
（4.1）
由上式可以看出CRC编码的检错能力与信息码序列无关，只和差错序列有关。因此在后面我们只考虑错误多项式E(x)。
分析下列两种情况：
1) ，CRC可以检出传输有错，通信系统一般采用ARQ机制进行重传；
2) ，且 ，CRC检错失效，产生漏检，可以看出此时的E(x)也属于一个码字，即T(x)，S(x)，E(x)都是合法的码字，这种情况下CRC就是失去了检错的能力。因此从 是否等于零可知是否产生漏检。下面以这种方法对CRC的检错性能进行研究。
4.2 CRC检错性能研究
本文的研究重点就是l6位冗余CRC编码。CRC－CCITT多项式为公式（2.13）即：
。这个多项式由两部分组成，前部分是因式(x+1)，可以提供具有差分运算的功能，后一部分是一个周期为 的本原多项式，可以证明两个本原多项式的周期都是32767，即 ，生成多项式的组成和周期在很大程度上决定了CRC的性能。
由生成多项式的组成可以得出下面的结论：
结论一：CRC-CCITI多项式为生成多项式的缩短循环码中非零项的个数为偶数个，即码重分布中奇次项都为零，或者说码字本身具有偶校验特性。这一特殊性质对分析码距和差错误码率有着重要的作用。对该性质的证明如下：
由于CRC-CCITI多项式中包含(x+1)项，所以任何码字都可以被(x+1)整除。即
（4.2）
同时
， ， m≠n，m≥0，n≥0 （4.3）
所以，当且仅当码字多项式中包含偶数个非零项时才能被x+l整除，证毕。
结论二：原始生成多项式是不可约分的，但不可约分的的多项式并不一定是原始的，因此对于某些奇数位差错，原始生成多项式是检测不出来的。
由前面分组码的性质可知，码字的最小码距决定纠错能力，而最小码距等于非零码字的最小码重。CRC-ANSI和CRC-CCITI的最小码重分析如下：
(1) 由于生成多项式本身码重为4，且都属于码字，所以最小码重d小于等于4；
(2) 由于所有码字中非零项的个数为偶数个，所以最小码重不等于l、3；
(3) 任何包含两个非零项的码字可以表示为 ，其中 不能被G(x)整除， 也不能被G(x)整除，否则与G(x)的周期为32767相矛盾。
综上所述，有以下结论：
CRC-CCITI的最小码重w和最小码距 为4。根据分组码的纠错能力可知，最小码距 为4的CRC编码至少具有下列性能：
(1) 可以纠正所有1个错误；
(2) 可以检出所有3个以下错误：
事实上出于CRC的特殊设计，其检错能力远远高于通用的分组码。下面对其性能做出分析。
4.2.1 检错性能分析
由前面的结论知CRC的检错性能由最小码距和编码本身的特性距定，文献[9] [10] [13]中都给出了部分性能，本文拓展描述如下：
1. 检奇数位错
若G(x)含有（x＋1）的因子，则能检测出所有奇数位错误。由CRC码字的性质可知，所有的码字的重量都是偶数，所有重量为奇数的错误都不属于码空间，都可以被检出。用反证法证明如下：
证明：
由已知条件
（4.4）
（4.5）
知G(x)含有（x＋1）因子。
假设 ，则
（4.6）
这里E(x)是奇数位错的差错模式多项式，必含有奇数个项。由于奇数个1相加仍为1，故E(x)＝1。而用1带入上式有
（4.7）
与E(x)＝1矛盾。
所以，假设不成立， ，即此种差错格式可检测出来的。
2. 检突发长度小于r的突发错
若G(x)不含有x的因子，或者换句话说， G(x)中含有常数项1，那么能检测出所有突发长度小于等于r的突发错。
证明：
对于这种错误格式，其多项式可写为
（4.8）
对于任意 。由于G(x)是r次多项式（最高项系数为1），且不含有x的因子，那么它肯定不可能整除小于r次的多项式 ， ，也不能整除E(x)，即 ，或者说此种差错是可检测的。
3. 检所有双错
若G(x)中不含有x的因子，而且对任何 的t，除不尽 ，则能检所有的双错。
证明：
双错模式对应的差错多项式为
（4.9）
这里 。由已知条件可知G(x) 除不尽 ，所以 。这一点也可以用距小码距为4来证明。
具体到CRC-CCITT，因为上述各项要求该多项式都满足，故上述错误都可以由它校验出来，换句话说，CRC-CCITT对所有奇数格错、所有突发长度小于等于16的突发错以及所有的双错的检错率为100％。
4.2.2 漏检错误概率分析
由前文可知当错误图样E(x)为码空间上的一个矢量时，CRC检错功能失效，产生不可检测错误(undetected error)，系统无法进行重传或者纠错，传输的信息被丢失。因此在通信系统设计中必须对CRC的漏检概率(probability of undetected error，Pud)进行分析，并采取必要的技术措施，这一点在高速数据传输中尤其重要。
在(n，k)CRC码中，设传输信道为BSC信道，误码率为P，则各种的概率分布如下：
正确传输的概率：
（4.10）
发生错误的概率：
（4.11）
单个码重为 的错误发生的概率：
（4.12）
设码重分布为 ，则发生不可检测的概率为
（4.13）
所以，求解的关键在于求出CRC的码重分布，一般在P<0.5，k>n-k时需要借助对偶码来降低求解的复杂度。一般而言对于n比较大的情况，精确求解 是很困难的。
这里可以通过整体分析的方法获得平均的量，对于(n，k)CRC编码而言，存在 个接收矢量T(x)， 个码元矢量S(x)，其中 个非零矢量可以是可能的不可检测错误矢量E(x)，在信道误码率为P的BSC信道上，不可检测错误发生的概率为
（4.12）
因此，可以将1／ 作为 分析的上限，对于CRC-ANSI和CRC-CCITT而言， 的上限是 ，约为1.52× ，就是说大约65 000个数据包中才会发生一个不可检测错误，这对于中低速的串行已经足够好了，甚至可以忽略。但是近年来随着高速数据通信的飞速发展，不可检测错误的影响已经不可忽视，例如在CISCO GSR12000路由器中每秒钟转发的数据包可以达到4 500万个，就是每秒钟可能会发生多达686次不可检测错误，这种情况不可以忽略不记，一般要考虑更高次数的CRC一32或者其它措施。
1. 突发长度为r＋1的突发错的概率分析
若G(x)中不含有x的因子，则对突发长度为r+1的突发错误的漏检率为
证明：突发长度为r+1的突发错误对应的差错多项式为
（4.12）
这里 是r次多项式，G(x)也是r次多项式，G(x)能除尽它的唯一可能是 就等于G(x)。只有在这种情况下， ，差错检测不出。多项式 中间有r－1项，每项系数都可以是0或者是1，即有 种不同的突发长度为r+1的突发错误，检测不出的只有一种故漏检率为
2. 突发长度大于r+1的突发错误的概率分析
若G(x)中不含有x的因子，则对突发长度b大于r+1的突发错误的漏检率为 。
证明：此时差错多项式为
（4.13）
检测不出差错时必是
（4.14）
G(x)为r次多项式，且最高项和常数项的系数都为1，故Q(x)必为(b-1)-r=b-r-1次多项式 ，共有 种不同的可能性，这是差错检测不出的情况。一般说来 共有 种不通的突发长度为b的错误模式。所以，漏检率为
（4.15）
综合这些性质，有如下结论：若适当选取G(x)，使其含有(x＋1)因子、常数项不为0且周期大于等于n，那么，由此G(x)作为生成多项式产生的CRC码可检测所有的奇数位错、双错和突发长度小于等于r的突发错以及 的突发长度为r+1的突发错和 的突发长度大于r+1的突发错误。所以CRC的生成多项式的阶数越高，那么CRC校验，误判的概率就越小。具体到取r=16,则能检测出所有的奇数位错、双错和突发长度小于等于r的突发错以及 （约为99.997％）的突发长度为17的突发错和 （约为99.998％）的突发长度大于17的突发错误。
4.2.3 单比特错误纠正的原理和方法
作为分组码的一种特例，CRC本身具有一定的纠错能力，CRC-CCITT具纠正单比特错误的能力，在传统的低速通信中由于误码较高，发生单比特错误的比例较小，纠错的效率不高；随着光纤通信的等低误码率信道的出现，发生单比特错误在总的错误中的比例大大提高，因此采用单比特纠正错误可以大大提高信道的吞吐量和降低对反向信道占用，一种典型应用(CRC-CCITT，帧长1024比特)下的单比特纠错性能如下表。
表4.1 CRC-CCITT多项式．帧长1024比特的单比特纠错性能
误码率 帧错误概率 单比特错误概率 百分比 纠错后的帧错误率
lE一2 0．999 966 0．000 350 836 0.000 350 848 0．999 615
lE一3 0．64l 029 0．367 955 0．574 007 0．273 074
lE一4 0．0 973 362 0．092 442 0．949 719 0．00489 412
lE一5 0．0 l01 878 0．0 l01 358 0．994 894 5．202 21e一005
lE一6 0．00 l02 348 0．00 l02 295 0．999 489 5．23l 9e-007
lE一7 0．000 l02 395 0．00 010 239 0．999 949 5．237 35e一009
lE一8 1．023 99e一005 1．023 099e一005 0．999 995 5．242 87e-0ll
由表4.1可知，当错误发生的数学期望np<=l时，单比特是帧错误的主要组成，在低误码率时这一点尤其明显，利用CRC的单比特纠错特性，可以显著地降低误码率，并提高网络的吞吐量。
纠正单比特错误的方法也很简单，首先将单比特错误图样依次送人编码器进行编码，选取最后输出n－k为构成一个长度为n的表，如果T(x)不能被G(x)整除，将余数和表中的数据逐个对比，如果相等则纠正相应位置的单个化特，如果全部不等，则发生超过一个错误，需要进行ARQ重传。
若如果有一位出错，则余数不为0，而且不同位出错，其余数也不同，余数和出错位有一一对应的关系。可以证明，余数与出错位的对应关系只与码制及生成多项式有关，而与待测码字（信息位）无关。
如果对余数补0继续除下去，能发现一个有趣的结果:各次余数按一定顺序循环。例如第一位出错，余数将为0×0001，补0后再除（补0后若最高位为1，则用除数做模2减取余；若最高位为0，则其最低3位就是余数），得到第二次余数为0×0002。以后继续补0作模2除，依次得到余数，反复循环，这就是”循环码”名称的由来。这是一个有价值的特点。如果求出余数不为0后，一边对余数补0继续做模2除，同时让被检测的校验码字循环左移。当出现余数对应出错位移到 位置，可通过异或门将它纠正后在下一次移位时送回 。这样我们就不必像海明校验那样用译码电路对每一位提供纠正条件。当位数增多时，循环码校验能有效地降低硬件代价，这是它得以广泛应用的主要原因。
4.3 程序仿真CRC的性能
前面理论分析求证了CRC-CCITT的性能，下面用程序仿真进一步对性能进行研究。这里，程序仿真的方法是先得出在传输过程中遇到的各种格式的错误序列，再对每个序列错误序列查表求 。由本章可知，如果 ，错误可以检出，反之则漏检，所以只要看 是否等于零即可仿真其错误性能。
4.3.1 检单比特错误仿真程序
对单比特序列的研究，若序列长度为n，就有n种出错位，即n个错误多项式形式，而CRC－CCITT的序列最大周期由可知为 。因此要对 个错误序列对做 求模运算。
程序流程如图4.1所示。

图4.1 检单个比特错误仿真流程图
该程序的部分代码为：
int i;
unsigned char x[n];
unsigned short crc;
printf(”n=%d
“,n);
for(i=0;i<n;i++)
x[i]=0;
for(i=0;i<n;i++)
{
x[i]=1;
crc=CRC_16(x,n); /*调用查表函数*/
printf(”0x%4x”,crc); /*输出余式值*/
if(i!=n-1)
printf(”, “);
x[i]=0;
}
当预定义n＝240时程序运行结果如图4.2所示：

图4.2 检单个比特错误仿真结果
从结果可以看出，余式都不等于0，即 ，说明序列长度n为240的各种错误格式都可以被检出。研究证实了，当0<n<=32767时，各种单个比特错误序列的余式都不为0，换句话说单个比特错误都可以被检出。
4.3.2 检所有双错的仿真程序
对所有双错的研究，一个长度为n的序列，出现两位错的错误序列有 个，同样这里最大周期n＝32767，即0<n<=32767。图4.3是对这些错误序列求余式的流程图：

图4.3 检两比特错误的仿真流程图

该程序的部分代码为：
int i,j;
unsigned char x[n];
unsigned short crc;
printf(”n=%d
“,n);
for(i=0;i<n;i++) /*构造两比特错误序列*/
x[i]=0;
for(i=0;i<n-1;i++)
{ x[i]=1;
for(j=i+1;j<n;j++)
{ x[j]=1;
crc=CRC_16(x,n); /*调用查表函数*/
printf(”0x%4x”,crc); /*输出余式值*/
if(i!=n-2)
printf(”, “);
x[j]=0; }
x[i]=0;
}
当预定义序列长度n＝20时，有 个双错的序列，结果如图4.4所示：
图4.4 检两比特错的仿真结果
由上面的结果可以看出，在这190个余式里面，没有一个是等于0的，即全部 ，当预定义0<n<=32767时研究证明，两比特错误的各种序列的余式都不为零，即都可以被检错。
4.3.3 检四位错的仿真程序
这里的仿真方法是指定一个长度的序列，让每个序列与生成多项式求余，但是不输出余式值，而是直接有程序计算出漏检概率。预定义n＝68，部分代码如下：
int i,j,k,l;
float a;
int count=0;
int sum=0;
unsigned char x[n];
unsigned short crc;
printf(”n=%d
“,n);
for(i=0;i<n;i++) /*构造四个比特错误的序列*/
x[i]=0;
for(i=0;i<n-3;i++)
{ x[i]=1;
for(j=i+1;j<n-2;j++)
{ x[j]=1;
for(k=j+1;k<n-1;k++)
{ x[k]=1;
for(l=k+1;l<n;l++)
{ x[l]=1;
sum++; /*记录序列的数量*/
crc=CRC_16(x,n); /*调用查表程序*/
if(crc==0)
count++;
x[l]=0; }
x[k]=0; }
x[j]=0; }
x[i]=0; }
a=count/sum; /*计算漏检概率*/
printf(”the probability of undetected error is”); /*输出漏检概率值*/

printf(”%8.5f”,a);
程序流程图如图4.5所示。

图4.5 检四个错误的仿真流程图

程序运行结果如图4.6所示。

图4.6 检四个错误序列长度为68的仿真结果

由仿真结果知，对有些一定长度的四个错的错误序列，CRC检错概率为100％，虽然没有完全仿真所有的序列，但在仿真了的一部分过程中未出现过漏检，可以看出CRC检错能力还是很强的。
4.3.4 检突发错的仿真程序
突发错误的仿真程序是根据系统产生一个随机数，该随机数即为突发长度。同样n为序列长度，其值在0到32767之间。
程序流程图如图4.7所示。该仿真程序代码如下：
int i,j,m;
unsigned short crc;
unsigned char x[n];
clrscr();
srand((unsigned)time(NULL)); /*使用当前时间做种子*/
for(i=0;i<n;i++)
x[i]=0;
printf(”n=%d
“,n);
do
m=rand()%(n+1); /*产生1～n范围内的随机数*/
while(m==0);
printf(”m=%d
“,m);
for(i=0;i<(n+1-m);i++)

图4.7 检突发错仿真程序流程图

{
x[i]=1;
for(j=1;j<m;j++)
x[i+j]=1;
crc=CRC_16(x,n); /*调用查表函数*/
printf(”0x%4x”,crc);
if(i!=n-m)
printf(”, “);
for(j=0;j<m;j++)
x[i+j]=0;
}
当预定义n＝200时，运行程序，产生一个突发错误长度为44的随机数。其结果如图4.8所示：

图4.8 检突发错仿真结果

由仿真测试时发现，基本上没有余式为0的。说明突发错虽然存在漏检，但是漏检概率很低。
通过对检错性能的分析，可得出序列的位长对检错性能的影响。r越长，对检测突发错误的长度也越长，检错性能也越强。反之，则越弱。
另外，对于k和r的关系，从以上推导中可看出，k和r之间没有必然的联系。即k可以大于、等于、小于r。考虑到编码效率，一般取k> r。

第五章 设计总结
本文主要导出的CRC差错校验码查表快速实现方法，和其一般编码方法所得的结果完全相同，但在实时性和简单性方面具有非常明显的优势，并且具有侦错效率高、运行速度快、程序小等优点。对其性能的研究是另一重点。本文给出了仿真程序。完成了应完成的任务。
5.1 设计中存在的不足
在设计中还存在一些不足，由于时间等原因，在仿真模块没有做的很理想，序列长度n是需要手动预定义的，而且对于最大周期长度为32767的CRC-CCITT来说分配最大存储空间是一个很大的工程，因此本程序还有待进一步的思考加以完善。
在突发仿真模块，由于时间原因未能分成三部分来完成，而只是产生一个随机数，因此存在一定的随机不确定度。
结束语
本文介绍了CRC的原理,算法及性能研究，并通过开发C的位操作能力,给出了C语言实现CRC的算法,简单易行。本算法很有实用价值。
采用软件方法实现的前提是实现算法要合理，校验速度要足够快。本文介绍的这种CRC查表校验方法，该方法具有侦错效率高、运行速度快、程序小等优点。
综上所述，CRC编码虽然存在一定的不可检测错误，但仍然是一种高效率、高性能的检错方式。CRC校验码以其良好的纠错和检错性能,广泛应用在许多实际数据传输工程应用中。l6位的CRC-ANSI和CRC-CCITF具有纠正所有单错误、检测所有奇数比特错误、检测所有单个突发错误、检测所有2比特错误的能力，和ARQ机制结合可以提供高可信度的数据通信，在低误码信道上采用单比特纠错可以有效地提高系统的吞吐量。值得注意的是在高速数据通信中不可检测错误则不可以忽略不记。
参考文献
[1] 曹志刚 钱亚生. 现代通信原理[M]. 北京：清华大学出版社，2000.279～315
[2] 高传善等. 数据通信与计算机网络[M]. 北京：高等教育出版社，2004.
[3] 樊昌信等. 通信原理[M]. 北京：国防工业大学出版社, 2000.322～365
[4] 王仲文. ARQ编码通信[M]. 北京：机械工业出版社，1991
[5] 王新梅等. 计算机中的纠错码技术[M]. 北京：人民邮电出版社，1999.47～70
[6] 孙丽华等. 信息论与纠错编码[M]. 北京：电子工业出版社，2005.173～185
[7] 王新梅 肖国镇. 纠错码－原理与方法[M]. 西安：西安电子科技大学出版社，2001
[8] 杨路明. C语言程序设计教程[M]. 北京：北京邮电大学出版社, 2003
[9] 米根锁CRC检错码的软件实现及其在通信中的应用[J]. 兰州铁道学院学报，2000，19(3)：42～44
[10] 瞿中 徐向之. 单片机通信中的CRC算法[J]. 微机发展,2001(4):74～76
[11] 黄海波，付微，孙未，等．高速大气激光通信收发模块的研究与设计[J]．激光与红外，2003，(6)
[12] 周祖荣，张鹏远．对帧校验序列的研究[J]．青岛科技大学学报．2003(2)．
[13] 王祖林. 循环冗余校验码的查表生成算法和实现[J]. 北京航空航天大学学报,1996,22(4):389～392
[14] R0ss Williams. A painless guide to CRC error detection algorithms[J]. Document url: http://www.repairfaq.org/filipg/ ,1993
[15] Peterson Wdldon．Error-correcting Codes [M ]．2nd Edition．The M IT Press， 1972