crc算法实现

⑴ CRC校验是怎么算的

你这个是CRC16要实现校验的话，你首先需要知道对方采用的是何种CRC公式不同的CRC公式 得到的校验码是不一样的在知道公式的情况下做crc表，然后按照crc算法，计算这8个字节的整体crc如果传输没有错误的话，最终的crc值是0也可以计算前六个的crc，然后和最后两个字节比较，效果是相同的。

⑵ 求一CRC算法，需要提供思路，最好有现成工具计算。

CRC
代数学的一般性算法
在代数编码理论中，将一个码组表示为一个多项式，码组中各码元当作多项式的系数。例如
1100101
表示为
1·x6+1·x5+0·x4+0·x3+1·x2+0·x+1，即
x6+x5+x2+1。
设编码前的原始信息多项式为P(x)，P(x)的最高幂次加1等于k；生成多项式为G(x)，G(x)的最高幂次等于r；CRC多项式为R(x)；编码后的带CRC的信息多项式为T(x)。
发送方编码方法：将P(x)乘以xr(即对应的二进制码序列左移r位)，再除以G(x)，所得余式即为R(x)。用公式表示为
T(x)=xrP(x)+R(x)
接收方解码方法：将T(x)除以G(x)，如果余数为0，则说明传输中无错误发生，否则说明传输有误。
举例来说，设信息码为1100，生成多项式为1011，即P(x)=x3+x2，G(x)=x3+x+1，计算CRC的过程为
xrP(x)
x3(x3+x2)
x6+x5
x
---------
=
------------
=
---------
=
(x3+x2+x)
+
---------
G(x)
x3+x+1
x3+x+1
x3+x+1
即
R(x)=x。注意到G(x)最高幂次r=3，得出CRC为010。
附：CRC算法的C程序
1)
求CRC码的运算采用模2运算,
所谓模2运算就是不带进位和借位,
因此加法和减法等价,实际上就是逻辑上的异或运算,
除法可以用多次模2减法实现.
2)
所谓CRC码,
就是把数据块左移16位,
然后除以0x11021所得到的余数(由CCITT推荐).
3)
据此写出以下的CRC的C程序.
*ptr指向发送数据块的首地址,
len是数据块以字节为单位的长度.
uint
cal_crc(uchar
*ptr,
uchar
len)
{
uint
crc;
uchar
i;
crc=0;
while(len--!=0)
{
for(i=0x80;
i!=0;
i/=2)
{
if((crc&0x8000)!=0)
{crc*=2;
crc^=0x1021;}
else
crc*=2;
if((*ptr&i)!=0)
crc^=0x1021;
}
ptr++;
}
return(crc);

⑶ 关于CRC算法，高手赐教

循环冗余校验（CRC）是一种根据网络数据封包或电脑档案等数据产生少数固定位数的一种散列函数，主要用来检测或校验数据传输或者保存后可能出现的错误。生成的数字在传输或者储存之前计算出来并且附加到数据后面，然后接收方进行检验确定数据是否发生变化。一般来说，循环冗余校验的值都是32位的整数。由于本函数易于用二进制的电脑硬件使用、容易进行数学分析并且尤其善于检测传输通道干扰引起的错误，因此获得广泛应用。它是由W. Wesley Peterson在他1961年发表的论文中披露[1]。

{{noteTA
|T=zh-hans:循环冗余校验;zh-hant:循环冗余校验;
|1=zh-hans:循环冗余校验;zh-hant:循环冗余校验;
}}
'''循环冗余校验'''（CRC）是一种根据网路数据封包或[[电脑档案]]等数据产生少数固定位数的一种[[散列函数]]，主要用来检测或校验数据传输或者保存后可能出现的错误。生成的数字在传输或者储存之前计算出来并且附加到数据后面，然后接收方进行检验确定数据是否发生变化。一般来说，循环冗余校验的值都是32位的整数。由于本函数易于用二进制的[[电脑硬件]]使用、容易进行数学分析并且尤其善于检测传输通道干扰引起的错误，因此获得广泛应用。它是由[[W. Wesley Peterson]]在他1961年发表的论文中披露<ref name="PetersonBrown1961">
{{cite journal
| author = Peterson, W. W. and Brown, D. T.
| year = 1961
| month = January
| title = Cyclic Codes for Error Detection
| journal = Proceedings of the IRE
| doi = 10.1109/JRPROC.1961.287814
| issn = 0096-8390
| volume = 49
| pages = 228
}}</ref>。

==简介==
CRC“校验和”是两个位元数据流采用二进制除法（没有进位，使用XOR异或来代替减法）相除所得到的余数。其中被除数是需要计算校验和的信息数据流的二进制表示；除数是一个长度为<math>n+1</math>的预定义（短）的二进制数，通常用多项式的系数来表示。在做除法之前，要在信息数据之后先加上<math>n</math>个0.

CRCa 是基于[[有限域]]GF(2)([[同余|关于2同余]])的[[多项式环]]。简单的来说，就是所有系数都为0或1（又叫做二进制）的多项式系数的集合，并且集合对于所有的代数操作都是封闭的。例如：

:<math>(x^3 + x) + (x + 1) = x^3 + 2x + 1 \equiv x^3 + 1</math>

2会变成0，因为对系数的加法都会模2. 乘法也是类似的：

:<math>(x^2 + x)(x + 1) = x^3 + 2x^2 + x \equiv x^3 + x</math>

我们同样可以对多项式作除法并且得到商和余数。例如， 如果我们用''x''³ + ''x''² + ''x''除以''x'' + 1。我们会得到：
:<math>\frac{(x^3 + x^2 + x)}{(x+1)} = (x^2 + 1) - \frac{1}{(x+1)}</math>
<!--注：在说“除以”的时候, 读者将会看到等式中的除号。这里看不到除号常使我感到有点混乱。-->

也就是说，

:<math>(x^3 + x^2 + x) = (x^2 + 1)(x + 1) - 1</math>

这里除法得到了商''x''² + 1和余数-1，因为是奇数所以最后一位是1。

字符串中的每一位其实就对应了这样类型的多项式的系数。为了得到CRC, 我们首先将其乘以<math>x^{n}</math>，这里<math>n</math>是一个固定多项式的[[多项式的阶|阶]]数, 然后再将其除以这个固定的多项式，余数的系数就是CRC。

在上面的等式中，<math>x^2+x+1</math>表示了本来的信息位是<code>111</code>, <math>x+1</math>是所谓的'''钥匙''', 而余数<math>1</math>（也就是<math>x^0</math>）就是CRC. key的最高次为1, 所以我们将原来的信息乘上<math>x^1</math>来得到<math>x^3 + x^2 + x</math>，也可视为原来的信息位补1个零成为<code>1110</code>。

一般来说，其形式为：

:<math>M(x) \cdot x^{n} = Q(x) \cdot K(x) + R (x) </math>

这里 M(x) 是原始的信息多项式。K(x)是<math>n</math>阶的“钥匙”多项式。<math>M(x) \cdot x^{n}</math>表示了将原始信息后面加上<math>n</math>个0。R(x)是余数多项式，既是CRC“校验和”。在通讯中，发送者在原始的信息数据M后加上<math>n</math>位的R（替换本来附加的0）再发送。接收者收到M和R后，检查<math>M(x) \cdot x^{n} - R(x)</math>是否能被<math>K(x)</math>整除。如果是，那么接收者认为该信息是正确的。值得注意的是<math>M(x) \cdot x^{n} - R(x)</math>就是发送者所想要发送的数据。这个串又叫做''codeword''.

CRCs 经常被叫做“[[校验和]]”, 但是这样的说法严格来说并不是准确的，因为技术上来说，校验“和”是通过加法来计算的，而不是CRC这里的除法。

“[[错误纠正编码]]”常常和CRCs紧密相关，其语序纠正在传输过程中所产生的错误。这些编码方式常常和数学原理紧密相关。

==实现==

==变体==
CRC 有几种不同的变体

* <code>shiftRegister</code> 可以逆向使用，这样就需要检测最低位的值，每次向右移动一位。这就要求 <code>polynomial</code> 生成逆向的数据位结果。''实际上这是最常用的一个变体。''
* 可以先将数据最高位读到移位寄存器，也可以先读最低位。在通讯协议中，为了保留 CRC 的[[突发错误]]检测特性，通常按照[[物理层]]发送数据位的方式计算 CRC。
* 为了检查 CRC，需要在全部的码字上进行 CRC 计算，而不是仅仅计算消息的 CRC 并把它与 CRC 比较。如果结果是 0，那么就通过这项检查。这是因为码字 <math>M(x) \cdot x^{n} - R(x) = Q(x) \cdot K(x)</math> 可以被 <math>K(x)</math> 整除。
* 移位寄存器可以初始化成 1 而不是 0。同样，在用算法处理之前，消息的最初 <math>n</math> 个数据位要取反。这是因为未经修改的 CRC 无法区分只有起始 0 的个数不同的两条消息。而经过这样的取反过程，CRC 就可以正确地分辨这些消息了。
* CRC 在附加到消息数据流的时候可以进行取反。这样，CRC 的检查可以用直接的方法计算消息的 CRC、取反、然后与消息数据流中的 CRC 比较这个过程来完成，也可以通过计算全部的消息来完成。在后一种方法中，正确消息的结果不再是 0，而是 <math>\sum_{i=n}^{2n-1} x^{i}</math> 除以 <math>K(x)</math> 得到的结果。这个结果叫作核验多项式 <math>C(x)</math>，它的十六进制表示也叫作[[幻数]]。

按照惯例，使用 CRC-32 多项式以及 CRC-16-CCITT 多项式时通常都要取反。CRC-32 的核验多项式是
<math>C(x) = x^{31} + x^{30} + x^{26} + x^{25} + x^{24} + x^{18} + x^{15} + x^{14} + x^{12} + x^{11} + x^{10} + x^8 + x^6 + x^5 + x^4 + x^3 + x + 1</math>。

==错误检测能力==
CRC 的错误检测能力依赖于关键多项式的阶次以及所使用的特定关键多项式。''误码多项式'' <math>E(x)</math> 是接收到的消息码字与正确消息码字的''异或''结果。当且仅当误码多项式能够被 CRC 多项式整除的时候 CRC 算法无法检查到错误。
* 由于 CRC 的计算基于除法，任何多项式都无法检测出一组全为零的数据出现的错误或者前面丢失的零。但是，可以根据 CRC 的[[#变体|变体]]来解决这个问题。
* 所有只有一个数据位的错误都可以被至少有两个非零系数的任意多项式检测到。误码多项式是 <math>x^k</math>，并且 <math>x^k</math> 只能被 <math>i \le k</math> 的多项式 <math>x^i</math> 整除。
* CRC 可以检测出所有间隔距离小于[[多项式阶次]]的双位错误，在这种情况下的误码多项式是
<math>E(x) = x^i + x^k = x^k \cdot (x^{i-k} + 1), \; i > k</math>。
如上所述，<math>x^k</math> 不能被 CRC 多项式整除，它得到一个 <math>x^{i-k} + 1</math> 项。根据定义，满足多项式整除 <math>x^{i-k} + 1</math> 的 <math>{i-k}</math> 最小值就是多项是的阶次。最高阶次的多项式是[[本原多项式]]，带有二进制系数的 <math>n</math> 阶多项式

==CRC 多项式规范==
下面的表格略去了“初始值”、“反射值”以及“最终异或值”。
* 对于一些复杂的校验和来说这些十六进制数值是很重要的，如 CRC-32 以及 CRC-64。通常小于 CRC-16 的 CRC 不需要使用这些值。
* 通常可以通过改变这些值来得到各自不同的校验和，但是校验和算法机制并没有变化。

CRC 标准化问题
* 由于 CRC-12 有三种常用的形式，所以 CRC-12 的定义会有歧义
* 在应用的 CRC-8 的两种形式都有数学上的缺陷。
* 据称 CRC-16 与 CRC-32 至少有 10 种形式，但没有一种在数学上是最优的。
* 同样大小的 CCITT CRC 与 ITU CRC 不同，这个机构在不同时期定义了不同的校验和。

==常用 CRC（按照 ITU-IEEE 规范）==
{|class="wikitable"
! 名称|| 多项式 || 表示法：正常或者翻转
|-
|CRC-1 || <math>x + 1</math><br>(用途：硬件，也称为[[奇偶校验位]]) || 0x1 or 0x1 (0x1)
|-
|CRC-5-CCITT || <math>x^{5} + x^{3} + x + 1</math> ([[ITU]] G.704 标准) || 0x15 (0x??)
|-
|CRC-5-USB || <math>x^{5} + x^{2} + 1</math> (用途：[[USB]] 信令包) || 0x05 or 0x14 (0x9)
|-
|CRC-7 || <math>x^{7} + x^{3} + 1</math> (用途：通信系统) || 0x09 or 0x48 (0x11)
|-
|CRC-8-ATM || <math>x^8 + x^2 + x + 1</math> (用途：ATM HEC) || 0x07 or 0xE0 (0xC1)
|-
|CRC-8-[[CCITT]] || <math>x^8 + x^7 + x^3 + x^2 + 1</math> (用途：[[1-Wire]] [[总线]]) ||
|-
|CRC-8-[[Dallas_Semiconctor|Dallas]]/[[Maxim_IC|Maxim]] || <math>x^8 + x^5 + x^4 + 1</math> (用途：[[1-Wire]] [[bus]]) || 0x31 or 0x8C
|-
|CRC-8 || <math>x^8 + x^7 + x^6 + x^4 + x^2 +1</math> || 0xEA(0x??)
|-
|CRC-10 || x¹⁰ + x⁹ + x⁵ + x⁴ + x + 1 || 0x233 (0x????)
|-
|CRC-12 || <math>x^{12} + x^{11} + x^3 + x^2 + x + 1</math><br>(用途：通信系统) || 0x80F or 0xF01 (0xE03)
|-
|CRC-16-Fletcher || 参见 [[Fletcher's checksum]] || 用于 [[Adler-32]] A & B CRC
|-
|CRC-16-CCITT || ''x''¹⁶ + ''x''¹² + ''x''⁵ + 1 ([[X25]], [[V.41]], [[Bluetooth]], [[PPP]], [[IrDA]]) || 0x1021 or 0x8408 (0x0811)
|-
|CRC-16-[[IBM]] || ''x''¹⁶ +''x''¹⁵ + ''x''² + 1 || 0x8005 or 0xA001 (0x4003)
|-
|CRC-16-[[BBS]] || x¹⁶ + x¹⁵ + x¹⁰ + x³ (用途：[[XMODEM]] 协议) || 0x8408 (0x????)
|-
|CRC-32-Adler || See [[Adler-32]] || 参见 [[Adler-32]]
|-
|CRC-32-MPEG2 || See [[IEEE 802.3]] || 参见 [[IEEE 802.3]]
|-
|CRC-32-[[IEEE 802.3]] || <math>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 + 1</math> || 0x04C11DB7 or 0xEDB88320 (0xDB710641)
|-
|CRC-32C (Castagnoli)<ref name="cast93"/>|| <math>x^{32} + x^{28} + x^{27} + x^{26} + x^{25} + x^{23} + x^{22} + x^{20} + x^{19} + x^{18} + x^{14} + x^{13} + x^{11} + x^{10} + x^9 + x^8 + x^6 + 1</math> || 0x1EDC6F41 or 0x82F63B78 (0x05EC76F1)
|-
|CRC-64-ISO || <math>x^{64} + x^4 + x^3 + x + 1</math><br>(use: ISO 3309) || 0x000000000000001B or 0xD800000000000000 (0xB000000000000001)
|-
|CRC-64-[[Ecma International|ECMA]]-182 || <math>x^{64} + x^{62} + x^{57} + x^{55} + x^{54} + x^{53} + x^{52} + x^{47} + x^{46} + x^{45} + x^{40} + x^{39} + x^{38} + x^{37} + x^{35} + x^{33} + x^{32} </math><br><!--Too long to display in one table--><math>+ x^{31} + x^{29} + x^{27} + x^{24} + x^{23} + x^{22} + x^{21} + x^{19} + x^{17} + x^{13} + x^{12} + x^{10} + x^9 + x^7 + x^4 + x + 1</math><br>(as described in [http://www.ecma-international.org/publications/standards/Ecma-182.htm ECMA-182] p.63) || 0x42F0E1EBA9EA3693 or 0xC96C5795D7870F42 (0x92D8AF2BAF0E1E85)
|-
|CRC-128 || IEEE-ITU 标准。被 [[MD5]] & [[SHA-1]] 取代||
|-
|CRC-160 || IEEE-ITU 标准。被 [[MD5]] & [[SHA-1]] 取代||
|-
|}

==CRC 与数据完整性==
尽管在[[错误检测]]中非常有用，CRC 并不能可靠地验证[[数据完整性]]（即数据没有发生任何变化），这是因为 CRC 多项式是线性结构，可以非常容易地''故意''改变数据而维持 CRC 不变，参见[http://www.woodmann.com/fravia/crctut1.htm CRC and how to Reverse it]中的证明。我们可以用 [[Message authentication code]] 验证数据完整性。

===CRC发生碰撞的情况===

与所有其它的[[散列函数]]一样，在一定次数的碰撞测试之后 CRC 也会接近 100% 出现碰撞。CRC 中每增加一个数据位，就会将碰撞数目减少接近 50%，如 CRC-20 与 CRC-21 相比。
* 理论上来讲，CRC64 的碰撞概率大约是每 18{{e|18}} 个 CRC 码出现一次。
* 由于 CRC 的不分解多项式特性，所以经过合理设计的较少位数的 CRC 可能会与使用较多数据位但是设计很差的 CRC 的效率相媲美。在这种情况下 CRC-32 几乎同 CRC-40 一样优秀。

===设计 CRC 多项式===

生成多项式的选择是 CRC 算法实现中最重要的部分，所选择的多项式必须有最大的错误检测能力，同时保证总体的碰撞概率最小。多项式最重要的属性是它的长度，也就是最高非零系数的数值，因为它直接影响着计算的校验和的长度。

最常用的多项式长度有
* 9 位 (CRC-8)
* 17 位 (CRC-16)
* 33 位 (CRC-32)
* 65 位 (CRC-64)

在构建一个新的 CRC 多项式或者改进现有的 CRC 时，一个通用的数学原则是使用满足所有模运算不可分解多项式约束条件的多项式。
* 这种情况下的不可分解是指多项式除了 1 与它自身之外不能被任何其它的多项式整除。

生成多项式的特性可以从算法的定义中推导出来：
* 如果 CRC 有多于一个的非零系数，那么 CRC 能够检查出输入消息中的所有单数据位错误。
* CRC 可以用于检测短于 2k 的输入消息中的所有双位错误，其中 k 是多项式的最长的不可分解部分的长度。
* 如果多项式可以被 x+1 整除，那么不存在可以被它整除的有奇数个非零系数的多项式。因此，它可以用来检测输入消息中的奇数个错误，就象奇偶校验函数那样。

==参见==
总的分类
* [[纠错码]]
* [[校验和算法列表]]
* [[奇偶校验位]]

特殊技术参考
* [[Adler-32]]
* [[Fletcher's checksum]]

==参考文献 ==
<references/>

==外部链接==
* [http://www.relisoft.com/science/CrcMath.html Tutorial and C++ implementation] of CRC
* Cyclic rendancy check - a simple guide to what it means for your data, CD and DVD discs. http://www.softwarepatch.com/tips/cyclic-rendancy.html
* [http://www.ross.net/crc/ ''The CRC Pitstop'']
* Williams, R. (1993-09) [http://www.repairfaq.org/filipg/LINK/F_crc_v3.html ''A Painless Guide to CRC Error Detection Algorithms'']
* [http://www.4d.com/docs/CMU/CMU79909.HTM ''Understanding Cyclic Rendancy Check'']
* Black, R. (1994-02) [http://www.cl.cam.ac.uk/Research/SRG/bluebook/21/crc/crc.html ''Fast CRC32 in Software''] — Algorithm 4 is used in Linux and info-zip's zip and unzip.
* Barr, M. ([http://www.netrino.com/Connecting/1999-11/ ''1999-11''], [http://www.netrino.com/Connecting/1999-12/ ''1999-12''], [http://www.netrino.com/Connecting/2000-01/ ''2000-01'']) checksums, CRCs, and their source code. Embedded Systems Programming
* [http://www.codeproject.com/cpp/crc32.asp CRC32: Generating a checksum for a file], C++ implementation by Brian Friesen
* Online [http://serversniff.net/hash.php Tool to compute common CRCs (8/16/32/64) from strings]
* Online [http://www.zorc.breitbandkatze.de/crc.html CRC calculator]
* Online [http://www.easics.com/webtools/crctool CRC Tool: Generator of synthesizable CRC functions]
* [http://www.paulschou.com/tools/xlate/ Online Char (ASCII), HEX, Binary, Base64, etc... Encoder/Decoder with MD2, MD4, MD5, SHA1+2, CRC, etc. hashing algorithms]
* [http://apollo.backplane.com/matt/crc64.html CRC16 to CRC64 collision research]
* [http://sar.informatik.hu-berlin.de/research/publications/index.htm#SAR-PR-2006-05 Reversing CRC – Theory and Practice.]

{{math-stub}}

[[Category:校验和算法]]

[[bg:CRC]]
[[ca:Control de rendància cíclica]]
[[cs:Cyklický rendantní součet]]
[[de:Zyklische Rendanzprüfung]]
[[en:Cyclic rendancy check]]
[[es:Control de rendancia cíclica]]
[[eu:CRC]]
[[fi:CRC]]
[[fr:Contrôle de redondance cyclique]]
[[he:בדיקת יתירות מחזורית]]
[[id:CRC]]
[[it:Cyclic rendancy check]]
[[ja:巡回冗长検査]]
[[ko:순환 중복 검사]]
[[nl:Cyclic Rendancy Check]]
[[pl:CRC]]
[[pt:CRC]]
[[ru:Циклический избыточный код]]
[[simple:Cyclic rendancy check]]
[[sk:Kontrola cyklickým kódom]]
[[sv:Cyclic Rendancy Check]]
[[vi:CRC]]

⑷ 关于CRC效验

为保证传输过程的正确性，需要对通信过程进行差错控制。差错控制最常用的方法是自动请求重发方式（ARQ）、向前纠错方式（FEC）和混合纠错（HEC）。在传输过程误码率比较低时，用FEC方式比较理想。在传输过程误码率较高时，采用FEC容易出现“乱纠”现象。HEC方式则是ARQ和FEC的结合。在许多数字通信中，广泛采用ARQ方式，此时的差错控制只需要检错功能。实现检错功能的差错控制方法很多，传统的有：奇偶校验、校验和检测、重复码校验、恒比码校验、行列冗余码校验等，这些方法都是增加数据的冗余量，将校验码和数据一起发送到接受端。接受端对接受到的数据进行相同校验，再将得到的校验码和接受到的校验码比较，如果二者一致则认为传输正确。但这些方法都有各自的缺点，误判的概率比较高。
循环冗余校验CRC（Cyclic Rendancy Check）是由分组线性码的分支而来，其主要应用是二元码组。编码简单且误判概率很低，在通信系统中得到了广泛的应用。下面重点介绍了CRC校验的原理及其算法实现。

CRC校验可以100％地检测出所有奇数个随机错误和长度小于等于k（k为g（x）的阶数）的突发错误。所以CRC的生成多项式的阶数越高，那么误判的概率就越小。

CRC代码的一些基本概念和运算：

CRC多项式：

例：

代码：1010111 对应的多项式为：X6+X4+X2+X+1

多项式X5+X3+X2+X1+1对应的代码为101111

CRC生成多项式:

首位和最后一位必须是1。CRC生成多项式是给定的，在传输过程中不变，即发送和接收端生成码相同。

一些常用的校验码为：

CRC8=X8+X5+X4+1

CRC-CCITT=X16+X12+X5+1

CRC16=X16+X15+X5+1

CRC12=X12+X11+X3+X2+1

CRC32=X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X1+1

CRC的运算本质是异或运算（模2除法）

例：原信息码为1011001

生成码为11001

校验码计算过程

① 将信息码左移4位（生成码长-1）；得到10110010000

② 异或运算

10110010000

11001

01111010000（前面的数进行异或运算，后面的直接抄下来）

11001

0011110000（和生成码异或运算的必须从1开始）

11001

00111000

11001

001010

这样得到的结果为1010，即为所需要的校验码，添加到信息码后，得到发送的代码为:

10110011010

我把上面的手算过程用c#写了一段程序，如下：

using System;

namespace mainClass
{
public class mainProgress
{
public static void Main()
{
byte[] msg={1,0,1,1,0,0,1};//信息码
byte[] gmsg=new byte[msg.Length+4];
crc c = new crc();
gmsg=c.code(msg);
Console.Write("编码后字符串为：");
for (int i = 0; i < gmsg.Length; i++)
{
Console.Write("{0}", gmsg[i].ToString());
}
Console.Write("\n");
byte[] gmsg1={ 1, 0, 1, 1, 0, 1, 1 };//接收到的代码
bool r = c.det(gmsg1);
if (r)
{
Console.WriteLine("传输正确");
}
else
{ Console.WriteLine("传输错误"); }
}
}

public class crc//CRC编码类
{
private byte[] g = { 1,1,0,0,1};//生成码
public byte[] code(byte[] msg)//编码
{
byte[] gmsg=new byte[g.Length+msg.Length-1];
msg.CopyTo(gmsg, 0);//
for (int i = 0; i < msg.Length; i++)//完成异或运算，即模2除法
{
if (gmsg[i] == 1)
{
for (int j = 0; j < g.Length; j++)
{
if (gmsg[i + j] == g[j])
gmsg[i + j] = 0;
else
gmsg[i + j] = 1;
}
}
}
msg.CopyTo(gmsg, 0);
return gmsg;
}
private bool f=true;

//接收端检测
public bool det(byte[] gmsg)
{
for (int i = 0; i < gmsg.Length - g.Length+1; i++)
{
if(gmsg[i]==0)
continue;
for (int j = 0; j < g.Length; j++)
{
if (gmsg[i + j] == g[j])
gmsg[i + j] = 0;
else
gmsg[i + j] = 1;
}
}
for (int i = 0; i < gmsg.Length; i++)
{
if (gmsg[i] == 1)
f = false;
}
return f;
}

}
}

⑸ CRC32的计算方法

CRC的本质是模-2除法的余数，采用的除数不同，CRC的类型也就不一样。通常，CRC的除数用生成多项式来表示。 最常用的CRC码及生成多项式名称生成多项式。

CRC-12：

(5)crc算法实现扩展阅读

通常的CRC算法在计算一个数据段的CRC值时，其CRC值是由求解每个数值的CRC值的和对CRC寄存器的值反复更新而得到的。这样，求解CRC的速度较慢。通过对CRC算法的研究，我们发现：一个8位数据加到16位累加器中去，只有累加器的高8位或低8位与数据相作用，其结果仅有256种可能的组合值。

因而，我们可以用查表法来代替反复的运算，这也同样适用于CRC32的计算。本文所提供的程序库中，函数crchware是一般的16位CRC的算法。mk-crctbl用以在内存中建立一个CRC数值表。

⑹ java中CRC算法是个什么东东

CRC校验码的基本思想是利用线性编码理论，在发送端根据要传送的k位二进制码序列，以一定的规则产生一个校验用的监督码（既CRC码）r位，并附在信息后边，构成一个新的二进制码序列数共(k+r)位，最后发送出去。在接收端，则根据信息码和CRC码之间所遵循的规则进行检验，以确定传送中是否出错。
在数据存储和数据通讯领域，CRC无处不在:着名的通讯协议X.25的FCS(帧检错序列)采用的是CRC. CCITT，ARJ、LHA等压缩工具软件采用的是CRC32，磁盘驱动器的读写采用了CRC16，通用的图像存储格式GIF、TIFF等也都用CRC作为检错手段。
CRC的本质是模-2除法的余数，采用的除数不同，CRC的类型也就不一样。通常，CRC的除数用生成多项式来表示。最常用的CRC码的生成多项式有CRC16,CRC32.
以CRC16为例,16位的CRC码产生的规则是先将要发送的二进制序列数左移16位（既乘以2^16）后，再除以一个多项式，最后所得到的余数既是CRC码，如下式所示，其中K(X)表示n位的二进制序列数，G(X)为多项式，Q(X)为整数，R(X)是余数（既CRC码）。
K(X)>>16=G(x)Q(x)+R(x)
求CRC码所采用模2加减运算法则，既是不带进位和借位的按位加减，这种加减运算实际上就是逻辑上的异或运算，加法和减法等价，乘法和除法运算与普通代数式的乘除法运算是一样，符合同样的规律。生成CRC码的多项式如下，其中CRC-16和CRC-CCITT产生16位的CRC码，而CRC-32则产生的是32位的CRC码
接收方将接收到的二进制序列数（包括信息码和CRC码）除以多项式，如果余数为0，则说明传输中无错误发生，否则说明传输有误，关于其原理这里不再多述。用软件计算CRC码时，接收方可以将接收到的信息码求CRC码，比较结果和接收到的CRC码是否相同。
CCITT推荐的高级数据链路控制规程HDLC的帧校验序列FCS中，使用CCITT-16即CRC16,其生成多项式为G(x)=x16+x12+x5+1,CRC-32的生成多项式为G(x)=x32+x26+x23+x22+x16+x11+x10+x16+x8+x7+x5+x4+x2+x+1

⑺ CRC校验的算法

在代数编码理论中，将一个码组表示为一个多项式，码组中各码元当作多项式的系数。例如 1100101 表示为1·x6+1·x5+0·x4+0·x3+1·x2+0·x+1，即 x6+x5+x2+1。
设编码前的原始信息多项式为P(x)，P(x)的最高幂次加1等于k；生成多项式为G(x)，G(x)的最高幂次等于r；CRC多项式为R(x)；编码后的带CRC的信息多项式为T(x)。
发送方编码方法：将P(x)乘以xr(即对应的二进制码序列左移r位)，再除以G(x)，所得余式即为R(x)。用公式表示为T(x)=xrP(x)+R(x)
接收方解码方法：将T(x)除以G(x)，得到一个数，如果这个余数为0，则说明传输中无错误发生，否则说明传输有误。
举例来说，设信息编码为1100，生成多项式为1011，即P(x)=x3+x2，G(x)=x3+x+1，计算CRC的过程为
xrP(x) =x3(x3+x2) = x6+x5 G(x)= x3+x+1 即 R(x)=x。注意到G(x)最高幂次r=3，得出CRC为010。
如果用竖式除法(计算机的模二，计算过程为
1110 ------- 1011 /1100000 (1100左移3位) 1011 ---- 1110 1011 ----- 1010 1011 ----- 0010 0000 ---- 010 因此，T(x)=(x6+x5)+(x)=x6+x5+x, 即 1100000+010=1100010
如果传输无误，
T(x)= （x6+x5+x）/G(x) = , G(x)= 无余式。回头看一下上面的竖式除法，如果被除数是1100010，显然在商第三个1时，就能除尽。
上述推算过程，有助于我们理解CRC的概念。但直接编程来实现上面的算法，不仅繁琐，效率也不高。实际上在工程中不会直接这样去计算和验证CRC。
下表中列出了一些见于标准的CRC资料：
名称 生成多项式 简记式* 应用举例
CRC-4 x4+x+1 3 ITU G.704
CRC-8 x8+x5+x4+1 31 DS18B20
CRC-12 x12+x11+x3+x2+x+1 80F
CRC-16 x16+x15+x2+1 8005 IBM SDLC
CRC-ITU** x16+x12+x5+1 1021 ISO HDLC, ITU X.25, V.34/V.41/V.42, PPP-FCS,ZigBee
CRC-32 x32+x26+x23+...+x2+x+1 04C11DB7 ZIP, RAR, IEEE 802 LAN/FDDI,IEEE 1394,PPP-FCS
CRC-32c x32+x28+x27+...+x8+x6+1 1EDC6F41 SCTP
* 生成多项式的最高幂次项系数是固定的1，故在简记式中，将最高的1统一去掉了，如04C11DB7实际上是104C11DB7。 ** 前称CRC-CCITT。ITU的前身是CCITT。
备注：
（1）生成多项式是标准规定的
（2）CRC校验码是基于将位串看作是系数为0或1的多项式，一个k位的数据流可以看作是关于x的从k-1阶到0阶的k-1次多项式的系数序列。采用此编码，发送方和接收方必须事先商定一个生成多项式G(x)，其高位和低位必须是1。要计算m位的帧M(x)的校验和，基本思想是将校验和加在帧的末尾，使这个带校验和的帧的多项式能被G(x)除尽。当接收方收到加有校验和的帧时，用G(x)去除它，如果有余数，则CRC校验错误，只有没有余数的校验才是正确的。

⑻ crc算法在单片机上的实现

CRC算法原理及C语言实现

摘 要 本文从理论上推导出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和CRC-CCITT产生16位的CRC码,而CRC-32则产生的是32位的CRC码。本文不讨论32位的CRC算法,有兴趣的朋友可以根据本文的思路自己去推导计算方法。
CRC-16：（美国二进制同步系统中采用）
CRC-CCITT：（由欧洲CCITT推荐）
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码。
式(3-5)是编程计算CRC的关键,它说明计算本位后的CRC码等于上一位CRC码乘以2后除以多项式,所得的余数再加上本位值除以多项式所得的余数。由此不难理解下面求CRC码的C语言程序。*ptr指向发送缓冲区的首字节,len是要发送的总字节数,0x1021与多项式有关。
unsigned int cal_crc(unsigned char *ptr, unsigned char len) {
unsigned char i;
unsigned int crc=0;
while(len--!=0) {
for(i=0x80; i!=0; i/=2) {
if((crc&;0x8000)!=0) {crc*=2; crc^=0x1021;} /* 余式CRC乘以2再求CRC */
else crc*=2;
if((*ptr&;i)!=0) crc^=0x1021; /* 再加上本位的CRC */
}
ptr++;
}
return(crc);
}
按位计算CRC虽然代码简单,所占用的内存比较少,但其最大的缺点就是一位一位地计算会占用很多的处理器处理时间,尤其在高速通讯的场合,这个缺点更是不可容忍。因此下面再介绍一种按字节查表快速计算CRC的方法。
4 按字节计算CRC
不难理解,对于一个二进制序列数可以按字节表示为式(4-1),其中 为一个字节(共8位)。
(4-1)
求此二进制序列数的CRC码时,先乘以 后（既左移16位）,再除以多项式G(X),所得的余数既是所要求的CRC码。如式(4-2)所示：
（4-2）
可以设： (4-3)
其中 为整数, 为16位二进制余数。将式(4-3)代入式(4-2)得：
（4-4）
因为：
（4-5）
其中 是 的高八位, 是 的低八位。将式（4-5）代入式（4-4）,经整理后得：
（4-6）
再设： (4-7)
其中 为整数, 为16位二进制余数。将式(4-7)代入式(4-6),如上类推,最后得：
(4-8)
很显然,十六位二进制数 既是我们要求的CRC码。
式(4-7)是编写按字节计算CRC程序的关键,它说明计算本字节后的CRC码等于上一字节余式CRC码的低8位左移8位后,再加上上一字节CRC右移8位（也既取高8位）和本字节之和后所求得的CRC码,如果我们把8位二进制序列数的CRC全部计算出来,放如一个表里,采用查表法,可以大大提高计算速度。由此不难理解下面按字节求CRC码的C语言程序。*ptr指向发送缓冲区的首字节,len是要发送的总字节数,CRC余式表是按0x11021多项式求出的。
unsigned int cal_crc(unsigned char *ptr, unsigned char len) {
unsigned int crc;
unsigned char da;
unsigned int crc_ta[256]={ /* CRC余式表 */
0x0000, 0x1021, 0x2042, 0x3063, 0x4084, 0x50a5, 0x60c6, 0x70e7,
0x8108, 0x9129, 0xa14a, 0xb16b, 0xc18c, 0xd1ad, 0xe1ce, 0xf1ef,
0x 1231, 0x0210, 0x3273, 0x2252, 0x52b5, 0x4294, 0x72f7, 0x62d6,
0x9339, 0x8318, 0xb37b, 0xa35a, 0xd3bd, 0xc39c, 0xf3ff, 0xe3de,
0x2462, 0x3443, 0x0420, 0x1401, 0x64e6, 0x74c7, 0x44a4, 0x5485,
0xa56a, 0xb54b, 0x8528, 0x9509, 0xe5ee, 0xf5cf, 0xc5ac, 0xd58d,
0x3653, 0x2672, 0x1611, 0x0630, 0x76d7, 0x66f6, 0x5695, 0x46b4,
0xb75b, 0xa77a, 0x9719, 0x8738, 0xf7df, 0xe7fe, 0xd79d, 0xc7bc,
0x48c4, 0x58e5, 0x6886, 0x78a7, 0x0840, 0x1861, 0x2802, 0x3823,
0xc9cc, 0xd9ed, 0xe98e, 0xf9af, 0x8948, 0x9969, 0xa90a, 0xb92b,
0x5af5, 0x4ad4, 0x7ab7, 0x6a96, 0x1a71, 0x0a50, 0x3a33, 0x2a12,
0xdbfd, 0xcbdc, 0xfbbf, 0xeb9e, 0x9b79, 0x8b58, 0xbb3b, 0xab1a,
0x6ca6, 0x7c87, 0x4ce4, 0x5cc5, 0x2c22, 0x3c03, 0x0c60, 0x1c41,
0xedae, 0xfd8f, 0xcdec, 0xddcd, 0xad2a, 0xbd0b, 0x8d68, 0x9d49,
0x7e97, 0x6eb6, 0x5ed5, 0x4ef4, 0x3e13, 0x2e32, 0x1e51, 0x0e70,
0xff9f, 0xefbe, 0xdfdd, 0xcffc, 0xbf1b, 0xaf3a, 0x9f59, 0x8f78,
0x9188, 0x81a9, 0xb1ca, 0xa1eb, 0xd10c, 0xc12d, 0xf14e, 0xe16f,
0x1080, 0x00a1, 0x30c2, 0x20e3, 0x5004, 0x4025, 0x7046, 0x6067,
0x83b9, 0x9398, 0xa3fb, 0xb3da, 0xc33d, 0xd31c, 0xe37f, 0xf35e,
0x02b1, 0x1290, 0x22f3, 0x32d2, 0x4235, 0x5214, 0x6277, 0x7256,
0xb5ea, 0xa5cb, 0x95a8, 0x8589, 0xf56e, 0xe54f, 0xd52c, 0xc50d,
0x34e2, 0x24c3, 0x14a0, 0x0481, 0x7466, 0x6447, 0x5424, 0x4405,
0xa7db, 0xb7fa, 0x8799, 0x97b8, 0xe75f, 0xf77e, 0xc71d, 0xd73c,
0x26d3, 0x36f2, 0x0691, 0x16b0, 0x6657, 0x7676, 0x4615, 0x5634,
0xd94c, 0xc96d, 0xf90e, 0xe92f, 0x99c8, 0x89e9, 0xb98a, 0xa9ab,
0x5844, 0x4865, 0x7806, 0x6827, 0x18c0, 0x08e1, 0x3882, 0x28a3,
0xcb7d, 0xdb5c, 0xeb3f, 0xfb1e, 0x8bf9, 0x9bd8, 0xabbb, 0xbb9a,
0x4a75, 0x5a54, 0x6a37, 0x7a16, 0x0af1, 0x1ad0, 0x2ab3, 0x3a92,
0xfd2e, 0xed0f, 0xdd6c, 0xcd4d, 0xbdaa, 0xad8b, 0x9de8, 0x8dc9,
0x7c26, 0x6c07, 0x5c64, 0x4c45, 0x3ca2, 0x2c83, 0x1ce0, 0x0cc1,
0xef1f, 0xff3e, 0xcf5d, 0xdf7c, 0xaf9b, 0xbfba, 0x8fd9, 0x9ff8,
0x6e17, 0x7e36, 0x4e55, 0x5e74, 0x2e93, 0x3eb2, 0x0ed1, 0x1ef0
};

crc=0;
while(len--!=0) {
da=(uchar) (crc/256); /* 以8位二进制数的形式暂存CRC的高8位 */
crc<<=8; /* 左移8位,相当于CRC的低8位乘以 */
crc^=crc_ta[da^*ptr]; /* 高8位和当前字节相加后再查表求CRC ,再加上以前的CRC */
ptr++;
}
return(crc);
}
很显然,按字节求CRC时,由于采用了查表法,大大提高了计算速度。但对于广泛运用的8位微处理器,代码空间有限,对于要求256个CRC余式表（共512字节的内存）已经显得捉襟见肘了,但CRC的计算速度又不可以太慢,因此再介绍下面一种按半字节求CRC的算法。
5 按半字节计算CRC
同样道理,对于一个二进制序列数可以按字节表示为式(5-1),其中 为半个字节(共4位)。
(5-1)
求此二进制序列数的CRC码时,先乘以 后（既左移16位）,再除以多项式G(X),所得的余数既是所要求的CRC码。如式(4-2)所示：
（5-2）
可以设： (5-3)
其中 为整数, 为16位二进制余数。将式(5-3)代入式(5-2)得：
（5-4）
因为：
（5-5）
其中 是 的高4位, 是 的低12位。将式（5-5）代入式（5-4）,经整理后得：
（5-6）
再设： (5-7)
其中 为整数, 为16位二进制余数。将式(5-7)代入式(5-6),如上类推,最后得：
(5-8)
很显然,十六位二进制数 既是我们要求的CRC码。
式(5-7)是编写按字节计算CRC程序的关键,它说明计算本字节后的CRC码等于上一字节CRC码的低12位左移4位后,再加上上一字节余式CRC右移4位（也既取高4位）和本字节之和后所求得的CRC码,如果我们把4位二进制序列数的CRC全部计算出来,放在一个表里,采用查表法,每个字节算两次（半字节算一次）,可以在速度和内存空间取得均衡。由此不难理解下面按半字节求CRC码的C语言程序。*ptr指向发送缓冲区的首字节,len是要发送的总字节数,CRC余式表是按0x11021多项式求出的。
unsigned cal_crc(unsigned char *ptr, unsigned char len) {
unsigned int crc;
unsigned char da;
unsigned int crc_ta[16]={ /* CRC余式表 */
0x0000,0x1021,0x2042,0x3063,0x4084,0x50a5,0x60c6,0x70e7,
0x8108,0x9129,0xa14a,0xb16b,0xc18c,0xd1ad,0xe1ce,0xf1ef,
}

crc=0;
while(len--!=0) {
da=((uchar)(crc/256))/16; /* 暂存CRC的高四位 */
crc<<=4; /* CRC右移4位,相当于取CRC的低12位）*/
crc^=crc_ta[da^(*ptr/16)]; /* CRC的高4位和本字节的前半字节相加后查表计算CRC,
然后加上上一次CRC的余数 */
da=((uchar)(crc/256))/16; /* 暂存CRC的高4位 */
crc<<=4; /* CRC右移4位, 相当于CRC的低12位） */
crc^=crc_ta[da^(*ptr&;0x0f)]; /* CRC的高4位和本字节的后半字节相加后查表计算CRC,
然后再加上上一次CRC的余数 */
ptr++;
}
return(crc);
}