摘 要

本文通过对本科课程中《计算机组成原理》和《计算机网络》中循环冗余校验(Cyclic Redundancy Check, CRC)的知识进行扩展，以研究CRC校验算法并实现其基本功能为目的，完成了对CRC-12、CRC-16、CRC-CCITT等标准的CRC码的生成和对CRC数据信息的校验，展示CRC校验不同余数对错误信息的检错及改错作用，其成果不仅可以运用到实际的数据检错工程中，还可以作为本科课堂例如计算机组成原理，计算机网络等课程信息校验的教学演示工具。

全文简单介绍了循环冗余校验码，从理论上对循环冗余校验码进行数学抽象方面的分析和推导，然后从计算机硬件软件方面分析了如何去实现循环冗余校验码的生成。讨论研究了循环冗余校验的演算程序的实现，对不同算法进行了研究和比较，描述了如何实现不同标准的生成多项式对相同信息的编码，最终比较后使用了相对来说运行效率最高的查余式表的CRC算法。

关键词：循环冗余校验；数字逻辑；数据恢复

Abstract

In this paper, we expand the knowledge of Cyclic Redundancy Check (CRC) in the course of "computer composition principle" and "computer network" in undergraduate course to study the CRC check algorithm and realize its basic function. CRC code, CRC-16, CRC-CCITT and other standard CRC code generation and CRC data on the verification, showing the CRC to verify the different remainder of the error message error detection and error correction, the results can not only use To the actual data error detection project, but also can be used as undergraduate classrooms such as computer composition principle, computer network and other course information verification teaching demonstration tool.
In this paper, the cyclic redundancy check code is introduced in detail, and the mathematical redundancy of the cyclic redundancy check code is analyzed and deduced in theory. Then, how to implement the cyclic redundancy check code is analyzed from the aspects of computer hardware software. This paper discusses the realization of the calculation program of the cyclic redundancy check, and studies and compares the different algorithms. It describes how to implement the coding of the same information in different standard generation polynomials. After the final comparison, the operation efficiency is the highest The CRC algorithm of the search table.

Key words: cyclic redundancy check; digital logic; data recovery

目录

目录 1

第1章 绪论 1

1.1 CRC算法研究背景和意义 1

1.2 论文主要研究内容 2

1.3 论文章节安排 2

第2章 循环冗余校验码 3

2.1 几种简单的校验码 3

2.1.1 奇偶校验 3

2.1.2 累加和校验 3

2.2 循环码 4

2.2.1 循环冗余校验计算方法（CRC） 5

2.3 本章小结 6

第3章 CRC算法理论基础 7

3.1 CRC代数推导 7

3.1.1 比特型算法 7

3.1.2 字节型算法 8

3.2 CRC生成多项式 9

3.3 本章小结 10

第4章 CRC演算程序实现 11

4.1 CRC算法分析 11

4.2 CRC算法实现 13

4.2.1 比特型算法实现 13

4.2.2按字节余式表法 14

4.2.3生成余式表 15

4.2.4程序测试 16

4.3 本章小结 20

第5章 总结和展望 21

5.1 总结 21

5.2 展望 22

参考文献 23

致 谢 24

第1章 绪论

这一章作为全文的开篇，主要对论文的研究背景和意义，论文主要论述的内容和论文的主要框架进行叙述。

1.1 CRC算法研究背景和意义

从古至今，从原始的“烽火台”、“灯塔”到书信，人们对信息的运用就十分频繁，随着社会进步，科技发展，传递信息的方式就越来越多，越来越先进，人们对信息传递的要求越来越多，到了20世纪人们对信息传递的速度和可靠性也越来越重视，如何提高信息传递的能力和可靠性也成为了研究课题。信息从一种形式转换为另一种形式称为编码，为了使码字到达接收方后仍然正确，即使在中途出错也能检验出错误，一般发送端会以原信息码字为基础，加上与原信息码字相关的冗余部分。加上冗余部分的码字到达接收端后，能通过冗余码字和原信息码字的关系来检测传递中是否出现错误，恢复原码的过程叫做译码或者解码。

随着大数据时代的到来，使用计算机和利用互联网交流的频率也越来越高，经常会有各种错误存在于计算机存储系统中，在计算机内的存储器上，由于磁介质表面的缺陷、尘埃等原因，导致出现很多误码。为了降低数字通信系统以及计算机存储、运算系统中的错误发生率，提高计算机传递信息的质量，大量西方国家已经大规模使用校验码，并为之制订了相关的国际标准，校验码是可以自动检测出错误和纠正错误的数据编码，也可以叫做检错纠错编码,校验码还大量应用于嵌入式开发、集成电路中，用来提高硬件产品的质量。不仅如此，在大数据时代，校验码技术已开始渗透到各类领域，与许多其他相关的技术协同工作，也取得了不少成果。

循环冗余校验码^[4]（Cyclic Redundancy Check，CRC）是一种可以发现并纠正数据在计算机存储或互联网传输过程中连续出现多位错误的代码，而在计算机网络方面，由于现实的通信链路都是不能完全隔绝干扰、噪声的，比特在传输过程中可能会发生错误，也就是比特差错。在通讯系统中，经常会用误码率BER（Bit Error Rate）来描述信息传递的质量，而在模拟信号处理中，也有这样一个计量单位，它就是信噪比。误码率与信噪比有很大的关系。信息传输时如果尽量提高信噪比，就能让信息的误码率降低。实际的通信链路不可能达到理想状态，由于信道上各种噪声和干扰等复杂因素的影响，它不可能使信噪比为零，可能会导致接收到的信息与发送端发送的信息不一致，为了尽可能地减小通信时的信噪比进而降低误码率，提高数字通信的可靠性，在计算机网络传输数据时，必须采用各种差错检验措施来保证数据的有效传输，当前，循环冗余校验码（Cyclic Redundancy Check，CRC）被广泛地用于数据链路层的数据传输，并且在嵌入式开发中，经常要用硬件实现CRC算法中的模2除法，也经常用到CRC算法对各种数据进行处理。因此，对于嵌入式开发人员，掌握基本的CRC算法也是不可缺少的技能。