文档介绍：CRC 详解 CRC 算法原理及 C 语言实现(介绍了 3 种方法) 摘要本文从理论上推导出 CRC 算法实现原理, 给出三种分别适应不同计算机或微控制器硬件环境的 C 语言程序。读者更能根据本算法原理,用不同的语言编写出独特风格更加实用的 CRC 计算程序。关键词 CRC 算法 C 语言 1 引言循环冗余码 CRC 检验技术广泛应用于测控及通信领域。 CRC 计算可以靠专用的硬件来实现,但是对于低成本的微控制器系统,在没有硬件支持下实现 CRC 检验, 关键的问题就是如何通过软件来完成 CRC 计算,也就是 CRC 算法的问题。这里将提供三种算法, 它们稍有不同, 一种适用于程序空间十分苛刻但 CRC 计算速度要求不高的微控制器系统, 另一种适用于程序空间较大且 CRC 计算速度要求较高的计算机或微控制器系统, 最后一种是适用于程序空间不太大,且 CRC 计算速度又不可以太慢的微控制器系统。 2 CRC 简介 CRC 校验的基本思想是利用线性编码理论, 在发送端根据要传送的 k 位二进制码序列,以一定的规则产生一个校验用的监督码(既 CRC 码)r位, 并附在信息后边, 构成一个新的二进制码序列数共(k+r) 位,最后发送出去。在接收端,则根据信息码和 CRC 码之间所遵循的规则进行检验,以确定传送中是否出错。 16 位的 CRC 码产生的规则是先将要发送的二进制序列数左移 16 位(既乘以)后,再除以一个多项式,最后所得到的余数既是 CRC 码, 如式( 2-1 ) 式所示, 其中 B(X) 表示 n 位的二进制序列数, G(X) 为多项式, Q(X) 为整数, R(X) 是余数(既 CRC 码)。( 2-1 ) 求 CRC 码所采用模 2 加减运算法则, 既是不带进位和借位的按位加减, 这种加减运算实际上就是逻辑上的异或运算, 加法和减法等价, 乘法和除法运算与普通代数式的乘除法运算是一样, 符合同样的规律。生成 CRC 码的多项式如下,其中 CRC-16 和 ITT 产生 16 位的 CRC 码,而 CRC-32 则产生的是 32 位的 CRC 码。本文不讨论 32 位的 CRC 算法,有兴趣的朋友可以根据本文的思路自己去推导计算方法。 CRC-16 : (美国二进制同步系统中采用) ITT : (ITT 推荐) CRC-32 : 接收方将接收到的二进制序列数(包括信息码和 CRC 码)除以多项式, 如果余数为 0, 则说明传输中无错误发生, 否则说明传输有误, 关于其原理这里不再多述。用软件计算 CRC 码时, 接收方可以将接收到的信息码求 CRC 码,比较结果和接收到的 CRC 码是否相同。 3 按位计算 CRC 对于一个二进制序列数可以表示为式(3-1): (3-1) 求此二进制序列数的 CRC 码时, 先乘以后( 既左移 16位), 再除以多项式 G(X) , 所得的余数既是所要求的 CRC 码。如式(3-2) 所示: (3-2) 可以设: (3-3) 其中为整数,为 16 位二进制余数。将式(3-3) 代入式(3-2) 得: (3-4) 再设: (3-5) 其中为整数, 为 16 位二进制余数,将式(3-5) 代入式(3-4) ,如上类推,最后得到: (3-6) 根据 CRC 的定义,很显然,十六位二进制数既是我们要求的 CRC 码